第6题

设

A=(a_{ij})

（

i,j=1,2,\ldots,n

）是元素为非负整数的方阵。假设只要

a_{ij}=0

，第

i

行与第

j

列元素之和就至少为

n

。证明矩阵所有元素之和至少为

n^2/2

。

第 1/7 步：通过置换最大化对角零元素

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

详细分析

条件和元素总和在交换行、交换列或转置下不变。通过置换使主对角线上零元素个数达到最大 $k$ ，即 $a_{11}=a_{22}=\cdots=a_{kk}=0$ 。若没有零元素，总和至少为 $n^2$ ，结论显然。