MinMax Theorem の証明。レイリー商と対称行列の固有値についての考察
今回扱う定理について
今回示す問題は、固有値にまつわる有名な定理であり、 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 だし、憧れます。 （もちろん、レポートに丸写ししてはなりません、、！）
