Kvant Math Problem 296

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m57s
Source on kvant.digital

Problem

In the table $n\times n$, $n^2$ numbers are written, the sum of which is non-negative. Prove that it is possible to rearrange the columns of the table so that the sum of $n$ numbers along the diagonal running from the bottom-left corner to the top-right corner is non-negative.

A. Tupanov

Exploration

Let the rows be numbered from top to bottom by $1,\dots,n$, and let $a_{ij}$ be the entry in row $i$, column $j$.

After a permutation $\sigma$ of the columns, the diagonal from the bottom-left corner to the top-right corner consists of the entries

$$a_{1,\sigma(n)},\ a_{2,\sigma(n-1)},\ \dots,\ a_{n,\sigma(1)}.$$

Equivalently, if we write $\tau(i)=\sigma(n+1-i)$, then the diagonal sum is

$$D(\tau)=\sum_{i=1}^{n} a_{i,\tau(i)},$$

where $\tau$ is an arbitrary permutation of ${1,\dots,n}$.

Thus the problem becomes: given an $n\times n$ matrix whose total sum of entries is non-negative, show that some permutation diagonal has non-negative sum.

For $n=2$, the two permutation diagonals have sums

$$a_{11}+a_{22}, \qquad a_{12}+a_{21}.$$

Their sum equals the total sum of the matrix. If the total sum is non-negative, at least one of these two diagonal sums is non-negative.

For $n=3$, there are six permutation diagonals. Each entry appears in exactly two of them. Hence the sum of all six diagonal sums equals twice the total sum of the matrix. If the total sum is non-negative, the average diagonal sum is non-negative, so one diagonal sum is non-negative.

This counting argument looks promising. For general $n$, there are $n!$ permutation diagonals. Fix an entry $a_{ij}$. The number of permutations $\tau$ with $\tau(i)=j$ is $(n-1)!$. Therefore each entry contributes exactly $(n-1)!$ times to the sum of all permutation diagonal sums. Hence

$$\sum_{\tau} D(\tau) = (n-1)!\sum_{i,j} a_{ij}.$$

Since the total sum is non-negative, the average of the numbers $D(\tau)$ is non-negative. Therefore at least one $D(\tau)$ is non-negative.

The only point requiring care is the identification between column permutations and permutation diagonals. Every permutation diagonal arises from a suitable column permutation, and conversely.

Problem Understanding

We are given an $n\times n$ table whose total sum of all $n^2$ entries is non-negative. We may permute the columns arbitrarily. We must prove that there exists a column permutation for which the sum of the entries on the diagonal running from the bottom-left corner to the top-right corner is non-negative.

This is a Type B problem, a pure proof.

The core difficulty is to relate all possible column permutations to a family of diagonal sums and then exploit the condition on the total sum of the table.

Proof Architecture

Define, for every permutation $\tau$ of ${1,\dots,n}$, the permutation diagonal sum

$$D(\tau)=\sum_{i=1}^{n} a_{i,\tau(i)}.$$

Every such sum corresponds to the anti-diagonal obtained after a suitable permutation of the columns, and every column permutation produces one such sum.

The sum of all numbers $D(\tau)$ over all $n!$ permutations equals

$$(n-1)!\sum_{i,j} a_{ij},$$

because each entry $a_{ij}$ appears in exactly $(n-1)!$ permutation diagonals.

Since the total sum of the matrix is non-negative, the average value of $D(\tau)$ over all permutations is non-negative.

A collection of real numbers with non-negative average must contain at least one non-negative member.

The most delicate point is the counting that each entry occurs in exactly $(n-1)!$ permutation diagonals.

Solution

Let the entries of the table be $a_{ij}$, where $i$ denotes the row and $j$ the column.

For a permutation $\tau$ of the set ${1,\dots,n}$, define

$$D(\tau)=\sum_{i=1}^{n} a_{i,\tau(i)}.$$

First we show that the numbers $D(\tau)$ are exactly the sums that can appear on the diagonal running from the bottom-left corner to the top-right corner after a permutation of the columns.

Suppose the columns are rearranged by a permutation $\sigma$. In the new table, the entry in row $i$ and column $k$ is $a_{i,\sigma(k)}$. The anti-diagonal consists of the positions

$$(1,n),(2,n-1),\dots,(n,1).$$

Its sum is

$$\sum_{i=1}^{n} a_{i,\sigma(n+1-i)}.$$

If we define

$$\tau(i)=\sigma(n+1-i),$$

then $\tau$ is a permutation and the anti-diagonal sum becomes

$$D(\tau).$$

Conversely, given any permutation $\tau$, define

$$\sigma(k)=\tau(n+1-k).$$

Then $\sigma$ is a permutation of the columns, and the corresponding anti-diagonal sum is exactly $D(\tau)$.

Thus it suffices to prove that there exists a permutation $\tau$ with $D(\tau)\ge 0$.

Consider the sum of $D(\tau)$ over all $n!$ permutations:

$$S=\sum_{\tau} D(\tau).$$

Interchanging the order of summation gives

$$S = \sum_{\tau}\sum_{i=1}^{n} a_{i,\tau(i)} = \sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij},N_{ij},$$

where $N_{ij}$ is the number of permutations $\tau$ satisfying

$$\tau(i)=j.$$

Once the value of $\tau(i)$ is fixed to be $j$, the remaining $n-1$ elements may be permuted arbitrarily. Hence

$$N_{ij}=(n-1)!.$$

Therefore

$$S = (n-1)!\sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}.$$

The total sum of all entries of the table is non-negative, so

$$S\ge 0.$$

There are $n!$ numbers $D(\tau)$. Their sum is non-negative, hence their average is non-negative. If every $D(\tau)$ were negative, their sum would be negative. Consequently at least one permutation $\tau$ satisfies

$$D(\tau)\ge 0.$$

By the correspondence established above, there exists a permutation of the columns for which the sum of the entries on the diagonal from the bottom-left corner to the top-right corner is non-negative.

This completes the proof.

∎

Verification of Key Steps

The correspondence between column permutations and permutation diagonals must be checked in both directions. After applying a column permutation $\sigma$, the anti-diagonal uses the entries $a_{i,\sigma(n+1-i)}$. Setting $\tau(i)=\sigma(n+1-i)$ converts this sum into $D(\tau)$. Conversely, from a prescribed permutation $\tau$, defining $\sigma(k)=\tau(n+1-k)$ reconstructs a column permutation producing that diagonal. No permutation diagonal is omitted.

For the counting argument, fix an entry $a_{ij}$. The condition $\tau(i)=j$ determines the image of one element. The remaining $n-1$ domain elements must be mapped bijectively onto the remaining $n-1$ values. There are exactly $(n-1)!$ such bijections. A careless count could mistakenly use $n!$, which would count all permutations rather than those containing the specified entry.

The final averaging step uses only the elementary fact that a finite collection of real numbers cannot all be negative if their sum is non-negative. This is the precise reason that some diagonal sum $D(\tau)$ must be non-negative.

Alternative Approaches

The argument may be phrased probabilistically. Choose a permutation $\tau$ uniformly at random. Then

$$D(\tau)=\sum_{i=1}^{n} a_{i,\tau(i)}.$$

For each fixed pair $(i,j)$,

$$\Pr(\tau(i)=j)=\frac1n.$$

Hence

$$\mathbb E[D(\tau)] = \sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}\Pr(\tau(i)=j) = \frac1n\sum_{i,j} a_{ij}.$$

The total sum of the matrix is non-negative, so $\mathbb E[D(\tau)]\ge0$. A random variable cannot have non-negative expectation if all its values are negative. Thus some permutation satisfies $D(\tau)\ge0$.

The counting proof is preferable because it avoids probabilistic language and directly explains why every entry contributes equally to the total of all permutation diagonal sums.