# Prove that the matrix is totally unimodular

Is there any (theoretic) way I can prove the matrix is totally unimodular? I have tested it by Matlab and know it is TU, however I cannot prove it.

-1 -1 -1 -1  0  0  0  0  0  0  0  0
0  0  0  0 -1 -1 -1 -1  0  0  0  0
0  0  0  0  0  0  0  0 -1 -1 -1 -1
1  1  1  1  0  0  0  0  0  0  0  0
0  0  0  0  1  1  1  1  0  0  0  0
0  0  0  0  0  0  0  0  1  1  1  1
1  0  0  0  1  0  0  0  1  0  0  0
0  1  0  0  0  1  0  0  0  1  0  0
0  0  1  0  0  0  1  0  0  0  1  0
0  0  0  1  0  0  0  1  0  0  0  1

• Yes, But I must prove that any square submatrix of it has a $det\in{-1,0,1}$. You can see the wiki for the definition. – remo Jun 23 '13 at 17:54
• Ah sorry, I didn't know that "totally unimodular" allowed for $det = 0$. – Calvin Lin Jun 23 '13 at 18:00

First, observe that since $R_1= - R_4$, $R_2= - R_5$, $R_3 = - R_6$, then if any sub matrix uses any of these pairs of rows, then the determinant must be 0. Hence, (WLOG) we may assume that rows $1, 2, 3$ are removed (and replaced with rows 4, 5, 6 respectively in the sub matrix determinant calculation). Now call this matrix $A$.
3. If two non-zero entries in a column of $A$ have the same sign, then the row of one is in $B$, and the other in $C$.
4. If two non-zero entries in a column of $A$ have opposite signs, then the rows of both are in $B$, or both in $C$.
Observe that if $B$ is the set of rows 4, 5, 6 and $C$ is the set of rows 7, 8, 9, 10, then this will satisfy the conditions. Hence we are done.