ゲルシュゴリンの定理，あるいは線形代数祭の講評

はじめに

この記事は，友人が企画した「 線形代数祭 」というイベントに寄せた問題の解説である．

問題

$\boldsymbol{A}=(a_{i\mskip2mu j})$を$n$次複素正方行列とする．$0\leq t\leq 1$とし，$\boldsymbol{F}(t)=(f_{i\mskip2mu j}(t))$を
$$ f_{i\mskip2mu j}(t) = \begin{cases}a_{i\mskip2mu j} & (i=j),\\ ta_{i\mskip2mu j} & (i\neq j)\end{cases} $$
と定める．

1. 複素数$\lambda$が$\boldsymbol{F}(t)$の固有値であるとき，ある$i\in\lbrace 1,2,\dotsc,n\rbrace$が存在して
   $$ \lvert\lambda-a_{i\mskip2mu i}\rvert \leq t\sum_{j\neq i}\lvert a_{i\mskip2mu j}\rvert $$
   を満たすことを示せ．

2. 複素数平面上の閉円板$D_{i}(t)$を
   $$ D_{i}(t) = \Biggl\lbrace z\in\mathbb{C}\Biggm\vert\lvert z-a_{i\mskip2mu i}\rvert \leq t\sum_{j\neq i}\lvert a_{i\mskip2mu j}\rvert\Biggr\rbrace $$
   で定める．$D_{1}(1),D_{2}(1),\dotsc,D_{n}(1)$がどの2つも共通部分を持たないとき，$\boldsymbol{A}$は対角化可能であることを示せ．

なお，次の事実は証明せずに使ってよい．多項式関数$w=f(z)$が，複素数平面の円周$C$上に零点を持たないとき，$C$の内側にある$f(z)$の零点の個数$N$は重複度を込めて
$$ N = \frac{1}{2\pi\mathrm{i}}\oint_{C}\frac{1}{w}\frac{\mathrm{d}w}{\mathrm{d}z}\,\mathrm{d}z $$
である．ただし，積分路の向きは反時計回りにとる．

解答 (1)

$\boldsymbol{x}=(\begin{matrix}x_{1} & x_{2} & \cdots & x_{n}\end{matrix})^{\mathsf{T}}$を$\boldsymbol{F}(t)$の固有値$\lambda$に属する固有ベクトルとすると，$\lambda\boldsymbol{x}=\boldsymbol{F}(t)\boldsymbol{x}$より，すべての$i\in\lbrace 1,2,\dotsc,n\rbrace$について
$$ \lambda x_{i} = \sum_{j=1}^{n}f_{i\mskip2mu j}(t)x_{j} = a_{i\mskip2mu i}x_{i}+\sum_{j\neq i}ta_{i\mskip2mu j}x_{j} $$
である．よって，$i$の値を$\lvert x_{i}\rvert=\max\lbrace\lvert x_{1}\rvert,\lvert x_{2}\rvert,\dotsc,\lvert x_{n}\rvert\rbrace$となるように選ぶと
$$ \lvert(\lambda-a_{i\mskip2mu i})x_{i}\rvert \leq t\sum_{j\neq i}\lvert a_{i\mskip2mu j}x_{j}\rvert \leq t\lvert x_{i}\rvert\sum_{j\neq i}\lvert a_{i\mskip2mu j}\rvert $$
となる．$\boldsymbol{x}\neq\boldsymbol{0}$より$x_{i}\neq 0$だから，不等式を$\lvert x_{i}\rvert$で割れば示す式が得られる．

解答 (2)

各$D_{i}(1)$の半径を$r_{i}$とおく．仮定から，$i\neq j$のとき$r_{i}+r_{j}\lt\lvert a_{i\mskip2mu i}-a_{j\mskip2mu j}\rvert$なので
$$ \min_{1\leq i\lt j\leq n}\biggl(\frac{\lvert a_{i\mskip2mu i}-a_{j\mskip2mu j}\rvert-r_{i}-r_{j}}{4}\biggr) $$
は正数である．この値を$\delta$とおくと，$i\lt j$のとき
$$ \begin{aligned} (r_{i}+\delta)+(r_{j}+\delta) &\leq r_{i}+r_{j}+\frac{\lvert a_{i\mskip2mu i}-a_{j\mskip2mu j}\rvert-r_{i}-r_{j}}{2}\\ &= \frac{\lvert a_{i\mskip2mu i}-a_{j\mskip2mu j}\rvert+r_{i}+r_{j}}{2}\\ &\lt\lvert a_{i\mskip2mu i}-a_{j\mskip2mu j}\rvert \end{aligned} $$
だから，円板$E_{i}=\lbrace z\in\mathbb{C}\mid\lvert z-a_{i\mskip2mu i}\rvert\leq r_{i}+\delta\rbrace$はどの2つも共通部分を持たない．

境界$\partial E_{i}$はどの円板$D_{1}(1),D_{2}(1),\dotsc,D_{n}(1)$とも交わらないので，小問1より$\partial E_{i}$に$\boldsymbol{F}(t)$の固有値は属さない．すなわち，$\boldsymbol{F}(t)$の固有多項式
$$ p(t;z) = \det(z\boldsymbol{I}-\boldsymbol{F}(t)) $$
は$\partial E_{i}$上に零点を持たない．よって，$E_{i}$に属する$p(t;z)$の零点の個数$N$は
$$ N = \frac{1}{2\pi\mathrm{i}}\oint_{\partial E_{i}}\biggl(\frac{1}{p(t;z)}\frac{\mathrm{d}}{\mathrm{d}z}p(t;z)\biggr)\,\mathrm{d}z $$
である．右辺は$t$の連続関数であり，$N$は整数なので，$N$の値は$t$によらず一定である．よって
$$ N = \frac{1}{2\pi\mathrm{i}}\oint_{\partial E_{i}}\biggl(\frac{1}{p(0;z)}\frac{\mathrm{d}}{\mathrm{d}z}p(0;z)\biggr)\,\mathrm{d}z $$
だが，$p(0;z)=\det(z\boldsymbol{I}-\boldsymbol{F}(0))$の零点で$E_{i}$に属するものは$a_{i\mskip2mu i}$だけだから，$N=1$である．

以上により，$p(1;z)$の零点，すなわち$\boldsymbol{A}$の固有値は，すべての$E_{i}$にちょうど1つ属する．よって，$\boldsymbol{A}$は対角化可能である．

講評

この問題はゲルシュゴリンの定理 (Gershgorin circle theorem) と呼ばれる定理を証明させる問題である．ゲルシュゴリンの定理は，固有値の精度保証付き数値計算の基本となる定理である（ 大石，2010 ）．

ゲルシュゴリンの定理は非常に有名だが，にもかかわらず，厳密な論証が載っている文献はあまり多くない．本問の誘導とは異なる証明も含めて，網羅的なサーベイが ( Chi-Kwong Li & Fuzhen Zhang, 2019 ) にある．