# 譜分解

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}$

from lingeo import random_int_list
from linspace import QR

## Main idea

Continuing the introduction of the spectral decomposition in 313, this section will provide the theoretical foundation of it.

Let $A$ be an $n\times n$ real symmetric matrix.
Recall that the spectral theorem ensures the following equivalent properties.

- There is an orthogonal matrix $Q$ such that $Q\trans AQ$ is diagonal.
- There is an orthonormal basis $\{\bv_1,\ldots, \bv_n\}$ of $\mathbb{R}^n$ such that $A\bv_i = \lambda_i\bv_i$ for some $\lambda_i$ for each $i = 1,\ldots, n$.

Here $Q$ is the matrix whose columns are $\{\bv_1, \ldots, \bv_n\}$.

Equivalently, we may write

$$
A = QDQ^\top =
\begin{bmatrix}
| & ~ & | \\
{\bf v}_1 & \cdots & {\bf v}_n \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
\lambda_1 & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \lambda_n \\
\end{bmatrix}
\begin{bmatrix}
- & {\bf v}_1^\top & - \\
~ & \vdots & ~\\
- & {\bf v}_n^\top & -
\end{bmatrix} =
\sum_{i = 1}^n \lambda_i {\bf v}_i{\bf v}_i^\top.
$$

Suppose $\{\lambda_1,\ldots,\lambda_n\}$ only has $q$ distinct values $\{\mu_1,\ldots, \mu_q\}$.
For each $j = 1,\ldots, q$, we may let $\displaystyle P_j = \sum_{\lambda_i = \mu_j} {\bf v}_i{\bf v}_i^\top$.
Thus, we have the following.

##### Spectral theorem (projection version)

Let $A$ be an $n\times n$ symmetric matrix.
Then there are $q$ distinct values $\mu_1,\ldots, \mu_q$ and $q$ projection matrices $P_1,\ldots, P_q$ such that

- $A = \sum_{j=1}^q \mu_j P_j$,
- $P_i^2 = P_i$ for any $i$,
- $P_iP_j = O$ for any $i$ and $j$, and
- $\sum_{j=1}^q P_j = I_n$.

## Side stories

- $P_i$ as a polynomial of $A$
- orthogonal projection matrix
- eigenvector-eigenvalue identity

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = None

while True:
    L = matrix(3, random_int_list(9, 2))
    eigs = random_int_list(2)
    if L.is_invertible() and eigs[0] != eigs[1]:
        break
    
Q,R = QR(L)
for j in range(3):
    v = Q[:,j]
    length = sqrt((v.transpose() * v)[0,0])
    Q[:,j] = v / length

eigs.append(eigs[-1])
D = diagonal_matrix(eigs)
A = Q * D * Q.transpose()

pretty_print(LatexExpr("A ="), A)
pretty_print(LatexExpr("A = Q D Q^{-1} ="), Q, D, Q.transpose())

if print_ans:
    print("eigenvalues of A:", eigs)
    print("eigenvectors of A = columns of Q")
    pretty_print(LatexExpr("A ="), 
                 eigs[0], Q[:,0]*Q[:,0].transpose(), 
                 LatexExpr("+"), 
                 eigs[1], Q[:,1:]*Q[:,1:].transpose())

##### Exercise 1(a)

求 $A$ 的所有特徵值及其對應的特徵向量。
**答:**

藉由 `seed = 0` 得到

$$
A = \begin{bmatrix}
\frac{8}{3} & \frac{1}{3} & \frac{1}{3} \\
\frac{1}{3} & \frac{8}{3} & -\frac{1}{3} \\
\frac{1}{3} & -\frac{1}{3} & \frac{8}{3} \\
\end{bmatrix}.
$$
找 $p_A(x) = \det(A-xI) = -(x-2)(x-3)^2$ ，若 $p_A(x) = 0$ ，即可得 $\spec(A) = \{2,3,3\}$ 。

##### Exercise 1(b)

求 $A$ 的譜分解。

**[由温佳明同學提供]**
藉由 `seed = 0` 得到

$$
A = \begin{bmatrix}
\frac{8}{3} & \frac{1}{3} & \frac{1}{3} \\
\frac{1}{3} & \frac{8}{3} & -\frac{1}{3} \\
\frac{1}{3} & -\frac{1}{3} & \frac{8}{3} \\
\end{bmatrix}.
$$
找 $p_A(x) = \det(A-xI) = -(x-2)(x-3)^2$ ，若 $p_A(x) = 0$ ，即可得 $\spec(A) = \{2,3,3\}$ 。

找每一個 $\ker(A - \lambda I)$ 的基底，且每一個 $\ker(A - \lambda I)$ 的基底必要垂直且長度為 $1$。

$\lambda = 2$,
$A-\lambda I = \begin{bmatrix}
\frac{2}{3} & \frac{1}{3}&\frac{1}{3} \\
\frac{1}{3} & \frac{2}{3}& -\frac{1}{3} \\
\frac{1}{3} & -\frac{1}{3}& \frac{2}{3} \\
\end{bmatrix}$ , $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}-1\\1\\1\end{bmatrix}\right\}=\vspan\left\{\begin{bmatrix}\frac{-1}{\sqrt3} \\\frac{1}{\sqrt3}\\ \frac{1}{\sqrt3}\\\end{bmatrix}\right\}$

$\lambda = 3$,
$A - \lambda I = \begin{bmatrix}
-\frac{1}{3} & \frac{1}{3}&\frac{1}{3} \\
\frac{1}{3} & -\frac{1}{3}& -\frac{1}{3} \\
\frac{1}{3} & -\frac{1}{3}& -\frac{1}{3} \\
\end{bmatrix}$, $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}1\\1\\0\end{bmatrix} 、\begin{bmatrix}1\\-1\\2\end{bmatrix}\right\}= \vspan\left\{\begin{bmatrix}\frac{1}{\sqrt2} \\\frac{1}{\sqrt2}\\0\\\end{bmatrix} 、\begin{bmatrix}\frac{1}{\sqrt6} \\\frac{-1}{\sqrt6}\\ \frac{2}{\sqrt6}\\\end{bmatrix}\right\}.$

建構一個 $S$ 由每一個 $\ker(A - \lambda I)$ 的基底所組成

$$S = \begin{bmatrix}
\frac{-1}{\sqrt3} & \frac{1}{\sqrt2} & \frac{1}{\sqrt6} \\
\frac{1}{\sqrt3}& \frac{1}{\sqrt2}& \frac{-1}{\sqrt6} \\
\frac{1}{\sqrt3} & 0 & \frac{2}{\sqrt6} \\
\end{bmatrix}.
$$

根據 $\spec(A) = \{2,3,3\}$,
$$A = 2P_1 + 3P_2.
$$
令 $\bu_1,\bu_2,\bu_3$ 為 $S$ 的各向量，則取 $P_1 = \bu_1\bu_1\trans$ 及 $P_2 = \bu_2\bu_2\trans + \bu_3\bu_3\trans$
$P_1 = \begin{bmatrix}\frac{-1}{\sqrt3} \\\frac{1}{\sqrt3}\\\frac{1}{\sqrt3}\\\end{bmatrix}\begin{bmatrix}\frac{-1}{\sqrt3} &\frac{1}{\sqrt3}&\frac{1}{\sqrt3}\\\end{bmatrix}= \begin{bmatrix}
\frac{1}{3} & - \frac{1}{3} & - \frac{1}{3}\\
-\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
-\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\end{bmatrix}.$

$P_2= \begin{bmatrix}\frac{1}{\sqrt2} \\\frac{1}{\sqrt2}\\0\\\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt2} &\frac{1}{\sqrt2}&0\\\end{bmatrix}+\begin{bmatrix}\frac{1}{\sqrt6} \\\frac{-1}{\sqrt6}\\\frac{2}{\sqrt6}\\\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt6} &\frac{-1}{\sqrt6}&\frac{2}{\sqrt6}\\\end{bmatrix} = \begin{bmatrix}
\frac{1}{2} &\frac{1}{2} & 0\\
\frac{1}{2} &\frac{1}{2} & 0\\
0 & 0 & 0\\
\end{bmatrix}+ \begin{bmatrix}
\frac{1}{6} &-\frac{1}{6} & \frac{1}{3}\\
-\frac{1}{6} &\frac{1}{6} & -\frac{1}{3}\\
\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}=\begin{bmatrix}
\frac{2}{3} &\frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} &\frac{2}{3}& -\frac{1}{3}\\
\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}$
故 $A = 2\begin{bmatrix}
\frac{1}{3} & - \frac{1}{3} & - \frac{1}{3}\\
-\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
-\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\end{bmatrix} + 3\begin{bmatrix}
\frac{2}{3} &\frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} &\frac{2}{3}& -\frac{1}{3}\\
\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}.$

## Exercises

##### Exercise 2

求以下矩陣的譜分解。

##### Exercise 2(a)

$$
A = \begin{bmatrix}
0 & 1 \\
1 & 0
\end{bmatrix}.
$$

**[由温佳明同學提供]**
找 $p_A(x) = \det(A-xI) = (x+1)(x-1)$ ， 若 $p_A(x) = 0$ ，即可得 $\spec(A) = \{1,-1\}$ 。
找每一個 $\ker(A - \lambda I)$ 的基底，且每一個 $\ker(A - \lambda I)$ 的基底必要垂直且長度為 $1$。

$\lambda = 1$ ,
$A-\lambda I = \begin{bmatrix}
-1 & 1 \\
1 & -1
\end{bmatrix}$ , $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}1\\1\end{bmatrix}\right\} = \vspan\left\{\begin{bmatrix}\frac{1}{\sqrt2}\\\frac{1}{\sqrt2}\end{bmatrix}\right\}.$

$\lambda = -1$ ,
$A-\lambda I = \begin{bmatrix}
1 & 1 \\
1 & 1
\end{bmatrix}$ , $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}1\\-1\end{bmatrix}\right\} = \vspan\left\{\begin{bmatrix}\frac{1}{\sqrt2}\\\frac{-1}{\sqrt2}\end{bmatrix}\right\}.$

建構一個 $S$ 由每一個 $\ker(A - \lambda I)$ 的基底所組成
$S= \begin{bmatrix}
\frac{1}{\sqrt2} & \frac{1}{\sqrt2} \\
\frac{1}{\sqrt2} & \frac{-1}{\sqrt2}
\end{bmatrix}.$

根據 $\spec(A) = \{1,-1\}$ ,
$$A = 1P_1 + (-1)P_2.
$$

令 $\bu_1,\bu_2$ 為 $S$ 的各向量，則取 $P_1 = \bu_1\bu_1\trans$ 及 $P_2 = \bu_2\bu_2\trans$。

$P_1 = \begin{bmatrix}\frac{1}{\sqrt2} \\\frac{1}{\sqrt2}\\\end{bmatrix}$$\begin{bmatrix}\frac{1}{\sqrt2} &\frac{1}{\sqrt2}\\\end{bmatrix}= \begin{bmatrix}\frac{1}{2} & \frac{1}{2}\\\frac{1}{2} & \frac{1}{2}
\end{bmatrix}.$
$P_2 = \begin{bmatrix}\frac{1}{\sqrt2} \\\frac{-1}{\sqrt2}\\\end{bmatrix}$$\begin{bmatrix}\frac{1}{\sqrt2} &\frac{-1}{\sqrt2}\\\end{bmatrix}=\begin{bmatrix}\frac{1}{2} & \frac{-1}{2}\\\frac{-1}{2} & \frac{1}{2}\end{bmatrix}.$

故 $A = 1\begin{bmatrix}\frac{1}{2} & \frac{1}{2}\\\frac{1}{2} & \frac{1}{2}\end{bmatrix} + (-1)\begin{bmatrix}\frac{1}{2} & \frac{-1}{2}\\\frac{-1}{2} & \frac{1}{2}\end{bmatrix}=\begin{bmatrix}
0 & 1 \\
1 & 0\end{bmatrix}.$

##### Exercise 2(b)

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \\
\end{bmatrix}.
$$

**[由温佳明同學提供]**
找 $p_A(x) = \det(A-xI) = x^2(-x+3)$ ，若 $p_A(x) = 0$ ，即可得 $\spec(A) = \{0,0,3\}$ 。
找每一個 $\ker(A - \lambda I)$ 的基底，且每一個 $\ker(A - \lambda I)$ 的基底必要垂直且長度為 $1$。

$\lambda = 3$ ,
$A-\lambda I = \begin{bmatrix}
-2 & 1 & 1 \\
1 & -2 & 1 \\
1 & 1 & -2 \\
\end{bmatrix}$ , $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}1\\1\\1\end{bmatrix}\right\}=\vspan\left\{\begin{bmatrix}\frac{1}{\sqrt3} \\\frac{1}{\sqrt3}\\ \frac{1}{\sqrt3}\\\end{bmatrix}\right\}$
$\lambda = 0.$
$A - \lambda I = \begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \\\end{bmatrix}$, $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}-1\\1\\0\end{bmatrix},\begin{bmatrix}1\\1\\-2\end{bmatrix}\right\}= \vspan\left\{\begin{bmatrix}\frac{-1}{\sqrt2} \\\frac{1}{\sqrt2}\\0\\\end{bmatrix},\begin{bmatrix}\frac{1}{\sqrt6} \\\frac{1}{\sqrt6}\\ \frac{-2}{\sqrt6}\\\end{bmatrix}\right\}.$

建構一個 $S$ 由每一個 $\ker(A - \lambda I)$ 的基底所組成
$$S = \begin{bmatrix}
\frac{1}{\sqrt3} & \frac{-1}{\sqrt2} & \frac{1}{\sqrt6} \\
\frac{1}{\sqrt3}& \frac{1}{\sqrt2}& \frac{1}{\sqrt6} \\
\frac{1}{\sqrt3} & 0 & \frac{-2}{\sqrt6} \\
\end{bmatrix}.$$

根據 $\lambda = 0,0,3$
$$A=3P_1+0P_2.
$$

令 $\bu_1,\bu_2,\bu_3$ 為 $S$ 的各向量，則取 $P_1 = \bu_1\bu_1\trans$ 及 $P_2 = \bu_2\bu_2\trans + \bu_3\bu_3\trans$
$P_1 = \begin{bmatrix}\frac{1}{\sqrt3} \\\frac{1}{\sqrt3}\\\frac{1}{\sqrt3}\\\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt3} &\frac{1}{\sqrt3}&\frac{1}{\sqrt3}\\\end{bmatrix}= \begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\end{bmatrix}.$

$P_2 = \begin{bmatrix}\frac{-1}{\sqrt2} \\\frac{1}{\sqrt2}\\0\\\end{bmatrix}\begin{bmatrix}\frac{-1}{\sqrt2} &\frac{1}{\sqrt2}&0\\\end{bmatrix}+\begin{bmatrix}\frac{1}{\sqrt6} \\\frac{1}{\sqrt6}\\\frac{-2}{\sqrt6}\\\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt6} &\frac{1}{\sqrt6}&\frac{-2}{\sqrt6}\\\end{bmatrix} = \begin{bmatrix}
\frac{1}{2} &\frac{-1}{2} & 0\\
\frac{-1}{2} &\frac{1}{2} & 0\\
0 & 0 & 0\\
\end{bmatrix}+ \begin{bmatrix}
\frac{1}{6} &\frac{1}{6} & -\frac{1}{3}\\
\frac{1}{6} &\frac{1}{6} & -\frac{1}{3}\\
-\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}=\begin{bmatrix}
\frac{2}{3} &-\frac{1}{3} &-\frac{1}{3}\\
-\frac{1}{3} &\frac{2}{3}& -\frac{1}{3}\\
-\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}$
故 $A = 3\begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\end{bmatrix} + 0\begin{bmatrix}
\frac{2}{3} &-\frac{1}{3} &-\frac{1}{3}\\
-\frac{1}{3} &\frac{2}{3}& -\frac{1}{3}\\
-\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}=\begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \\
\end{bmatrix}.$

##### Exercise 2(c)

$$
A = \begin{bmatrix}
2 & -1 & -1 \\
-1 & 2 & -1 \\
-1 & -1 & 2
\end{bmatrix}.
$$

**[由温佳明同學提供]**
找 $p_A(x) = \det(A-xI) = -x(x-3)^2$ ，若 $p_A(x) = 0$ ，即可得 $\spec(A) = \{0,3,3\}$ 。
找每一個 $\ker(A - \lambda I)$ 的基底，且每一個 $\ker(A - \lambda I)$ 的基底必要垂直且長度為 $1$。

$\lambda = 0$ ,
$A-\lambda I = \begin{bmatrix}
2 & -1 & -1 \\
-1 & 2 & -1 \\
-1 & -1 & 2 \\
\end{bmatrix}$ , $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}1\\1\\1\end{bmatrix}\right\}=\vspan\left\{\begin{bmatrix}\frac{1}{\sqrt3} \\\frac{1}{\sqrt3}\\ \frac{1}{\sqrt3}\\\end{bmatrix}\right\}.$

$\lambda = 3$ ,
$A-\lambda I = \begin{bmatrix}
-1 & -1 & -1 \\
-1 & -1 & -1 \\
-1 & -1 & -1 \\
\end{bmatrix}$ , $\ker(A-\lambda I) = \vspan\left\{\begin{bmatrix}-1\\1\\0\end{bmatrix}、\begin{bmatrix}1\\1\\-2\end{bmatrix}\right\}= \vspan\left\{\begin{bmatrix}\frac{-1}{\sqrt2} \\\frac{1}{\sqrt2}\\0\\\end{bmatrix} 、\begin{bmatrix}\frac{1}{\sqrt6} \\\frac{1}{\sqrt6}\\ \frac{-2}{\sqrt6}\\\end{bmatrix}\right\}.$

建構一個 $S$ 由每一個 $\ker(A - \lambda I)$ 的基底所組成
$$S = \begin{bmatrix}
\frac{1}{\sqrt3} & \frac{-1}{\sqrt2} & \frac{1}{\sqrt6} \\
\frac{1}{\sqrt3}& \frac{1}{\sqrt2}& \frac{1}{\sqrt6} \\
\frac{1}{\sqrt3} & 0 & \frac{-2}{\sqrt6} \\
\end{bmatrix}.
$$

根據$\lambda = 0,3,3$
$$A=0P_1+3P_2.
$$
令 $\bu_1,\bu_2,\bu_3$ 為 $S$ 的各向量，則取 $P_1 = \bu_1\bu_1\trans$ 及 $P_2 = \bu_2\bu_2\trans + \bu_3\bu_3\trans.$

$P_1 = \begin{bmatrix}\frac{1}{\sqrt3} \\\frac{1}{\sqrt3}\\\frac{1}{\sqrt3}\\\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt3} &\frac{1}{\sqrt3}&\frac{1}{\sqrt3}\\\end{bmatrix}= \begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\end{bmatrix}.$
$P_2 = \begin{bmatrix}\frac{-1}{\sqrt2} \\\frac{1}{\sqrt2}\\0\\\end{bmatrix}\begin{bmatrix}\frac{-1}{\sqrt2} &\frac{1}{\sqrt2}&0\\\end{bmatrix}+\begin{bmatrix}\frac{1}{\sqrt6} \\\frac{1}{\sqrt6}\\\frac{-2}{\sqrt6}\\\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt6} &\frac{1}{\sqrt6}&\frac{-2}{\sqrt6}\\\end{bmatrix} = \begin{bmatrix}
\frac{1}{2} &\frac{-1}{2} & 0\\
\frac{-1}{2} &\frac{1}{2} & 0\\
0 & 0 & 0\\
\end{bmatrix}+ \begin{bmatrix}
\frac{1}{6} &\frac{1}{6} & -\frac{1}{3}\\
\frac{1}{6} &\frac{1}{6} & -\frac{1}{3}\\
-\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}=\begin{bmatrix}
\frac{2}{3} &-\frac{1}{3} &-\frac{1}{3}\\
-\frac{1}{3} &\frac{2}{3}& -\frac{1}{3}\\
-\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}$
故 $A = 0\begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
\end{bmatrix} + 3\begin{bmatrix}
\frac{2}{3} &-\frac{1}{3} &-\frac{1}{3}\\
-\frac{1}{3} &\frac{2}{3}& -\frac{1}{3}\\
-\frac{1}{3}& -\frac{1}{3}& \frac{2}{3}\\
\end{bmatrix}=\begin{bmatrix}
2 & -1 & -1 \\
-1 & 2 & -1 \\
-1 & -1 & 2 \\
\end{bmatrix}.$

##### Exercise 3

令 $\bu$ 為一長度為 $1$ 的實向量。
令 $P = \bu\bu\trans$。

##### Exercise 3(a)

說明 $P$ 為垂直投影到 $\vspan\{\bu\}$ 的投影矩陣。

:::warning

- [x] 我沒看出哪一部份有解釋到 "投影"
:::

$Ans:$

令 $\bu = \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix}$。那麼，
$$
\begin{array}{l}
P = \bu\bu\trans &= \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} \begin{pmatrix} a_1 ,\cdots, a_n \end{pmatrix} =
\begin{bmatrix}
a_1^2 & a_1a_2 & \cdots & a_1a_n \\
a_2a_1 & a_2^2 & \cdots & a_2a_n \\
\vdots & & \ddots & \vdots \\
a_na_1 & a_na_2 & \cdots & a_n^2
\end{bmatrix} \\
&=\begin{bmatrix}
a_1\begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} & a_2\begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} & \cdots & a_n\begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix}
\end{bmatrix} = \begin{bmatrix}
| & | & ~ & | \\
a_1\bu & a_2\bu & \cdots & a_n\bu \\
| & | & ~ & |
\end{bmatrix}.
\end{array}
$$

如此，對於每一個 $\bx = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}$，我們都有
$$
P\bx = a_1x_1\bu + a_2x_2\bu + \cdots + a_nx_n\bu = \inp{\bx}{\bu}\bu.
$$
因此我們得知 $P$ 為垂直投影到 $\vspan\{\bu\}$ 的投影矩陣，
並且我們從中可以看到 $P$ 為對稱矩陣。

##### Exercise 3(b)

證明 $\tr(P\trans P) = \rank(P) = 1$。

$Ans:$

藉由 $P$ 的形式我們可以很清楚的知道 $\rank(P) = 1$。而
$$
P\trans P =
\begin{bmatrix}
-& a_1\bu\trans & - \\
-& a_2\bu\trans & -\\
~ & \vdots & ~ \\
-& a_n\bu\trans & -
\end{bmatrix}
\begin{bmatrix}
| & | & ~ & | \\
a_1\bu & a_2\bu & \cdots & a_n\bu \\
| & | & ~ & |
\end{bmatrix}=
\begin{bmatrix}
a_1^2\bu\trans \bu & a_1a_2\bu\trans \bu & \cdots & a_1a_n\bu\trans \bu \\
a_2a_1\bu\trans \bu & a_2^2\bu\trans \bu & \cdots & a_2a_n\bu\trans \bu \\
\vdots & ~ & \ddots & \vdots \\
a_na_1\bu\trans \bu & a_na_2\bu\trans \bu & \cdots & a_n^2\bu\trans \bu
\end{bmatrix} = P.
$$

由於 $\bu\trans\bu = a_1^2 + \cdots + a_n^2 = 1$，故
$$
\tr(P\trans P) = a_1^2\bu\trans \bu + \cdots + a_n^2\bu\trans \bu = a_1^2 + \cdots + a_n^2 = 1.
$$
所以 $\tr(P\trans P) = \rank(P) = 1$。

:::info
也可以用 $\tr(AB) = \tr(BA)$ 來說明。
:::

##### Exercise 4

令 $\{\bu_1, \ldots, \bu_d\}$ 為一群互相垂直且長度均為 $1$ 的實向量。
令 $P = \bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans$。

##### Exercise 4(a)

說明 $P$ 為垂直投影到 $\vspan\{\bu_1,\ldots, \bu_d\}$ 的投影矩陣。

:::warning

- [x] 集合 $\subseteq$ 集合，元素 $\in$ 集合；所以要寫「令 $\bu_1, \ldots, \bu_d \in \mathbb R^n$」或「令 $\{\bu_1, \ldots, \bu_d\} \subseteq \mathbb R^n$」
- [x] 這裡的 $a_1,\ldots,a_d$ 沒解釋到什麼事情？
- [ ] 如果有兩個向量 $\{\bx,\by\}$ 把另一向量投影到 $\bx$ 及投影到 $\by$ 後相加，會等於這向量投影到 $\vspan\{\bx,\by\}$ 嗎？
:::

$Ans:$

假設有一向量 $\bu$ 投影到 $\bx$ 及 $\by$ 上分別為 $k\bx$，$m\by$，其中 $m，k \in \mathbb R$，$\bx，\by \in \mathbb R^n$ 且不為線性相依。那投影後的向量相加就會是 $k\bx+m\by$，也就會是我們將 $\bu$ 投影到 $\vspan{\{\bx,\by}\}$ 上。

那麼，令 $\{\bu_1, \ldots, \bu_d\} \subseteq \mathbb R^n$。

根據 **Exercise 3**，我們知道 $\bu\bu\trans$ 會垂直投影到 $\vspan{\{\bu}\}$ 上，我們可以利用這個性質以及矩陣的分配律得到
$$
P\bx = (\bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans)\bx = \bu_1\bu_1\trans\bx + \cdots + \bu_d\bu_d\trans\bx.
$$
這裡 $\bx \in \mathbb R^n$。

因此我們可以看出 $P$ 為垂直投影到 $\vspan\{\bu_1,\ldots, \bu_d\}$ 的投影矩陣。

##### Exercise 4(b)

證明 $\tr(P\trans P) = \rank(P) = d$。

:::warning

- [x] 第一段沒有解釋為什麼 $\{\bu_1,\ldots,\bu_d\}$ 獨立可以得到 $\rank(P) = d$。這應該跟 $\Col(P)$ 有關。
- [x] 後半段可以再簡單一點，因為 $\bu_1\bu\trans\bu_1\bu_1\trans = \bu_1\bu_1\trans$
:::

$Ans:$

由於我們知道 $P$ 會把向量投影到 $\Col(P)$ 上，而 $\Col(P)$ 由 $\{\bu_1, \ldots, \bu_d\}$ 組成，又這些向量正交，所以這些向量為線性獨立。由此我們可以確定 $\rank(P) = d$。

另外，從 **Exercise 3(a)** 中我們也能知道這邊的 $P$ 也是一個對稱矩陣。所以
$$
P\trans P = P^2 = (\bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans)(\bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans).
$$
利用他們互相垂直的性質，得到

$$
(\bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans)(\bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans) = (\bu_1\bu_1\trans)^2 + \cdots + (\bu_d\bu_d\trans)^2 = \bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans.
$$
所以，$\tr(P\trans P)$ 就會是這些矩陣的對角線相加後出來的數字，而 **Exercise 3(a)** 告訴我們對於每一個 $\bu\bu\trans$，$\tr(\bu\bu\trans) = 1$。因此，$\tr(P\trans P) = d$。
得證 $\tr(P\trans P) = \rank(P) = d$。

##### Exercise 5

一個 **垂直投影矩陣** 指的是一個可以被垂直矩陣對角化且特徵值均是 $1$ 或 $0$ 的矩陣。

令 $P$ 為一實方陣。
證明以下敘述等價：

1. $P$ 為一垂直投影矩陣。
2. $P$ 是對稱矩陣，且 $P^2 = P$。

:::warning

- [x] 可是 $P$ 不見得只投到一維空間；$1\Rightarrow 2$ 的部份可以直接用投影公式
:::

$Ans:$
設矩陣 $A$ 的行為空間 $S$ 中的垂直基底且矩陣 $P$ 垂直投影到 $S$，
由投影公式得知 $P = A(A\trans A)^{-1}A\trans$，
其中 $A\trans A = I_n$，
則 $P$ 可以化簡為 $P = AA\trans$，
將 $P$ 平方得
$$\begin{aligned}
P^2 &= (AA\trans)(AA\trans)\\
&= A(A\trans A)A\trans\\
&= AA\trans = P.
\end{aligned}
$$
故 $1.\Rightarrow2.$ 得證。

$2.\Rightarrow1.$

因為 $P$ 為一個對稱矩陣，
我們可以設 $P = QDQ\trans$，
其中 $Q$ 為一個垂直矩陣、$D$ 為一個對角矩陣，
可以算出 $P^2 = PP = (QDQ\trans)(QDQ\trans) = QD^2Q\trans$，
又 $P^2 = P$，
所以 $D^2 = D$，
為滿足上述條件，
$D$ 主對角線上的元素必須為 $1$ 或 $0$，
得到 $P$ 為一個可以被垂直矩陣對角化且特徵值均是 $1$ 或 $0$ 的矩陣，
故 $2.\Rightarrow1.$ 得證。

##### Exercise 6

雖然譜分解裡的條件沒有明顯說明 $P_i$ 是垂直投影矩陣，
依照以下步驟證明下列條件

1. $A = \sum_{j=1}^q \mu_j P_j$,
2. $P_i^2 = P_i$ for any $i$,
3. $P_iP_j = O$ for any $i$ and $j$, and
4. $\sum_{j=1}^q P_j = I_n$.

足以說明每一個 $P_i$ 都是垂直投影矩陣。

##### Exercise 6(a)

驗證

$$
\begin{aligned}
I &= P_1 + \cdots + P_q, \\
A &= \mu_1 P_1 + \cdots + \mu_q P_q, \\
A^2 &= \mu_1^2 P_1 + \cdots + \mu_q^2 P_q, \\
~ & \vdots \\
A^{q-1} &= \mu_1^{q-1} P_1 + \cdots + \mu_q^{q-1} P_q.
\end{aligned}
$$

並利用拉格朗日多項式來說明對每一個 $i = 1,\ldots, q$ 來說，
都找得到一些係數 $c_0,\ldots,c_{q-1}$ 使得 $P_i = c_0 I + c_1 A + \cdots + c_{q-1} A^{q-1}$。
因此每一個 $P_i$ 都是對稱矩陣。

:::warning

- [x] 沒辦法這樣寫矩陣喔... 這題要參考 311-5 或是 510-6
:::

**答:**
令 $f_1$ 使得 $f(\mu_1) = 1$ 且對 $i = 2,\ldots,q$ 都有 $f_1(\mu_i) = 0$.
將 $f_1$ 展開寫成
$f_1 = \alpha_0I + \alpha_1A + \cdots + \alpha_{q-1}A^{q-1}$。則
$$
\begin{aligned}
\alpha_0(&P_1 + \cdots + P_q &= I)\\
\alpha_1(&\mu_1 P_1 + \cdots + \mu_q P_q &= A)\\
&\vdots\\
+)\alpha_{q-1}(&\mu_1^{q-1} P_1 + \cdots + \mu_q^{q-1} P_q &= A^{q-1})\\
\hline
&f(\mu_1)P_1+\cdots+f(\mu_q)P_q&=
\alpha_0I + \alpha_1A + \cdots + \alpha_{q-1}A^{q-1}.
\end{aligned}
$$
\
而對 $i = 2,3,4,\ldots,q$ 都有 $f_1(\mu_i) = 0$。
所以 $f_1(\mu_1)P_1= \alpha_0I + \alpha_1A + \cdots + \alpha_{q-1}A^{q-1}$。
其中 $f(\mu_1) = 1$，推得
$$
P_1= \alpha_0I + \alpha_1A + \cdots + \alpha_{q-1}A^{q-1}.
$$

\
令 $f_2$ 使得 $f_2(\mu_2) = 1$ 且對 $i = 1,3,4,\ldots,q$ 都有 $f_2(\mu_i) = 0$。
將 $f_2$ 展開寫成
$\beta_0I + \beta_1A + \cdots + \beta_{q-1}A^{q-1}$。則

$$
\begin{aligned}
\beta_0(&P_1 + \cdots + P_q &= I)\\
\beta_1(&\mu_1 P_1 + \cdots + \mu_q P_q &= A)\\
&\vdots\\
+)\beta_{q-1}(&\mu_1^{q-1} P_1 + \cdots + \mu_q^{q-1} P_q &= A^{q-1})\\
\hline
&f(\mu_1)P_1+\cdots+f(\mu_q)P_q&=
\beta_0I + \beta_1A + \cdots + \beta_{q-1}A^{q-1}.
\end{aligned}
$$
\
而對 $i = 1,3,4,\ldots,q$ 都有 $f(\mu_i) = 0$。
所以 $f(\mu_2)P_2= \beta_0I + \beta_1A + \cdots + \beta_{q-1}A^{q-1}$。 其中 $f(\mu_2) = 1$，推得
$$
P_2= \beta_0I + \beta_1A + \cdots + \beta_{q-1}A^{q-1}.
$$

用以上觀點推廣對於任意 $i = 1,2,\ldots,q$，都有 $f_i(x)$ 使得
$$
P_i = c_0 I + c_1 A + \cdots + c_{q-1} A^{q-1}.
$$

其中 $c_0,\ldots,c_{q-1} \in \mathbb R$。故得證。

##### Exercise 6(b)

說明每一個 $P_i$ 都是垂直投影矩陣。

**[由黃佑祥同學提供]**
藉由 **Exercise 6(a)** 可以得出 $P_i$ 是對稱矩陣，
而題目已經假設 $P_i^2 = P_i$。

再加上 **Exercise 5** 的等價敘述，由於 $P_i$ 為一個對稱矩陣且 $P_i^2 = P_i$ ，所以 $P_i$ 是一個垂直投影矩陣。

##### Exercise 7

依照以下步驟證明下述定理。

##### Eigenvector-eigenvalue identity
若 $A$ 為一 $n\times n$ 實對稱矩陣。
其特徵值為 $\lambda_1,\ldots,\lambda_n$ 且某一個 $\lambda_i$ 只出現一次沒有重覆。
令 $\bv_1,\ldots, \bv_n$ 為其相對應的特徵向量，且其形成一垂直標準基底。

$$
(A - \lambda_i I)\adj = \left(\prod_{j\neq i}(\lambda_j - \lambda_i)\right)\bv_i\bv_i\trans.
$$

##### Exercise 7(a)

說明當 $x$ 不為 $A$ 的特徵值時，

$$
\begin{aligned}
(A - xI)\adj &= \det(A - xI) \times \sum_{j = 1}^n (\lambda_j - x)^{-1}\bv_j\bv_j\trans \\
&= \sum_{j = 1}^n p_i(x) \bv_j\bv_j\trans,
\end{aligned}
$$

其中

$$
p_j(x) = \prod_{k \neq j}(\lambda_k - x).
$$

:::warning
原本題目有錯 $\bv_i\bv_i\trans$ 應該是 $\bv_j\bv_j\trans$

- [x] 由伴隨矩陣的定義得知 --> 由伴隨矩陣的性質得知

:::

解：
由伴隨矩陣的性質得知，

$$
\begin{aligned}
(A - xI)\adj & \times (A - xI) = \det(A - xI)I
\end{aligned}.
$$

因為 $x$ 不為 $A$ 的特徵值，所以 $(A - xI)$ 為可逆矩陣，且有下式，

$$
\begin{aligned}
(A - xI)\adj & = \det(A - xI) \times (A - xI)^{-1}
\end{aligned},
$$

在將 $(A - xI)^{-1}$ 對角化之前，我們先探討 $A$ 與 $(A - xI)$ 對角化的關係。

將 $A$ 對角化，求
$$ \begin{aligned} \det(A - yI) = 0 \end{aligned}
$$
的解；將 $(A - xI)$ 對角化，求
$$
\begin{aligned}
\det((A - xI)-zI) = \det(A - (x+z)I) = \det(A - yI) = 0
\end{aligned}
$$

的解，其中等式成立時，$y$ 與 $z$ 分別為 $A$ 與 $(A - xI)$ 的特徵值，
故由上述得知，兩矩陣的特徵值有關係式 $z = y - x$，
且兩矩陣可以找到相同的特徵向量將其對角化。

接下來，假設 $A = QDQ^{-1}$，$D$ 為一對角矩陣，由上述推論得知，
我們有 $(A - xI) = QD'Q^{-1}$，並且可以推得 $(A - xI)^{-1} = QD'^{-1}Q^{-1}$，
其中

$$
A = QDQ^{-1} =
\begin{bmatrix}
| & ~ & | \\
{\bf v}_1 & \cdots & {\bf v}_n \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
\lambda_1 & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \lambda_n
\end{bmatrix}
\begin{bmatrix}
- & {\bf v}_1 & - \\
~ & \vdots & ~ \\
- & {\bf v}_n & -
\end{bmatrix},
$$

$$
(A - xI)^{-1} = QD'^{-1}Q^{-1} =
\begin{bmatrix}
| & ~ & | \\
{\bf v}_1 & \cdots & {\bf v}_n \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\lambda_1 - x} & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \frac{1}{\lambda_n - x}
\end{bmatrix}
\begin{bmatrix}
- & {\bf v}_1 & - \\
~ & \vdots & ~ \\
- & {\bf v}_n & -
\end{bmatrix}.
$$

故對於任意給定的 $x$，皆存在 $n$ 個相應的 $\frac{1}{\lambda_i - x}$，對於 $i= 1,2, \cdots ,n$，使得

$$
\begin{aligned}
(A - xI)\adj &= \det(A - xI) \times (A - xI)^{-1} \\
&= \det(A - xI) \times
\begin{bmatrix}
| & ~ & | \\
{\bf v}_1 & \cdots & {\bf v}_n \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\lambda_1 - x} & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \frac{1}{\lambda_n - x}
\end{bmatrix}
\begin{bmatrix}
- & {\bf v}_1 & - \\
~ & \vdots & ~ \\
- & {\bf v}_n & -
\end{bmatrix} \\
&= \det(A - xI) \times \sum_{j = 1}^n (\lambda_j - x)^{-1}\bv_j\bv_j\trans \\
&= \left(\prod(\lambda_i - x)\right) \times \sum_{j = 1}^n (\lambda_j - x)^{-1}\bv_j\bv_j\trans \\
&= \sum_{j = 1}^n \left(\prod_{k \neq j}(\lambda_k - x)\right)\bv_j\bv_j\trans \\
&= \sum_{j = 1}^n p_i(x) \bv_j\bv_j\trans.
\end{aligned}
$$

:::success
Nice work!
:::

##### Exercise 7(b)

將 $x$ 趨近到 $\lambda_i$，並證明特徵向量-特徵值定理。

解：
若 $x$ 趨近到 $\lambda_i$，則在 $\sum_{j = 1}^n \left(\prod_{k \neq j}(\lambda_k - x)\right)\bv_j\bv_j\trans$ 所有的通項中，
連乘中有乘上 $(\lambda_i - x)$ 的通項可以忽略不計，
也就是說，除了第 $j=i$ 的通項以外，其餘的通項皆可視為 $0$，
所以 $\sum_{j = 1}^n \left(\prod_{k \neq j}(\lambda_k - x)\right)\bv_j\bv_j\trans$ 可以化簡為 $\left(\prod_{j\neq i}(\lambda_j - \lambda_i)\right)\bv_i\bv_i\trans$，
故當 $x$ 趨近到 $\lambda_i$，下式成立
$$
\begin{aligned}
(A - xI)\adj
&= \sum_{j = 1}^n \left(\prod_{k \neq j}(\lambda_k - x)\right)\bv_j\bv_j\trans \\
&= \left(\prod_{j\neq i}(\lambda_j - \lambda_i)\right)\bv_i\bv_i\trans.
\end{aligned}
$$

:::success
Excellent!
:::

:::info
目前分數 = 6 × 檢討 = 6.5
:::