レイリー商

レイリー商  

院試の過去問を解いていて，おもしろい話題を見つけたので$${\LaTeX}$$の練習も兼ねて記録する．

定義１．$${A}$$を$${n}$$次の実対称行列，$${\bm{x}\in\mathbb{R}^n}$$，$${\bm{x}\neq\bm{0}}$$とする．このとき，
$${\displaystyle f(\bm{x})=\frac{\bm{x}^\top A\bm{x}}{\bm{x}^\top \bm{x}}}$$で定まる$${f:\mathbb{R}^n\backslash \{\bm{0}\}\rightarrow \mathbb{R}}$$をレイリー商という．

レイリー商の分子は$${A}$$の二次形式であり，分母は$${\bm{x}^\top\bm{x}=\|\bm{x}\|^2}$$より，$${\bm{x}}$$のノルムの二乗である．このレイリー商の最大値・最小値について，非常に興味深い定理が存在する．前提として，$${A}$$は実対称行列より，固有値はすべて実数である．

定理２．定義１における$${\displaystyle f(\bm{x})=\frac{\bm{x}^\top A\bm{x}}{\bm{x}^\top \bm{x}}\quad(\bm{x}\neq 0)}$$の最大値，最小値は，それぞれ$${A}$$の最大の固有値，最小の固有値となる．

証明　$${A}$$の固有値を$${\lambda_1,\lambda_2,\cdots,\lambda_n}$$とする．$${A}$$は実対称行列より，ある直交行列$${P}$$を用いて対角化できる：

$$
P^{-1}AP=B
$$

ただし，$${\displaystyle B=\begin{pmatrix} \lambda_1\\ &\lambda_2& &  \\ & & \ddots \\ &  & & \ddots \\ & & & &\lambda_n \end{pmatrix}}$$である．
ここで，$${\bm{y}=\begin{pmatrix}y_1\\y_2\\ \vdots\\y_n\end{pmatrix}\in\mathbb{R}^n}$$として，$${\bm{y}=P^{-1}\bm{x}}$$という変換を考える．$${\bm{x}\neq{0}}$$より，$${\bm{y}\neq{0}}$$である．
このとき，$${P}$$は直交行列より，$${P^\top P=E}$$($${E}$$は単位行列)であるから，

$$
\begin{align}\notag
\bm{x}^\top\bm{x}&=(P\bm{y})^\top P\bm{y}\\
\notag &= \bm{y}^\top P^\top P\bm{y}\\
\notag &= \bm{y}^\top\bm{y}\\
\notag &=y_1^2+y_2^2+\cdots+y_n^2
\end{align}
$$

であり，

$$
\begin{align}
\notag\bm{x}^\top A\bm{x}&= (P\bm{y})^\top PBP^{-1}(P\bm{y}) \\
\notag &= \bm{y}^\top(P^\top P)B(P^{-1}P)\bm{y} \\
\notag &= \bm{y}^\top B\bm{y} \\
\notag &=\lambda_1y_1^2+\lambda_2y_2^2+\cdots+\lambda_ny_n^2
\end{align}
$$

となる．

$$
\notag \displaystyle \therefore \frac{\bm{x}^\top A\bm{x}}{\bm{x}^\top \bm{x}}=\frac{\lambda_1y_1^2+\lambda_2y_2^2+\cdots+\lambda_ny_n^2}{ y_1^2+y_2^2+\cdots+y_n^2}
$$

ここで，$${\lambda_{\max}=\max\{\lambda_1,\lambda_2,\cdots,\lambda_n\}}$$，$${\lambda_{\min}=\min\{\lambda_1,\lambda_2,\cdots,\lambda_n\}}$$とおくと，

$$
\notag \displaystyle
\lambda_{\min}=\frac{\lambda_{\min}\left(y_1^2+y_2^2+\cdots+y_n^2\right)}{y_1^2+y_2^2+\cdots+y_n^2}\leq \frac{\lambda_1y_1^2+\lambda_2y_2^2+\cdots+\lambda_ny_n^2}{ y_1^2+y_2^2+\cdots+y_n^2}\leq \frac{\lambda_{\max}\left(y_1^2+y_2^2+\cdots+y_n^2\right)}{y_1^2+y_2^2+\cdots+y_n^2}=\lambda_{\max}
$$

となる．また，等号成立における$${\bm{x}}$$はそれそれ$${\lambda_{\max},\lambda_{\min}}$$に対応する固有ベクトル$${\bm{x}_{\max},\bm{x}_{\min}}$$となる．実際，

$$
\displaystyle
\begin{align}
\notag f(\bm{x}_{\max})&=\frac{\bm{x}_{\max}^\top \left(A\bm{x}_{\max}\right)}{\bm{x}_{\max}^\top\bm{x}_{\max}}\\
\notag &=\frac{\bm{x}_{\max}^\top\left( \lambda_{\max}\bm{x}_{\max}\right)}{\bm{x}_{\max}^\top\bm{x}_{\max}}\\
\notag &=\frac{\lambda_{\max}\bm{x}_{\max}^\top\bm{x}_{\max}}{\bm{x}_{\max}^\top\bm{x}_{\max}}\\
\notag &= \lambda_{\max}
\end{align}
$$

である．$${\bm{x}_{\min}}$$のときも同様．
以上より，題意は示された．$${\blacksquare}$$

さて，$${\bm{0}}$$でない$${\bm{x\in \mathbb{R}^n}}$$について，$${\bm{x}^\top\bm{x}=\|\bm{x}\|^2=1}$$とすると，レイリー商の最大値・最小値問題は，ノルム制約の下での$${A}$$の二次形式の最大値・最小値問題に帰着される．なお，最大・最小となるような$${\bm{x}}$$は，それぞれ$${A}$$の最大・最小固有値に対応する固有ベクトルのうち，ノルムが$${1}$$のものとなる．そして，このことはラグランジュの未定乗数法を用いても導出することができる．

定理３．$${A}$$を$${n}$$次の実対称行列，$${\bm{x}\in\mathbb{R}^n，\bm{x}\neq0}$$とする．$${\|\bm{x\|^2}=\bm{x}^\top \bm{x}=1}$$のもとでの二次形式$${\bm{x}^\top A\bm{x}}$$の最大値・最小値は，それぞれ$${A}$$の最大・最小の固有値であり，そのときの$${x}$$は，それぞれの固有値に対応する固有ベクトルのうち，ノルムが$${1}$$のものとなる．

証明　ラグランジュの未定乗数法により示す．なお，ラグランジュの未定乗数法により得られる点はあくまで極値の候補点であるが，拘束条件である$${\|\bm{x}\|^2=1}$$は有界閉集合より，最大値・最小値が存在する．よって，極大値・極小値がそのまま最大値・最小値となる．
ラグランジュ関数を，$${\mathfrak{L}(\bm{x},\lambda)=\bm{x}^\top A\bm{x}-\lambda\left(\bm{x}^\top\bm{x}-1\right)}$$と定めると，１階条件より，

$$
2A\bm{x}-2\lambda\bm{x}=0\qquad\therefore A\bm{x}=\lambda\bm{x}
$$

ゆえに，極値において未定乗数$${\lambda}$$は$${A}$$の固有値に一致し，そのときの$${\bm{x}}$$は$${\lambda}$$に対応する固有ベクトルのうち，ノルムが$${1}$$のものとなる．よって，$${A}$$の固有値のうち最大のものを$${\lambda_{\max}}$$，最小のものを$${\lambda_{\min}}$$とすると，

$$
\lambda_{\min}=\lambda_{\min}\bm{x}^\top\bm{x}=\bm{x}^\top\left(\lambda_{\min}\bm{x}\right)\leq\bm{x}^\top(\lambda\bm{x})= \bm{x}^\top A\bm{x},\\
\bm{x}^\top A\bm{x}=\bm{x}^\top(\lambda\bm{x})\leq\bm{x}^\top(\lambda_{\max}\bm{x})\leq\lambda_{\max}\bm{x}^\top\bm{x}=\lambda_{\max}
$$

となり，題意は示された．$${\blacksquare}$$

レイリー商は，数値解析において固有値の解析的評価をする際によく出てくるようである．また，グラスマン多様体といった多様体における最適化理論や，グラフ理論との関係もあるようである．さらに勉強を深めていければと思う．