6.4.18.定理 6.4.18（Brualdi の定理）
定理 6.4.18（Brualdi）。\( A = [a_{ij}] \in M_n \) とし、\( n \ge 2 \) と仮定する。もし \(A\) が弱既約（weakly irreducible）であるならば、\(A\) のすべての固有値は次の集合に含まれる：
\bigcup_{\gamma \in C(A)}
\left\{ z \in \mathbb{C} :
\prod_{P_i \in \gamma} |z - a_{ii}| \le
\prod_{P_i \in \gamma} R_i^{\ast}
\right\}
ここで、記号の意味を説明する。もし \(\gamma = P_{i_1} P_{i_2}, \ldots, P_{i_k} P_{i_{k+1}}\) が非自明なサイクル（\(P_{i_{k+1}} = P_{i_1}\)）であるならば、上式の和集合中の対応する集合は、ちょうど \(k\) 個の因子をもつ積で定義される。添字 \(i\) は \(i_1, \ldots, i_k\) の値を取る。
証明：\(A\) が弱既約であることから、削除された各行和は正である。したがって、もし \(\lambda\) が \(A\) の固有値であり、ある \(i = 1, \ldots, n\) に対して \(\lambda = a_{ii}\) であるならば、\(\lambda\) は集合 (6.4.19) の内部に含まれる。
以降では、\(\lambda\) が \(A\) の固有値であり、すべての \(i = 1, \ldots, n\) に対して \(\lambda \ne a_{ii}\) であると仮定する。非零ベクトル \(x = [x_i] \in \mathbb{C}^n\) に対して \(A x = \lambda x\) が成り立つとする。
このとき、有向グラフ \(\Xi\) のノード上に次のように前順序 \(R\) を定義する：
P_i R P_j \iff |x_i| \le |x_j|
以下の3つの性質を満たすサイクル \(\gamma^\ast\) が \(\Xi(A)\) に存在することを主張する：
(a) \(\gamma^\ast = P_{i_1} P_{i_2}, P_{i_2} P_{i_3}, \ldots, P_{i_k} P_{i_{k+1}}
\text{ は非自明サイクルで } k \ge 2,~ P_{i_{k+1}} = P_{i_1}\).
(b) 各 ( j = 1, \ldots, k ) に対して、ノード \( P_{i_{j+1}} \) は \(\Xi_{\text{out}}(P_{i_j})\) 内で最大ノード、すなわち
\( |x_{i_{j+1}}| \ge |x_m| \) （ただし \(P_m \in \Xi_{\text{out}}(P_{i_j})\)）を満たす。
(c) すべての \(x_{i_j} \ne 0, j = 1, \ldots, k\)
\text{(a)} \gamma^\ast = P_{i_1} P_{i_2}, P_{i_2} P_{i_3}, \ldots, P_{i_k} P_{i_{k+1}} \text{ は非自明サイクルで } \\
k \ge 2,~ P_{i_{k+1}} = P_{i_1}. \\
\text{(b)} \text{各 (} j = 1, \ldots, k \text{に対して、ノード} P_{i_{j+1}} \text{ は} \Xi_{\text{out}}(P_{i_j})) \text{内で最大ノード、すなわち} \\
|x_{i_{j+1}}| \ge |x_m| \text{（ただし \(P_m \in \Xi_{\text{out}}(P_{i_j})\)）を満たす。}
\\
\text{(c)~ すべての} x_{i_j} \ne 0, ~ j = 1, \ldots, k.
もし \(\gamma^\ast\) が上記 (6.4.21) の条件を満たすサイクルであるならば、恒等式 \(A x = \lambda x\) より、各 \( j = 1, \ldots, k \) について次が成り立つ：
(\lambda - a_{i_j i_j}) x_{i_j}
= \sum_{m \ne i_j} a_{i_j m} x_m
= \sum_{P_m \in \Xi_{\text{out}}(P_{i_j})} a_{i_j m} x_m
したがって、
|\lambda - a_{i_j i_j}| |x_{i_j}|
\le \sum_{P_m \in \Xi_{\text{out}}(P_{i_j})} |a_{i_j m}| |x_m|
\le \sum_{P_m \in \Xi_{\text{out}}(P_{i_j})} |a_{i_j m}| |x_{i_{j+1}}|
= R_{i_j}^\ast |x_{i_{j+1}}|
これを \(\gamma^\ast\) 上のすべてのノードについて掛け合わせると、
\prod_{j=1}^k |\lambda - a_{i_j i_j}| |x_{i_j}|
\le \prod_{j=1}^k R_{i_j}^\ast |x_{i_{j+1}}|
ここで \(P_{i_{k+1}} = P_{i_1}\) なので \(|x_{i_{k+1}}| = |x_{i_1}|\) が成り立つ。したがって、
\prod_{j=1}^k |x_{i_j}| = \prod_{j=1}^k |x_{i_{j+1}}| \ne 0
よって、これらを消去して次を得る：
\prod_{P_i \in \gamma^\ast} |\lambda - a_{ii}|
\le
\prod_{P_i \in \gamma^\ast} R_i^\ast
\(\gamma^\ast\) は \(\Xi(A)\) の非自明サイクルであるため、固有値 \(\lambda\) は集合 (6.4.19) に含まれる。
次に、条件 (6.4.21) を満たすサイクル \(\gamma^\ast\) が存在することを示す。任意の \(x_i \ne 0\) なる添字 \(i\) を取る。グラフ \(\Xi(A)\) は弱連結であるから、\(\Xi_{\text{out}}(P_i)\) は空でない。
さらに、\(\lambda - a_{ii} \ne 0\) なので、
0 = (\lambda - a_{ii}) x_i - \sum_{j \ne i} a_{ij} x_j
= \sum_{P_j \in \Xi_{\text{out}}(P_i)} a_{ij} x_j
したがって、\(\Xi_{\text{out}}(P_i)\) の中には少なくとも1つ、対応する固有ベクトル成分 \(x_j \ne 0\) のノード \(P_j\) が存在する。
\(P_{i_1} = P_i\) とし、\(\Xi_{\text{out}}(P_{i_1})\) の中で最大ノード \(P_{i_2}\) を選ぶ。このとき \(|x_{i_2}| \ge |x_j| > 0\) が成り立つ。
同様の構成を繰り返すと、有限個のノードしか存在しないため、ある段階で既に出現したノード \(P_{i_p}\) が再び現れる。このとき、
\gamma^\ast = P_{i_p} P_{i_{p+1}}, P_{i_{p+1}} P_{i_{p+2}}, \ldots, P_{i_{q-1}} P_{i_q}
は条件 (6.4.21) の3つすべてを満たすサイクルである。■
なお、\(A\) が既約である場合、Brualdi の定理はさらに鋭い形をとる。このとき、それは (6.2.26) の一般化された Brauer 版（式 (6.4.7)）となる。
行列解析の総本山
コメント