7.4 Total unimodularity
Every vertex in Example 7.1.2 has integer coordinates, although nothing in the LP asks for this. The reason is a property of the constraint matrix.
Definition 7.4.1. A matrix is totally unimodular (TU) if every square submatrix has determinant \(0\), \(1\) or \(-1\).
Theorem 7.4.2. If \(A\) is TU and \(b\) is integral, every vertex of \(\{x : Ax = b, x \geq 0\}\) (and of \(\{x : Ax \leq b, x \geq 0\}\)) is integral.
Proof. A vertex is a BFS, \(x_B = B^{-1}b\) with \(B\) a square non-singular submatrix of \(A\). By Cramer’s rule \((B^{-1}b)_i = \det B_i/\det B\), where \(B_i\) is \(B\) with column \(i\) replaced by \(b\); \(\det B = \pm 1\) and \(\det B_i\) is an integer. For the inequality form, \([A \mid I]\) is TU when \(A\) is. □
Theorem 7.4.3. Let \(A\) have entries in \(\{0, 1, -1\}\), at most two non-zero entries in each column, and rows that can be split into two groups so that a column with two non-zeros of the same sign has them in different groups, and one with opposite signs in the same group. Then \(A\) is TU. In particular the constraint matrix of every transportation and assignment problem, the incidence matrix of a bipartite graph, is TU.
Proof. By induction on the size \(k\) of a square submatrix \(M\); for \(k = 1\) it is clear. If \(M\) has a zero column, \(\det M = 0\). If some column has exactly one non-zero, expand along it: \(\det M = \pm \det M'\) with \(M'\) of size \(k - 1\), and use the induction hypothesis. Otherwise every column of \(M\) has two non-zeros, and adding the rows of the first group and subtracting those of the second gives \(0\) in every column, so the rows are dependent and \(\det M = 0\). For the transportation matrix, put the supply rows in one group and the demand rows in the other: each column \(x_{ij}\) has a \(1\) in each. □
So the transportation problem with integer supplies and demands has an integer optimal solution, found by the simplex method without any integer programming. The condition fails for the incidence matrix of an odd cycle, which has determinant \(2\) (Software 7.6.3): integrality is special to bipartite structure, and to the network matrices of the next section.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.