totally unimodular matrix - negative identity matrix

Question

Theorem: The inverse of a (non-singular) totally unimodular matrix is totally unimodular.

The proof will use the following lemmas.

Lemma 1: Permuting rows and columns preserves total unimodularity.

Lemma 2: Matrix A is totally unimodular if and only if the matrix [AI] is totally unimodular (where I is the identity matrix of the appropriate size).

---

The slides provided as a support material for my course say that:

Given A $\in M_{m x n}$

such affermations are equivalent

$A$ is TU

$[A, I]$ is TU

$A^T$ is TU

$[A, -A]$ is TU

$-A$ is TU

$\begin{bmatrix} A\\ I \end{bmatrix}$ is TU

$[A, A]$ is TU

$\begin{bmatrix} A\\ -I \end{bmatrix}$ is TU

Based on such assumption, is it correct to assume that matrix A is totally unimodular if and only if the matrix [A -I] is totally unimodular (where I is the identity matrix of the appropriate size).

Answer 1

If $[A, -I]$ is totally unimodular then also $A$.

Conversely, let $A$ be totally unimodular. Let $B$ be a square sub-matrix of $[A, -I]$. We do a proof by induction of the size of the sub-matrix. If $B$ is $1\times 1$ then $B=\{\pm1,0\}$. Now assume that the determinant of all sub-matrices of size strictly less than $k$ are in $\{\pm1,0\}$. Let $B$ be of size $k\times k$. Let $(b_1\dots b_k)$ denote the columns of of $B$. If one such column is zero, then $\det B=0$. If one of these $b_i$ is non-zero, and this $b_i$ is a column of $I$ then $b_i$ is a unit vector. We can develop the determinant of $B$ with respect column $i$ and have to compute the determinant of a submatrix of size $k-1$. By induction assumption this is in $\{\pm 1,0\}$, so is the determinant of $B$.

Answer 2

I am not sure how to use those two lemmata, but it seems easier to consider the minors of $B=A^{-1}$ directly. In general, if $\mathcal I,\mathcal J\subseteq\{1,2,\ldots,n\}$ are such that $|\mathcal I|=|\mathcal J|=p$ for some $1\le p\le n$, then $$ \det B(\mathcal I,\mathcal J) =\pm\frac{\det A(\mathcal I^c,\mathcal J^c)}{\det A}.\tag{1} $$ (See e.g. Prasolov, Problems and Theorems in Linear Algebra, theorem 2.5.1.) Therefore, if $A$ is a nonsingular totally unimodular matrix, the RHS of $(1)$ must lie inside $\{0,1,-1\}$. Hence $B=A^{-1}$ is totally unimodular.