Past exam of the integer programming course of the University of Oxford / 2010 / 2 / a

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\le b,x\ge 0\}$ is integral. Adding rows of the identity preserves total unimodularity. A nonsingular active basis therefore has determinant $\pm 1$ 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: 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.