今回扱う定理について
今回示す問題は、固有値にまつわる有名な定理であり、 Min-Max Theorem と呼ばれている。
Min-Max Theorem:
定理の紹介
はレイリー商と呼ばれている。 証明に入る前にレイリー商の性質について述べる。レイリー商は、引数が 行列 の固有ベクトルの時に、その固有ベクトルに対応する固有値を返す。 このことは簡単に確認できる。固有ベクトル は を満たすことから、
The Proof of Min-Max Theorem
行列 は の実対称行列である。 を定数として考える。証明の流れとしては、二つの不等式を導出し、 導出された不等式を利用して、等号を示す。また、「」と「」に 注意することが重要であり、それがこの定理の本質であると考えている。
A は実対称行列なので、対角化できる。 固有ベクトルを、対応する固有値が小さい方から大きい順に とおくと、 は正規直交基底をなす。
実 次元空間の 次元部分空間 について、 を考えると、 に対して、
を満たす が存在する。 を利用すると、 どんな に対しても (どんな に対しても)、レイリー商は、
\begin{equation}
R_A(v) =
\dfrac{\lambda_1 \alpha_1^2
+ \lambda_2 \alpha_2^2 + \dots \lambda_k \alpha_k^2}
{\alpha_1^2 + \alpha_2^2 + \dots + \alpha_k^2}
\leq \dfrac{\lambda_k(\alpha_1^2 + \alpha_2^2 + \dots + \alpha_k^2)}
{\alpha_1^2 + \alpha_2^2 + \dots + \alpha_k^2}
= \lambda_k
\end{equation}
を満たす。 は任意の において成り立ち、 についての条件も再度まとめると、今までの議論は以下のように書き下すことができる。すなわち、
この式は次の式の十分条件である。 つまり、この式が成り立てば、以下の式も成り立つということである。
\begin{equation} \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \leq \lambda_k \end{equation}
これが、導出しようとしていた不等式の一方になる。
続いて、もう一方についても導出する。 ここで、補題「どんな 次元部分空間 であっても、 基底 で表現できる が存在する」 を証明する。背理法による。もし、ある 次元部分空間 で、そういった が存在しないとすると、 基底 からなる 次元部分空間と 次元部分空間に 共通部分がないということになる。そのことから、全体の空間は少なくとも 次元より大きくなければならないが、 < なので、矛盾。したがって、この補題は示された。
補題を用いて議論を続ける。補題から、 どのような 次元部分空間 においても、 ある で、
\begin{equation} v = \alpha_k {u_k} + \alpha_{k+1} {u_{k+1}} + \dots + \alpha_n {u_n} \end{equation}
を満たす が存在する。 そういった を用いると、レイリー商は、
\begin{align} R_A(v) & = \dfrac{\lambda_k \alpha_k^2 + \lambda_{k+1} \alpha_{k+1}^2 + \dots + \lambda_n \alpha_n^2} {\alpha_k^2 + \alpha_{k+1}^2 + \dots + \alpha_n^2} \\ & \geq \dfrac{\lambda_k(\alpha_k^2 + \alpha_{k+1}^2 + \dots + \alpha_n^2)} {\alpha_k^2 + \alpha_{k+1}^2 + \dots + \alpha_n^2} \\ & = \lambda_k \end{align} つまり、
\begin{align} \max_{v \in (V_k \cap \text{span} \lbrace {u_k}, {u_{k+1}}, \dots, {u_n} \rbrace)} R_A(v) \geq \lambda_k. \label{max 十分} \end{align}
これは、以下を示すのに十分である。(この式が成り立つならば次の式は成り立つ。)
\begin{align} \max_{v \in V_k} R_A(v) \geq \lambda_k. \end{align}
ここで、議論の始めの方で述べたように、 上の式は任意の 次元部分空間 について 成立するので、以下が成り立つ。すなわち、
\begin{equation} \max_{v \in V_k }R_A(v) \geq \lambda_k \Leftrightarrow \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \geq \lambda_k \end{equation}
これが導出したかった二つ目の不等式になる。 今までの議論で得た二つの不等式( と )から、以下が導かれる。すなわち、
\begin{align} & \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \leq \lambda_k \text{ かつ } \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \geq \lambda_k \\ \Leftrightarrow & \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) = \lambda_k \end{align} となり、Min-Max Theorem は示された。 以上。
終わりに
結構丁寧に論を運んだ自信がある。英語版 wikipedia よりもかなり丁寧に書いた。 Cauchy's Interlace Theorem もレイリー商の不等式評価を利用して証明することができる。 レイリー商、名前もかっこいいし、性質も Cool だし、憧れます。 (もちろん、レポートに丸写ししてはなりません、、!)