Given a totally unimodular matrix $A \in\{-1,0,1\}^{m\times n}$, show that the matrix $$\begin{bmatrix} A &\pm A\end{bmatrix}$$ is also totally unimodular.
I want to prove that exchanging any two columns in $A$ will still be unimodular at first but it seems that the idea is wrong. Thanks in advanceļ¼
Best Answer
The goal is to show that if a square submatrix of $[A,\pm A]$ is nonsingular then it has determinant $\pm 1$. Observe that any nonsingular square submatrix of $[A,\pm A]$ is (up to permutation and sign of the columns) a nonsingular square submatrix of $A$ (justified later). Hence since permutation changes determinants by the sign of the permutation, which is $\pm 1$, and changing the sign of a columns also multiplies the determinant by $-1$ for each such column, we observe that this implies that the determinant of every nonsingular square submatrix of $[A,\pm A]$ is $\pm 1$.
Now to justify the claim. Well, if we choose a square submatrix of $[A,\pm A]$, we are choosing a subset of the rows and columns of $[A,\pm A]$. Let's label the columns of $[A,\pm A]$ as $C_1,\ldots,C_n,C_{n+1},C_{2n}$. By definition $C_i=\pm C_{i+n}$ for $1\le i\le n$, so if the subset of the columns that we choose contains index $i$ and $i+n$ for some $1\le i\le n$, the resulting matrix must have determinant 0 because $C_i$ and $C_{i+n}$ will be linearly dependent no matter what subset of the rows we choose. Thus there is a map identifying the subset of the columns of $[A,\pm A]$ with a subset of the columns of $A$ given by $$ i\mapsto \begin{cases} i & \textrm{if $1\le i \le n$} \\ i-n & \textrm{otherwise.}\end{cases}. $$