[行列解析8.7.P8]二重確率行列と置換行列

(8.7.P8)

問題
ヒント
解答例
- 1. 集合 \(D\) がコンパクトかつ凸であること
  - 凸性（Convexity）
  - コンパクト性（Compactness）
- 2. 極端点であることと置換行列であることが同値である理由
  - \(\Leftarrow\) 置換行列ならば極端点である
  - \(\Rightarrow\) 極端点ならば置換行列である
行列解析の総本山
- 総本山の目次📚
- 記号の意味🔎

問題

\( n \times n \) の二重確率行列の集合がコンパクトかつ凸であることを踏まえ、ある行列がその集合の極端点であることと、置換行列であることが同値である理由を説明せよ。

ヒント

(8.7.2)

解答例

二重確率行列の集合を \(D\) と定義する。

\(D\) は、成分がすべて非負で、すべての行和および列和が \(1\) である \(n \times n\) 行列の集合である。

1. 集合 \(D\) がコンパクトかつ凸であること

凸性（Convexity）

任意の二重確率行列 \(A, B \in D\) と \(\lambda \in [0, 1]\) に対して、\(C = \lambda A + (1-\lambda) B\) が再び \(D\) に属することを示す。

非負性：\(A_{ij} \ge 0\) かつ \(B_{ij} \ge 0\) であり、\(\lambda \ge 0, 1-\lambda \ge 0\) であるため、\(C_{ij} = \lambda A_{ij} + (1-\lambda) B_{ij} \ge 0\) である。
行和が 1：任意の行 \(i\) について、
\(\sum_{j=1}^n C_{ij} \\= \sum_{j=1}^n (\lambda A_{ij} + (1-\lambda) B_{ij}) \\= \lambda \sum_{j=1}^n A_{ij} + (1-\lambda) \sum_{j=1}^n B_{ij} \\= \lambda \cdot 1 + (1-\lambda) \cdot 1 = 1\)
列和が 1：同様に、任意の列 \(j\) について \(\sum_{i=1}^n C_{ij} = 1\) が成り立つ。

したがって、\(D\) は凸集合である。

コンパクト性（Compactness）

\(D\) は \(\mathbb{R}^{n^2}\) における閉集合かつ有界集合であるため、ハイネ・ボレルの定理（Heine-Borel theorem）によりコンパクト集合である。

有界性：任意の \(A \in D\) の成分 \(A_{ij}\) は \(0 \le A_{ij} \le 1\) の範囲にあり、すべての成分が有界であるため、\(D\) は有界である。
閉性：行和・列和が \(1\) という条件は線形な等式制約であり、成分が非負という条件は線形な不等式制約である。これらによって定義される集合は閉集合となる。

2. 極端点であることと置換行列であることが同値である理由

\(D\) はコンパクトな凸集合であるため、Krein–Milman の定理により、\(D\) はその極端点の凸包（convex hull）に等しい。

置換行列を \(P\) とし、極端点の集合を \(\text{Ext}(D)\) とする。示したいのは、\(A \in \text{Ext}(D) \iff A\) は置換行列である、ということである。

\(\Leftarrow\) 置換行列ならば極端点である

この方向は、Birchoff の定理の証明の鍵となる部分である。

置換行列 \(P\) が極端点でないと仮定し、\(P = \lambda A + (1-\lambda) B\) (\(A, B \in D, A \neq B, 0 < \lambda < 1\)) と表されるとする。

\(P\) の成分は \(0\) または \(1\) のみである。ここで、\(P_{ij}\) について次の議論を行う。

\(P_{ij} = 0\) の場合：\(0 = \lambda A_{ij} + (1-\lambda) B_{ij}\) となる。\(A, B\) は非負行列であり、\(\lambda \in (0, 1)\) であるため、\(A_{ij}=0\) かつ \(B_{ij}=0\) でなければならない。
\(P_{ij} = 1\) の場合：\(1 = \lambda A_{ij} + (1-\lambda) B_{ij}\) となる。\(A, B\) は行和が \(1\) の非負行列であるため、成分は \(A_{ij} \le 1, B_{ij} \le 1\) である。この等式が成り立つには、\(A_{ij}=1\) かつ \(B_{ij}=1\) でなければならない。

すべての成分について \(A_{ij} = P_{ij}\) かつ \(B_{ij} = P_{ij}\) が導かれ、\(A=P\) かつ \(B=P\) となる。これは \(A \neq B\) という仮定に矛盾するため、置換行列 \(P\) は極端点でなければならない。

\(\Rightarrow\) 極端点ならば置換行列である

極端点 \(A \in \text{Ext}(D)\) が置換行列でないと仮定する。このとき、\(A\) の少なくとも一つの行、例えば行 \(i\) に、\(0\) でも \(1\) でもない成分 \(A_{ij}\) が存在する。すなわち \(0 < A_{ij} < 1\) となる成分が存在する。

二重確率行列の性質（行和・列和が \(1\)）と \(A\) が置換行列でないという仮定から、\(A\) の成分の配置において、少なくとも一つのサイクル（またはそれを一般化した集合の組）を見つけることができる。これは、\(A\) からある成分 \(\epsilon > 0\) を加減算することで、二つの異なる二重確率行列 \(A_1, A_2 \in D\) を構成できることを意味する。具体的には、