Positive Diagonals in Doubly Stochastic Matrices

From Matrix Entries to a Matching

A doubly stochastic matrix distributes one unit of weight across each row and one unit across each column. Although some entries may be zero, the row and column sums together prevent any collection of rows from placing all its positive weight into too few columns. That constraint is precisely Hall’s condition in the matrix’s support graph. Hall’s theorem then gives a choice of positive entries using every row and every column exactly once.

Throughout, let \(A=(a_{ij})\) be an \(n\times n\) matrix with \(n\ge 1\). A permutation \(\sigma\) of \(\{1,\ldots,n\}\) selects one entry \(a_{i,\sigma(i)}\) from each row, with every column selected once. The selected entries form a positive permutation diagonal if \(a_{i,\sigma(i)}>0\) for every \(i\). The permutation need not be the identity, so this diagonal need not be the matrix’s main diagonal.

For a set \(S\) of row vertices, write \(N(S)\) for the set of column vertices adjacent to at least one vertex in \(S\). Hall’s condition is \(|N(S)|\ge |S|\) for every set \(S\) of row vertices. A matching is a set of edges with no shared endpoints; it is perfect if it covers every vertex.

Proof. Suppose first that a permutation \(\sigma\) gives a positive permutation diagonal. By the definition of the support graph, \(a_{i,\sigma(i)}>0\) means that \(r_ic_{\sigma(i)}\) is an edge. The edges \(r_ic_{\sigma(i)}\), for \(1\le i\le n\), share no row vertices, and the fact that \(\sigma\) is a permutation means they share no column vertices either. They cover all \(n\) row vertices and all \(n\) column vertices, so they form a perfect matching. Conversely, a perfect matching has one edge incident with each row vertex and one with each column vertex. Write the matched column for row \(r_i\) as \(c_{\sigma(i)}\). Since every column is matched exactly once, \(\sigma\) is a permutation. Each matched edge belongs to the support graph, so \(a_{i,\sigma(i)}>0\) for every \(i\). These entries form a positive permutation diagonal. \(\square\)

Why Hall’s Condition Must Hold

The key calculation sums the entries in a chosen collection of rows, then bounds that weight using the columns they can reach. Entries outside the neighborhood are zero by the definition of the support graph. Each column in the neighborhood can contribute at most its full column sum, which is one.

Proof. Let \(S\) be any set of row indices, and let \(N(S)\) denote the column indices \(j\) for which \(a_{ij}>0\) for at least one \(i\in S\). By the row sums, the total weight in the rows indexed by \(S\) is \(|S|\). If \(j\notin N(S)\), then \(a_{ij}=0\) for every \(i\in S\). Therefore

The inequality holds because all entries are nonnegative, so restricting a column sum to rows in \(S\) cannot increase it. The last equality uses the column sums, each of which is one. Thus Hall’s condition holds for every set of row vertices, including the empty set, for which both sides equal zero. By Hall’s theorem, a finite bipartite graph has a matching covering its row side if every subset of that side has at least as many neighbors as vertices. The support graph therefore has a matching covering all \(n\) rows. It also covers all \(n\) columns: its \(n\) edges have distinct column endpoints, and there are exactly \(n\) columns. It is a perfect matching. By the lemma, this perfect matching gives a positive permutation diagonal in \(A\). \(\square\)

Hall’s theorem is used here in its standard form; its proof is established in the earlier material on Hall’s theorem. The matrix-specific work is the displayed inequality: it verifies Hall’s hypothesis directly from the row and column sums. No assumption that the entries are strictly positive is needed; zeros simply mean that the corresponding edges are absent.

Worked Examples

Common Pitfalls and Why the Argument Matters

Counting edges is not counting neighbors. Hall’s condition compares the number of rows in \(S\) with the number of distinct columns adjacent to \(S\), not with the number of support edges leaving \(S\). In the first example, take \(S=\{r_1,r_2\}\). Its incident support edges are \(r_1c_1,r_1c_2,r_2c_2,r_2c_3\): there are four edges, but only three distinct neighboring columns. The correct Hall check is \(|N(S)|=3\ge2=|S|\), not a comparison involving four neighbors. In the theorem’s proof, the relevant quantity is also weight, not the count of positive entries: a column’s total available weight is one, regardless of how many positive entries it contains.

Do not reverse the inequality. The row sums give total weight \(|S|\), while the columns in \(N(S)\) can supply at most \(|N(S)|\). Therefore the conclusion is \(|S|\le |N(S)|\). An argument that says the rows in \(S\) can reach fewer columns than rows has not established Hall’s condition.

The result links a numerical constraint to a discrete selection. It is useful whenever matrix entries represent allowed assignments with weights: the positive entries specify which assignments are available, while the doubly stochastic sums guarantee a one-to-one selection among them. The theorem asserts existence of that selection; it does not assert uniqueness, and it does not say that every positive entry can belong to a positive permutation diagonal.