MathLabs

第6問

A=(aij)A=(a_{ij}) (i,j=1,2,…,ni,j=1,2,\ldots,n) を非負整数要素の正方行列とする。aij=0a_{ij}=0 ならば第 ii 行と第 jj 列の要素の和が少なくとも nn であると仮定する。行列の全要素の和が少なくとも n2/2n^2/2 であることを証明せよ。
ステップ 6/7: 右下ブロックの正値を強制する
aij≠0 (i,j>k)  ⟹  Z≥(n−k)2a_{ij}\ne0\ (i,j>k)\implies Z\ge(n-k)^2
詳しい解説

aij=0a_{ij}=0 かつ i,j>ki,j>k となるものがあれば、列 ii と jj を交換すると (i,i)(i,i) に新しい対角零が生じ、最初の kk 個の対角零を保ったまま最大性に反する。従って右下ブロックの全要素は零でなく、少なくとも 11 であり、Z≥(n−k)2Z\ge(n-k)^2。