From Matrix Entries to a Bipartite Graph
A matrix records both which row-column pairs are allowed and how much weight each pair carries. For questions about matchings, the first information is captured by a graph: retain an edge exactly when the corresponding entry is positive. When all row and column sums are one, the weights impose a strong constraint on this graph. We will show that every set of row vertices has at least as many neighboring column vertices, so Hall’s theorem guarantees a perfect matching.
Let \(A=(a_{ij})\) be an \(n\times n\) matrix with \(n\ge1\) and \(a_{ij}\ge0\) for all \(i,j\). We use row labels \(r_1,\dots,r_n\) and column labels \(c_1,\dots,c_n\), keeping these two sets disjoint even when the indices agree.
The graph remembers only which entries are zero and which are positive. It does not record the sizes of the positive entries. For \(X\subseteq R\), write \(N(X)\subseteq C\) for the set of column vertices adjacent to at least one vertex in \(X\). Equivalently, \(c_j\in N(X)\) precisely when \(a_{ij}>0\) for some \(r_i\in X\).
A matching is a set of edges with no shared endpoints. A perfect matching in \(G_A\) is a matching that covers every row vertex and every column vertex. Hall’s theorem, established in the earlier material on Hall’s theorem, states that a finite bipartite graph with parts \(R,C\) has a matching covering \(R\) if and only if \(|N(X)|\ge |X|\) for every \(X\subseteq R\). Since \(|R|=|C|=n\), a matching covering \(R\) in \(G_A\) also covers all of \(C\), and is therefore perfect.
Why the Row and Column Sums Enforce Hall’s Condition
Proof. Fix \(X\subseteq R\). The row sum of each \(r_i\in X\) is one, so summing those row sums gives \(|X|=\sum_{r_i\in X}\sum_{j=1}^n a_{ij}\). If \(c_j\notin N(X)\), no row vertex in \(X\) is adjacent to \(c_j\). By the definition of the support graph, \(a_{ij}=0\) for every \(r_i\in X\) and such a column \(c_j\). Therefore the sum over all columns can be restricted to \(N(X)\), giving the displayed equality. For each \(c_j\in N(X)\), nonnegativity and the column sum condition give \(\sum_{r_i\in X}a_{ij}\le\sum_{i=1}^n a_{ij}=1\). Adding this inequality over the \(|N(X)|\) columns yields \(\sum_{c_j\in N(X)}\sum_{r_i\in X}a_{ij}\le |N(X)|\). This includes \(X=\varnothing\): both sides of the equality are zero and the inequality reads \(0\le0\). \(\square\)
Proof. Let \(A\) be doubly stochastic and \(G_A\) its support bipartite graph with parts \(R,C\). For every subset \(X\subseteq R\), the lemma gives \(|X|\le |N(X)|\), so \(G_A\) satisfies Hall’s condition. By Hall’s theorem, there is a matching covering \(R\). It contains \(n\) edges because \(|R|=n\), and each edge in a matching uses a different column vertex. Since \(|C|=n\), those \(n\) distinct column vertices are all of \(C\). The matching is therefore perfect. \(\square\)
The argument is a translation: the row sums provide a total weight of \(|X|\) leaving the chosen rows, and all of that weight must reach columns in \(N(X)\). Each such column can receive at most one unit in total, by its column sum. Consequently, at least \(|X|\) neighboring columns are needed. The weights certify the inequality; Hall’s theorem turns that inequality into a matching.
Worked Examples
Worked Example: A Sparse Support Graph
Consider $$ A=\begin{pmatrix} \frac12&\frac12&0\\ 0&\frac12&\frac12\\ \frac12&0&\frac12 \end{pmatrix}. $$ The row sums are \(\frac12+\frac12+0=1\), \(0+\frac12+\frac12=1\), and \(\frac12+0+\frac12=1\). The column sums are \(\frac12+0+\frac12=1\), \(\frac12+\frac12+0=1\), and \(0+\frac12+\frac12=1\). Thus \(A\) is doubly stochastic.
Its support graph has \(R=\{r_1,r_2,r_3\}\), \(C=\{c_1,c_2,c_3\}\), and \(E(G_A)=\{r_1c_1,r_1c_2,r_2c_2,r_2c_3,r_3c_1,r_3c_3\}\). The positive entry \(a_{ij}=\frac12\) corresponds to each listed edge; the other three entries are zero and give no edges.
One perfect matching is \(\{r_1c_2,r_2c_3,r_3c_1\}\). These edges are in the listed edge set, use distinct rows and columns, and cover all six vertices. Their matrix entries are \(a_{12}=\frac12\), \(a_{23}=\frac12\), and \(a_{31}=\frac12\), each strictly positive. As a check, the selected rows are \(r_1,r_2,r_3\) exactly once each, and the selected columns are \(c_2,c_3,c_1\) exactly once each.
Worked Example: A Tight Set of Rows
Consider $$ A=\begin{pmatrix} 1&0&0\\ 0&\frac13&\frac23\\ 0&\frac23&\frac13 \end{pmatrix}. $$ The row sums are \(1+0+0=1\), \(0+\frac13+\frac23=1\), and \(0+\frac23+\frac13=1\). The column sums are \(1+0+0=1\), \(0+\frac13+\frac23=1\), and \(0+\frac23+\frac13=1\). Hence the matrix is doubly stochastic.
Here \(R=\{r_1,r_2,r_3\}\), \(C=\{c_1,c_2,c_3\}\), and \(E(G_A)=\{r_1c_1,r_2c_2,r_2c_3,r_3c_2,r_3c_3\}\). Take \(X=\{r_2,r_3\}\). Its neighborhood is \(N(X)=\{c_2,c_3\}\), so \(|X|=2=|N(X)|\). The row weight from \(X\) is \(1+1=2\). It is all located in columns \(c_2,c_3\): the contributions to \(c_2\) total \(\frac13+\frac23=1\), and those to \(c_3\) total \(\frac23+\frac13=1\). Together these columns hold \(1+1=2\), exactly the weight from \(X\).
The matching \(\{r_1c_1,r_2c_2,r_3c_3\}\) is perfect: its entries are \(1,\frac13,\frac13\), all positive, and every row and column occurs once. The equality for this particular \(X\) illustrates why the Hall inequality may be tight rather than strict.
Worked Example: All Entries Positive
Let $$ A=\begin{pmatrix} \frac12&\frac13&\frac16\\ \frac13&\frac13&\frac13\\ \frac16&\frac13&\frac12 \end{pmatrix}. $$ The row sums are \(\frac12+\frac13+\frac16=1\), \(\frac13+\frac13+\frac13=1\), and \(\frac16+\frac13+\frac12=1\). The column sums are \(\frac12+\frac13+\frac16=1\), \(\frac13+\frac13+\frac13=1\), and \(\frac16+\frac13+\frac12=1\). Every entry is strictly positive, so the support graph has \(R=\{r_1,r_2,r_3\}\), \(C=\{c_1,c_2,c_3\}\), and \(E(G_A)=\{r_ic_j:1\le i\le3,\ 1\le j\le3\}\).
For any nonempty \(X\subseteq R\), every column is adjacent to each row in \(X\), so \(N(X)=C\) and \(|N(X)|=3\ge|X|\). For \(X=\varnothing\), both cardinalities are zero. In particular, the edges \(\{r_1c_1,r_2c_2,r_3c_3\}\) form a perfect matching. The corresponding entries are \(\frac12,\frac13,\frac12\), each positive. The row and column indices each occur once, which directly checks that this is a matching covering both parts.
What the Support Graph Does—and Does Not—Tell Us
The conclusion depends on both sets of sum conditions. The row sums alone do not force Hall’s condition. For example, take \(B=\begin{pmatrix}1&0\\1&0\end{pmatrix}\). Both row sums equal one, but the column sums are \(1+1=2\) and \(0+0=0\), so \(B\) is not doubly stochastic. Its support graph has \(R=\{r_1,r_2\}\), \(C=\{c_1,c_2\}\), and \(E=\{r_1c_1,r_2c_1\}\). For \(X=\{r_1,r_2\}\), \(N(X)=\{c_1\}\), giving \(|X|=2>|N(X)|=1\). No matching can cover both row vertices.
A common mistake is to include zero entries as edges. In the example \(B\), incorrectly adding \(r_1c_2\) and \(r_2c_2\) would make the graph appear complete bipartite and would hide the Hall obstruction. The support graph uses the strict test \(a_{ij}>0\), not \(a_{ij}\ge0\); a zero contributes no edge. Conversely, every positive entry must be included, regardless of how small it is.
Another distinction matters: a perfect matching in the support graph means that the selected matrix entries are positive and occupy distinct rows and columns. The matching conclusion uses only the zero pattern, while the proof that Hall’s condition holds uses the actual values through the row and column sums. This makes the support graph a useful bridge from numerical constraints to a discrete existence result.
Check Your Understanding
Use the definition of support and the Hall condition to answer the following.
- For \(A=\begin{pmatrix}\frac12&0\\\frac12&1\end{pmatrix}\), list the support graph’s edges and determine whether the matrix is doubly stochastic.
- Explain why, for \(X\subseteq R\), every entry in a column outside \(N(X)\) is zero in all rows belonging to \(X\).
- In the second worked example, find \(N(\{r_1,r_2\})\) and check the Hall inequality.
- Give a nonnegative matrix whose row sums are one but whose support graph fails Hall’s condition.
- Why does a matching covering all row vertices also cover all column vertices when the matrix is square?