第6题

设

A=(a_{ij})

（

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

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

a_{ij}=0

，第

i

行与第

j

列元素之和就至少为

n

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

n^2/2

。

第 6/7 步：迫使右下分块为正

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

详细分析

若存在 $a_{ij}=0$ 且 $i,j>k$ ，交换列 $i$ 和 $j$ 会在 $(i,i)$ 产生新的对角零，同时保留前 $k$ 个对角零，与最大性矛盾。因此右下分块每个元素均非零，至少为 $1$ ，故 $Z\ge(n-k)^2$ 。