2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Copi
    Mar 6 '13 at 9:37
  • $\begingroup$ 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. $\endgroup$ Mar 6 '13 at 23:48
2
$\begingroup$

Consider the matrix: $$\begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1\\ \end{bmatrix}$$

Observe that the determinant of this matrix is two so the matrix is not totally unimodular as required.

Note: credit for this example goes to Camion for his nice characterization of TU matrices in his 1965 paper (see citation below).

Camion, P., Characterization of totally unimodular matrices, Proc. Am. Math. Soc. 16, 1068-1073 (1965). ZBL0134.25201.

$\endgroup$
2
  • $\begingroup$ Israel's $3\times3$ example is correct and your comment about it is wrong. E.g. $\det\pmatrix{0&1&1\\ 1&0&1\\ 1&1&0}=2$. Note that every matrix is a submatrix of itself. We are not only talk about proper submatrices in the definition of TU. $\endgroup$
    – user1551
    Jan 4 '18 at 12:42
  • $\begingroup$ Yep, you are right! My mistake. The answer has been updated. $\endgroup$ Jan 5 '18 at 13:46

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.