[行列解析8.7.2]定理（ビルコフの定理）：二重確率行列の凸結合表現

8.7.2　定理（ビルコフの定理）：二重確率行列の凸結合表現
行列解析の総本山

8.7.2　定理（ビルコフの定理）：二重確率行列の凸結合表現

定理 8.7.2（ビルコフの定理）　

行列 \( A \in M_n \) が二重確率行列であることと、次の条件が成り立つことは同値である。

すなわち、置換行列 \( P_1, P_2, \ldots, P_N \in M_n \) と正の実数 \( t_1, t_2, \ldots, t_N \in \mathbb{R} \) が存在して、

t_1 + t_2 + \cdots + t_N = 1

かつ

8.7.3

A = t_1 P_1 + t_2 P_2 + \cdots + t_N P_N \tag{8.7.3}

が成り立つ。さらに、\( N \le n^2 - n + 1 \) である。

証明

式 (8.7.3) の表現が成り立つことの「十分性」は明らかである。以下では、その「必要性」を、有限回の手順でこの表現を構成するアルゴリズムを示すことで証明する。

まず、\( A \) が置換行列である場合は証明の必要がない。そうでない場合、前の補題により、恒等置換ではない置換 \( \sigma \) が存在し、次が成り立つ：

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

ここで、次のように定義する：

\alpha_1 = \min\{ a_{1\sigma(1)}, a_{2\sigma(2)}, \ldots, a_{n\sigma(n)} \}

また、置換行列 \( P_1 = [p_{ij}] \in M_n \) を各 \( i = 1, \ldots, n \) に対して \( p_{i\sigma(i)} = 1 \) として定める。

もし \( \alpha_1 = 1 \) ならば、\( A \) は置換行列である。したがって \( 0 \lt \alpha_1 \lt 1 \) である。次に、

A_1 = (1 - \alpha_1)^{-1}(A - \alpha_1 P_1)

と定義する。このとき、\( A_1 \) は二重確率行列であり、\( A \) よりも少なくとも1つ多くのゼロ要素をもつ。また、

A = (1 - \alpha_1) A_1 + \alpha_1 P_1

が成り立つ。もし \( A_1 \) が置換行列であれば、2項の形で (8.7.3) が得られるので終了する。そうでなければ、同様の議論を繰り返して、\( \alpha_2 \in (0, 1) \) と置換行列 \( P_2 \) を見つけ、

A_2 = (1 - \alpha_2)^{-1}(A_1 - \alpha_2 P_2)

とする。このとき \( A_2 \) は二重確率行列であり、\( A_1 \) よりも少なくとも1つ多くのゼロ要素をもつ。そして

A = (1 - \alpha_1)(1 - \alpha_2)A_2 + (1 - \alpha_1)\alpha_2 P_2 + \alpha_1 P_1

が成り立つ。もし \( A_2 \) が置換行列であれば、3項の形で (8.7.3) が得られる。そうでなければ、この操作を繰り返す。有限回のステップの後、ある \( A_k \) が置換行列となり、次の形を得る：

A = t_1 P_1 + t_2 P_2 + \cdots + t_{k+1} P_{k+1}

ここで \( A_k \) は少なくとも \( k \) 個のゼロ要素をもつ。また、二重確率行列は高々 \( n^2 - n \) 個のゼロ要素しかもたない。したがって、最大でも \( n^2 - n \) 回の反復が必要であり、(8.7.3) における項数は最大で \( n^2 - n + 1 \) である。□