第6問

A=(a_{ij})

(

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

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

a_{ij}=0

ならば第

i

行と第

j

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

n

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

n^2/2

であることを証明せよ。

ステップ 3/7: 行列を3ブロックに分ける

X=\sum_{i,j\le k}a_{ij},\quad Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij},\quad Z=\sum_{i,j>k}a_{ij}

詳しい解説

$k<n$ と仮定する。 $X$ を左上 $k\times k$ ブロック、 $Y$ を2つの非対角長方形ブロック、 $Z$ を右下 $(n-k)\times(n-k)$ ブロックの和とする。このとき $S=X+Y+Z$ 。