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 3 of 7: Split the matrix into three blocks

Previous step Next step

X=\sum_{i,j\le k}a_{ij},\quad Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij},\quad Z=\sum_{i,j>k}a_{ij}

Detailed analysis

Assume $k<n$ . Define $X$ as the sum in the upper-left $k\times k$ block, $Y$ as the sum in the two off-diagonal rectangular blocks, and $Z$ as the sum in the lower-right $(n-k)\times(n-k)$ block. Then $S=X+Y+Z$ .