6.4.26 定理（Brualdiの定理）
行列 \( A = [a_{ij}] \in M_n \) が既約であり、かつ \( n \ge 2 \) であるとする。集合 (6.4.19) の境界点 \(\lambda\) が \(A\) の固有値となるのは、すべての非自明な閉路 \(\gamma \in C(A)\) に対して、次の集合
\left\{ z \in \mathbb{C} : \prod_{i \in \gamma} |z - a_{ii}| \le \prod_{i \in \gamma} R_i \right\}
の境界が \(\lambda\) を通る場合に限る。
証明
すべての \(R_i \gt 0\) なので、もしある \(i \in \{1, \ldots, n\}\) に対して \(\lambda = a_{ii}\) ならば、\(\lambda\) は上の集合 (6.4.27) の境界上にはない。したがって、\(\lambda \ne a_{ii}\) がすべての \(i = 1, \ldots, n\) について成り立つと仮定してよい。
さらに、(6.4.18) の証明で用いた記法をそのまま用い、加えて \(\lambda\) が集合 (6.4.19) の境界上にある \(A\) の固有値であると仮定する。このとき、(6.2.3) の証明と同様に、\(\lambda\) は次の不等式を満たさねばならない。
\prod_{i \in \gamma} |\lambda - a_{ii}| \ge \prod_{i \in \gamma} R_i
これはすべての非自明な閉路 \(\gamma \in C(A)\) に対して成り立ち、少なくとも1つの閉路 \(\gamma \in C(A)\) に対して等号が成立する。(6.4.25) の不等式と比較すると、次が得られる。
\prod_{i \in \gamma^*} |\lambda - a_{ii}| = \prod_{i \in \gamma^*} R_i
ここで \(\gamma^*\) は (6.4.18) の証明で構成された特定の閉路である。したがって、(6.4.23) の不等式は等号となり、また (6.4.22) のすべての不等式（すべての \(j \in \{1, \ldots, k\}\) に対して）も等号である。
特に (6.4.22a) が等号であるため、\(\gamma^*\) に含まれる各 \(P_{ij}\) と、\(P_m \in \text{out}(P_{ij})\) であるすべての \(m\) に対して \(|x_m| = |x_{i,j-1}| = c_{i,j+1} = \text{定数}\) が成り立つ。この結論は、条件 (6.4.21) を満たす任意の閉路にも適用できる。
ここで次の集合を定義する。
K = \{ P_i \in \mathcal{G}(A) : |x_m| = c_i = \text{定数},\ \forall m \text{ s.t. } P_m \in \text{out}(P_i) \}
閉路 \(\gamma^*\) に含まれるすべてのノードが \(K\) に属するため、\(K\) は空ではない。次に、グラフ \(\mathcal{G}(A)\) のすべてのノードが \(K\) に属することを示す。
もしあるノード \(P_q \in \mathcal{G}(A)\) が \(K\) に属さないと仮定すると、\(\mathcal{G}(A)\) は強連結なので、\(K\) の各ノードからこの外部ノード \(P_q\) への少なくとも1つの有向路が存在する。その中で最短の有向路を選ぶと、その最初の弧は \(K\) 内のノードから \(K\) に属さないノード \(P_f\) へのものである。
(6.4.18) の証明で用いた順序を再び使い、次のように構成する。まず \(P_f = P_{j_1}\) から始め、\(\text{out}(P_{j_1})\) の中から最大ノード \(P_{j_2}\) を選び、次に \(\text{out}(P_{j_2})\) の中から最大ノード \(P_{j_3}\) を選ぶ、という操作を続ける。各段階で \(\text{out}(P_{j_i})\) は空でないため、最大ノードは条件 (6.4.21)(c) を満たす。
もし途中の段階で、\(K\) に属する最大ノードと属さない最大ノードのどちらかを選べる場合には、\(K\) に属さないものを選ぶ。すべての選択可能な最大ノードが \(K\) に属する場合は、そのうちの1つを選び、\(K\) 内の最短有向路をたどって、最初に \(K\) に属さないノードに到達した時点で再び最大ノード選択を再開する。
集合 \(K\) の定義より、\(K\) 内の任意の有向路では、各ノードがその前のノードの \(\text{out}\) における最大ノードである。これは条件 (6.4.21)(b) である。\(K\) の補集合には有限個のノードしかないため、この構成を続けると、以前に出現したノードが再び現れる最初の最大ノードが補集合内に現れる。この2回出現の間の有向路は非自明な閉路であり、単純でない場合もある。
\(K\) 内に含まれる部分に有限個の閉路があるとしても、それらを取り除くことで単純閉路 \(\gamma^{**}\) が得られる。この \(\gamma^{**}\) は条件 (6.4.21) を満たし、少なくとも1つのノードが \(K\) に属さない。
閉路 \(\gamma^{**}\) は条件 (6.4.21) を満たすため、(6.4.18) の証明において \(\gamma^*\) の代わりに用いることができる。よって、証明の最初の段落と同様の議論から、\(\text{out}(P_{jr})\) に属するすべての \(P_m\) に対して \(|x_m| = c_{jr} = \text{定数}\) が成り立つ。したがって、\(\gamma^{**}\) に含まれるすべてのノードは \(K\) に属する。これは、\(\gamma^{**}\) が少なくとも1つの \(K\) に属さないノードを含むという仮定に矛盾する。
ゆえに、\(\mathcal{G}(A)\) のすべてのノードは \(K\) に属することが示された。
したがって、任意の非自明な閉路 \(\gamma \in \mathcal{G}(A)\) は自動的に条件 (6.4.21) を満たす。ゆえに、(6.4.18) の証明で \(\gamma^*\) の代わりに用いることができ、したがって (6.4.28) においても \(\gamma^*\) の代わりに用いることができる。
以上が示すように、すべての集合 (6.4.27) の境界は \(\lambda\) を通る。これが所要の結論である。
行列解析の総本山
コメント