Proof that this matrix is TUM

Question

Suppose that A is a mxn TU Matrix. (Totally unimodular). Proof that [A I]^T (so I mean the column vector with A the first element and I the second, where I is the identity matrix) is also TUM. Can somebody help me?

Answer 1

First, a matrix is TUM if and only if its transpose is, which I hope is easy enough for you to see. So the only issue is showing $[A\,\,I]$ is TUM. By definition you need to check that every minor has determinant $\pm 1$ or $0$. Well, take a square submatrix of $[A\,\,I]$. Some of its columns are from the $A$ block, and some are from the $I$ block. Apply induction on the number of columns from the $I$ part.