[行列解析8.7.1]補題：非単位二重確率行列における置換の存在

8.7.1　補題：非単位二重確率行列における置換の存在
行列解析の総本山

8.7.1　補題：非単位二重確率行列における置換の存在

補題 8.7.1　

\( A = [a_{ij}] \in M_n \) を、単位行列ではない二重確率行列とする。

このとき、恒等置換でない置換 \( \sigma \) が存在し、次を満たす：

a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)} \gt 0

証明

恒等置換ではないすべての置換 \( \sigma \) に対して \( a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)} = 0 \) であると仮定する。

この仮定と式 (0.3.2.1) により、\( A \) の特性多項式を次のように計算できる：

p_A(t) = \det(tI - A) = \prod_{i=1}^n (t - a_{ii}) + \sum_{\sigma \ne \sigma_0} \mathrm{sgn}(\sigma) \prod_{i=1}^n (-a_{i\sigma(i)}) = \prod_{i=1}^n (t - a_{ii})

したがって、\( A \) の主対角成分はその固有値であることがわかる。

二重確率行列では \( +1 \) が固有値であるため、少なくとも1つの主対角成分が \( +1 \) である。

前の演習問題より、\( A \) は置換相似であり、次の形にできる：

A \sim [1] \oplus B

ここで \( B = [b_{ij}] \in M_{n-1} \) は二重確率行列であり、その主対角成分は \( A \) の主対角成分から1つの \( +1 \) を除いたものである。また \( +1 \) は \( B \) の固有値であり、

p_B(t) = \frac{p_A(t)}{t - 1} = \prod_{i=1}^{n-1} (t - b_{ii})

前と同様の議論を \( B \) に適用すると、ある \( b_{ii} = 1 \) が存在する。

したがって、\( A \) の主対角成分には少なくとも2つの \( +1 \) がある。これを繰り返すと、高々 \( n - 1 \) 回のステップで、すべての主対角成分が \( +1 \) であることがわかる。

ゆえに \( A = I \) となる。

これは仮定に反するため、少なくとも1つの積 \( a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)} \) が正である必要がある。□

補足と帰結

ビルコフの定理の証明では、この補題を用いて、与えられた二重確率行列 \( A \) から置換行列の正の定数倍を取り出す。この操作によって、新しい二重確率行列が得られるが、それは \( A \) よりも少なくとも1つ多くのゼロ要素を持つように構成される。この抽出過程を繰り返すことで、有限回のステップの後、\( A \) を有限個の置換行列の凸結合として表現できることがわかる。