Total unimodularity

Storage

This note is not stored correctly.

In mathematics, total unimodularity ^[1] is a property of a matrix $\mathbf{A}\in {\mathbb{Z}}^{m\times n}$ requiring that every square submatrix $\mathbf{B}$ of $\mathbf{A}$, not just $\mathbf{A}$ itself, satisfy $\det (\mathbf{B})\in \{0,1,-1\}$.

It is strictly stronger than being unimodular, and its significance lies in guaranteeing that the polyhedron $\{\mathbf{x}\mid \mathbf{A}\mathbf{x}\le \mathbf{b},\mathbf{x}\ge 0\}$ has only integral vertices for every integral $\mathbf{b}$, which is why it is a central tool for proving that linear program relaxations of combinatorial optimization problems solve exactly.

Definition

---

Definition 1 (Square submatrix)

Given a matrix $\mathbf{A}=(a_{ij})\in {\mathbb{R}}^{m\times n}$ together with row indices $1\le i_1<\cdots <i_k\le m$ and column indices $1\le j_1<\cdots <j_k\le n$, the $k\times k$ matrix $\mathbf{B}$ formed from the entries $a_{i_r,j_s}$ is called a square submatrix of $\mathbf{A}$.

Definition 2 (Totally unimodular matrix)

A matrix $\mathbf{A}\in {\mathbb{Z}}^{m\times n}$ is totally unimodular (TU) if every square submatrix $\mathbf{B}$ of $\mathbf{A}$ satisfies $\det (\mathbf{B})\in \{0,1,-1\}$. Every entry of a totally unimodular matrix is therefore itself $0$, $1$, or $-1$, though the converse does not hold.

Properties

---

Lemma 1 (Closure properties)

Let $\mathbf{A}\in {\mathbb{Z}}^{m\times n}$ be totally unimodular. Then:

1. Every submatrix of $\mathbf{A}$ is totally unimodular.
2. ${\mathbf{A}}^T$, $-\mathbf{A}$, and $-{\mathbf{A}}^T$ are totally unimodular.
3. $\mathbf{A}$ extended by a unit column or unit row vector is totally unimodular.

Proof of Lemma 1

(1) Every square submatrix of a submatrix of $\mathbf{A}$ is itself a square submatrix of $\mathbf{A}$, so its determinant is $0$, $1$, or $-1$ by assumption.

(2) Transposing does not change the determinant of a square submatrix, since the submatrix of ${\mathbf{A}}^T$ on rows $J$ and columns $I$ is the transpose of the submatrix of $\mathbf{A}$ on rows $I$ and columns $J$. Negating $\mathbf{A}$ negates every entry of each $k\times k$ square submatrix, which multiplies its determinant by $(-1{)}^k$; since $(-1{)}^k\in \{1,-1\}$, the determinant stays in $\{-1,0,1\}$.

(3) Let ${\mathbf{A}}^{\prime }$ be a square submatrix of $\mathbf{A}$ extended by a unit column vector ${\mathbf{e}}_i$. If ${\mathbf{A}}^{\prime }$ does not contain the new column, it is a square submatrix of $\mathbf{A}$ and the claim holds by assumption. Otherwise, expand $\det ({\mathbf{A}}^{\prime })$ along that column: it has a single nonzero entry, so $\det ({\mathbf{A}}^{\prime })=\pm \det ({\mathbf{A}}^{\prime \prime })$, where ${\mathbf{A}}^{\prime \prime }$ is the square submatrix of $\mathbf{A}$ obtained by deleting the row and column of that entry. Since $\det ({\mathbf{A}}^{\prime \prime })\in \{-1,0,1\}$ by assumption, so is $\det ({\mathbf{A}}^{\prime })$. The argument for an added unit row vector is symmetric. $\square$

Lemma 2 (Invariance under permutation)

Let $\mathbf{A}\in {\mathbb{Z}}^{m\times n}$ and let ${\mathbf{A}}^{\prime }=\mathbf{P}\mathbf{A}\mathbf{Q}$ for permutation matrices $\mathbf{P}\in \{0,1{\}}^{m\times m}$ and $\mathbf{Q}\in \{0,1{\}}^{n\times n}$. Then $\mathbf{A}$ is totally unimodular if and only if ${\mathbf{A}}^{\prime }$ is totally unimodular.

Proof of Lemma 2

Assume $\mathbf{A}$ is totally unimodular and let ${\mathbf{B}}^{\prime }$ be a $k\times k$ square submatrix of ${\mathbf{A}}^{\prime }$ on rows $I^{\prime }$ and columns $J^{\prime }$. Since $\mathbf{P}$ and $\mathbf{Q}$ only permute rows and columns, the entries of ${\mathbf{B}}^{\prime }$ are exactly the entries of the square submatrix $\mathbf{B}$ of $\mathbf{A}$ on the preimages of $I^{\prime }$ and $J^{\prime }$, read in a different order. Hence ${\mathbf{B}}^{\prime }$ arises from $\mathbf{B}$ by permuting rows and columns, which changes the determinant only by the sign of those permutations, so $\det ({\mathbf{B}}^{\prime })=\pm \det (\mathbf{B})\in \{0,1,-1\}$.

For the converse, note that $\mathbf{A}={\mathbf{P}}^{-1}{\mathbf{A}}^{\prime }{\mathbf{Q}}^{-1}$ and that ${\mathbf{P}}^{-1}$ and ${\mathbf{Q}}^{-1}$ are again permutation matrices, so the same argument applies with the roles of $\mathbf{A}$ and ${\mathbf{A}}^{\prime }$ exchanged. $\square$

The Ghouila-Houri theorem gives a second view of Lemma 2. It characterizes total unimodularity by a condition on unordered row subsets and per-column sums, requiring that every subset of rows splits into two parts whose difference has all entries in $\{0,1,-1\}$. Permuting rows only relabels which subsets are enumerated and permuting columns only reorders the inequalities to be checked, so the theorem’s condition holds for $\mathbf{A}$ exactly when it holds for ${\mathbf{A}}^{\prime }$. Total unimodularity is thus order-independent by construction under that characterization, whereas Definition 2 refers to ordered index sets and needs the sign argument above to reach the same conclusion.

Lemma 3 (Two-sided constraint systems)

Let $\mathbf{A}\in {\mathbb{Z}}^{m\times n}$ be totally unimodular. Then

$$\mathbf{C}=\left(\begin{array}{c}\mathbf{A}\\ -\mathbf{A}\\ {\mathbf{I}}_n\\ -{\mathbf{I}}_n\end{array}\right)$$

is totally unimodular. Consequently, for integral vectors $\mathbf{b},{\mathbf{b}}^{\prime }\in {\mathbb{Z}}^m$ and $\mathbf{l},\mathbf{u}\in {\mathbb{Z}}^n$, the polyhedron $\{\mathbf{x}\in {\mathbb{R}}^n\mid {\mathbf{b}}^{\prime }\le \mathbf{A}\mathbf{x}\le \mathbf{b},\mathbf{l}\le \mathbf{x}\le \mathbf{u}\}$ has only integral vertices.

Proof of Lemma 3

Let $\mathbf{D}$ be a $k\times k$ square submatrix of $\mathbf{C}$. If $\mathbf{D}$ selects the same row of $\mathbf{A}$ from both the $\mathbf{A}$ block and the $-\mathbf{A}$ block, then two rows of $\mathbf{D}$ are negatives of each other, so $\det (\mathbf{D})=0$. The same holds for a row taken from both ${\mathbf{I}}_n$ and $-{\mathbf{I}}_n$.

Otherwise every row of $\mathbf{D}$ comes from a distinct row of $\mathbf{A}$ or of ${\mathbf{I}}_n$, possibly negated, so $\mathbf{D}$ arises from a square submatrix ${\mathbf{D}}^{\prime }$ of $\left(\begin{array}{c}\mathbf{A}\\ {\mathbf{I}}_n\end{array}\right)$ by negating some rows. That matrix is totally unimodular by Lemma 1 of the total unimodularity note, applied once for each of the $n$ unit rows, so $\det (\mathbf{D})=\pm \det ({\mathbf{D}}^{\prime })\in \{0,1,-1\}$. $\square$

Theorem 1 (Integrality of totally unimodular polyhedra)

Let $\mathbf{A}\in {\mathbb{Z}}^{m\times n}$ be totally unimodular and $\mathbf{b}\in {\mathbb{Z}}^m$. Then the polyhedron $\{\mathbf{x}\in {\mathbb{R}}^n\mid \mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}\ge 0\}$ has only integral vertices. The same holds for $\{\mathbf{x}\in {\mathbb{R}}^n\mid \mathbf{A}\mathbf{x}\le \mathbf{b},\mathbf{x}\ge 0\}$ and $\{\mathbf{x}\in {\mathbb{R}}^n\mid \mathbf{A}\mathbf{x}\le \mathbf{b}\}$.

Proof of Theorem 1

Assume without loss of generality that $\mathbf{A}$ has full row rank $m$. A point $\mathbf{x}$ is a vertex of the polyhedron if and only if it is a feasible basic solution: there exist column indices $j_1,\dots ,j_m$ such that the columns ${\mathbf{a}}^{j_1},\dots ,{\mathbf{a}}^{j_m}$ are linearly independent and the corresponding entries of $\mathbf{x}$ solve ${\mathbf{A}}^{\prime }{\mathbf{x}}^{\prime }=\mathbf{b}$ for ${\mathbf{A}}^{\prime }=({\mathbf{a}}^{j_1},\dots ,{\mathbf{a}}^{j_m})$. By Cramer’s rule, $x_{j_k}=\det ({\mathbf{A}}_{j_k}^{\prime })/\det ({\mathbf{A}}^{\prime })$. Since $\mathbf{A}$ is totally unimodular and the columns of ${\mathbf{A}}^{\prime }$ are linearly independent, $\det ({\mathbf{A}}^{\prime })=\pm 1$. Since $\mathbf{b}$ is integral, $\det ({\mathbf{A}}_{j_k}^{\prime })$ is integral, so each $x_{j_k}$ is integral. $\square$

A key source of totally unimodular matrices is the incidence matrix of a graph: the incidence matrix of a directed graph is always totally unimodular, which is what makes network flow and transportation problems solvable exactly by linear programming.

TODO

---

• A matrix is TU if and only if its transpose matrix is TU.

References

1. [1]

   “Unimodular matrix”, Wikipedia, Available: https://en.wikipedia.org/wiki/Unimodular_matrix, Accessed: 2026-07-15 ↩