Unimodular Matrix Inverse Proof Confusion

Question

Regarding the proof of Lemma 2: Matrix $A$ is totally unimodular if and only if the matrix $[A |I]$ is TU, I do not understand the first step on permuting square submatrix of B to the desired form.

Proof of Lemma 2: Let $A$ be totally unimodular. Any square submatrix $B$ of $begin{bmatrix} A & Iend{bmatrix}$ can be permuted to the form
$$
tilde B = begin{bmatrix}
  A_1 & 0 \
  A_2 & I_k \
end{bmatrix}.
$$
where $A_1$ is a square sub-matrix of $A$, and so $det(A_1) in {-1,0,1}$.

We have

$$ det(B) = pmdet(tilde B) = det(A_1) in {-1,0,1}.$$

boreal · Answer

This proof is easy piece.
Okay, so for a matrix $A$ to be $TU$ we need to have that any submatrix $A'$ in $A$ must verify:
$$det(A') in {-1,0,1}$$
Let's say that $B$ is then $[A~~ I]$ and that $B'$ is a submatrix of $B$ then $B'$ can be written as $[A'~~ I']$
By the Determinant Expansion by Minors from the columns in $I'$ we have:
$$det(B') = pm det(B'') = ldots = pm det(B'''') = pm det(A'''')$$
$$rank(I') = rank(I'') + 1 = rank(I''') + 2 = ldots$$

Siong Thye Goh · Answer

Take a submatrix $B$ of $begin{bmatrix} A & Iend{bmatrix}$,

Suppose you pick $k$ columns from $I$.

Note that row swapping doesn't change the magnitude of the matrix. Hence when you examine the TU property, you can permute the rows. Just move those zero rows to the top. That would result in the form that they describe.

Unimodular Matrix Inverse Proof Confusion

2 Answers

Add your own answers!

Ask a Question