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 5 of 7: Force positive entries across the blocks

Previous step Next step

a_{ij}+a_{ji}\ge1\quad(i\le k<j)\implies Y\ge k(n-k)

Detailed analysis

For $i\le k<j$ , both $a_{ij}$ and $a_{ji}$ cannot be zero: swapping columns $i$ and $j$ would then create a diagonal zero at position $j$ in addition to the existing $k$ , contradicting maximality of $k$ . Since entries are nonnegative integers, $a_{ij}+a_{ji}\ge1$ . Summing over the $k(n-k)$ pairs gives $Y\ge k(n-k)$ .