(8.7.P15)
問題
バーコフの定理における頂点の上界 \( n^2 - n + 1 \) を、
\( (n^2 - n + 1) - (n - 1) = n^2 - 2n + 2 \)
に改良できることを示せ。詳細を以下の手順で説明せよ：
(a) 任意の \( n \times n \) 二重確率行列 \( S = [s_{ij}] \) は、次の \( 2n - 1 \) 個の線形方程式を満たす：
\sum_{k=1}^n s_{ik} = 1, \quad i = 1, \dots, n, \\
\sum_{k=1}^n s_{ki} = 1, \quad i = 1, \dots, n-1
(b) これらの方程式を \( A \, \mathrm{vec}(S) = e \in \mathbb{R}^{2n-1} \) の形に書き直せ（式 (0.7.8) を参照）。
(c) \( A \in M_{2n-1, n^2} \) は満行ランクをもつ。
(d) \( \mathrm{nullspace}(A) \) の次元は \( n^2 - 2n + 1 \) である。
(e) 二重確率行列の集合は、\( \mathbb{R}^{n^2 - 2n + 1} \) における凸多面体とみなせる。
(f) 式 (8.7.3) および Carathéodory の定理（付録B参照）より、任意の二重確率 \( n \times n \) 行列は、高々 \( n^2 - 2n + 2 \) 個の置換行列の凸結合として表せる。
解答例
(a)
\( S = [s_{ij}] \)は二重確率行列であるから、行和、列和はそれぞれ\(1\)で下記の\(2n\)個の等式が成立する。
\sum_{k=1}^n s_{ik} = 1, \quad i = 1, \dots, n, \\
\sum_{k=1}^n s_{ki} = 1, \quad i = 1, \dots, n
このうち、最後の等式\(\sum_{k=1}^n s_{kn}\)は、
\sum_{k=1}^n s_{kn}
= \sum_{i=0}^n\sum_{k=1}^n s_{ik}
-\sum_{i=0}^{n-1} \sum_{k=1}^n s_{ki} \\
= \sum_{i=0}^n1 -\sum_{i=0}^{n-1} 1
= n-(n-1)=1
であるので、残りの\(2n-1\)個の等式から得ることができる事に注意し省略して考える。
(b)
A_i=\begin{bmatrix}
0 & \cdots & 1 & \cdots & 0 \\
\end{bmatrix} \in M_{1,n} \text{---(i列目のみ1)} \\
A_c=\begin{bmatrix}
1 & 1 & \cdots & 1 \\
\end{bmatrix} \in M_{1,n} \\
A=\begin{bmatrix}
A_1 & A_1 & \cdots & A_1 & A_1 & \\
\vdots & \vdots & & \vdots & \vdots \\
A_n & A_n & \cdots &A_n & A_n \\
A_c & 0 & \cdots & 0 &0 \\
0 & A_c & \cdots & 0 &0 \\
\vdots & \vdots & \ddots & \vdots &\vdots & \\
0 & 0 \ & \cdots & A_c &0 \\
\end{bmatrix} \in M_{2n-1,n^2}
と置くと、(a)の等式より、\( A \, \mathrm{vec}(S) = e \in \mathbb{R}^{2n-1} \)となる。
(c)
行列\(A\ \in M_{2n-1,n^2}\)は、どの行も他の行の組み合わせで表せないので、満行(full row)ランクである。
つまり、\( \mathrm{rank}(A)=2n-1\)である。
(d)
\( \mathrm{rank}(A)=2n-1\)であるので、
\( \dim \mathrm{nullspace}(A) = n^2 - (2n-1)\)となる。
(e)
バーコフの定理により、二重確率行列の集合（Birkhoff 多面体）は置換行列の凸包であり、任意の二重確率行列は置換行列の凸結合として表せる（極点は置換行列）。
すなわち、二重確率行列の集合は、\( \mathbb{R}^{n^2 - 2n + 1} \) における凸多面体とみなせる。
(f)
Carathéodory の定理（アフィン空間内の点はそのアフィン次元\(＋1\) 個以下の極点の凸結合として表せる）を適用すると、アフィン次元が(d)より \(n^2−2n+1\) であることから、任意の二重確率行列は最多で \((n^2−2n+1)+1= n^2−2n+2\) 個の置換行列の凸結合として表される。
これで、元の上界\( n^2−n+1\) を改良して \(n^2−2n+2\) が成り立つことが示された。■
行列解析の総本山
総本山の目次📚
記号の意味🔎
コメント