Section 6.3 Totally Unimodular Matrices and Matchings
Our goal in this section is to investigate a nice application of totally unimodular matrices to matching problems in bipartite graphs. Given a graph with vertices \(v_1,\dots,v_n\) and edges \(e_1,\dots,e_m\text{,}\) the incidence matrix of \(G\) is an \(n\times m\) matrix in which the entry on the \(i\)th row and \(j\)th column is \(1\) if \(v_i\) is an endpoint of \(e_j\) and \(0\) otherwise. As it turns out, the incidence matrix of a graph is totally unimodular if and only if that graph is bipartite.
Proof.
First, suppose that \(G\) is not bipartite. Let \(C\) be the matrix obtained by restricting the incidence matrix of \(G\) to the rows and columns corresponding to the vertices and edge of the shortest odd cycle in \(G\text{.}\) We claim that this is not totally unimodular which will imply that our original matrix was not either. Perhaps the most natural way of doing this is to show that the determinant of this matrix is not equal to \(0,1\) or \(-1\) (in fact, it can be shown that is equal to \(2\) or \(-2\text{,}\) depending on how you order the rows/columns; see Exercise 10). However, for fun, we will prove that this matrix fails to be totally unimodular in another way. Suppose that the number of rows/columns in \(C\) is \(2k+1\) and let \(b\) be the all-ones vector of length \(2k+1\text{.}\) We will show that the polytope \(P=\{x: Cx\leq b\}\) has a vertex that is not integer, which will imply that it is not totally unimodular by Lemma 6.2.3. Indeed, the vector \(z=\frac{1}{2}b\) is in the polytope \(\{x: Cx\leq b\}\) and satisfies \(A_z=C\text{.}\) Also, the matrix \(C\) has rank \(2k+1\) because, if \(x\) is a with \(Cx=0\text{,}\) then we would need that the entries of \(x\) corresponding to any two edges of the cycle that share an edge must be negatives of each other; but, by parity, this can only happen if \(x=0\) and so \(C\) has full rank. This proves that \(z\) is a non-integer vertex of \(P\) and completes this direction of the proof.
Next, suppose that \(G\) is bipartite. We let \(A\) be any \(k\times k\) submatrix of the incidence matrix of \(G\) and show that \(\det(A)\) is \(0,1\) or \(-1\text{.}\) The case \(k=1\) is trivial and so we assume \(k\geq2\text{.}\) If \(A\) has a zero column, then its determinant is obviously zero. So, we can assume that all columns are non-zero. Next, suppose that \(A\) has a column with a unique \(1\text{.}\) If we apply cofactor expansion along this column, then we get that the determinant of \(A\) is equal to the determinant of a \((k-1)\times (k-1)\) submatrix, possibly times \(-1\text{,}\) and so we are done by induction in this case. So, we assume that every column has exactly two ones in it. Now, recall that \(G\) is bipartite. If we sum all of the rows of \(A\) corresponding to vertices in one of the classes of its bipartition and subtract all of the rows corresponding to vertices in the other, then it equals the all zero vector and so the determinant of \(A\) is zero. This completes the proof.
Given this, we see that the maximum weight perfect matching problem in bipartite graphs can be reduced to a simple LP. That is, if \(A\) is the incidence matrix of a bipartite graph \(G\) and \(c\) is a vector assigning a weight to each edge of \(G\text{,}\) then, by Corollary 6.2.4 and Lemma 6.3.1, the following LP (which is clearly bounded) is always optimized by an integer vector:
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq 1\\
\amp \amp x\geq0
\end{align*}
where, in the first constraint, we use \(1\) to denote the all-ones vector. However, its not hard to see that an optimal integer vector for this LP corresponds to a matching of maximum weight. As it turns out, a similar reduction works for the maximum or minimum weight perfect matching problems on bipartite graphs as well; see Exercise 3.
We can also use total unimodularity to obtain the following nice generalization of Kőnig’s Theorem to general integer valued weight functions. This can be seen as an alternative proof to the result of Exercise 15.
Theorem 6.3.2.
Let \(G\) be a bipartite graph and let \(c: E(G)\to \mathbb{Z}\) be a weight function for the edges of \(G\text{.}\) Then the maximum weight of a matching in \(G\) is equal to the minimum value of \(\sum_{v\in V(G)}f(v)\) where \(f:V(G)\to\mathbb{N}\cup\{0\}\) is a function such that \(f(u)+f(v)\geq c(uv)\) for every edge \(uv\in E(G)\text{.}\)Proof.
Let \(A\) be the incidence matrix of \(G\) and assume that it is \(n\times m\text{.}\) Let \(c\) be the vector where the \(i\)th entry is equal to the weight of the \(i\)th edge of \(G\text{.}\) The problem of finding the maximum weight matching can be expressed as
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq 1\\
\amp \amp x\geq0
\end{align*}
where \(1\) denotes the all ones vector. The dual is
\begin{align*}
\text{min } \amp \amp 1^Ty\\
\text{subject to } \amp \amp A^Ty\geq c^T\\
\amp \amp y\geq0
\end{align*}
Clearly both of these LPs are feasible. For example, the zero vector is feasible for the primal and any vector in which all entries are larger than the maximum value of \(c\) is feasible for the dual. So, Lemma 6.2.5 implies that the optima of both problems are attained by integer vectors. It is clear that the optimal vector for the primal corresponds to a matching of maximum weight whereas the optimal vector for the dual corresponds to a function \(f\) as in the statement of the theorem.
To close this section, we remark that totally unimodular matrices can also be used to reduce the Max-Flow problem (Problem 3.6.2) to linear programming; see Exercise 11.
Here is a YouTube video related to this section:
