1971 IMO Problems/Problem 6

Problem

Let $A = (a_{ij})(i, j = 1, 2, \cdots, n)$ be a square matrix whose elements are non-negative integers. Suppose that whenever an element $a_{ij} = 0$, the sum of the elements in the $i$th row and the $j$th column is $\geq n$. Prove that the sum of all the elements of the matrix is $\geq n^2 / 2$.


Solution 1

Take the the row or column (without loss of generality, a row) with the minimum possible sum $S$ of its elements. Let $z$ be the number of zeros in this row. We will assume $S < \frac{n}{2}$ once the other case is obvious. Clearly $S \ge n - z \Rightarrow z \ge n - S$. The total sum $T$ of all elements of the matrix is at least the number of zeros in this row multiplicated by $n - S$ (because the sum of the elements of a row and a column meeting in a zero is $\ge n$) plus the number of nonzero elements times $S$ (that is the minimum possible sum), it is,\[z(n - S) + (n - z)S.\]Note that, being $z \ge n - S$ and $n - S \ge S$, we can put $z - 1$ instead of $z$ and $n - z + 1$ instead of $n - z$ until we get $z = n - S$, what makes the sum become smaller. So we have\[T \ge (n - S)^2 + S^2 \ge 2(\frac{n - S + S}{2})^2 = \frac{n^2}{2}\]by AM - QM inequality.

The above solution was posted and copyrighted by Renan. The original thread for this problem can be found here: [1]


Solution 2

Denote $\ell_i,c_i$ the $i$th line and column and $s(\ell_i), s(c_i)$ the sum of the elements on that row. Let $M=\max_{\sigma \in S_n} | \{ 1\le i\le n| a_{i\sigma(i)}=0\} |$. For each permutation $\sigma\in S_n$, assign to it the number\[\sum\limits_{a_{i\sigma(i)=0}} \left ( s(\ell_i)+s(c_{\sigma(i)}) \right  )\]Now pick a permutation $\sigma$ such that it generates $M$ and its assigned number is minimal. Suppose wlog that $\{ 1\le i\le n| a_{i\sigma(i)}=0\}=\{1,2,..,k\}$. If $k=n$, we are done as twice the sum of all elements is\[\sum\limits_{i=1}^{n} s(\ell_i) +\sum\limits_{i=1}^{n} s(c_i)=\sum\limits_{i=1}^{n} (s(\ell_i)+s(c_{\sigma(i)}))\ge n^2\] So suppose $k<n$ and look at a $j$ such that $k+1\le j\le n$. By the maximality of $M$, $\ell_j$ can have $0$ only on the columns $\sigma(1),...,\sigma(k)$. Note that if $\ell_j$ has a $0$ on $c_{\sigma(r)}$ with $r\le k$, i.e. $a_{j\sigma(r)}=0$, by the minimality of the assigned number of $\sigma$, we have that $s(\ell_j)\ge s(\ell_r)$. However, if the column $c_{\sigma(j)}$ has a $0$ on $\ell_r$, i.e. $a_{r\sigma(j)}=0$, by the same argument we have $s(c_\sigma(j))\ge s(c_\sigma(r))$, hence $s(\ell_j)+s(c_{\sigma(j)})\ge s(r)+s(c_{\sigma(r)})\ge n$.

Suppose that $0$ appears exactly $t$ times on $\ell_j$. This means that $s(\ell_j)\ge n-t$. Suppose that the $0$s of $\ell_j$ appear on the columns $c_{\sigma(i_1)},...,c_{\sigma(i_t)}$. We have seen earlier that if $c_\sigma(j)$ has a $0$ on $i_1,..,i_t$ we have that $s(\ell_j)+s(c_{\sigma(j)})\ge n$. So suppose that it doesn't have $0$ on these lines. However, $c_{\sigma(j)}$ has $0$s only on the lines $\ell_1,..,\ell_k$ by the maximality of $M$, hence $c_{\sigma(j)}$ has at most $k-t$ zeroes, so $s(c_{\sigma(j)})\ge n-k+t$. We thus infer that\[s(\ell_j)+s(c_{\sigma(j)})\ge (n-t)+(n-k+t)=2n-k\ge n\]so $s(\ell_j)+s(c_{\sigma(j)})\ge n,\ \forall j\ge k+1$. By the hypothesis this is also true for $j\le k$ so summing over all values of $j$ we get that the sum is at least $\dfrac{n^2}{2}$.

The above solution was posted and copyrighted by Aiscrim. The original thread for this problem can be found here: [2]


Solution 3

If the main diagonal contains all zeroes, we can immediately deduce from the condition that the sum $S$ of the elements is at least $n^2/2$. This motivates us to consider the largest possible subset of elements, all zero, which are pairwise in different rows of columns - let the size of this subset be $k$. (If there is no such subset, $S\ge n^2$.)

Since the condition is invariant under the operation of switching rows or columns, we may rearrange the matrix such that these $k$ entries are on the main diagonal of the matrix, i.e. $a_{11}=a_{22}=\dots=a_{kk}=0$. Let $X=\sum_{1\le i,j\le k}a_{ij}$, $Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij}$ and $Z=\sum_{k<i,j\le n}a_{ij}$. Then applying the condition to $a_{11},\dots,a_{kk}$, we get $2X+Y\ge kn$.

If $i\le k<j$, then if $a_{ij}=a_{ji}=0$, then we may toss $a_{ii}$ out of our set and replace it with $a_{ij}$ and $a_{ji}$, to form a larger feasible set of elements, contradiction. Consequently, $a_{ij}+a_{ji}\ge 1$ for $i\le k<j$, which upon summation yields $Y\ge k(n-k)$. Finally, $Z\ge (n-k)^2$, trivially. Therefore, \[2S=2(X+Y+Z)\ge 2X+Y+Y+Z\ge kn+k(n-k)+(n-k)^2=k^2+2k(n-k)+(n-k)^2=n^2.\]

The above solution was posted and copyrighted by randomusername. The original thread for this problem can be found here: [3]


Remarks (added by pf02, March 2025)

Solutions 1 and 2 above are incorrect, and there is room for better wording in solution 3.

Solution 1 is plainly wrong, but it can be salvaged.

Solution 2 is hopelessly incorrect. An attempt to salvage it would be along the lines of Solution 3, in the context of the unnecessarily complicated setup of Solution 2.

Solution 3 is based on a very good idea, and it is easy to make the necessary improvements to make it robust.

The discussion page https://artofproblemsolving.com/community/c6h60831s1_sum_of_all_the_elements_in_the_matrix_is_at_least_n22 contains a fourth solution, but it is incomplete. If completed, it would be just a version of the corrected version of solution 1 given below.

Below I will point out the issues in the three solutions given above, and when I can, I will give the corrected or improved solutions. Then I will give some examples. The examples will show that the inequality $\sum_{i, j = 1}^n a_{ij} \ge \frac{n^2}{2}$ is optimal.

Notation: in all the discussions and proofs given below, I will denote $r_i, c_j$ the $i$th row and $j$th column respectively, and $sum(r_i), sum(c_j), \text{or}\ s(r_i), s(c_j)$ the sums of their entries.


Solution 1 analysis and correction

The error in Solution 1

I will use the notation of the solution. We chose a row or column with minimal sum of its elements (we can assume it was a row), $S$ was the sum of the elements in this row, and $z$ was the number of zeros in it.

At some point in the solution the author writes:

"Note that, being $z \ge n - S$ and $n - S \ge S$, we can put $z - 1$ instead of $z$ and $n - z + 1$ instead of $n - z$ until we get $z = n - S$"

This is wrong! If $z$ was chosen to represent a chosen quantity, we can not change its value in the middle of the proof.

We could try to make sense of the proof by saying that we replace the given matrix A by a matrix B, where the rows of B are equal to the rows of A, except for the "minimal" row we chose, in which we replace one of the zeros by a number $> 0$ (which would replace $z$ by $z - 1$). This does not work, because if we would show that the sum of the elements of $B$ is $\ge \frac{n^2}{2}$, it would not follow that the same is true for $A$.

Solution 1 corrected

As in the solution, choose a row or column such that the sum of its elements is minimal. We can assume this is a row (either notice that taking the transpose of $A$ changes neither the hypothesis, nor the conclusion; or notice that if we do the proof in the case of a row, the proof in the case of a column is analogous.) Let $S$ be the sum of the elements of this row, and $z$ be the number of zeros in this row.

For an element $a_{ij}$ of $A$, we denote $r_i, c_j$ the row and the column containing $a_{ij}$. We denote $sum(r_i), sum(c_j)$ the sum of the entries of the matrix in row $r_i$ and $c_j$ respectively.

If $S \ge \frac{n}{2}$, then each row $r_i$ has its sum of elements $sum(r_i) \ge S \ge \frac{n}{2}$, so $\sum_{i, j = 1}^n a_{ij} = \sum_{i=1}^n sum(r_i) \ge \frac{n^2}{2}$.

So, let us assume $S < \frac{n}{2}$. Let $r_i = \{a_{ij}, j = 1, \dots, n\}$ be the row we chose (now $i$ is fixed). For each $j$ consider the sum of the elements of the column $c_j$ containing $a_{ij}$. If $a_{ij} = 0$, we know that $sum(r_i) + sum(c_j) \ge n$ (by hypothesis), so $S + sum(c_j) \ge n$, so $sum(c_j) \ge n - S$. We have $z$ such columns.

If $a_{ij} \ne 0$, we know that $sum(c_j) \ge S$ because $S$ was minimal. We have $n - z$ such columns.

So, $\sum_{i, j = 1}^n a_{ij} = \sum_{j = 1}^n sum(c_j) \ge z(n - S) + (n - z)S$.

Let $S = n - z + E$. Here we split $S$ in two parts: $n - z$ represents the number of non-zeroes in $r_i$, and $E$ represents the sum of the "excess" amounts over $1$ of the non-zero entries. More explicitly, $E = \sum_{\substack{j = 1 \\ a_{ij} \ne 0}}^n (a_{ij} - 1)$. (To clarify: if all non-zero entries of $r_i$ would $= 1$, we would have $S = n - z$, and $E = 0$.) In general, $E \ge 0$.

Then, $\sum_{i, j = 1}^n a_{ij} \ge z(n - S) + (n - z)S = (n - S + E)(n - S) + (S - E)S = n^2 - 2nS + 2S^2 + nE - 2SE =$

$\frac{n^2}{2} + \frac{1}{2}\left(n^2 - 4nS + 4S^2\right) + E(n - 2S) = \frac{n^2}{2} + \frac{1}{2}(n - 2S)^2 + E(n - 2S)$.

The last term is $\ge 0$ since $E \ge 0$ and we assumed we are in the case $S < \frac{n}{2}$. It follows that $\sum_{i, j = 1}^n a_{ij} > \frac{n^2}{2}$.

Note: The strict inequality is not true in general. We obtained it assuming that $S < \frac{n}{2}$. When $S \ge \frac{n}{2}$ we have $\sum_{i, j = 1}^n a_{ij} \ge \frac{n^2}{2}$.

Note: We could have proven directly that $z(n - S) + (n - z)S = \frac{n^2}{2} + \frac{1}{2}(n - 2S)^2 + (S + z - n)(n - 2S)$ and note that the last term is the product of two non-negative factors. However, introducing $E$ gives better insight into the inequality.


Solution 2 analysis

The error in Solution 2

This solution starts by considering all the permutations $\sigma$ of $\{1, 2, \dots, n\}$. For each $\sigma$ consider the set $S_\sigma = \{i, \text{such that}\ a_{i\sigma(i)} = 0\}$, and denote $M_\sigma$ to be the number of elements in $S_\sigma$. Let $M = \text{maximum of all}\ M_\sigma$. Choose a $\sigma$ such that $M_\sigma = M$.

We can assume that $S_\sigma = \{1, 2, \dots, k\}$. (Note: this would normally need some justification, but a diligent reader can supply it.)

For given row $r_i$ and column $c_j$ define $s(r_i), s(c_j)$ the sum of the elements of $r_i$ and $c_j$, respectively.

For any permutation $\sigma$ "assign to it the number" $N_\sigma = \sum_{\substack{i\ \text{such that} \\ a_{i\sigma(i)} = 0}} (s(r_i) + s(c_{\sigma(i)}))$.

At this point, the author says:

"Now pick a permutation $\sigma$ such that it generates $M$ and its assigned number [$N_\sigma$] is minimal."

This is the first problem with this proof. It is not clear whether the author wants to choose $\sigma$ to minimize $N_\sigma$ from among the permutations for which $M_\sigma = M$, or choose a $\sigma$ to minimize $N_\sigma$ over all the possible permutations, and at the same time $M_\sigma = M$. Since the latter may be impossible, we should assume the author meant the former. (Note: it does not make much difference, we could assume that a $\sigma$ in the sense of the latter interpretation is found, since we will soon see that the proof is flawed anyway.)

Under the assumption $k < n$, take $j \ge k + 1$. The author goes on to say:

"if $r_j$ has a $0$ on $c_{\sigma(p)}$ with $p \le k$, i.e. $a_{j\sigma(p)} = 0$, by the minimality of the assigned number [$N_\sigma$] of $\sigma$, we have that $s(r_j) \ge s(r_p)$"

This is completely wrong! One flaw is that $N_\sigma$ is the sum of many terms, one of them being $s(r_p)$. Just because $N_\sigma$ is in some way minimal, we can not conclude that one of the terms is $\le$ than a term in some other sum. The other flaw is that it is not clear how the minimality of $N_\sigma$ is used. The minimality would mean that $N_\sigma \le N_\tau$ for other permutations $\tau$, but in this solution there is no other permutation defined.

There is no point in continuing the analysis, since this is a crucial argument in the proof, and it is an unrecoverable error.

Idea for a fix to Solution 2

We could drop all the discussion about the assigned number $N_\sigma$, and about trying to make it minimal.

The author wants to prove that for $j \ge k + 1$ (for which $a_{j\sigma(j)} \ne 0$) we have $s(r_j) + s(c_{\sigma(j)}) \ge n$. (This would yield the desired conclusion). I believe this is true, and it can be done with a careful examination of the zeros on $r_j$ and $c_{\sigma(j)}$. It would use ideas along the lines of the ideas in solution 3. It is not worth the effort of doing this (especially not in the formalism of permutations) since it would use no new ideas. This solution would be just a repetition of solution 3 with a much more complicated formalism.

Note: We know that every permutation is a combination of swaps, so the permutation could be replaced by swapping rows and/or columns. Instead of having $a_{i\sigma(i)} = 0$ for $i = 1, 2, \dots, k$, we could make $a_{ii} = 0$ for $i = 1, 2, \dots, k$, and $k$ be maximal with this property.


Solution 3 analysis and improvement

Bad choices of words in Solution 3

The author says:

"consider the largest possible subset of elements, all zero, which are pairwise in different rows of columns - let the size of this subset be $k$

...

we may rearrange the matrix such that these $k$ entries are on the main diagonal of the matrix, i.e. $a_{11} = a_{22} = \dots = a_{kk} = 0$"

This is unclear: the definition of $k$ does not make much sense, but if we insist of giving it some meaning, I would interpret it as counting the zeroes of $A$ which are not on the diagonal. Note that this $k$ could be larger than $n$. Fortunately this flaw is very easy to correct.

Since there are a few more unhappy choices of words in the proof, I will repeat the proof below, making the improvements to wording.

Solution 3 rewritten

Both the hypothesis and the conclusion of the problem stay true if we swap rows, or swap columns, or take the transpose of the given matrix A. If the matrix has no zeroes then the sum of its entries is $\ge n^2$. So assume there are zeroes in the matrix.

Recursively, swap rows and swap columns to bring more and more zeroes onto the diagonal. Let $k$ be the maximum number of zeroes we can bring onto the diagonal. Swap more rows and columns if needed, so that we will have $a_{11} = a_{22} = \dots = a_{kk} = 0$.

If $k = n$ then $\sum_{i = 1}^n (sum(r_i) + sum(c_i)) \ge n \cdot n$ (by hypothesis). On the other hand $\sum_{i = 1}^n (sum(r_i) + sum(c_i)) = 2 \sum_{i, j = 1}^n a_{ij}$, so the desired result follows.

Assuming $k < n$, let $X = \sum_{1 \le i, j \le k} a_{ij}$, and let $Y = \sum_{i \le k < j} a_{ij} + \sum_{j \le k < i} a_{ij}$, and let $Z = \sum_{k < i, j \le n} a_{ij}$.

Because of the hypothesis applied to $a_{11}, \dots, a_{kk}$, we get $2X + Y \ge kn$.

Assume we have $i \le k < j$ and $a_{ij} = a_{ji} = 0$. Now swap columns $i$ and $j$. Then $a_{ij}$ becomes the new entry at $(i, i)$ and $a_{ji}$ becomes the new entry at $(j, j)$. It follows that we have $k + 1$ zero entries on the diagonal, which contradicts the fact that $k$ was maximal. Consequently, at least one of $a_{ij}, a_{ji}$ is non-zero, so $a_{ij} + a_{ji} \ge 1$ for $i \le k < j$. It follows that $Y \ge k(n - k)$.

If we had $a_{ij} = 0$ with $i, j > k$ then again, we could swap columns $i$ and $j$. Then $a_{ij}$ becomes the new entry at $(i, i)$, and again, we have a contradiction of the fact that $k$ was maximal. Consequently, all elements $a_{ij}$ with $i, j > k$ are non-zero. It follows that $Z \ge (n - k)^2$.

Therefore, $2S = 2(X + Y + Z) \ge (2X + Y) + Y + Z \ge kn + k(n - k) + (n - k)^2 = n^2$.

Note: Another way of finishing off the proof would be to look at $\sum_{i = 1}^n (sum(r_i) + sum(c_i))$. We know that the terms for $1 = 1, \dots, k$ are $\ge n$ by hypothesis. For $i > k$, we know that $a_{ij} + a_{ji} \ge 1$ for $j \le k$, and that $a_{ij} \ne 0$ for $j > k$. It follows that $sum(r_i) + sum(c_i) \ge k + 2(n - k) = 2n - k \ge n$. This is the argument solution 2 would have made in its complicated formalism, had it reached this point correctly.


Examples

We will say that a matrix is minimal if it satisfies the hypothesis of the problem (i.e. $a_{ij} = 0$ implies $sum(r_i) + sum(c_j) \ge n$), and no entry of the matrix could be replaced by a smaller number such that the new matrix still satisfies the hypothesis of the problem.

For example, in the matrices below, the first, third and fifth are minimal, but the second is not, since one of its entries could be made smaller to yield the third matrix, and similarly the fourth is not, since one of its entries could be made smaller to yield the fifth matrix.

(1001)(0120)(0110)(1022)(0022)

The examples I will give are all minimal.

Now consider the following matrices:

(1010010110100101)(1100110000110011)(0011001111001100)(2000020000200002)

These examples show that for $n$ even, it is possible to have matrices so that $\sum_{i, j = 1}^n a_{ij} = \frac{n^2}{2}$. Note that the first three are essentially the same, they can be obtained from each other by swapping rows and/or columns.

Now let us look at some examples with $n$ odd.

(1010101010101010101010101)(1110011100111000001100011)(0000300030003001100011000)(3000002100012000001100011)

The first two are essentially equivalent, since they can be obtained from each other by swapping rows and/or columns. These all show that the minimum sum can be reached. The minimum sum is $\sum_{i, j = 1}^n a_{ij} = \frac{n^2 + 1}{2}$, which in this case ($n = 5$) is $13$.

And finally, let us look at a few examples which are minimal, but the sum of the entries is not the minimum (which for $n = 5$ means that the sum is $> 13$).

(3000003000003000003000002)(0000000000000000000055555)(1000001111011110111101111)

(1444410000100001000010000)(1555540000000000000000000)(0220020200220000001100011)


See Also

1971 IMO (Problems) • Resources
Preceded by
Problem 5
1 2 3 4 5 6 Followed by
Last Question
All IMO Problems and Solutions