Totally Unimodular Matrices

John Mitchell

See Nemhauser and Wolsey, section III.1.2, for more information.

Definition 1 An m×n matrix A is totally unimodular (TU) if the determinant of each square submatrix is equal to 0, 1, or -1.

Necessary conditions:

Theorem 1 If A is totally unimodular then all the vertices of {x _{+}^{n} : Ax = b} are
integer for any integer vector b ^{m}.

Theorem 2 If A is totally unimodular then all the vertices of {x _{+}^{n} : Ax ≤ b} are
integer for any integer vector b ^{m}.

It follows that if A is totally unimodular then the optimal solution to the integer program

can be found by solving its LP relaxation.

Theorem 3 The following statements are equivalent:

- 1.
- A is totally unimodular.
- 2.
- A
^{T }is totally unimodular. - 3.
- [A,I] is totally unimodular.
- 4.
- A matrix obtained by deleting a unit row or column of A is totally unimodular.
- 5.
- A matrix obtained by multiplying a row or column of A by -1 is totally unimodular.
- 6.
- A matrix obtained by interchanging two rows or two columns of A is totally unimodular.
- 7.
- A matrix obtained by duplicating rows or columns of A is totally unimodular.
- 8.
- A matrix obtained by pivot operations on A is totally unimodular.

Note: unit rows and columns are rows and columns of the identity matrix.

Sufficient conditions:

Theorem 4 An integer matrix A with every entry a_{ij} = 0 or ±1 is totally unimodular if no more
than two nonzero entries appear in any column, and if the rows of A can be partitioned into two
sets I_{1} and I_{2} such that:

- 1.
- If a column has two nonzero entries of the same sign then their rows are in different sets.
- 2.
- If a column has two nonzero entries of opposite signs then their rows are in the same set.

Corollary 1 Any linear program of the form

where A is either

- 1.
- the node-arc incidence matrix of a directed graph, or
- 2.
- the node-edge incidence matrix of an undirected bipartite graph

has only integer optimal vertices.

Thus, the following problems can be solved by solving linear programs, and the optimal solutions to the LPs are integral:

shortest path, max-flow, assignment, weighted bipartite matching, …

Theorem 5 If all the extreme points of {x _{+}^{n} : Ax ≤ b} are integral for all b ℤ^{m}
then A is totally unimodular.

Necessary and sufficient condition:

Theorem 6 The following statements are equivalent:

- 1.
- A is totally unimodular.
- 2.
- For every J ⊆ N := {1,…,n}, there exists a partition J
_{1},J_{2}of J such that

Note that Theorem 4 is a special case of this theorem (after transposing the matrix).