（8.7.P6）
問題
\( | \| \cdot \| | \) を、\( \mathbb{R}^n \) 上の置換不変ノルム \( \| \cdot \| \) によって誘導される行列ノルムとする。
このとき、任意の二重確率行列 \( A \in M_n \) に対して \( | \|A\| | = 1 \) が成り立つことを示せ。
ヒント
\(Ae = e ⇒ | \| A\| | \geq 1\)
\( |\|P\|| = 1（すべての置換行列Pに対して）⇒ | \|A\| | \leq 1\)
解答例
問題の理解と前提
\(\mathbb{R}^n\) 上の置換不変ノルム (permutation invariant norm) \(\|\cdot\|\) とは、任意の
\(x = (x_1, \dots, x_n) \in \mathbb{R}^n\) と任意の置換 \(\sigma \in S_n\) に対して、
\|(x_1, \dots, x_n)\| = \|(x_{\sigma(1)}, \dots, x_{\sigma(n)})\|
を満たすノルムの事である。
このノルムによって誘導される行列ノルム (induced matrix norm) \(|\| \cdot \||\) は、
| \|A\| | = \sup_{x \in \mathbb{R}^n, x \neq 0} \frac{\|Ax\|}{\|x\|} = \sup_{\|x\|=1} \|Ax\|
と定義される。
二重確率行列 (doubly stochastic matrix) \(A \in M_n\) とは、成分が非負であり、すべての行和および列和が \(1\) である行列の事である。
証明
目標は、任意の二重確率行列 \(A\) に対して \(|\|A\|| = 1\) を示すことである。
1. \(|\|A\|| \le 1\) の証明
Birchoff の定理により、二重確率行列 \(A\) は置換行列(\(P_k\)) の凸結合として表される。
A = \sum_{k=1}^{m} \alpha_k P_k \quad (\alpha_k \ge 0, \sum_{k=1}^m \alpha_k = 1)
ノルム \(\|\cdot\|\) は置換不変であるため、任意の \(x \in \mathbb{R}^n\) と置換行列 \(P_k\) に対して、\(\|P_k x\| = \|x\|\) が成り立つ。
三角不等式とノルムの斉次性より、
\|Ax\| = \left\| \sum_{k=1}^{m} \alpha_k (P_k x) \right\| \le \sum_{k=1}^{m} \alpha_k \|P_k x\| = \sum_{k=1}^{m} \alpha_k \|x\| = \left( \sum_{k=1}^{m} \alpha_k \right) \|x\| = \|x\|
したがって、\(\|Ax\| \le \|x\|\) である。
誘導される行列ノルムの定義から、
| \|A\| | = \sup_{x \in \mathbb{R}^n, x \neq 0} \frac{\|Ax\|}{\|x\|} \le \sup_{x \in \mathbb{R}^n, x \neq 0} \frac{\|x\|}{\|x\|} = 1
すなわち、\(|\|A\|| \le 1\) が示された。
2. \(\|\!|A\|\!| \ge 1\) の証明
二重確率行列 \(A\) の行和は \(1\) であるため、成分がすべて \(1\) のベクトル \(\mathbf{1} = (1, 1, \dots, 1)^T \in \mathbb{R}^n\) に対して、\(A\mathbf{1} = \mathbf{1}\) が成り立つ。
\(\mathbf{1}\) は零ベクトルではないので、誘導される行列ノルムの定義から、
| \|A\| | \ge \frac{\|A\mathbf{1}\|}{\|\mathbf{1}\|} = \frac{\|\mathbf{1}\|}{\|\mathbf{1}\|} = 1
すなわち、\(|\|A\|| \ge 1\) が示された。
結論
(1) \(|\|A\|| \le 1\)
(2) \(|\|A\|| \ge 1\)
上記 (1) および (2) より、任意の二重確率行列 \(A \in M_n\) に対して
| \|A \| | = 1
が成り立つ。\(\square\)
行列解析の総本山
総本山の目次📚
記号の意味🔎
コメント