View Question
 ```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. ?``` Request for Question Clarification by rbnn-ga on 04 Nov 2002 12:58 PST `What is a "unit row"?` Request for Question Clarification by rbnn-ga on 04 Nov 2002 23:16 PST ```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.``` Clarification of Question by truman-ga on 05 Nov 2002 08:43 PST ```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```
 ```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.``` Request for Answer Clarification by truman-ga on 05 Nov 2002 10:11 PST ```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.``` Clarification of Answer by rbnn-ga on 05 Nov 2002 11:48 PST ```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.``` Clarification of Answer by rbnn-ga on 05 Nov 2002 19:40 PST ```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.``` Clarification of Answer by rbnn-ga on 05 Nov 2002 20:10 PST ```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)``` Clarification of Answer by rbnn-ga on 06 Nov 2002 09:38 PST ```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.```