8.7.問題集
8.7.P1
\( M_n \) における確率行列および二重確率行列の集合が、それぞれ行列積に関して半群（セミグループ）を構成することを示せ。
すなわち、\( A, B \in M_n \) が（それぞれ二重）確率行列であるならば、\( AB \) もまた（それぞれ二重）確率行列であることを示せ。
8.7.P2
\( A \in M_n \) を確率行列とし、\( |\lambda| = 1 \) を満たす固有値 \( \lambda \) を考える。
ただし、\( \lambda = 1 \) はそのような固有値の一つであるが、他にも存在する可能性がある。\( A \) がべき有界であることを示し、さらに \( \lambda \) が \( A \) の半単純（semisimple）固有値であることを結論づけよ。
8.7.P3
\( A \in M_n \) を非負で零でない行列とし、正の固有ベクトル \( x = [x_i] \) をもつとする。\( D = \mathrm{diag}(x_1, \dots, x_n) \) とおく。
このとき、\( \rho(A)^{-1} D^{-1} A D \) が確率行列であることを示せ。
この結果により、正の固有ベクトルをもつ非負行列に関する多くの問題を、確率行列に関する問題に還元できる。
8.7.P4
\( A \in M_n \) を非負で零でない行列とし、正の固有ベクトルをもつとする。
このとき、\( A \) のすべての最大絶対値の固有値が半単純であることを説明せよ。
8.7.P5
\( A \in M_n \) を二重確率行列とし、その最大特異値を \( \sigma_1(A) \) とする。\( \sigma_1(A) = \rho(A) = 1 \) を、すなわち二重確率行列はスペクトル行列であることを2通りの方法で示せ。
(a) 式 (8.7.3) を用いる方法。
(b) 式 (2.6.P29) を用いる方法。
8.7.P6
\( \| \! | \cdot \| \! | \) を、\( \mathbb{R}^n \) 上の置換不変ノルム \( \| \cdot \| \) によって誘導される行列ノルムとする。
このとき、任意の二重確率行列 \( A \in M_n \) に対して \( \| \! |A\| \! | = 1 \) が成り立つことを示せ。
8.7.P7
任意の置換行列が、二重確率行列の凸集合における極端点（extreme point）であることを示せ。さらに、\( A \) が置換行列である場合に、どのような追加の性質がいえるか述べよ。
8.7.P8
\( n \times n \) の二重確率行列の集合がコンパクトかつ凸であることを踏まえ、ある行列がその集合の極端点であることと、置換行列であることが同値である理由を説明せよ。
8.7.P9
\( A \in M_n \) を二重確率行列とする。
(a) \( A \) がちょうど \( n + 1 \) 個の正の要素をもつことはできないことを示せ。
(b) \( A \) が置換行列でない場合、\( A \) は高々 \( n^2 - n - 2 \) 個のゼロ成分しかもたないことを説明せよ。
8.7.P10
2×2 の二重確率行列は対称であり、対角要素が等しいことを示せ。
8.7.P11
表現式 (8.7.3) が一意でないことを示せ。
8.7.P12
\( A \in M_n \) を二重確率・対称・半正定値行列とし、\( A^{1/2} \) をその半正定値平方根とする。 (a) \( A^{1/2} e = e \) であることを示せ。
したがって、\( A^{1/2} \) のすべての行および列の和は 1 である。 (b) \( A^{1/2} \) は一般には非負でないが、\( n = 2 \) の場合には非負（したがって二重確率）であることを示せ。
8.7.P13
\( \| \! | \cdot \| \! | \) をユニタリ不変な行列ノルムとする。このとき、任意の二重確率行列 \( A \in M_n \) に対して \( \| \! |A\| \! | \le \| \! |I\| \! | \) が成り立つことを示せ。
8.7.P14
\( A \in M_n \) が二重確率かつ既約でない（reducible）場合、\( A \) は置換相似により、二重確率行列 \( A_1, A_2 \) からなる直和 \( A_1 \oplus A_2 \) の形に変換できることを示せ。
8.7.P15
(8.7.2) における上界 \( 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.7) を参照）。
(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 \) 個の置換行列の凸結合として表せる。
注と参考文献
定理 8.7.2 は G. Birkhoff により “Tres observaciones sobre el álgebra lineal”, Univ. Nac. Tucumán Rev. Ser. A 5 (1946) 147–150 に現れる。
1916年に D. Kőnig は、非負有理数成分をもつ行列に対して (8.7.2) と同値な定理を発表した（Kőnig (1936) p.239 または Kőnig (1990) p.381 参照）。したがって、(8.7.2) はしばしば「Birkhoff–Kőnigの定理」と呼ばれる。
(8.7.2) の証明の中で非構成的な部分は、積 \( a_{1\sigma(1)} \cdots a_{n\sigma(n)} > 0 \) を満たす特定の置換 \( \sigma \) を同定する点のみである。
このような置換を構成的に求めるアルゴリズムは、Bapat と Raghavan (1997) の pp.64–65 に記されている。
この書籍には、二重確率行列に関する包括的な議論（第2章参照）と、多数の参考文献が収録されている。
行列解析の総本山
コメント