PRML　演習問題 2.18（難問）　解答

## はじめに
本記事は, 機械学習の教科書の決定版ともいえる, **Christopher Bishop先生**による[**『Pattern Recognition and Machine Learning （パターン認識と機械学習）』**](https://www.microsoft.com/en-us/research/people/cmbishop/prml-book/), 通称**PRML**の演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する[生物測定学研究室](https://www.ut-biomet.org/)の輪読会で**PRML**を取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, [PRML　演習問題　解答集　まとめ](https://qiita.com/Lab_of_Biomet/items/15e38ca34fafa8176d89)をご覧ください.


## 問題
> 実対称行列 $\mathbf { \Sigma }$ を考える. この行列について
$$
\begin {align*}
\boldsymbol { \Sigma } \mathbf { u } _ { i } = \lambda _ { i } \mathbf { u } _ { i }
\tag{2.45}
\end{align*}
$$
の固有値の方程式が成立する． この式の複素共役から, もとの式を引いた後, 固有ベクトル $\mathbf { u } _ { i }$ との内積をとることで, 固有値が実数となることを示せ. 同様に, $\mathbf { \Sigma }$ の対称性を用いて, 2つの固有ベクトル $\mathbf { u } _ { i }$ と $\mathbf { u } _ { j }$ が, $\lambda _ { j } \neq \lambda _ { i }$ であれば, 直交することを示せ. 最後に, たとえいくつかの固有値が $0$ であっても, 一般性を失うことなく, 
$$
\begin {align*}
\mathbf { u } _ { i } ^ { \mathrm { T } } \mathbf { u } _ { j } = I _ { i j }
\tag{2.46}
\end{align*}
$$
を満たす, 正規直交となるように固有ベクトル集合を選ぶことが可能であることを示せ.




## 問題の解釈
とりあえず, この問題は以下の3つの問題を証明することになります.

1. **対称行列の固有値は実数**となる. （以下, 2.18-1）
2. 異なる固有値に対応する**固有ベクトル同士は直交**する. （以下, 2.18-2）
3. いくつかの**固有値が0であっても, 正規直交となるように固有ベクトル集合を選ぶ**ことができる. （以下, 2.18-3）

このあと, これらを順番に証明していきます.


## 問題 2.18-1 の証明
> 実対称行列 $\mathbf { \Sigma }$ を考える. この行列について
$$
\begin {align*}
\boldsymbol { \Sigma } \mathbf { u } _ { i } = \lambda _ { i } \mathbf { u } _ { i }
\tag{2.45}
\end{align*}
$$
の固有値の方程式が成立する． この式の複素共役から, もとの式を引いた後, 固有ベクトル $\mathbf { u } _ { i }$ との内積をとることで, 固有値が実数となることを示せ.

### 複素共役とは？
そもそも**複素共役**とは, ある複素数 $z$ を, 実数 $a$, $b$ を用いて
 
```math
\begin {align*}
z = a + i b 
\tag{2.18.1}
\end{align*}
```

のように表しとき,

```math
\begin {align*}
\bar { z } = a - i b 
\tag{2.18.2}
\end{align*}
```

が, $z$ の複素共役となります.
よって行列 $\mathbf { A }$ が以下のようであったとき, 

```math
\begin {align*}
\mathbf { A } = \left[ \begin{array} { c c } 1 & - 1 - i \\ 1 + i & i \end{array} \right]
\tag{2.18.3}
\end{align*}
```
複素共役行列は,

```math
\begin {align*}
\bar { \mathbf { A } } = \left[ \begin{array} { c c } 1 & - 1 + i \\ 1 - i & - i \end{array} \right]
\tag{2.18.4}
\end{align*}
```

のように表されます. 
これに関連するもう一つ重要な行列として, **随伴行列**とよばれる行列が存在し, これは複素共役転置として表される行列で, 例えば $\mathbf { A }$ の随伴行列は,


```math
\begin {align*}
\mathbf { A } ^ \dagger = \left[ \begin{array} { c c } 1 & 1 - i \\ - 1 + i & - i \end{array} \right]
\tag{2.18.5}
\end{align*}
```

のように表されます.

### 証明
まず, (2.45) 式の両辺に左側から $\mathbf { u } _ { i }$ の複素共役 $\mathbf { u } _ { i } ^ \dagger$ をかけた式を用意します.

```math
\begin {align*}
\mathbf { u } _ { i } ^ \dagger \boldsymbol { \Sigma } \mathbf { u } _ { i } = \lambda _ { i } \mathbf { u } _ { i } ^ \dagger \mathbf { u } _ { i }
\tag{2.18.6}
\end{align*}
```

また, もう一つの式として, (2.45) 式の両辺の複素共役転置をとって, 右側から $\mathbf { u } _ { i }$ をかけることを考えます.

```math
\begin {align*}
\mathbf { u } _ { i } ^ \dagger \boldsymbol { \Sigma } ^ \dagger \mathbf { u } _ { i } = \bar { \lambda } _ { i }  \mathbf { u } _ { i } ^ \dagger \mathbf { u } _ { i }
\tag{2.18.7}
\end{align*}
```

ここで, $\boldsymbol { \Sigma }$ は実対称行列であるため, $\boldsymbol { \Sigma } = \boldsymbol { \Sigma } ^ \dagger$ であることを考慮に入れて, (2.18.6), (2.18.7)式を比較すると, 

```math
\begin {align*}
0 = \left ( \bar { \lambda } _ { i } - \lambda _ { i } \right ) \mathbf { u } _ { i } ^ \dagger \mathbf { u } _ { i }
\tag{2.18.8}
\end{align*}
```

が得られるため, $\bar { \lambda } _ { i } = \lambda _ { i }$ であり, $\lambda _ { i }$ が実数であることがわかります.


## 問題2.18-2 の証明
> $\mathbf { \Sigma }$ の対称性を用いて, 2つの固有ベクトル $\mathbf { u } _ { i }$ と $\mathbf { u } _ { j }$ が, $\lambda _ { j } \neq \lambda _ { i }$ であれば, 直交することを示せ.


次に, (2.45)式の両辺に左側から $\mathbf { u } _ { j } ^ \mathrm { T }$ をかけることを考えます.

```math
\begin {align*}
\lambda _ { i } \mathbf { u } _ { j } ^ \mathrm { T } \mathbf { u } _ { i } & = \mathbf { u } _ { j } ^ \mathrm { T } \boldsymbol { \Sigma } \mathbf { u } _ { i } \\
& = \left ( \boldsymbol { \Sigma } \mathbf { u } _ { j } \right ) ^ \mathrm { T } \mathbf { u } _ { i } \\
& = \lambda _ { j } \mathbf { u } _ { j } ^ \mathrm { T } \mathbf { u } _ { i }
\tag{2.18.9}
\end{align*}
```

(2.18.9)式は以下の３つの場合に場合分けして考えることができます.

1. $\lambda _ { j } \neq \lambda _ { i }$
2. $\lambda _ { j } = \lambda _ { i } \neq 0$
3. $\lambda _ { j } = \lambda _ { i } = 0$

さて, この問題 2.18-2においては, 1. $\lambda _ { j } \neq \lambda _ { i }$ の場合を考えればよく, このときは, (2.18.9)式より, $\mathbf { u } _ { j } ^ \mathrm { T } \mathbf { u } _ { i } = 0$ となるため, 異なる固有値に対応する固有ベクトル同士が直交することがわかります.

---

（これ以降自信ありません。。。）


ちなみに, 2. $\lambda _ { j } = \lambda _ { i } \neq 0$ のときは, 固有ベクトル $\mathbf { u } _ { i }$, $\mathbf { u } _ { j }$ の任意の線形結合に関して,

```math
\begin {align*}
\boldsymbol { \Sigma } \left ( a \mathbf { u } _ { i } + b \mathbf { u } _ { j } \right)
& = a \lambda _ { i } \mathbf { u } _ { i } + b \lambda _ { j } \mathbf { u } _ { j } \\
& = \lambda \left ( a \mathbf { u } _ { i } + b \mathbf { u } _ { j } \right)
\tag{2.18.10}
\end{align*}
```

となるため, $\mathbf { u } _ { i }$, $\mathbf { u } _ { j }$ の任意の線形結合

```math
\begin {align*}
& \mathbf { u } _ { \alpha }  = a \mathbf { u } _ { i } + b \mathbf { u } _ { j }, \\
& \mathbf { u } _ { \beta } = c \mathbf { u } _ { i } + d \mathbf { u } _ { j }
\tag{2.18.11}
\end{align*}
```

は互いに直交し, (2.46) 式を満たすことがわかります.


## 問題 2.18-3 の証明
> 最後に, たとえいくつかの固有値が $0$ であっても, 一般性を失うことなく, 
$$
\begin {align*}
\mathbf { u } _ { i } ^ { \mathrm { T } } \mathbf { u } _ { j } = I _ { i j }
\tag{2.46}
\end{align*}
$$
を満たす, 正規直交となるように固有ベクトル集合を選ぶことが可能であることを示せ.

もしいくつかの $\lambda _ { i } = 0$ ならば, 対称行列 $\mathbf { \Sigma }$ は特異な行列 (逆行列をもたない) になり, $\mathbf { u } _ { i }$ は $\mathbf { \Sigma }$ の零空間 ($\mathbf { A } \mathbf { x } = \mathbf { 0 }$ を満たすようなベクトル $\mathbf { x }$ の集合のこと) を成すことがわかります. この場合, $\mathbf { u } _ { i }$ は実対称行列 $\mathbf { \Sigma }$ の行空間 (行列の各行ベクトルの線型結合として起こり得るすべてのものからなる集合) に射影される固有ベクトルに直交となり, かつ正規化条件 $|| \mathbf { u } _ { i } || = 1$ を満たすようます. したがって, (2.46) 式が満たされることがわかります. なお, 0である固有値が複数ある場合でも, これらの固有値に対応する固有ベクトルが零空間に存在する限り,　その零空間内で[グラム・シュミットの正規直交化法](https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%A0%E3%83%BB%E3%82%B7%E3%83%A5%E3%83%9F%E3%83%83%E3%83%88%E3%81%AE%E6%AD%A3%E8%A6%8F%E7%9B%B4%E4%BA%A4%E5%8C%96%E6%B3%95)を用いれば, (2.46)式を満たすような固有ベクトルを任意に選ぶことができます。