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.
