Totally Unimodular Matrices

A square or rectangular matrix M is said to be totally unimodular if every non-singular square submatrix (i.e., one with non-zero determinant) is a unimodular matrix.

A square submatrix is unimodular if its determinant is either +1 or −1.

In this definition, we also include individual non-zero entries of M, as they can be viewed as 1×1 submatrices with determinant equal to the entry itself.

Note. Zero entries are excluded from this criterion, since they correspond to singular 1×1 submatrices with determinant equal to zero.

A Practical Example

Consider the following rectangular matrix:

$$ \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \end{pmatrix} $$

This matrix is totally unimodular because all of its non-singular square submatrices are unimodular - that is, each has determinant either +1 or −1.

$$ \det \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix} = 1 $$

$$ \det \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} = -1 $$

$$ \det \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = 1 $$

We also take into account the non-zero individual entries, treating them as unimodular 1×1 submatrices:

$$ \det(1) = 1 \qquad \det(-1) = -1 $$

Note. Zero elements are disregarded, since as 1×1 submatrices they are singular: $$ \det(0) = 0 $$

Key Properties of Totally Unimodular Matrices

Totally unimodular matrices exhibit several important structural properties:

• A necessary (but not sufficient) condition for a matrix to be totally unimodular is that all its non-zero entries must be either 1 or −1.

  Note. If a matrix contains entries other than 1 or −1, those values form 1×1 submatrices with determinant not equal to ±1, violating the definition. However, the converse is not true: a matrix composed only of 0s, 1s, and −1s may still fail to be totally unimodular. For instance, the matrix $$ \begin{pmatrix} 1 & -1 & 0 \\ 1 & 1 & 0 \end{pmatrix} $$ is not totally unimodular because it contains at least one square submatrix with determinant not equal to ±1: $$ \det \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} = 2 $$

• Not every unimodular matrix is totally unimodular.

  Example. The matrix $$ \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} $$ is unimodular, since its determinant is $$ \det \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} = 3 \cdot 1 - 1 \cdot 2 = 1 $$ However, it is not totally unimodular, as some 1×1 submatrices (i.e., the individual entries) are not unimodular: $$ \det(3) = 3 \qquad \det(2) = 2 $$

• If a matrix $M_{m,n}$ is totally unimodular, then appending an identity matrix $I_m$ or $-I_m$ horizontally (i.e., as additional columns), or $I_n$ or $-I_n$ vertically (i.e., as additional rows), preserves total unimodularity.

  Example. Consider the totally unimodular matrix $$ M_{2,3} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \end{pmatrix} $$ Appending $I_2$ or $-I_2$ as additional columns yields: $$ [ M_{2,3} \ I_2 ] = \begin{pmatrix} 1 & -1 & 0 & \color{red} 1 & \color{red} 0 \\ 1 & 0 & 1 & \color{red} 0 & \color{red} 1 \end{pmatrix} $$ $$ [ M_{2,3} \ -I_2 ] = \begin{pmatrix} 1 & -1 & 0 & \color{red} {-1} & \color{red} 0 \\ 1 & 0 & 1 & \color{red} 0 & \color{red} {-1} \end{pmatrix} $$ Likewise, appending $I_3$ or $-I_3$ as additional rows results in: $$ \begin{bmatrix} M_{2,3} \\ I_3 \end{bmatrix} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \\ \color{red} 1 & \color{red} 0 & \color{red} 0 \\ \color{red} 0 & \color{red} 1 & \color{red} 0 \\ \color{red} 0 & \color{red} 0 & \color{red} 1 \end{pmatrix} $$ $$ \begin{bmatrix} M_{2,3} \\ -I_3 \end{bmatrix} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \\ \color{red} {-1} & \color{red} 0 & \color{red} 0 \\ \color{red} 0 & \color{red} {-1} & \color{red} 0 \\ \color{red} 0 & \color{red} 0 & \color{red} {-1} \end{pmatrix} $$

And so on.