If A is a matrix, what is the proof that the following statements are
equivalent: 1. A is Totally Unimodular (hereafter TU). 2 The
transpose of A is TU. 3. A matrix obtained by deleting a unit
row/column from A is TU. 4. A matrix obtained by a pivot operation on
A is TU. ? Linear Discrepancy of Basic Totally Unimodular Matrices::
File Format: PDF/Adobe Acrobat - View as HTMLunimodular matrices due to Crama, Loebl and Poljak [CLP92]. A matrix A is called totally unimodular if the determinant of each square submatrix is
http://www.emis.de/journals/EJC/Volume_7/PDF/v7i1r48.pdfHOME |
Thanks again for your patience.
The primary purpose of this note is to correct an error in my answer.
My definition of "totally unimodular" was incorrect, because my
definition of "submatrix" was not correct. A totally unimodular matrix
is a matrix all of whose square submatrices have determinant 1, -1, or
0, where a "submatrix" of a matrix is formed by deleting an arbitrary
set of rows and columns from the original matrix.
Sorry for the confusion; although the definition I used for
"submatrix" was also a valid definition, I should have figured out
from the context what the correct usage was. I am posting a partial
resolution of your question because I wanted to correct my error as
soon as possible.
Secondarily, I have located an on-line source that proves the theorem
that you are looking for.
The monograph
Matroid Decomposition, by Klaus Truemper at
http://www.emis.de/monographs/md has this material.
The lemma you are looking for is proved in chapter 9, "Matrix total
unimodularity and matroid regularity", as Lemma 9.2.2 on page 190,
from the URL: http://www.emis.de/monographs/md/ch9.ps.gz
Unfortunately, this version is likely to be even more difficult to
download for you than a normal postscript file: it is a "compressed
postscript file" for which you will need, not only a postscript
viewer, but an uncompressor like WinZip from as well.
You can download ghostview, a postscript previewer, from:
http://www.cs.wisc.edu/~ghost/doc/AFPL/get704.htm . You would first to
download ghostscript, say here for windows:
ftp://mirror.cs.wisc.edu/pub/mirrors/ghost/AFPL/gs704/gs704w32.exe ,
and then download the actual viewer, here:
ftp://mirror.cs.wisc.edu/pub/mirrors/ghost/ghostgum/gsv43w32.exe .
However, this process can be a bit involved an prone to error.
In any case, the text says:
"Lemma. Total unimodularity is maintained under the taking of
submatrices, transposition, pivots, and the adjoining of zero unit
vectors..." .
You can download an evaluation copy of Winzip from
http://www.winzip.com/ddchomea.htm .
Here a unit vector is a vector with one "1" in it and everything else
0.
"pivot" is defined in chapter 2 (page 20) at:
http://www.emis.de/monographs/md/ch2.ps.gz .
However, both the definition of pivot, and the proof, that pivoting
maintains total unimodularity seem a bit obscure to me.
I am not satisfied yet with the answer because:
1. You may have trouble downloading .gz and .ps files , and
2. I am unable to follow the reasoning used in the proof in the
monograph above.
Therefore, I will continue to search or try to derive a clear,
understandable statement and proof.
This might take a few more days, but please be assured I am continuing
to work towards a satisfactory answer.
As I've done some research on this, I will present the results here. I
suspect your question may not be asking what it seems to be; in which
case, just rephrase the question as a "Request Clarification", before
rating the answer and I will answer the revised question.
On the other hand, if in fact the question is asking what it claims to
be asking, then the answer below is best answer, that is, it shows the
claim is false.
Now, a square submatrix of an m x n matrix A is the k x k matrix B
such that for some 1<=i<=m-k+1 and 1<=j<=n-k+1 ,
for all 1<=r<=k and 1<=s<=k
B = A
r,s i+r-1,j+s-1
(e.g., see mathworld: http://mathworld.wolfram.com/Submatrix.html )
A totally unimodular matrix is a matrix A such that every square
submatrix of A has determinant equal to 0, -1, or 1. Note that this
implies that every element of A has value 1,0, or -1 .
(e.g., http://carbon.cudenver.edu/~hgreenbe/glossary/U.html ,
http://ssor.twi.tudelft.nl/~deklerk/WI4064/week7_sl.pdf )
1=>2
If A is unimodular, then the tranpose A' is unimodular, because the
square submatrices of A' are exactly the transposes of the square
submatrices of A, and the determinant of the tranpose of a matrix
equals the determinant of the original matrix.
2=>3
A "unit row" is sometimes considered to be a row with exactly one 1
and everything else 0, or any row with unit norm.
Unfortunately, the claim fails even under the stricter
interpretetation, as can be considered from the matrix
A=
0 1 1
0 1 0
0 -1 1
This matrix is totally unimodular, but the matrix that we get by
deleting the second row is:
0 1 1
0 -1 1
is not totally unimodular, since the determinant of the submatrix:
1 1
-1 1
is 2 .
-----
1=>4
A "pivot operation" on a matrix is the addition of a scalar multiple
of one row to another row. (e.g.
http://calculusplus.cuny.edu/Linalg_Reduced%20Echelon%20Form1.htm ,
http://216.239.51.100/search?q=cache:6ZGoSW4GNZQC:www.tutor.ms.unimelb.edu.au/matrix/matrix_rowops.html+%22pivot+operation%22+matrix&hl=en&ie=UTF-8
, http://people.hofstra.edu/faculty/Stefan_Waner/tutorialsf1/unit2_2B.html
among other references)
This is also trivially false.
Consider the matrix:
1 1
1 1
This matrix is totally unimodular, but if we add the first row to the
second, we get some twos in it, and so it is not totally unimodular.
-----
4=>1
If each matrix resulting from a pivot operation is totally unimodular,
then the original matrix is totally unimodular, since we can add 0
times a row to get another row.
I need to track down the exact (differing) definitions here.
If indeed [1 1;-1 1] is a "square submatrix" of the original matrix A,
then we are using different definitions of totally unimodular, of
submatrix, and of pivot; and we aren't sure what a unit row is. The
definitions I was using were standard, but there may be alternate
definitions. This may take a little more time to research, so please
bear with me while I perform further research.
I'll reiterate the request here. What do you mean by "unit
row/column". This is not a term of art or, in the commonest sense, I
don't even think the claim holds.
Actually, I did a web search and found a site that will convert ps to
pdf files automatically, namely Ps To PDF at
http://www.ps2pdf.com/convert/convert.htm . I used this site to
convert the above referenced files to pdf format, which I hope will be
easier to read for you than compressed postscript. I have placed the
files, which include the proof you want, at:
http://www.rbnn.com/google/ch2.pdf
http://www.rbnn.com/google/ch9.pdf
However, as I mentioned, I personally do not follow the proof and I am
continuing to look for a clearer source (if you can follow the proof
though, then I guess that's sufficient)
Thanks again for your patience. I have finally figured out a proof,
based on published sources, of this result. It is substantially
complicated by the fact that there seem to be more than one definition
of most of the terms floating around.
We show the following are equivalent:
(1) A is totally unimodular
(2) A' is totally unimodular
(3) Deleting a unit row or unit column from A yields a totally
unimodular matrix.
(4) The result of a q-pivot operation on A yields a totally
unimodular matrix
A totally unimodular matrix is a matrix all of whose square
submatrices have determinant 0,1, or -1, where a submatrix of a matrix
is formed by deleting rows and columns from the original matrix.
A "unit row" is a row with exactly one 1 and zeros everywhere else.
A "Friesz pivot operation" is defined on p. 42 of "Optimization
theory" by Terry Friesz,
http://classweb.gmu.edu/tfriesz/SYST417/Master1.ps:
http://classweb.gmu.edu/tfriesz/SYST417/Master1.ps. Here I paraphrase
it slightly.
Let A be an m x n matrix.
Suppose that for integers i,j we have 1<=i<=m and 1<=j<=n and A_{ij}
is nonzero .
Then the "Friesz pivot operation" for (i,j) is defined as follows:
1. Replace row i of A by its product with 1/(A_{ij})
2. For each i' not equal to i, with 1<=i'<=m, subtract the product of
A_{i'j} and row i from row i' .
What this does is transform a particular column of A (namely the j'th
column) into a column that has a 1 in the i'th row and a zero
everywhere else, using only "elementary row operations".
This seems to be the more standard definition of "pivot operation",
and its certainly straightforward and natural. And one can prove that
the result of applying a Friesz pivot operation to a totally
unimodular matrix A yields a totally unimodular matrix. This will show
that (1)=>(4), but the converse (4)=>(1) would fail for a Friesz
pivot, since for example the matrix [0] can be formed from a Friesz
pivot operation on the non-totally-unimodular matrix [2] .
So we have to use another definition of pivot, namely the q-pivot,
which is defined in the Truemper monograph.
Definition: The q-pivot operation on a matrix A is the same as the
Friesz pivot, except that after the Friesz pivot operation is
performed, each element in the same row and each element in the same
column of the pivot element is restored to its original value before
the pivot.
[Note: for q-pivot I am using page 21 of
http://www.rbnn.com/google/ch2.pdf of Matroid Decomposition by Klaus
Truemper at http://www.emis.de/monographs/md (op cit.) In the final
step, however, Truemper adds the comment to "interchange x and y" for
the pivot element; I have no idea what this means but it doesn't seem
to make any difference. Note that Truemper helpfully begins by
defining his pivot operation and proofs over GF(2) - we want the
general field definitions which are on the next page]
In order to understand this proof, I suggest first of all ignoring the
q-pivot and just using the following to show that:
1 <==> 2 <==> 3 ==> 4 for Friesz pivot
Once the 1=>4 part is clear with a Friesz pivot, if you delve into the
nitty gritty, the arguments that 1==>4 for a q-pivot and that 4==>1
for a q-pivot should be more clear.
-----
(1)<=> (2)
This is trivial.
-----
(1)<=>(3)
It is clear that deleting any row or column from a totally unimodular
matrix yields a totally unimodular matrix, so that (1)=>(3) is
trivial.
Conversely, suppose that A is formed from some B by adjoining a unit
row or column somewhere, and suppose B is totally unimodular. Then any
square submatrix of A either intersects the row/column in question or
it doesn't.
If it doesn't, it's determinant equals the determinant of the
corresponding square submatrix of B.
If it does intersect this row or column, then either it contains the 1
in that column or not. If it does contain that 1, then normal
determinant computation by expansion along that row will show that its
determinant equals the determinant of some square submatrix of B;
otherwise it has a column or row of zeroes and so must have
determinant 1, and the implication follows.
-----
(1)=>(4)
This of course is the key case.
Let B be any matrix with r rows and s columns, where r<=s.
I say B is *unimodular* if any r x r submatrix of B has determinant 0,
1, or -1.
I write [A I] for the result of adjoining the mxm identity matrix to
A.
We need this lemma:
Lemma: A is totally unimodular if and only if [A I] is unimodular.
Proof:
It is clear that if A is totally unimodular then [A I] is unimodular .
On the other hand, suppose that [A I] is unimodular. We want to show
that any square submatrix X of A has determinant 1. Suppose X has t
rows and t columns.
Suppose the row indices in A of the rows of X are R={r_1, r_2, ... ,
r_t}.
Suppose the column indices in A of the rows of X are
C={c_1,c_2,...,c_t} .
Now, I will use matlab notation and write A(:,j} for the j'th column
of A and A(i,:) for the ith row .
I will write e_i for the column vector of length m that has a single 1
in row i and a zero everywhere else.
Let S={s_1,...,s_{m-t}}={s: 1<=s<=m and s is not in R}.
Consider the m x m matrix D:
A(:,c_1) A(:,c_1) ... A_(:,c_t) e_{s_1},e_{s_2},...,e_{s_{m-t}}
Then D is a submatrix of [A I] and it is not hard to see that the
determinant of D equals the determinant of X . (Actually it is a
little hard to see from this notation but if you draw out an example
or two, preferably with X being a block submattrix starting at 1,1, it
should be clear why this is so).
Since [A I] is unimodular, D has determinant 0, 1, or -1, and
therefore so does B, and so A is totally unimodular, and the lemma
follows.
Lemma: If B is unimodular, then the following operations on B each
yield a matrix that is also unimodular:
(i) Interchanging two columns of B
(ii) Adding a multiple of a row of B to another row of B .
Proof: This is basic linear algebra; it follows from the
multilinearity in columns of the determinant.
Theorem: If A is totally unimodular then the result of a Friesz pivot
operation on A leaves a totally unimodular matrix B.
Proof:
Suppose for simplicity that the pivot element is a nonzero element at
(1,1); the proof is the same otherwise, just with more convoluted
notation. As usual, we assume A is an m x n matrix. We then see that
the first column of B is the unit vector e_1 . Also, suppose again
that the value is 1; the proof is similar if the value is -1 .
Let X be a t x t submatrix of B . We need to be prove that X has
determinant 1, 0, or -1.
Let Y be the txt submatrix of A with the same row and column indices
of X; we already know that Y has determinant in {-1,0,1}.
Now, if X intersects the first row of B, then certainly det(X)=det(Y),
because X is then formed from Y by adding multiples of a row of Y to
its own rows.
If X does not intersect the first row of A, but does intersect the
first column of B, then X has a column of zeros, and so in this case
det(X) =0.
So it is enough to show the result is true when each row index and
column index of X is greater than 1.
To do this is a little tricky.
We start by forming the matrix
C=[A I] .
Then, for each elementary row operation used to construct B from A, we
do the same thing to C.
Let D be the result of applying a (1,1) Friesz pivot operation on C.
Then D(1:m,1:n)=B .
D(:,1) = [1 0 0 ... 0]'
B(:,r) for r<=n
D(:,r) =
e_{n-r} for r>n+1
Now, let E be the result of interchanging columns 1 and n+1 of D .
Then for some matrix U,
E=[U I]
where all the columns of U other than the first equal the
corresponding columns of B .
But E is unimodular, because only elementary row operations were used
to construct E from [A I].
Since E is unimodular, U is totally unimodular, and so each submatrix
of U has determinant 1,-1,or 0; and so each submatrix of U formed from
columns and rows other the first of U has such determinant, and so
each submatrix of B formed from columns and rows other than the first
has such determinant, and so B is totally unimodular, and the result
follows.
Theorem: Let A be a totally unimodular matrix and let B be the result
of applying a q-pivot operation on A. Then A is totally unimodular.
Proof: The proof is exactly the same as for the preceding theorem,
except that:
i. Supposing the pivot element is equal to 1, we start by negating
the n+1 column of [A I].
ii. At the end after interchanging the n+1 and 1st columns, we
negate the first column again.
With these operations, the matrix U will equal the q-pivot of A
------
(4) => (1)
Here we need to show that if B was formed from a q-pivot operation on
A, and B is totally unimodular, then so is A. I will not write out a
proof here; in the q-pivot case, each operation is invertible. That
is, from the final matrix
[U I]
we can obtain the matrix
[A I]
by a sequence of elementary row operations, each of which leave the
magnitude of the determinant of each submatrix of the matrix
unchanged. Since B is totally unimodular, [U I] = [B I] is unimodular;
so that [A I] will be unimodular and the result follows.
Search Strategy:
----------------
The unusual thing about proving this theorem was the
there were so many slightly different definitions of the terms used in
its statement; I had to find a consistent set of definitions that
would make the theorem true. Even finding a definition of "unimodular"
proved to be quite tricky: nearly every reference only defined it for
square matrices.
I went through about 40 papers on unimodularity and total
unimodularity, using standard search terms, before finding an exercise
(Problem 4) http://www.engin.umich.edu/class/ioe614/Homework%202.pdf
. The exercise stated that A is totally unimodular if and only if [A
I] is unimodular. I proved this and the rest was easy. Also, the
monograph by Truemper http://www.emis.de/monographs/md mentioned in an
earlier clarification uses [I A] although I still am not entirely sure
what that monograph is doing and it uses (I think) a slightly
different definition of pivot operation.
As always, please feel free to ask for clarification if anything is
unclear.
I don't know myself what is meant here by Unit row/column. And so,
let me suggest that #3 simply be dropped from the list.
(#2 could also be dropped because it's trivial)
It's #4 I'm most interested in.
thanks much
-Truman
Thanks for all your time and effort.
As I mentioned, I'm not sure what is meant by unit row/column.
However, in your contradiction of 2=>3 you state that A =
0,1,1;0,1,0;0,-1,1 is TU. It is not. precisely because 1,1;-1,1 is
considered in this context to be a square submatrix of A.
also a pivot operation is not what you think, it's not something from
an introductory Linear Algebra course. I'm not sure where to find you
a good on-line definition of a pivot operation, but you can read about
them offline in R.T.Rockafellar's Network Optimization Book.
Type into Google: "A matrix obtained by a pivot operation on A is TU"
and you'll see you've contradicted a number of folks giving lectures
on Total Unimodularity.
Thanks again for your time.
My apologies for having written such a hastily worded question to
being with.
-Truman
I'm happy to rate this effort highly at this point. It may be best to
start fresh.
What is a "unit row"?
 How much does getting a small tattoo on your hip/stomach hurt?
 Do anyone else have an itchy anus? ?
|
Totally Unimodular Matrices