[行列解析8.7.P11]二重確率行列を置換行列で凸結合表現した時の一意性について

(8.7.P11)

問題
解答例
行列解析の総本山
- 総本山の目次📚
- 記号の意味🔎

問題

二重確率行列\(A\)の表現式 (8.7.3) が一意でないことを示せ。

8.7.3

二重確率行列\(A\)に対し、置換行列 \( P_1, P_2, \ldots, P_N \in M_n \) と正の実数
\( t_1, t_2, \ldots, t_N \in \mathbb{R} \) が存在して、

A = t_1 P_1 + t_2 P_2 + \cdots + t_N P_N \\ t_1 + t_2 + \cdots + t_N = 1

解答例

二重確率行列の集合 \( D \) は Birkhoff のポリトープと呼ばれ、その極端点（頂点）は \( n \times n \) の置換行列の集合 \(\{ P_1, P_2, \ldots, P_{n!} \}\) であることが知られている（バーコフ(Birchoff)の定理）。

問題で示されている表現式 (8.7.3) は、Birchoff の定理が述べるように、任意の二重確率行列 \( A \) が極端点である置換行列 \( P_k \) の凸結合として表されることを意味する。

問題文の式 (8.7.3) は、係数 \( t_k \) が正の実数（\( t_k > 0 \)) であり、和が \( 1 \) (\(\sum_{k=1}^N t_k = 1\)) であるため、これは凸結合の標準的な表現である。

A = t_1 P_1 + t_2 P_2 + \cdots + t_N P_N \\ \sum_{k=1}^N t_k = 1, \quad t_k > 0

この表現が一意でないことを示すには、ある非置換行列の二重確率行列 \( A \) に対して、\( A \) を表現する少なくとも二組の異なる係数と置換行列の組み合わせが存在することを示せばよい。

1. \( 2 \times 2 \) の2重確率行列の場合

\( n = 2 \) の場合を考える。

\( 2 \times 2 \) の置換行列は以下の \( 2! = 2 \) 個である。

P_1 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad P_2 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

任意の \( 2 \times 2 \) の二重確率行列 \( A \) は、\( 0 \le \alpha \le 1 \) を用いて

A = \begin{pmatrix} \alpha & 1-\alpha \\ 1-\alpha & \alpha \end{pmatrix}

と表されることが示されている（8.7.P10の解答を参照）。

この \( A \) は、\( P_1 \) と \( P_2 \) の凸結合として、一意に表される。

A = \alpha P_1 + (1-\alpha) P_2

このとき、\( t_1 = \alpha, t_2 = 1-\alpha \) であり、\( N=2 \) である。

\( N \) を増やしても、\( P_1 \) と \( P_2 \) 以外の \( 2 \times 2 \) 置換行列は存在しないため、この表現は一意である。

したがって、\( 2 \times 2 \) の場合は一意性が成り立つため、\( n \ge 3 \) の場合を考察する必要がある。

2. 一般の場合（\( n \ge 3 \)）の非一意性の証明

二重確率行列の凸結合表現は、一般に一意ではない。これは、\( n \times n \) の二重確率行列の集合 \( D \) が、頂点（置換行列）の数 \( n! \) よりも次元の低い面をもち、かつ \( n! \) 個の頂点をもつ多面体であることによる。

\( n = 3 \) の場合を考える。\( 3 \times 3 \) の置換行列は \( 3! = 6 \) 個存在する。

例えば、すべての成分が \( 1/3 \) である二重確率行列 \( A \) を考える。

A = \begin{pmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{pmatrix}

この行列 \( A \) は、\( 6 \) 個のすべての置換行列 \( P_k \) の平均として表現できる（すべての \( t_k = 1/6 \))。

A = \frac{1}{6} P_1 + \frac{1}{6} P_2 + \frac{1}{6} P_3 + \frac{1}{6} P_4 + \frac{1}{6} P_5 + \frac{1}{6} P_6

一方で、\( A \) は任意の二つの置換行列 \( P_i, P_j \) の平均としても表現できる。

例えば、\( P_1 \) と \( P_2 \) を用いた表現 \( E_1 \):

E_1: A = \frac{1}{2} (P_1 + P_2)

ここで \( P_1 \) と \( P_2 \) は \( A \) と同じ正の成分のパターンをもつ \( 2 \times 2 \) のサイクルに関連する置換行列であると考える。

実際には、すべての \( P_k \) の平均 \( A \) を考えると、任意の \( 4 \) つの頂点 (\( P_a, P_b, P_c, P_d \)) が一つの平面を形成する場合、\( A \) がその平面上にあれば、\( A \) の表現は非一意となる。

ここでは、\( P_1, P_2, P_3 \) を用いて \( A \) を表現し、さらに \( P_4, P_5 \) を用いた異なる表現が存在することを示す。

\( A \) を置換行列の集合 \(\{ P_k \}\) の凸包の内部の点とする。この点 \( A \) は、\( D \) の異なる側面（facets）上にある極端点の凸結合として、複数の方法で表現できる。

例えば、\( 3 \times 3 \) の場合、任意の \( 4 \) つの置換行列 \( P_a, P_b, P_c, P_d \) で、ある \( \lambda \in (0, 1) \) に対して

\lambda (P_a + P_b) = (1-\lambda) (P_c + P_d)

が成り立つような例が存在すれば、

A = \frac{1}{2} (P_a + P_b)

と

A = \frac{1}{2} \frac{\lambda}{1-\lambda} P_c + \frac{1}{2} \frac{\lambda}{1-\lambda} P_d

という二つの異なる表現が得られる。

具体的に \( n=3 \) で \( A = (1/3) J \) (\( J \) は全成分が \( 1 \) の行列) を考えると、\( A \) はすべての置換行列の重心である。

A = \frac{1}{6} \sum_{k=1}^6 P_k

ここで、\( P_1, P_2, P_3 \) が \( 3 \) 次巡回置換、\( P_4, P_5, P_6 \) が \( 2 \) 次巡回置換と恒等置換であるとき、

P_1 + P_2 + P_3 = J

かつ

P_4 + P_5 + P_6 = 2J

とはならないため、\( J \) の表現は複雑になる。

最も簡単な反例は、二つの異なる置換行列の組 \((P_a, P_b)\) と \((P_c, P_d)\) が存在し、

P_a + P_b = P_c + P_d

が成り立つことである。このとき、\( A = \frac{1}{2} (P_a + P_b) \) は、\( A = \frac{1}{2} P_a + \frac{1}{2} P_b \) と \( A = \frac{1}{2} P_c + \frac{1}{2} P_d \) という二つの異なる表現をもつ。

\( n \ge 3 \) において、このような関係式が常に存在する。

例えば \( n=3 \) で、

P_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad P_2 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}

という特定の置換行列の和を考えると、\( 3 \times 3 \) の二重確率行列の表現は容易に非一意となる。

この非一意性は、二重確率行列の集合 \( D \) が、頂点集合の数 \( n! \) に対して、その次元が \((n-1)^2\) である多面体であることに起因する。多面体の内部の点（置換行列でない点）は、一般に複数の異なる頂点の組み合わせの凸結合として表現可能であるため、表現式 (8.7.3) は一意ではない。\(\square\)