第6問

A=(a_{ij})

(

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

) を非負整数要素の正方行列とする。

a_{ij}=0

ならば第

i

行と第

j

列の要素の和が少なくとも

n

であると仮定する。行列の全要素の和が少なくとも

n^2/2

であることを証明せよ。

ステップ 4/7: 対角の零に仮定を適用する

2X+Y\ge kn

詳しい解説

$i\le k$ では零 $a_{ii}$ により行和と列和の和が少なくとも $n$ 。この $k$ 個の不等式を足すと、左上ブロックは2回、非対角ブロックは1回数えられるので $2X+Y\ge kn$ 。