[行列解析8.7.P7]バーコフ多面体の極端点（頂点）

(8.7.P7)

問題
ヒント
解答例
- 1. 置換行列が二重確率行列の凸集合における極端点であることの証明
- 2. 置換行列 \(A\) がもつ追加の性質
行列解析の総本山
- 総本山の目次📚
- 記号の意味🔎

問題

任意の置換行列が、二重確率行列の凸集合における極端点（extreme point）であることを示せ。さらに、\( A \) が置換行列である場合に、どのような追加の性質がいえるか述べよ。

ヒント

\(A = α_1B + α_2C（α_1, α_2 \in (0, 1), \quad α_1 + α_2 = 1）\)であり、
\(A,B,C\)が二重確率的である場合、\(A\)のゼロ要素と同じ位置にある\(B\)と\(C\)のすべての要素はゼロでなければならない。

解答例

本問は、二重確率行列の集合がバーコフ多面体（Birkhoff polytope）と呼ばれる凸集合をなし、その極端点（頂点）が置換行列であることを示す問題である。

1. 置換行列が二重確率行列の凸集合における極端点であることの証明

前提

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

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

極端点の定義

集合 \(D\) の点 \(P \in D\) が極端点であるとは、\(P\) が \(D\) の異なる二点 \(A, B\) を用いて
\(P = \lambda A + (1-\lambda) B\) (\(0 < \lambda < 1\)) と表されるならば、
\(P=A=B\) が成り立つことである。

置換行列 \(P\) が極端点であることの証明

任意の置換行列 \(P\) を考える。\(P\) は、各行、各列にちょうど一つの \(1\) があり、それ以外の成分は \(0\) であるため、二重確率行列である。すなわち、\(P \in D\) である。

ここで、\(P\) が極端点でないと仮定し、\(P\) が二重確率行列 \(A, B \in D\) (\(A \neq B\)) と \(\lambda \in (0, 1)\) を用いて、

P = \lambda A + (1-\lambda) B

と表されるとする。

置換行列 \(P\) の成分は \(0\) か \(1\) である。

\(P_{ij}\) について次の二つの場合が考えられる。

\(P_{ij} = 0\) の場合：成分表示すると、\(P_{ij} = \lambda A_{ij} + (1-\lambda) B_{ij} = 0\) となる。ここで、\(A, B\) は二重確率行列であるため、すべての成分は非負、すなわち \(A_{ij} \ge 0\) かつ \(B_{ij} \ge 0\) である。また、\(\lambda \in (0, 1)\) であるため、この等式が成り立つには \(A_{ij}=0\) かつ \(B_{ij}=0\) でなければならない。
\(P_{ij} = 1\) の場合： \(P_{ij} = \lambda A_{ij} + (1-\lambda) B_{ij} = 1\) となる。\(A, B\) は二重確率行列であるため、成分は \(A_{ij} \le 1\) かつ \(B_{ij} \le 1\) である。この等式が成り立つには、\(A_{ij}\) と \(B_{ij}\) が最大値 \(1\) をとる必要があり、すなわち \(A_{ij}=1\) かつ \(B_{ij}=1\) でなければならない。

上記のいずれの場合も、すべての成分 \((i, j)\) について \(A_{ij} = P_{ij}\) かつ \(B_{ij} = P_{ij}\) が成り立つ。これは \(A=P\) かつ \(B=P\) を意味し、\(A \neq B\) という仮定に矛盾する。したがって、置換行列 \(P\) は二重確率行列の凸集合 \(D\) の極端点である。\(\square\)