Total unimodularity

Let \(\mathbf{B}\) be a \(k\times k\) submatrix of \(\mathbf{A}\). It suffices to prove that \(\det(\mathbf{B})\) is \(-1\), \(0\), or \(1\). The proof is by induction on \(k\). When \(k = 1\), \(\mathbf{B}\) just contains one entry of \(\mathbf{A}\) which is \(-1\), \(0\), or \(1\). So \(\det(\mathbf{B})\) is \(-1\), \(0\), or \(1\).

Suppose that \(k \geq 2\). Assume that all \(k\times k\) submatrices of \(\mathbf{A}\) have determinant \(0\), \(1\), or \(-1\). If \(\mathbf{B}\) contains a column composed entirely of \(0\), then \(\det(\mathbf{B}) = 0\). If every column of \(\mathbf{B}\) has exactly one \(1\) and one \(-1\), then \(\det(\mathbf{B}) = 0\) since adding all the rows of \(\mathbf{B}\) gives a row of zeros.

Now, assume that \(B\) has a column with exactly one nonzero entry \(v\), which is \(1\) or \(-1\). Let \(\mathbf{B}'\) denote the submatrix obtained from \(\mathbf{B}\) by deleting the row and column containing \(v\). Applying the cofactor formula to \(\det(\mathbf{B})\) by expanding along the column containing \(v\), we see that \(\det(\mathbf{B})\) is either \(\det(\mathbf{B}')\) or its negative. Since \(\det(\mathbf{B}')\) is \(-1\), \(0\), or \(1\), so is \(\det(\mathbf{B})\).

Let \(B\) be a basis determining the basic solution \(\mathbf{x}^*\). Then \(\mathbf{A}_B\mathbf{x}^*_B = \mathbf{b}\) and \(x^*_j = 0\) for all \(j \notin B\). For each \(j \in B\), let \(\mathbf{B}^{(j)}\) denote the matrix obtained from \(\mathbf{A}_B\) by replacing \(\mathbf{A}_j\) with \(\mathbf{b}\).

By Cramer's rule, for each \(j \in B\), we have \(x^*_j = \dfrac{\det(\mathbf{B}^{(j)})}{\det(\mathbf{A}_B)}\), which is integral since \(\det(\mathbf{A}_B)\) is either 1 or -1 as \(\mathbf{A}\) is totally unimodular and \(\det(\mathbf{B}^{(j)})\) is integral since all the entries in \(\mathbf{B}^{(j)}\) are integers. Hence, \(\mathbf{x}^* \in \mathbb{Z}^n\).

The Assignment Problem

The Assignment Problem can be stated as follows: There are \(n\) persons and \(n\) tasks. Each person is to be assigned to exactly one task such that no two persons are assigned to the same task. The cost of person \(i\) doing task \(j\) is given by \(c_{ij}\). The problem is to find an assignment of persons to tasks that minimizes total cost.

For each person \(i\) and each task \(j\), we create a variable \(x_{ij}\). We want to assign either 0 or 1 to this variable so that a value 1 means person \(i\) is assigned to task \(j\). Then the total cost is given by \[\sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij}.\]

Note that the variables must satisfy the following constraints: \begin{align*} \sum_{j = 1}^n x_{ij} & = 1 & i = 1,\ldots, n \\ \sum_{i = 1}^n x_{ij} & = 1 & j = 1,\ldots, n \end{align*} The first set of constraints enforces that each person is assigned to exactly one task. The second set of constraints enforces that exactly one person is assigned to each one task. We multiply both sides of the second set of constraints by \(-1\): \begin{align*} \sum_{i = 1}^n -x_{ij} & = -1 & j = 1,\ldots, n \end{align*}

Now, consider the following linear programming problem: \[\begin{array}{rll} \min & \displaystyle\sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij} \\ (AP)~~\text{s.t.} & \displaystyle\sum_{j = 1}^n x_{ij} = 1 & i = 1,\ldots, n \\ & \displaystyle\sum_{i = 1}^n -x_{ij} = -1 & j = 1,\ldots, n \\ & x_{ij} \geq 0 & \mbox{for all } i, j \in \{1,\ldots,n\}. \end{array}\] For example, when \(n = 2\), we have the following: \[\begin{array}{rll} \min & c_{1,1}x_{1,1}+c_{1,1}x_{1,2}+c_{2,1}x_{2,1}+c_{2,2}x_{2,2} \\ \mbox{s.t.} & x_{1,1} + x_{1,2} = 1 \\ & x_{2,1} + x_{2,2} = 1 \\ & -x_{1,1} - x_{2,1} = -1 \\ & -x_{1,2} - x_{2,2} = -1 \\ & x_{1,1}, x_{1,2}, x_{2,1}, x_{2,2} \geq 0. \end{array}\]

Observe that the system ofequality constraints can be expressed in the form \[\mathbf{A}\mathbf{x} = \mathbf{b}\] where \(\mathbf{A}\) has exactly one \(1\) and one \(-1\) in each column.

It is easy to see that \((AP)\) is not unbounded and is feasible (simply set all variables to \(\frac{1}{n}\) for example.) Hence, \((AP)\) has an optimal solution by the Fundamental Theorem of Linear Programming.

Since the entries of each column of \(\mathbf{A}\) sum to 1, \(\mathbf{A}\) does not have full row-rank. It can be show that we can remove any one equality constraint to end up with a system \(\mathbf{A'}\mathbf{x} =\mathbf{b'}\) such that \(\mathbf{A'}\) has full row-rank. By Proposition 7.1, \(\mathbf{A'}\) is totally unimodular. Since \(\mathbf{b}\) is integral, by Proposition 7.2, every basic feasible solution is integral. Thus, solving the modified \((AP)\) using the simplex method will give us an integral solution. Notice that such a solution must have entries that are \(0\) or \(1\) and corresponds to an assignment. Hence, solving the linear programming problem \((AP)\) solves the Assignment Problem!

Worked examples

1. Let \(\mathbf{A} \in \mathbb{Z}^{m\times n}\) be totally unimodular. Prove that \(\mathbf{A}^\mathsf{T}\) \(-\mathbf{A}\), and \(\begin{bmatrix} {\mathbf{A}} & {\mathbf{I}}_m \end{bmatrix}\), where \({\mathbf{I}}_m\) denotes the \(m\times m\) identity matrix, are totally unimodular.

   Let \(\mathbf{M}\) be a \(k\times k\) square submatrix of \(\mathbf{A}\). Since \(\mathbf{A}\) is totally unimodular, we have \det(\mathbf{M}) \in \{-1,0,1\}. Thus \(\det(\mathbf{M}^\mathsf{T}) = \det(\mathbf{M}) \in \{-1,0,1\}\) and \(\det(-\mathbf{M}) = (-1)^k\det(\mathbf{M}) \in \{-1,0,1\}\). It follows that \(\mathbf{A}^\mathsf{T}\) and \(-\mathbf{A}^\mathsf{T}\) are totally unimodular.

   Now, let \(\mathbf{M}\) be a \(k\times k\) square submatrix of \(\begin{bmatrix} {\mathbf{A}} & {\mathbf{I}}_m \end{bmatrix}\). We show that \(\det(\mathbf{M}) \in \{-1,0,1\}\) by induction on the number of columns of \(\mathbf{M}\) that are not subcolumns of \(\mathbf{A}\).

   Clearly, \(\det(\mathbf{M}) \in \{-1,0,1\}\) if every column of \(\mathbf{M}\) is a subcolumn of \(\mathbf{A}\).

   Suppose that at least one column of \(\mathbf{M}\) is a subcolumn of \({\mathbf{I}}_m\). If all the entries in the column are 0, then \(\det(\mathbf{M}) = 0\). Otherwise, there is exactly one 1 in the column. Let \(\mathbf{N}\) be the matrix obtained from \(\mathbf{M}\) by removing the column and row containing that 1. Then \(|\det(\mathbf{M})| = |\det(\mathbf{N})| \in \{0,1\}\) by the induction hypothesis since \(\mathbf{N}\) has one fewer column not a subcolumn of \(\mathbf{A}\).

2. Give an example of a matrix \(\mathbf{A}\) with entries in \(\{-1,0,1\}\) and an integral \(\mathbf{b}\) such that \(\mathbf{A}\mathbf{x} = \mathbf{b},\,\mathbf{x} \geq \mathbf{0}\) has at least one basic feasible solution and every basic feasible solution is integral but \(\mathbf{A}\) is not totally unimodular.

   Take \(\mathbf{A} = \begin{bmatrix} 1 & -1 & 1 \\ 1 & 1 & 0 \end{bmatrix}\) and \(\mathbf{b} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}\). Clearly, \(\mathbf{A}\) is not totally unimodular since the \(2\times 2\) submatrix consisting of the first two columns of \(\mathbf{A}\) has determinant 2.

   Note that the only basic feasible solutions are \(\begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}\) and \(\begin{bmatrix} 0 \\ 1 \\ 3 \end{bmatrix}\) which are integral.