From a Matrix to a Selection Problem
A positive diagonal in a matrix is a selection of one positive entry from each row, with no two selected entries in the same column. The selection need not lie on the matrix’s main diagonal: the columns can be rearranged to put the selected entries there. For a doubly stochastic matrix, a graph records exactly which row-column choices are available. Hall’s theorem then explains why a complete selection must exist, while a direct check of the graph helps us find one.
Throughout, the matrices are square and have nonnegative real entries. A matrix is doubly stochastic if every row sum and every column sum equals \(1\). The support graph of an \(n\times n\) matrix \(A=(a_{ij})\) is a bipartite simple graph with row vertices \(r_1,\ldots,r_n\), column vertices \(c_1,\ldots,c_n\), and an edge \(r_i c_j\) exactly when \(a_{ij}>0\). Thus zero entries give no edge, and positive entries give edges.
For a set \(S\) of row vertices, write \(N(S)\) for the set of column vertices adjacent to at least one row in \(S\). A perfect matching in a bipartite graph is a set of edges that meets each vertex exactly once. In a support graph, such a matching is precisely a positive diagonal: each matched edge specifies a positive matrix entry, and no row or column is used twice.
Why Doubly Stochasticity Gives Hall’s Condition
Proof. The entries in the rows indexed by \(S\) sum to \(|S|\), since each of those rows sums to \(1\). Every positive entry in those rows lies in a column indexed by \(N(S)\). The total of all entries in those columns, across every row, is \(|N(S)|\), since each column sums to \(1\). All entries are nonnegative, so the sum contributed by the rows in \(S\) cannot exceed the sum of all entries in those columns. Hence \(|S|\leq |N(S)|\). This also holds for \(S=\varnothing\), since both sides are zero. \(\square\)
Hall’s theorem states that a finite bipartite graph with row side \(R\) has a matching meeting every vertex of \(R\) if and only if \(|N(S)|\geq |S|\) for every \(S\subseteq R\). In particular, when the two sides have the same size, such a matching is perfect. Hall’s theorem and its proof were established in the earlier material on matchings. The proposition verifies its condition for every support graph of a doubly stochastic matrix. It follows that such a matrix has a positive diagonal.
Proof. Construct its support graph. The proposition shows that every set of row vertices has at least as many neighbors as vertices. By Hall’s theorem, there is a matching meeting every row. There are equally many row and column vertices, so this matching also meets every column. Each edge of the matching corresponds, by the definition of the support graph, to a positive matrix entry. Those edges therefore specify a positive diagonal. \(\square\)
A Practical Check for Small Matrices
For an explicit small matrix, first check its row and column sums. Then record each row’s positive column choices as its neighbors in the support graph. To test Hall’s condition directly, compare \(|S|\) with \(|N(S)|\) for row subsets. For a doubly stochastic matrix the proposition already proves the condition, but listing the neighborhoods is useful both for understanding the structure and for finding a particular matching.
To construct the diagonal, choose a positive column for each row without reusing any column. A short table can keep track of the chosen edge and the columns already used. If a choice leaves a later row with no available column, backtrack and try a different choice. This is a finite search through possible assignments; a successful assignment is exactly a perfect matching. Hall’s theorem guarantees that some successful assignment exists for a doubly stochastic matrix.
Worked Example: A Three-Row Support Cycle
Consider
Every row sums to \(1\): the sums are \(\frac12+\frac12+0=1\), \(0+\frac12+\frac12=1\), and \(\frac12+0+\frac12=1\). The column sums are also \(1\): column 1 has \(\frac12+0+\frac12=1\), column 2 has \(\frac12+\frac12+0=1\), and column 3 has \(0+\frac12+\frac12=1\).
The support graph has row vertices \(\{r_1,r_2,r_3\}\), column vertices \(\{c_1,c_2,c_3\}\), and edge set \(\{r_1c_1,r_1c_2,r_2c_2,r_2c_3,r_3c_1,r_3c_3\}\). The individual neighborhoods are \(N(\{r_1\})=\{c_1,c_2\}\), \(N(\{r_2\})=\{c_2,c_3\}\), and \(N(\{r_3\})=\{c_1,c_3\}\). Every singleton therefore has two neighbors. Each of the three two-row subsets has all three columns as neighbors, and the full row set also has all three columns. Thus every nonempty row subset satisfies Hall’s condition.
Here is a distinct-column selection, with the used columns recorded after each choice:
| Row processed | Available positive columns | Chosen edge | Columns used |
|---|---|---|---|
| \(r_1\) | \(c_1,c_2\) | \(r_1c_1\) | \(c_1\) |
| \(r_2\) | \(c_2,c_3\) | \(r_2c_2\) | \(c_1,c_2\) |
| \(r_3\) | \(c_1,c_3\) | \(r_3c_3\) | \(c_1,c_2,c_3\) |
The selected entries are \(a_{11}=\frac12\), \(a_{22}=\frac12\), and \(a_{33}=\frac12\). Each is positive and the chosen columns are distinct, so the main diagonal is a positive diagonal. The selected entries themselves sum to \(\frac12+\frac12+\frac12=\frac32\); no requirement says that selected entries must sum to \(1\).
Check: the matching edges \(r_1c_1,r_2c_2,r_3c_3\) meet all three row vertices and all three column vertices exactly once. This verifies directly that the assignment is a perfect matching and that its three corresponding entries are positive.
When the Main Diagonal Does Not Work
Worked Example: A Positive Diagonal Away from the Main One
Let
The row sums are \(\frac13+\frac23=1\), \(\frac13+\frac23=1\), \(\frac13+\frac23=1\), and \(\frac23+\frac13=1\). The column sums are also \(1\): column 1 has \(\frac13+\frac23=1\); column 2 has \(\frac23+\frac13=1\); column 3 has \(\frac23+\frac13=1\); and column 4 has \(\frac23+\frac13=1\). Thus \(B\) is doubly stochastic.
Its support graph has row vertices \(\{r_1,r_2,r_3,r_4\}\), column vertices \(\{c_1,c_2,c_3,c_4\}\), and edge set \(\{r_1c_1,r_1c_2,r_2c_2,r_2c_3,r_3c_3,r_3c_4,r_4c_1,r_4c_4\}\). Each singleton row has two neighbors. Two consecutive rows in the cyclic order have three neighbors; two opposite rows have four. Every three-row subset has all four columns as neighbors, as does the full set. These counts verify \(|N(S)|\geq |S|\) for every row subset.
We can choose the second available column in each row successively, wrapping from \(c_4\) back to \(c_1\):
| Row processed | Available positive columns | Chosen edge | Columns used |
|---|---|---|---|
| \(r_1\) | \(c_1,c_2\) | \(r_1c_2\) | \(c_2\) |
| \(r_2\) | \(c_2,c_3\) | \(r_2c_3\) | \(c_2,c_3\) |
| \(r_3\) | \(c_3,c_4\) | \(r_3c_4\) | \(c_2,c_3,c_4\) |
| \(r_4\) | \(c_1,c_4\) | \(r_4c_1\) | \(c_1,c_2,c_3,c_4\) |
The corresponding entries are \(b_{12}=\frac23\), \(b_{23}=\frac23\), \(b_{34}=\frac23\), and \(b_{41}=\frac23\). All are positive, and the selected columns \(c_2,c_3,c_4,c_1\) are all different. This is a positive diagonal determined by the permutation \(\sigma(1)=2,\sigma(2)=3,\sigma(3)=4,\sigma(4)=1\), even though the choice is not the main diagonal.
Check: the four matching edges meet each row and column once. Their entries are all \(\frac23>0\), confirming the selection by direct substitution into the matrix.
Zeros on the Main Diagonal Are Not an Obstruction
Worked Example: Every Main-Diagonal Entry Is Zero
Consider
Each row contains two entries equal to \(\frac12\) and one zero, so each row sum is \(\frac12+\frac12+0=1\). Each column also contains two entries equal to \(\frac12\) and one zero, so each column sum is \(1\). The matrix is doubly stochastic.
The support graph has row vertices \(\{r_1,r_2,r_3\}\), column vertices \(\{c_1,c_2,c_3\}\), and edge set \(\{r_1c_2,r_1c_3,r_2c_1,r_2c_3,r_3c_1,r_3c_2\}\). Each singleton row has two neighbors. Every pair of rows has all three columns as neighbors, and all three rows together have all three columns. Hence the neighborhood sizes are at least the corresponding subset sizes.
Select entries in order, keeping columns distinct:
| Row processed | Available positive columns | Chosen edge | Columns used |
|---|---|---|---|
| \(r_1\) | \(c_2,c_3\) | \(r_1c_2\) | \(c_2\) |
| \(r_2\) | \(c_1,c_3\) | \(r_2c_3\) | \(c_2,c_3\) |
| \(r_3\) | \(c_1,c_2\) | \(r_3c_1\) | \(c_1,c_2,c_3\) |
The selected entries are \(c_{12}=\frac12\), \(c_{23}=\frac12\), and \(c_{31}=\frac12\), so the permutation is \(\sigma(1)=2,\sigma(2)=3,\sigma(3)=1\). Each selected entry is positive. By contrast, the main diagonal consists of \(c_{11}=c_{22}=c_{33}=0\).
Check: the chosen columns are \(2,3,1\), which are exactly the three columns, each used once. This is a perfect matching in the support graph despite every main-diagonal entry being zero.
Common Pitfalls and a Reliable Workflow
A frequent mistake is to treat “positive diagonal” as meaning that all entries \(a_{11},a_{22},\ldots,a_{nn}\) must be positive. That is only the main diagonal. In the last example, testing the main diagonal gives \(0,0,0\), which does not give a positive diagonal there; the valid selection instead uses \(a_{12},a_{23},a_{31}\). The definition allows a permutation of columns.
Another error is to check only that each row has at least one positive entry. That condition alone does not guarantee distinct columns: several rows might have all their positive entries in the same small set of columns. Hall’s condition tests every subset of rows against its combined neighborhood, ensuring there are enough distinct columns available. For doubly stochastic matrices, the row and column sums prove this condition; for a concrete selection, still record the columns used so that no column is accidentally repeated.
For a small matrix, a reliable workflow is:
- Check that all entries are nonnegative and that every row and column sums to \(1\).
- Draw or list the support graph, putting an edge exactly at each positive entry.
- For row subsets of interest, list their combined neighborhoods and compare the sizes.
- Choose one incident edge per row while avoiding previously used columns; backtrack if a choice blocks a later row.
- Verify the final selection by checking every chosen entry is positive and every row and column occurs exactly once.
The support graph is useful because it separates two questions: whether a selection is guaranteed to exist, and which particular selection to use. Doubly stochasticity and Hall’s theorem answer the first question. The explicit neighborhood lists and a careful assignment answer the second.
Check Your Understanding
Use support graphs and distinct-column selections to answer these questions.
- For the matrix with rows \((\frac12,\frac12,0)\), \((0,\frac12,\frac12)\), and \((\frac12,0,\frac12)\), list the neighborhood of each pair of rows.
- Explain why the positive entries \(a_{12},a_{23},a_{31}\) form a positive diagonal in a \(3\times3\) matrix.
- In a support graph, what does the inequality \(|N(S)|\geq|S|\) say about a set \(S\) of rows?
- Give a reason that checking each row separately for at least one positive entry is not a substitute for checking Hall’s condition.
- For the displayed \(4\times4\) matrix \(B\), write down the permutation corresponding to the selected entries \(b_{12},b_{23},b_{34},b_{41}\).