半正定値対称行列の和と固有値を計算したい
Matrix Analysisを読んでいます. 間違っていたら直します.
主張
対称行列$A$, $B$の固有値を小さい順に並べた時, 先頭から$i$番目の固有値を$\lambda_i (A)$, $\lambda_i (B)$などと表すことにする.
このとき, n次の半正定値対称行列$A$, $B$について,
\[
\lambda _i (A+B) \geq \lambda _i (A)
\]
が成り立つ.
観察
$A$, $B$が同時対角化できる場合は自明な結果ですね.
準備
準備0
まずは記法について.
$A$, $B$を半正定値対称行列とします.
対称行列なので固有値は実数.
$A$の固有値を小さい順に$\lambda_1(A), ... , \lambda_n(A)$として, 対応する固有ベクトルを$x_1, ..., x_n$とします.
同様に, $B$の固有値, $A+B$ の固有値を小さい順に並べてから, $i$番目の固有値に対応する固有ベクトルを$y_i$, $z_i$ とします.
準備1
$n$次元ベクトル空間$V$の部分空間$S_1$, $S_2$として,
\[
\dim (S_1 \cap S_2) + \dim (S_1 \oplus S_2) = \dim (S_1) + \dim (S_2)
\]
が成り立ちます.
これより,
\begin{align*}
\dim (S_1 \cap S_2) &= \dim (S_1) + \dim (S_2) - \dim(S_1 \oplus S_2) \\
& \geq \dim (S_1) + \dim (S_2) - n
\end{align*}
ですね.
最後の不等式は, $\dim(S_1 \oplus S_2) \leq n$であることを使いました.
なので,
\[
\dim (S_1) + \dim (S_2) - n \geq 1
\]
ならば, $S_1 \cap S_2$の次元が1以上, すなわち0でない元を持つことになります.
部分空間の数が増えた時には, 同じ事を繰り返すことで,
\[
\sum\limits ^k _{i=1} \dim (S_i) \geq (k-1)n +1
\]
であれば$\bigcap \limits _{i=1}^k S_i$が0でない元を持つ, といえます.
準備2
レイリー商です.
0でないベクトル$x$について,
\[
\frac{x^* A x}{x^*x} \geq \lambda _1 (A)
\]
が成り立ちます.
つまり$A$の最小固有値よりも大きくなります.
$\|x \| = 1$とすると, つまり単位ベクトルとすると,
\[
x^* A x \geq \lambda _1 (A)
\]
です.
また, $i+1$番以上の固有ベクトルから作られる空間だけで考えると,
つまり$x \in \text{span} (x_{i+1}, ... , x_n)$ , $\|x\| = 1$とすると,
\[
x^* A x \geq \lambda_{i+1} (A)
\]
となります. そらそうよ.
証明
それでは本題.
\begin{align*}
\ S_1 &= \text{span} (x_1, ..., x_{i+j}), \\
\ S_2 &= \text{span} (y_1, ..., y_{n-j} ), \\
\ S_3 &= \text{span} (z_{i}, ... , z_n)
\end{align*}
という部分空間を考えます.
共通部分について,
\begin{align*}
\dim (S_1) + \dim (S_2) + \dim (S_3) &= (i+j) + (n-j) + (n-i +1) \\
&= 2n +1
\end{align*}
なので, 準備1での主張から,
$S_1 \cap S_2 \cap S_3$は0でない元をもちます.
ここで$x \in S_1 \cap S_2 \cap S_3$として, さらに$\| x \| = 1$とします.
$x \in S_3 = \text{span}(z_i , ... , z_{n})$であることを利用すると, 準備2のように考えることで,
\begin{align*}
\lambda _i (A+B) \leq x^* (A+B) x
\end{align*}
となります.
次です.
\begin{align*}
\lambda _i (A+B) & = \leq x^* (A+B) x \\
& = x^* A x + x^* B x \\
& \leq \lambda_{i+j} (A) + \lambda _{n-j} (B)
\end{align*}
です.
最後の不等式は,
$x$は$A$の$i+j$番目までの固有値から作られる空間$S_1$にあり,
$B$についても同様に言えるからです.
最終的に得られた不等式は,
\[
\lambda _i (A+B)\leq \lambda_{i+j} (A) + \lambda_{n-j}(B)
\]
です.
もう少し頑張ります.
不等号が逆向きの形が欲しいので, マイナスをかけて式を調整します.
$A$の固有値は$-A$の固有値にマイナスをつけたものです.
固有値の順位は逆になることを踏まえると,
\begin{align*}
- \lambda _{n - i + 1} (A+B) &= \lambda _{i} (-A -B)\\
& \leq \lambda _{i+j} (-A) + \lambda _{n - j }(-B)\\
& = -\lambda _{n - i - j +1}(A) - \lambda_{j+1}(B)
\end{align*}
ですね.
$n-i+1 = i'$, $j+1 = j'$ として, マイナスを取っ払うと,
\[
\lambda _{i'} (A+B)\geq \lambda_{i'-j'+1} (A) + \lambda_{j'}(B)
\]
です. $(j' = 1, ... , i')$
大事なことなので2回言います.
\begin{align*}
\lambda _i (A+B) &\leq \lambda_{i+j} (A) + \lambda_{n-j}(B), \\
\lambda _{i} (A+B)&\geq \lambda_{i-j+1} (A) + \lambda_{j}(B)
\end{align*}
です.
これからは下側の式を使います.
$B$に負の固有値が$\nu$個あるとします.
添字を揃えるために$j =\nu + 1 $として,
\[
\lambda _{i} (A+B)\geq \lambda_{i -\nu} (A) + \lambda_{\nu +1}(B)
\]
となります.
$B$の小さい方から$\nu +1$番目の固有値は非負なので,
\[
\lambda _{i} (A+B)\geq \lambda_{i -\nu} (A)
\]
です. 最後に, $B$が半正定値なら$\nu = 0$なので,
\begin{align}
\lambda _{i} (A+B)\geq \lambda_{i} (A)
\end{align}
です.
感想
遠回りしている気がしますので, ショートカットを考え中です.
最後の式は色々使える気がします. また今度.
