Is the matrix totally unimodular?

Question

Let $A=\begin{bmatrix}1&0&1&1&0&0&1&0&0\\0&1&0&1&0&0&0&0&0& \\0&0&1&1&1&0&0&0&0\\0&0&-1&-1&0&1&-1&0&0\\0&0&0&-1&0&0&0&1&0\\0&0&-1&-1&0&0&0&0&1\end{bmatrix}$, is the matrix totally unimodular?

I realised that if I change the order of columns in A I could get change the matrix I would get $A=( B I_{6x6})$, but I wasn't sure if I could use this for anything.

Answer 1

Successively applying column-swapping, $C_3 \leftrightarrow C_5$, $C_4 \leftrightarrow C_6$, $C_7 \leftrightarrow C_8$ and $C_8 \leftrightarrow C_9$, we get,

$A^{\prime}=\begin{bmatrix}1&0&0&0&0&0&1&1&1\\0&1&0&0&0&0&0&1&0& \\0&0&1&0&0&0&1&1&0\\0&0&0&1&0&0&-1&-1&-1\\0&0&0&0&1&0&0&-1&0\\0&0&0&0&0&1&-1&-1&0\end{bmatrix}=\left[I_6 \mid B\right]$, where $B=\begin{bmatrix}1&1&1\\0&1&0& \\1&1&0\\-1&-1&-1\\0&-1&0\\-1&-1&0\end{bmatrix}$

Now, from here, we have

• $A$ is unimodular iff $A^{\prime}$ is unimodular.
• $A^{\prime}$ is unimodular iff $B$ is unimodular.

Now, all remains to be shown is that $B$ is unimodular.

• All elements of $B \in \{-1,0,1\}$
• Any $2 \times 2$ submatrix of $B$ is of the form $\begin{bmatrix}x&x\\ x&x\end{bmatrix}$ or $\begin{bmatrix}x&x\\ -x&-x\end{bmatrix}$ or $\begin{bmatrix}y&0\\ x&x\end{bmatrix}$ or $\begin{bmatrix}0&y\\ x&x\end{bmatrix}$ or $\begin{bmatrix}x&x\\ y&0\end{bmatrix}$ or $\begin{bmatrix}x&x\\ 0&y\end{bmatrix}$ or $\begin{bmatrix}x&y\\ x&0\end{bmatrix}$ or $\begin{bmatrix}y&x\\ 0&x\end{bmatrix}$, or their transpose matrices, where $x,y \in \{-1,0,1\}$, clearly $det(B) = 0$ or $xy \in \{-1,0,1\}$
• Finally, show that all $3 \times 3$ submatrices (there are only ${6 \choose 3} = 20$ of them, each one having all cofactors $\in \{-1,0,1\}$) have determinant $\in \{-1,0,1\}$.

Answer 2

In general stacking TU matrices does not always produce a TU matrix, but in this case I agree that it suffices to show that $C = \begin{bmatrix}1 & 1 & 1 \\ 0 & 1& 0 \\ 1 & 1 & 0\end{bmatrix}$ is TU. We can then get $B$ (defined in the other answer) by adding copies of the rows and then multiplying those rows by $-1$; both operations are easily seen to preserve TU.

For $C$, just note that any $2\times 2$ $(0,1)$-matrix is TU, so it only remains to check the full 3x3-matrix, which is easily done by developing along, say, the third column.