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 1 of 7: Maximize diagonal zeroes by permutations

Previous step Next step

a_{11}=a_{22}=\cdots=a_{kk}=0

Detailed analysis

The hypothesis and the total sum are unchanged by row or column permutations and transposition. Permute rows and columns to make the maximum possible number $k$ of zero entries lie on the main diagonal, so $a_{11}=a_{22}=\cdots=a_{kk}=0$ . If there are no zero entries, the total is at least $n^2$ and we are done.