Kvant Math Problem 15

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m51s
Source on kvant.digital

Problem

A square table of size $n\times n$ is filled with non-negative numbers such that the sum of the numbers in each row and the sum of the numbers in each column are both equal to 1. Prove that it is possible to select $n$ positive numbers from the table, no two of which are in the same row or the same column.

Exploration

Consider small instances to develop intuition. For $n=2$, let the table be

$$\begin{pmatrix} a & b \ c & d \end{pmatrix}, \quad a,b,c,d\ge 0, \quad a+b=c+d=1, \quad a+c=b+d=1.$$

Solving these equations, one sees that $a+d = b+c =1$, so choosing $a$ and $d$ yields two positive entries in different rows and columns if all entries are positive. Even if some entries are zero, the non-negativity conditions force at least one positive per row and column, making it possible to select a transversal of positive entries.

For $n=3$, the table

$$\begin{pmatrix} 1/2 & 1/2 & 0 \ 1/2 & 0 & 1/2 \ 0 & 1/2 & 1/2 \end{pmatrix}$$

illustrates that one can choose one positive number per row and column. Attempting a configuration with many zeros indicates that as long as row and column sums are 1, a positive number exists in every row and column. The crucial step is proving the existence of such a choice for general $n$, not just constructing it for specific examples.

The problem reduces to a combinatorial statement about selecting one element from each row without conflict, which suggests a connection to matchings in bipartite graphs, specifically to Hall's Marriage Theorem.

The key difficulty lies in guaranteeing that, even with zeros, one can select $n$ positive entries with no two in the same row or column. This step is most likely to hide subtle counterexamples if handled non-rigorously.

Problem Understanding

The problem asks to prove that in an $n\times n$ matrix with non-negative entries and row and column sums equal to 1, it is possible to choose $n$ positive entries such that no two lie in the same row or column. This is a Type B problem, as it is a pure existence proof. The core difficulty is ensuring the selection is possible despite the presence of zeros. Intuitively, the condition that all row and column sums are 1 forces enough positive entries to construct such a selection, because zeros alone cannot dominate any row or column.

Proof Architecture

Lemma 1: In each row, there exists at least one positive entry. This is true because the sum of the row is 1 and all entries are non-negative.

Lemma 2: For any subset $R$ of $k$ rows, the union of columns containing positive entries in these rows has size at least $k$. This is true because if it were smaller, the total sum in these rows would be strictly less than $k$, contradicting the sum condition.

Lemma 3: Hall's Marriage Theorem guarantees that a perfect matching exists in a bipartite graph if and only if every subset of one part has at least as many neighbors as its size. Lemma 2 establishes this condition for the graph formed by rows and columns connected by positive entries.

The hardest step is Lemma 2, as a careless argument could overlook configurations where zeros are arranged to reduce the neighborhood size. Ensuring the inequality holds rigorously is essential.

Solution

Construct a bipartite graph $G$ with vertex sets $R$ and $C$ corresponding to the rows and columns of the table, respectively. Connect a row $r\in R$ to a column $c\in C$ if the entry in row $r$ and column $c$ is positive.

Lemma 1: Every row contains at least one positive entry. Since each row sums to 1 and all entries are non-negative, if a row contained only zeros, its sum would be 0, contradicting the hypothesis. Similarly, every column contains at least one positive entry.

Lemma 2: Let $S\subseteq R$ be any set of $k$ rows. Denote by $N(S)\subseteq C$ the set of columns that contain a positive entry in at least one row from $S$. Suppose $|N(S)|<k$. Then the sum of all entries in rows $S$ is at most $|N(S)|<k$, since entries outside $N(S)$ are zero and each column sum is at most 1. This contradicts the fact that the sum of the entries in $k$ rows is exactly $k$, because each row sums to 1. Therefore $|N(S)|\ge k$ for every $S\subseteq R$.

Applying Hall's Marriage Theorem to the bipartite graph $G$, the condition of Lemma 2 guarantees the existence of a perfect matching, that is, a set of $n$ edges such that each row and each column is incident to exactly one chosen edge. Each edge corresponds to a positive entry in the table. Selecting these entries yields $n$ positive numbers, no two in the same row or column.

This completes the proof.

∎

Verification of Key Steps

In Lemma 2, consider $S$ containing a single row. The argument requires that there is at least one positive entry, which follows from the row sum being 1. For $|S|=2$, if the union of columns with positive entries in these two rows had size 1, then the sum of the entries in these two rows could not reach 2, as the single column sum is at most 1. Testing $n=3$ examples with entries concentrated in few columns confirms that the argument correctly bounds the union size. The argument is robust to zeros scattered across the table.

In applying Hall's Theorem, verifying that the constructed bipartite graph satisfies the neighborhood condition for all subsets $S\subseteq R$ ensures that a perfect matching exists. Small $n$ examples, such as $n=2$ or $n=3$, illustrate that the matching corresponds exactly to the desired selection of positive entries.

Alternative Approaches

An alternative approach uses induction on $n$. One could select any positive entry in the first row, remove the corresponding row and column, and consider the $(n-1)\times (n-1)$ submatrix. The sum conditions still hold in the submatrix after appropriate normalization. The inductive step requires careful rescaling to preserve positivity, which complicates the argument. The Hall's Theorem approach is preferable because it handles all zeros automatically, avoids rescaling, and provides a fully combinatorial, non-iterative proof applicable to all $n$ without additional technical overhead.