[行列解析8.7.P9]二重確率行列の正の成分数に関する考察

(8.7.P9)

問題
解答例
- (a) \( A \) がちょうど \( n + 1 \) 個の正の要素をもつことはできないことの証明
- (b) \( A \) が置換行列でない場合、\( A \) は高々 \( n^2 - n - 2 \) 個のゼロ成分しかもたないことの説明
行列解析の総本山
- 総本山の目次📚
- 記号の意味🔎

問題

\( A \in M_n \) を二重確率行列とする。

(a) \( A \) がちょうど \( n + 1 \) 個の正の要素をもつことはできないことを示せ。

(b) \( A \) が置換行列でない場合、\( A \) は高々 \( n^2 - n - 2 \) 個のゼロ成分しかもたないことを説明せよ。

解答例

\( A \in M_n \) を \( n \times n \) の二重確率行列とする。これは、すべての成分 \( A_{ij} \ge 0 \) であり、すべての行和および列和が \( 1 \) である行列である。

(a) \( A \) がちょうど \( n + 1 \) 個の正の要素をもつことはできないことの証明

1. 行列のスパース性に関する考察

\( A \) の正の成分の数を \( p \) とする。各行、各列の和が \( 1 \) であることから、少なくとも \( 1 \) 個の正の成分をもつ行および列が存在する。したがって、\( n \le p \) である。

2. \( n+1 \) 個の正の要素をもつと仮定する

ここで、\( A \) がちょうど \( p = n + 1 \) 個の正の要素をもつと仮定する。これらの \( n + 1 \) 個の正の要素が存在する行と列の添字集合をそれぞれ \( R \) と \( C \) とする。添字の重複を許せば、\( R \) と \( C \) の要素数はそれぞれ \( n+1 \) 個である。

3. 最小数の行・列でカバーされることの確認

すべての行の和は \( 1 \) であるため、各行には少なくとも \( 1 \) 個の正の要素が存在する。つまり、\( n \) 個の行のそれぞれに少なくとも \( 1 \) 個の正の要素があるため、合計 \( n \) 個の正の要素は少なくとも必要である。同様に、列についても \( n \) 個の正の要素が少なくとも必要である。

4. 矛盾の導出（Hallの結婚定理の応用）

二重確率行列の理論では、ある行列が正の成分をもつかどうかは、その行列に対応する**二部グラフ**の辺の存在に対応する。

二重確率行列の正の成分のパターンは、**パーマネント** (permanent) の理論と関連付けられる。

**Frobenius-König の定理**により、\( A \) が対角線上に \( n-k \) 個以上のゼロをもつならば、\( k \times k \) のゼロ部分行列が存在する。これは、\( A \) のパーマネントがゼロでないこと、すなわち \( A \) が**置換を含む**（\( n \) 個の正の成分の積が存在する）ことと密接に関連する。

ここでは、より初等的な手法で示す。

\( p \) 個の正の成分をもつ \( n \times n \) 行列 \( A \) を考える。\( p = n+1 \) とする。正の成分をもつすべての行を \( r_1, \dots, r_{n} \in \mathbb{R}^n \) とする。行の線形従属性を考察するために、正の成分のみに注目する。

正の成分 \( A_{ij} > 0 \) のペア \((i, j)\) を \( S \) とすると、\( |S| = n+1 \) である。ここで、\( n \times n \) 行列 \( A \) が \( n+1 \) 個の正の成分のみをもつと仮定する。これらの成分は、行和・列和の制約 (\( 2n \) 個の線形制約) を満たさなければならない。

これらの \( n+1 \) 個の変数 \(\{ A_{ij} | (i, j) \in S \}\) には、行和および列和に関する \( 2n \) 個の制約条件がある。しかし、全行和と全列和は等しい (\( \sum_i \sum_j A_{ij} = n \)) ため、これらの制約は独立ではない。具体的には、\( 2n \) 個の制約のうち**独立な制約は \( 2n - 1 \) 個**である。

独立な変数の数 \( d \) は、

d = p - (2n - 1) = (n+1) - (2n - 1) = 2 - n

となる。

\( n \ge 2 \) のとき、\( d \le 0 \) となる。これは、\( p = n+1 \) の場合、変数の数が行和・列和の独立な制約の数以下であることを示している。

\( n \ge 3 \) の場合、\( d \le -1 \) となり、この場合、すべての変数は \( 0 \) でなければならない（つまり、独立な変数が存在しない）。しかし、\( A \) が二重確率行列であるためには、少なくとも \( n \) 個の正の要素が必要であり、これは矛盾である。

したがって、\( A \) はちょうど \( n + 1 \) 個の正の要素をもつことはできない。実際、二重確率行列の任意の極端点（置換行列）は \( n \) 個の正の要素をもち、極端点でない二重確率行列は少なくとも \( 2n \) 個の正の要素をもつ（後述の(b)の説明に近くなる）。

(b) \( A \) が置換行列でない場合、\( A \) は高々 \( n^2 - n - 2 \) 個のゼロ成分しかもたないことの説明

1. 置換行列の場合

\( A \) が**置換行列**である場合、正の成分の数はちょうど \( n \) 個であり、ゼロ成分の数は \( n^2 - n \) 個である。

2. 置換行列でない場合（極端点でない場合）

\( A \) が置換行列でない、すなわち \( A \) が二重確率行列の集合 \( D \) の**極端点ではない**場合を考える。このとき、\( A \) は異なる二重確率行列 \( A_1, A_2 \in D \) と \(\lambda \in (0, 1)\) を用いて、

A = \lambda A_1 + (1-\lambda) A_2

と表される。

\( A_1 \) と \( A_2 \) は異なる (\( A_1 \neq A_2 \)) ため、少なくとも一つの成分 \((i, j)\) で \( A_{1, ij} \neq A_{2, ij} \) である。また、\( A_1 \) と \( A_2 \) が二重確率行列であることから、それぞれ少なくとも \( n \) 個の正の成分をもつ。

3. 正の成分数の下限

\( A \) の正の成分 \( p \) の数は、\( A_1 \) の正の成分と \( A_2 \) の正の成分の**和集合**の数に等しい：

\{ (i, j) | A_{ij} > 0 \} = \{ (i, j) | A_{1, ij} > 0 \} \cup \{ (i, j) | A_{2, ij} > 0 \}

\( A \) が極端点でない場合、\( A \) は少なくとも一つの**サイクル**（またはその一般化）を含まなければならない。これは、\( A \) が少なくとも二つの置換行列の凸結合として表現可能であることを意味する（Birchoffの定理）。

二つの異なる置換行列 \( P_1 \) と \( P_2 \) の凸結合 \( A = \frac{1}{2} P_1 + \frac{1}{2} P_2 \) を考える。\( P_1 \neq P_2 \) であるため、\( P_1 \) と \( P_2 \) は少なくとも \( 2 \times 2 \) の部分行列において異なるパターンをもつ。この違いを生み出す最小のパターンの組み合わせ（\( 2 \times 2 \) のサイクル）は \( 4 \) 個の正の要素を含む。

しかし、\( P_1 \) と \( P_2 \) の正の成分の位置がまったく異なると仮定すると、\( A \) の正の成分数は \( 2n \) 個となる。一般に、\( P_1 \) と \( P_2 \) が \( k \) 個の共通の \( 1 \) をもつならば、\( A \) の正の成分数は \( n + (n - k) = 2n - k \) 個となる。最小の \( k \) は \( n-2 \) である（\( P_1 \) と \( P_2 \) がちょうど \( 2 \times 2 \) のブロックでのみ異なる場合）。

置換行列でない二重確率行列は、少なくとも \( 4 \) 個の正の要素をもつ \( 2 \times 2 \) の部分行列を含まなければならない。この最小の非極端点行列は、少なくとも \( 2n \) 個の正の成分（\( 2 \times 2 \) ブロックの \( 4 \) 個と、残りの \( n-2 \) 行/列の \( n-2 \) 個の \( 1 \) がそれぞれ \( 2 \) つずつで計 \( 2(n-2) \) 個）をもつ。

より簡潔に、置換行列でない二重確率行列 \( A \) は、少なくとも \( 2n-2 \) 個の正の成分をもつことが知られている。ここで \( n \ge 2 \) とする。

最も厳密な下限は、**\( A \) が置換行列でないならば、\( A \) は少なくとも \( 2n-1 \) 個の正の要素をもつ**ことが知られている。ただし、\( n=2 \) の場合は \( 3 \) 個の正の要素をもつことはできない（(a)で示した通り）。

\( n=2 \) の場合、置換行列でない二重確率行列 \( A \) は

A = \begin{pmatrix} \alpha & 1-\alpha \\ 1-\alpha & \alpha \end{pmatrix}, \quad 0 \lt \alpha \lt 1

の形をもち、**正の成分は \( 4 \) 個**である。ゼロ成分は \( 2^2 - 4 = 0 \) 個である。

ここで、\( n \ge 3 \) とする。置換行列でない \( A \) は、少なくとも \( 2n \) 個の正の成分をもつことが知られている（\( n=2 \) の場合は \( 4 \) 個）。

\( n=3 \) の場合、\( 2n = 6 \) 個の正の成分をもつ最小の例は、\( A = \frac{1}{2} (P_1 + P_2) \) で、\( P_1 \) と \( P_2 \) が \( 2 \times 2 \) のブロックでのみ異なる場合である。このとき、ゼロ成分の数は \( 3^2 - 6 = 3 \) 個である。
\( n \ge 2 \) の場合、置換行列でない \( A \) の正の成分数の最小値 \( p_{\min} \) は、\( p_{\min} \ge 2n \) となる（\( n=2 \) の場合は \( 4 \text{個} = 2 \times 2 \text{個} \))。

4. ゼロ成分の数の上限

\( A \) のゼロ成分の数を \( z \) とすると、\( z = n^2 - p \) である。置換行列でない場合、**正の成分数の最小値 \( p_{\min} \) は \( 2n \) である**（\( n=2 \) の \( 4 \) 個から \( n \ge 3 \) の \( 2n \) 個まで）。

したがって、ゼロ成分の数の最大値 \( z_{\max} \) は、

z_{\max} = n^2 - p_{\min} \le n^2 - 2n

となる。しかし、問題文は \( z \le n^2 - n - 2 \) を示唆している。この値は \( n^2 - 2n \) よりも小さい。

この差分 \( (n^2 - n - 2) - (n^2 - 2n) = n - 2 \) を考慮すると、問題の主張は**\( A \) の正の成分数が \( p \ge n + 2 \) である**ことを意味している。つまり、\( p = n+1 \) のケースは存在しないため、置換行列でない場合の最小の正の成分数は \( n+2 \) 以上のいずれかの値となる。

結論として、二重確率行列 \( A \) の正の成分の数が \( p \le n+1 \) の場合、\( A \) は**置換行列**である（\( p=n \) のみ）。したがって、\( A \) が置換行列でないならば、\( p \ge n+2 \) である必要がある。

よって、ゼロ成分の数は、