Problem 6

Let

A=(a_{ij})

(

i,j=1,2,\ldots,n

) be a square matrix whose elements are nonnegative integers. Suppose that whenever

a_{ij}=0

, the sum of the elements in the

i

th row and the

j

th column is at least

n

. Prove that the sum of all elements of the matrix is at least

n^2/2

Step 2 of 7: Handle a full zero diagonal

Previous step Next step

k=n\implies 2S=\sum_{i=1}^n(r_i+c_i)\ge n^2\implies S\ge n^2/2

Detailed analysis

Let $S=\sum_{i,j}a_{ij}$ and let $r_i,c_i$ denote row and column sums. If $k=n$ , the hypothesis applied to every diagonal zero gives $r_i+c_i\ge n$ . Summing yields $2S=\sum_i(r_i+c_i)\ge n^2$ , hence $S\ge n^2/2$ .