An unimodular matrix is a square matrix with integer entries such that its determinant is either -1, 0 or 1. A matrix is said totally unimodular (TU for short) if all its square submatrices are unimodular.
Sometime ago, we said that problems such as the minimum path, maximum flow and minimum cost max flow can be modeled using linear programming with the interesting property that the optimal solutions are always integer.
In that post, we also said that it was because the coefficient matrix of the constraints of the formulations are totally unimodular. More formally, we have the following theorem:
Theorem 1. Let be a totally unimodular matrix and be an integer vector. Then, the polyhedra has integer vertices.
In this post we’ll present some properties of TU matrices and discuss about two simple examples.
Let be a totally unimodular matrix. Then we have the following properties:
- Its transpose, , is TU.
- The matrix obtained by appending the identity matrix to , that is , is TU
- Any submatrix of is TU
- The matrix obtained by multiplying any row of by -1 is TU
- The matrix obtained by duplicating any row of is TU
Using this properties we can get some Corollaries from Theorem 1.
Since is TU, we have the following
Corollary 1. The polytope has integer vertices.
Also, since is TU,
Corollary 2. The dual of , namely has also integer vertices.
1. Bipartite Graphs
Let be an undirected graph and the incidence matrix of . That is, a binary matrix where each line corresponds to a vertex and each column to an edge . We have if is an endpoint of or otherwise. Then, we have the following result:
Theorem 2. The incidence matrix of a graph is totally unimodular if and only if, is bipartite.
This result can be used to derive the König-Egerváry theorem, stating that the maximum cardinality matching and the minimum vertex cover have the same value bipartite graphs.
The maximum cardinality can be modeled as integer linear programming:
And its dual is the minimum vertex cover:
It’s not hard to see that if is the incidence matrix of the graph, then the problems can be stated as
If the graph is bipartite, we can use Theorem 2 and the strong duality for linear programs to conclude that (1) = (2).
2. Directed Graphs
Let a directed graph, and be the incidence matrix of . That is, a matrix where each line corresponds to a vertex and each column to an arc. For each arc , we have and and 0 otherwise. For directed graphs, we have a even stronger result:
Theorem 3. The incidence matrix of a directed graph is totally modular.
Consider a network represented by and with capacities represented by . For each directed edge , let be the flow in this edge.
If is the incidence matrix of , then corresponds to
which are the flow conservation constraints. Since is totally unimodular, then if is integer, it’s possible to show that the polytope has integral vertices. This polytope also represents the constraints of the max circulation problem.
Now, we can use these observations to prove that the following LP formulation for the max-flow problem has an optimal integer solution:
We can see that the constraints matrix of the above formulation is a submatrix of the max circulation problem and by Property 3, it’s also TU, which in turn means the corresponding polytope has integral vertices.
In this post, we introduced the concept of total unimodular matrices and presented two simple examples: the incidence matrix of a bipartite graph and the incidence matrix of a directed graph.
Here’s a cool chart of common polynomial time solvable problems organized by their generality .
In future posts, we’ll keep exploring this subject by studying other examples and properties of TU matrices.
 Theory of Linear and Integer Programming – A. Schrijver
 Marco Chiarandini – Scheduling, Timetabling and Routing DM204 (Lecture Notes)
 Ted Ralphs – Integer Programming IE418 (Lecture Notes)