[行列解析3.5.P11]置換行列とランクによる復元

3.5.P11

3.5.問題11

置換行列 \( P = [p_{ij}] \in M_n \) を考える。

これは \(1, …, n\) の置換 \(\pi_1, …, \pi_n\) に対応し、\( p_{\pi_j,j} = 1 \)（その他の成分は 0）である。

3.5.9 の記法を用い、

\text{rank } P_{[l,0]} = 0, \quad l = 1, \dots, n

を定義する。

(3.5.9)

P_{[p,q]} = P[\{1, \ldots, p\}, \{1, \ldots, q\}]

次を示せ：

\pi_j = \min \{ k \in \{1, \dots, n\} : \text{rank } P_{[k,j]} = \text{rank } P_{[k,j-1]} + 1 \}, \\ \quad j = 1, \dots, n

結論として、\( n^2 \) 個の数 \(\text{rank } P_{[k,j]}, \quad k,j = 1,\dots,n\) により \( P \) は一意に決まる。

ヒント

置換行列では各列にちょうど1つの1が存在する。

部分行列 \( P_{[k,j]} \) のランクは、最初の \( k \) 行・\( j \) 列に含まれる1の個数に一致する。

列を1つ進めたときにランクが1増えるのは、その列の1が初めて現れた行に対応する。

解答例

置換行列 \( P = [p_{ij}] \in M_n \) は、各列にちょうど1つの1を持ち、それ以外は0である。第 \( j \) 列において、1は行 \( \pi_j \) に現れる。

ここで、部分行列 \( P_{[k,j]} \) を「最初の \( k \) 行と最初の \( j \) 列からなる部分行列」とする。

このとき、\( P[k,j] \) のランクは、その中に含まれる1の個数に等しい。
なぜなら、各列に高々1つしか1がなく、それらは異なる行に現れるため、線形独立であるからである。

したがって、列数を1つ増やしたときのランクの増分

\mathrm{rank}\,P_{[k,j]} - \mathrm{rank}\,P_{[k,j-1]}

は、第 \( j \) 列の1が最初の \( k \) 行の中に含まれているかどうかを表す。すなわち、この差が1になるのは、\( \pi_j \le k \) のときである。

したがって、ランクが1増加する最小の \( k \) は、ちょうど \( \pi_j \) に一致する。すなわち

\pi_j = \min \{ k \in \{1, \dots, n\} : \mathrm{rank}\,P_{[k,j]} = \mathrm{rank}\,P_{[k,j-1]} + 1 \}

が成り立つ。

以上より、すべての \( j = 1,\dots,n \) に対して \( \pi_j \) が一意に決まる。したがって、\( n^2 \) 個の値 \( \mathrm{rank}\,P_{[k,j]} \)（\( k,j = 1,\dots,n \)）が与えられれば、各列における1の位置がすべて決まり、置換行列 \( P \) は一意に定まる。