Recognizing TU Structure in Practice

Checking total unimodularity (TU) directly from the definition would require computing the determinant of every square submatrix — exponentially many of them. In practice we recognize TU using the following sufficient condition.

Heller-Tompkins criterion. A matrix $A$ with entries in $\{-1, 0, +1\}$ is totally unimodular if both of the following hold:

1. Every column has at most two nonzero entries.
2. The rows can be partitioned into two sets $R_1$ and $R_2$ such that, for each column with two nonzero entries:
   • the two entries have opposite signs $\implies$ their rows lie in the same set;
   • the two entries have the same sign $\implies$ their rows lie in different sets.

As a quick illustration, consider

$$A = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 0 & -1 \\ 0 & 1 & 1 \end{bmatrix}.$$

Every column has exactly two nonzeros with opposite signs. Taking $R_1 = \{1,2,3\}$ and $R_2 = \emptyset$ satisfies condition 2 trivially (every opposite-sign pair lies in $R_1$). Therefore $A$ is TU.