Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am just wondering if there are matrices that only consists of $0$s and a few $1$s that are not totally unimodular (TU)? I cannot come up with an example but I am not very experienced with this stuff.

In a specific case, if I have a very sparse $0-1$ matrix where every row consist of at most two $1$s and every column consists of at most three $1$s, how can I find out whether this matrix is TU?

I cannot use the four sufficient conditions for $A$ to be totally unimodular (where $B, C$ is a disjoint partition of the rows of $A$), because condition 3 might be violated:

  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 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 have opposite signs, then the rows of both are in $B$, or both in $C$.

Thank you!

share|improve this question

1 Answer 1

There is a (very simple) $2 \times 2$ example where the determinant is $0$. Any $3 \times 3$ example with all rows having two $1$'s that does not have determinant $0$ has determinant $\pm 2$.

share|improve this answer
    
Ok, thank you. Than seems to be rather easy. However, the 2-2 matrix with determinant 0 would still be TU. And the matrices I have are very large and usually don't contain columns with two consecutuve 1s. –  Copi Mar 6 '13 at 9:37
    
Any square submatrix that has a row or column containing only one $1$ is unimodular iff the sub-submatrix obtained by deleting the row and column with that $1$ is unimodular. So you want to look at square submatrices where all rows and columns have two $1$'s. –  Robert Israel Mar 6 '13 at 23:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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