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

2 added 1415 characters in body

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.

1

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?