第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$ なので終わる。