第6問

A=(a_{ij})

(

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

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

a_{ij}=0

ならば第

i

行と第

j

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

n

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

n^2/2

であることを証明せよ。

ステップ 2/7: 対角線がすべて零の場合

k=n\implies 2S=\sum_{i=1}^n(r_i+c_i)\ge n^2\implies S\ge n^2/2

詳しい解説

$S=\sum_{i,j}a_{ij}$ とし、 $r_i,c_i$ を行和・列和とする。 $k=n$ なら各対角零に仮定を適用して $r_i+c_i\ge n$ 。従って $2S=\sum_i(r_i+c_i)\ge n^2$ 、ゆえに $S\ge n^2/2$ 。