TU is Totally Unimodular Verify that the top two matrices ar

TU is Totally Unimodular

Verify that the top two matrices are TU but the bottom two are not. (1 -1 0 0 -1 -1 1 -1 0 0 0 -1 1 -1 0 0 0 -1 1 -1 -1 0 0 -1 1) (1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1) (1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1) (1 0 1 0 0 1 0 1 -1 1 0 -1 0 0 -1 1)

Solution

Following are the sufficient conditions for totally unimodular matrices:-

Let A be an m by n matrix whose rows can be partitioned into two disjoint sets B and C. Then the following four conditions together are sufficient for A to be totally unimodular:

1) Every column of A contains at most two non-zero entries.
2) Every entry in A 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.

The top two matrices satisfy all the above four conditions, hence they are TU.
The bottom two don\'t satify all the above four conditions, hence they are not TU.