# Matrix with max sum on all diagonals

I knew this problem a long time ago but could not recall the solution. I know the solution is interesting though. Anybody want to help? Thanks.

There is a $n \times n$ matrix. A collection of $n$ entries of the matrix is called good if no two of them have a same row or column. For each good collection we consider the sum of its elements, and let $M$ be the maximum among all these sums. Now any entry of the matrix belongs to at least one good collection with sum $M$. Prove that every good collection has sum $M$.

• Note that it is true for n=1,2 (proof by exhaustion). The rest is so nice tthat I will just start it. Suppose m=n+1 and there is an m by m matrix with entry, say a_11, which is part of a good set with sum less than the max. ... Gerhard "Can You Finish The Rest" Paseman, 2011.04.19 Commented Apr 20, 2011 at 1:50

Let $\circ$ denote the Hadamard product, $A\circ B=(a _{ij} b _{ij}) _{1\le i,j\le n}$, and let $f(A)$ denote the sum of the entries of $A$. Each good set corresponds to a permutation in $S _n$. Let our matrix be $C$, then we are given that there are $k$ permutation matrices $P _{\sigma_i}$, $\sigma _i\in S _n$, such that $f(P _{\sigma _i}\circ C)=M$, and $\sum P _{\sigma _i}$ has all entries $\geq 1$.
Let $\pi\in S_n$ be so that, $M _{0}=f(P _{\pi}\circ C) < M$, then we look at $\sum P _{\sigma _i}-P _{\pi}$, it has nonnegative entries and equal sums of rows and columns. Such a matrix can be written as a sum $\sum P _{\tau _i}$, $\tau _i\in S_n$, this is a simple exercise in combinatorics (maybe you have heard it in the form, every bipartite regular multigraph can be written as a union of perfect matchings). So we have $$kM-M _{0}=f\left((\sum P _{\sigma _i}-P _{\pi})\circ C\right)=f\left((\sum P _{\tau _i})\circ C\right)=\sum f(P _{\tau _i}\circ C)\le (k-1)M$$ which gives us a contradiction. So $f(P _{\pi}\circ C)=M$, but $\pi$ was arbitrary, so we are done.
• Gerhard the point is that the number of permutation matrices in the sum $\sum P _{\tau _i}$ can be found by the sum of all entries divided by $n$. This means that the last sum has $k-1$ terms, each of which is at most $M$, since they are diagonal sums. Commented Apr 20, 2011 at 3:55