4.2 Sylvester の慣性律による説明

二分法を Sylvester の慣性律を用いて説明するのは、 森・杉原・室田 [5] による。

線形代数でおなじみの Sylvester の慣性律「行列の符号数は座標 変換で変化しない」を復習しよう。正則行列 $M$ に対して

$$\pi(M) := \mbox{$M$\ の固有値のうち正のものの個数} ,$$

$$\zeta(M) := \mbox{$M$\ の固有値のうち $0$\ のものの個数} ,$$

$$\nu(M) := \mbox{$M$\ の固有値のうち負のものの個数}$$

とおく。

任意に選んだ $\sigma\in\R$ に対して、 $A-\sigma I$ を LDU 分解する、 すなわち

$$A-\sigma I= L D L^T,$$   $$\mbox{$L$\ は下三角行列}$$$$,$$   $$\mbox{$D$\ は対角行列}$$$$.$$

このとき定理から

$$\pi(A-\sigma I)=\pi(D), \quad \zeta(A-\sigma I)=\zeta(D), \quad \nu(A-\sigma I)=\nu(D)$$

であるが、$\pi(D)$ , $\zeta(D)$ , $\nu(D)$ はすぐに分かる。従って、 行列 $A$ の固有値について、任意に与えられた実数 $\sigma$ よりも大きい もの、小さいものの個数が勘定できることになる。

$A$ が三重対角行列であれば、 LDU 分解は $O(n)$ の計算量で済ませられることを注意しておく。