MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 changed title to something a little more descriptive

# CombinatorialQuestionExtremalquestiononmatrices

3 added 54 characters in body; deleted 29 characters in body

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

Let

Suppose that $M$ be is an $n$ x $n$ matrix of non-negative integers. Suppose 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]

2 added 93 characters in body

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

Let $M$ be an $n$ x $n$ matrix of non-negative integers. If 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]

1