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 6 of 7: Force the lower-right block to be positive

Previous step Next step

a_{ij}\ne0\ (i,j>k)\implies Z\ge(n-k)^2

Detailed analysis

If some $a_{ij}=0$ with $i,j>k$ , swapping columns $i$ and $j$ would create a further diagonal zero at $(i,i)$ while leaving the first $k$ diagonal zeroes intact, again contradicting maximality. Thus every entry in the lower-right block is nonzero, hence at least $1$ , and $Z\ge(n-k)^2$ .