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$.

  • $\begingroup$ 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 $\endgroup$ Commented Apr 20, 2011 at 1:50

1 Answer 1


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.

  • $\begingroup$ Can you say more of why the last sum is less than or equal to k(M- 1)? I do not see those permutations as having maximal sums, or their being fewer than k. Gerhard "Ask Me About System Design" Paseman, 2011.04.19 $\endgroup$ Commented Apr 20, 2011 at 3:33
  • $\begingroup$ 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. $\endgroup$ Commented Apr 20, 2011 at 3:55
  • $\begingroup$ Ah. I was composing the sum with C. Got it now, thanks. Gerhard "Ask Me About System Design" Paseman, 2011.04.19 $\endgroup$ Commented Apr 20, 2011 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.