[行列解析8.7.P5]二重確率行列の最大特異値とスペクトル半径

(8.7.P5)

問題

\( A \in M_n \) を二重確率行列とし、その最大特異値を \( \sigma_1(A) \) とする。

\( \sigma_1(A) = \rho(A) = 1 \) を、すなわち二重確率行列はスペクトル行列であることを、2通りの方法で示せ。

(a) 式 (8.7.3) を用いる方法。

8.7.3

置換行列 \( 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

(b) 問題 (2.6.P29) を用いる方法。

\(x \in \mathbb{C}^n\) が \(A \in M_n\) の正規固有ベクトルであり、対応する固有値を \(\lambda\) とするとき、\(|\lambda|\) が \(A\) の特異値である
(2.6.P29)

二重確率行列 \( A \in M_n \) とは、非負成分を持ち、行と列の成分の和がすべて \( 1 \) となる行列の事である。

最大特異値を \( \sigma_1(A) \)、スペクトル半径を \( \rho(A) \) としたとき、
\( \sigma_1(A) = \rho(A) = 1 \) を示せばよい。

\( \sigma_1(A)=1 \)であることを２通りの方法で示す。

成分が全て \( 1 \) のベクトルを \(\mathbf{e} = [1, 1, \dots, 1]^T \in \mathbb{R}^n\) と定義する。

\( A \) は行和が \( 1 \) であるため、

A\mathbf{e} = 1\mathbf{e}

が成り立ち、\(\lambda = 1\) は固有値である。

また、\( \| A \|_\infty = \max_i \sum_j |A_{ij}| = 1 \) より、任意の固有値 \(\lambda\) に対して
\( |\lambda| \le \| A \|_\infty = 1 \) が成立する。

したがって、最大の固有値の絶対値であるスペクトル半径は、\( \rho(A) = 1 \) である。

\rho(A) = 1

二重確率行列 \( A \) は、置換行列行列 \( P_i \) の凸結合として表現できる（バーコフ＝フォン・ノイマンの定理）。

A = t_1 P_1 + t_2 P_2 + \cdots + t_N P_N \quad (t_i \ge 0, \sum t_i = 1)

置換行列 \( P_i \) はユニタリ行列（直交行列）であるため、その \( \ell_2 \) ノルム、すなわち最大特異値は \( \| P_i \|_2 = \sigma_1(P_i) = 1 \) である。

行列ノルムの性質 \(\| A+B \| \le \| A \| + \| B \|\) を用いると、

\sigma_1(A) = \|A\|_2 = \left\| \sum_{i=1}^N t_i P_i \right\|_2 \le \sum_{i=1}^N \| t_i P_i \|_2 = \sum_{i=1}^N t_i \| P_i \|_2 = \sum_{i=1}^N t_i \cdot 1 = 1

したがって、\( \sigma_1(A) \le 1 \) である。

一方、最大特異値はスペクトル半径を下回らない (\( \sigma_1(A) \ge \rho(A) \)) ため、\( \sigma_1(A) \ge 1 \) も成立する。

両者の条件から、\( \sigma_1(A) = 1 \) が示される。

二重確率行列 \( A \) は、行和が \( 1 \) (\( A\mathbf{e} = 1\mathbf{e} \)) かつ列和が
\( 1 \) (\( A^T\mathbf{e} = 1\mathbf{e} \)) の非負行列である。

既に示したように、固有値 \(\lambda = 1\) が存在するため、スペクトル半径は \( \rho(A) = 1 \) である。
一般に、最大特異値 \( \sigma_1(A) \) はスペクトル半径より小さくなることはないため、\( \sigma_1(A) \ge \rho(A) = 1 \) である。

また、最大特異値は行列の \( \ell_1 \) ノルムと \( \ell_\infty \) ノルムを用いて \( \sigma_1(A) \le \sqrt{\|A\|_1 \|A\|_\infty} \) と評価できる。

二重確率行列の場合、