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 4 of 7: Use the hypothesis on the diagonal zeroes

Previous step Next step

2X+Y\ge kn

Detailed analysis

For each $i\le k$ , the zero $a_{ii}$ implies that its row sum plus its column sum is at least $n$ . Summing these $k$ inequalities counts the upper-left block twice and the off-diagonal blocks once, so $2X+Y\ge kn$ .