The following question was posed to me a while ago. No one I know has a given a satisfactory (or even a complete) proof:


Suppose that $M$ is an $n$ x $n$ matrix of non-negative integers. Additionally, suppose that if a coordinate of $M$ is zero, then the sum of the entries in its row and its column is at least $n$.


What is the smallest that the sum of all the entries in $M$ can be?


The conjecture posed to me was that it was $\frac{n^2}{2}$ which is obtained by the diagonal matrix with $\frac{n}{2}$ in all diagonal entries.


[I'm guessing that there should be a "suppose that" in describing M. -- GJK]



Extremal question on matrices
The following looks too simple, so perhaps there's a mistake, but here goes.


Let $m$ be the smallest among all row sums *and* column sums. If $m\geq n/2$, we are done.


Otherwise, $m=cn$ with $c\lt 1/2$. Suppose it is a column which has sum $m$. This column has at least $n-m$ zeroes, and each of the corresponding rows has sum $\geq n-m$. The remaining $m$ rows each has sum $\geq m$.


In total we have a sum of at least $(n-m)^2+m^2 = ((1-c)^2+c^2)n^2$. Finally, note that $(1-c)^2+c^2\gt 1/2$ when $c\lt 1/2$.


So this gives a lower bound of $n^2/2$, and equality requires that any row and any column sums to exactly $n/2$, so the matrix is a sum of $n/2$ permutation matrices by König's Theorem.


Now what about the case when $n$ is odd?


**Edit:** Since the sum is an integer, the lower bound $n^2/2$ actually gives $(n^2+1)/2$, which can be attained by for example taking the direct sum of an $m\times m$ matrix of $1$s with an $(n-m)\times (n-m)$ matrix of $1$, where $m=(n-1)/2$. *When $n$ is odd, this is the only extremal example up to column and row permutations.* Here is a proof.


Let $m$ now, as originally, denote the minimum over all row and column sums. If $m\geq (n+1)/2$, then the total sum is too large: at least $nm\geq n(n+1)/2$. Therefore, $m\leq(n-1)/2$, and the $(n-m)^2+m^2$ lower bound now gives a total sum of at least $(n-n(n-1)/2)^2+((n-1)/2)^2 = (n^2+1)/2$ (using the fact that $(1-c)^2+c^2$ is decreasing when $c\lt 1/2$).
So up to now we have only rederived the lower bound for $n$ odd.


However, if equality now holds, we get that $m=(n-1)/2$, that each row adds up to either $m$ ($m$ times) or $n-m$ ($n-m$ times), and that in a column that adds up to $m$, there are exactly $n-m$ $0$s, so all entries are $0$ or $1$ (and similar statements with columns and rows interchanged). By permuting the rows and columns we may assume that the first $m$ rows [columns] each add up to $m$.There can't be a $0$ in the upper left $m\times m$ submatrix, since then the sum of the row and column containing the $0$ adds up to only $2m\lt n$. We have found a direct sum of an $m\times m$ and an $(n-m)\times(n-m)$ all $1$ matrix.


