= Solution
A <totally unimodular matrix> has the property that every square submatrix has <determinant> zero, one or minus one. This includes the one-by-one submatrices, so every entry belongs to $\{0,1,-1\}$.
Its importance is integrality of linear-programming vertices: if $A$ is totally unimodular and $b$ is integral, every vertex of $\{x:Ax\leq b,\ x\geq0\}$ is integral. Adding rows of the identity preserves total unimodularity. A nonsingular active basis therefore has <determinant> $\pm1$ and an <integer> inverse by the <cofactor> formula, making its basic solution integral. Thus a finite optimum attained at a vertex of the <linear programming relaxation> gives an <integer> optimum without branching.
One sufficient condition is: \b[entries belong to $\{0,1,-1\}$, each column has at most two nonzero entries, and any column with two has one $+1$ and one $-1$.] This is the <signed column condition for total unimodularity>, satisfied by directed vertex-edge incidence matrices. It is sufficient, not necessary.
Back to article page
