4
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – remo Jun 23 '13 at 17:54
  • $\begingroup$ Ah sorry, I didn't know that "totally unimodular" allowed for $det = 0 $. $\endgroup$ – Calvin Lin Jun 23 '13 at 18:00
7
$\begingroup$

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$.

If you look up the Wikipedia article, you will see a sufficient condition for Totally Unimodular matrices:

  1. Every column of contains at most two non-zero entries.
  2. Every entry in is 0, +1, or −1
  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.

$\endgroup$
  • $\begingroup$ @remo I came up with it when I started reading about totally unimodular matrices. Off the top of my head, I don't know a proof of the quoted result, though since it's in the appendix of a paper, it should be easy. $\endgroup$ – Calvin Lin Jun 23 '13 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.