# 體驗譜分解

Understanding the spectral decomposition

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}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

from lingeo import random_int_list

## Main idea

Let $A$ be an $n\times n$ matrix and
$f_A : \mathbb{R}^n\rightarrow\mathbb{R}^n$ the corresponding linear function defined by $f(\bv) = A\bv$.
Let $\mathcal{E}_n$ be the standard basis of $\mathbb{R}^n$.
Then $[f_A] = [f_A]_{\mathcal{E}_n}^{\mathcal{E}_n} = A$.

Let $\beta$ be another basis of $\mathcal{R}^n$ and $Q = [\idmap]_\beta^{\mathcal{E}_n}$.
Then $[f_A]_\beta^\beta = Q^{-1}AQ$.

##### Spectral theorem (vector version)

Let $A$ be an $n\times n$ symmetric matrix.
Then there is an orthonormal basis $\beta$ of $\mathbb{R}^n$ such that $[f_A]_\beta^\beta = D$ is a diagonal matrix.
That is, there is an orthogonal matrix $Q$ such that $Q\trans AQ = D$ is a diagonal matrix.

Let $\beta = \{ \bv_1, \ldots, \bv_n \}$ be the basis in the spectral theorem.
Then $Q$ is the matrix whose columns are vectors in $\beta$.
Since $\beta$ is orthonormal, $Q$ is orthogonal and $Q^{-1} = Q\trans$.

Suppose the $D$ matrix in the spectral theorem is

$$
\begin{bmatrix}
\lambda_1 & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \lambda_n \\
\end{bmatrix}.
$$

By examining $AQ = QD$, we have

$$
AQ =
A\begin{bmatrix}
| & ~ & | \\
\bv_1 & \cdots & \bv_n \\
| & ~ & |
\end{bmatrix} =
QD =
\begin{bmatrix}
| & ~ & | \\
\bv_1 & \cdots & \bv_n \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
\lambda_1 & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \lambda_n
\end{bmatrix} =
\begin{bmatrix}
| & ~ & | \\
\lambda_1\bv_1 & \cdots & \lambda_n\bv_n \\
| & ~ & |
\end{bmatrix}.
$$

Therefore, $A\bv_i = \lambda_i \bv_i$ for $i = 1,\ldots, n$.

If a nonzero vector $\bv$ satisfies $A\bv = \lambda\bv$ for some scalar $\lambda$, then $\bv$ is called an **eigenvector** of $A$ and $\lambda$ is called an **eigenvalue** of $A$.

On the other hand, we may write $A = QDQ\trans$.
Thus,

$$
A = QDQ\trans =
\begin{bmatrix}
| & ~ & | \\
\bv_1 & \cdots & \bv_n \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
\lambda_1 & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \lambda_n \\
\end{bmatrix}
\begin{bmatrix}
- & \bv_1\trans & - \\
~ & \vdots & ~\\
- & \bv_n\trans & -
\end{bmatrix} =
\sum_{i = 1}^n \lambda_i \bv_i\bv_i\trans.
$$

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} \bv_i\bv_i\trans$.
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

- quadratic form
- differential equation
- diagonalization for general matrices

## Experiments

##### Exercise 1

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
n = 3
Q = matrix([
    [1 / sqrt(3), 1 / sqrt(2), 1 / sqrt(6)],
    [1 / sqrt(3), -1 / sqrt(2), 1 / sqrt(6)],
    [1 / sqrt(3), 0, -2 / sqrt(6)]
])
v = random_int_list(n)
D = diagonal_matrix(v)
A = Q * D * Q.transpose()

cs = random_int_list(n)

print("A =")
show(A)
for i in range(n):
    print("v%s ="%(i+1), Q.column(i))
print("b = " + " + ".join("%s v%s"%(cs[i], i+1) for i in range(n))) 

if print_ans:
    for i in range(n):
        print("A v%s = %s v%s"%(i+1, v[i], i+1))
    print("A b = " + " + ".join("%s v%s"%(cs[i]*v[i], i+1) for i in range(n))) 
    print("Q =")
    show(Q)
    print("D =")
    show(D)

##### Exercise 1(a)

驗證 $\bv_1, \ldots, \bv_3$ 是 $A$ 的特徵向量﹐並找出相對應的特徵值。

<!-- eng start -->
Verify that $\bv_1, \ldots, \bv_3$ are eigenvectors of $A$ and find the corresponding eigenvalues.
<!-- eng end -->

##### Exercise 1(b)

把 $A\bb$ 寫成 $\{\bv_1, \ldots, \bv_3\}$ 的線性組合。

<!-- eng start -->
Write $A\bb$ as a linear combination of $\{\bv_1, \ldots, \bv_3\}$.
<!-- eng end -->

##### Exercise 1(c)

找出一個垂直矩陣 $Q$ 和一個對角矩陣 $D$ 使得 $D = Q\trans AQ$。

<!-- eng start -->
Find an orthogonal matrix $Q$ and a diagonal matrix $D$ such that $D = Q\trans AQ$.
<!-- eng end -->

## Exercises

##### Exercise 2

令 $A$ 為一 $3\times 3$ 矩陣而
$\beta = \{ \bv_1,\ldots,\bv_3 \}$ 為 $\mathbb{R}^3$ 的一組基底。
已知

$$
[f_A]_\beta^\beta = \begin{bmatrix}
3 & 0 & 0 \\
0 & 4 & 0 \\
0 & 0 & 5 \\
\end{bmatrix}.
$$

將 $A\bv_1$、$A\bv_2$、$A\bv_3$、及 $A(\bv_1 + \bv_2 + \bv_3)$ 分別寫成 $\beta$ 的線性組合。

<!-- eng start -->
Let $A$ be a $3\times 3$ matrix and $\beta = \{ \bv_1,\ldots,\bv_3 \}$ a basis of $\mathbb{R}^3$. Suppose

$$
[f_A]_\beta^\beta = \begin{bmatrix}
3 & 0 & 0 \\
0 & 4 & 0 \\
0 & 0 & 5 \\
\end{bmatrix}.
$$

Write $A\bv_1$, $A\bv_2$, $A\bv_3$, and $A(\bv_1 + \bv_2 + \bv_3)$ as linear combinations of $\beta$.
<!-- eng end -->

##### Exercise 3

令

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

且 $\beta = \{ \bv_1, \ldots, \bv_3 \}$ 為

$$
\begin{bmatrix}
\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\
\frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\
\frac{1}{\sqrt{3}} & 0 & -\frac{2}{\sqrt{6}} \\
\end{bmatrix}
$$

的行向量集合。

<!-- eng start -->
Let

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

and $\beta = \{ \bv_1, \ldots, \bv_3 \}$ the columns of

$$
\begin{bmatrix}
\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\
\frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\
\frac{1}{\sqrt{3}} & 0 & -\frac{2}{\sqrt{6}} \\
\end{bmatrix}.
$$
<!-- eng end -->

##### Exercise 3(a)

寫出 $[f_A]_\beta^\beta$ 並說明 $f_A$ 的作用。

<!-- eng start -->
Find $[f_A]_\beta^\beta$ and describe the effect of $f_A$.
<!-- eng end -->

##### Exercise 3(b)

找出一個垂直矩陣 $Q$ 和一個對角矩陣 $D$ 使得 $D = Q\trans AQ$。

<!-- eng start -->
Find an orthogonal matrix $Q$ and a diagonal matrix $D$ such that $D = Q\trans AQ$.
<!-- eng end -->

##### Exercise 3(c)

令 $P_1$ 為投影到 $\vspan(\{\bv_1\})$ 的投影矩陣、
$P_2$ 為投影到 $\vspan(\{\bv_2, \bv_3\})$ 的投影矩陣。
說明 $P_1 = \bv_1\bv_1\trans$ 且 $P_2 = \bv_2\bv_2\trans + \bv_3\bv_3\trans$。

<!-- eng start -->
Let $P_1$ be the projection matrix onto $\vspan(\{\bv_1\})$ and $P_2$ the projection matrix onto $\vspan(\{\bv_2, \bv_3\})$. Show that $P_1 = \bv_1\bv_1\trans$ and $P_2 = \bv_2\bv_2\trans + \bv_3\bv_3\trans$.
<!-- eng end -->

##### Exercise 3(d)

將 $A$ 寫成一些投影矩陣的線性組合﹐並再次說明 $f_A$ 的作用﹐看看是否和第一小題一致。

<!-- eng start -->
Write $A$ as a linear combination of some projection matrices. Use this representation to describe again the effect of $f_A$. Is it the same as 3(a)?
<!-- eng end -->

##### Exercise 4

令

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

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 2 \\
2 & 4 \\
\end{bmatrix}.
$$
<!-- eng end -->

##### Exercise 4(a)

說明要找一個非零向量 $\bv$ 使得 $A\bv = \lambda\bv$﹐
等同於在 $(A - \lambda I)\bv = \bzero$ 中找非零解。

<!-- eng start -->
Let $\lambda$ be a given number. Show that finding a nonzero vector $\bv$ with $A\bv = \lambda\bv$ is equivalent to finding a nonzero solution to $(A - \lambda I)\bv = \bzero$.
<!-- eng end -->

##### Exercise 4(b)

方程式 $(A - \lambda I)\bv = \bzero$ 有非零解只會發生在 $\det(A - \lambda I) = 0$ 的時候。
利用這個性質找出所有可能的 $\lambda$。

<!-- eng start -->
The equation $(A - \lambda I)\bv = \bzero$ has a nonzero solution only when $\det(A - \lambda I) = 0$. Use this fact to find all possible $\lambda$.
<!-- eng end -->

##### Exercise 4(c)

對每一個 $\lambda$ 解出相對應的 $\bv$。
向量 $\bv$ 的選擇可能很多﹐把它的長度縮為 $1$。

<!-- eng start -->
For a given number $\lambda$, there might be many choices of $\bv$. Find one with length $1$.
<!-- eng end -->

##### Exercise 4(d)

找出一個垂直矩陣 $Q$ 和一個對角矩陣 $D$ 使得 $D = Q\trans AQ$。

<!-- eng start -->
Find an orthogonal matrix $Q$ and a diagonal matrix $D$ such that $D = Q\trans AQ$.
<!-- eng end -->

##### Exercise 5

令

$$
A = \begin{bmatrix}
1 & 2 \\
2 & 1 \\
\end{bmatrix},
Q = \begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} \\
\end{bmatrix},
D = \begin{bmatrix}
3 & 0 \\
0 & -1 \\
\end{bmatrix}.
$$

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 2 \\
2 & 1 \\
\end{bmatrix},
Q = \begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} \\
\end{bmatrix},
D = \begin{bmatrix}
3 & 0 \\
0 & -1 \\
\end{bmatrix}.
$$
<!-- eng end -->

##### Exercise 5(a)

驗證 $Q\trans AQ = D$。

<!-- eng start -->
Verify that $Q\trans AQ = D$.
<!-- eng end -->

##### Exercise 5(b)

令 $p(x,y) = x^2 + 4xy + y^2$。
找一些係數 $a,b,c,d$ 並令
$\hat{x} = a x + b y$、
$\hat{y} = c x + D y$﹐
使得 $p(x,y) = 3\hat{x}^2 - \hat{y}^2$。
藉此說明 $p(x,y) = 1$ 的圖形是雙曲線。

<!-- eng start -->
Let $p(x,y) = x^2 + 4xy + y^2$. Find some coefficients $a, b, c, d$ and define $\hat{x} = a x + b y$ and $\hat{y} = c x + D y$ such that $p(x,y) = 3\hat{x}^2 - \hat{y}^2$. Use this fact to show that $p(x,y) = 1$ is a hyperbola.
<!-- eng end -->

##### Exercise 5(c)

令 $x(t), y(t)$ 為以 $t$ 為變數的函數。
令 $x'(t), y'(t)$ 為其對 $t$ 的微分。
考慮微分方程

$$
\begin{aligned}
x' &= x + 2y, \\
y' &= 2x + y.
\end{aligned}
$$

找一些係數 $a,b,c,d$ 並令
$\hat{x} = a x + b y$、
$\hat{y} = c x + D y$﹐
使得原方程可以改寫為
$\hat{x}' = 3\hat{x}$、
$\hat{y}' = -\hat{y}$。
（此方程的解為
$\hat{x} = C_1e^{3t}$、
$\hat{y} = C_2e^{-t}$﹐
其中 $C_1$ 和 $C_2$ 是任意常數。）
解原方程。

<!-- eng start -->
Let $x(t)$ and $y(t)$ be functions on variable $t$. Let $x'(t)$ and $y'(t)$ their derivative with respect to $t$. Consider the system of differential equations

$$
\begin{aligned}
x' &= x + 2y, \\
y' &= 2x + y.
\end{aligned}
$$

Find some coefficients $a, b, c, d$ and define $\hat{x} = a x + b y$ and $\hat{y} = c x + D y$ so that the original system becomes

$$
\begin{aligned}
\hat{x}' &= 3\hat{x}, \\
\hat{y}' &= -\hat{y}.
\end{aligned}
$$

Note that the solutions to this system is $\hat{x} = C_1e^{3t}$ and $\hat{y} = C_2e^{-t}$, where $C_1$ and $C_2$ can be any constants.
<!-- eng end -->

##### Exercise 6

以下例題說明並非對稱矩陣才能表示成對角矩陣。
然而其所用的基底不再是垂直的。
（也有可能這樣的基底找不到。）
令

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

<!-- eng start -->
The following examples indicate that not only the symmetric matrices can be transformed into a diagonal matrices by using a different basis. However, the basis might not be orthogonal. (It is also possible that such a basis does not exist.)

Let

$$
A = \begin{bmatrix}
1 & 2 \\
1 & 2 \\
\end{bmatrix}.
$$
<!-- eng end -->

##### Exercise 6(a)

說明要找一個非零向量 $\bv$ 使得 $A\bv = \lambda\bv$﹐
等同於在 $(A - \lambda I)\bv = \bzero$ 中找非零解。

<!-- eng start -->
Let $\lambda$ be a given number. Show that finding a nonzero vector $\bv$ with $A\bv = \lambda\bv$ is equivalent to finding a nonzero solution to $(A - \lambda I)\bv = \bzero$.
<!-- eng end -->

##### Exercise 6(b)

方程式 $(A - \lambda I)\bv = \bzero$ 有非零解只會發生在 $\det(A - \lambda I) = 0$ 的時候。
利用這個性質找出所有可能的 $\lambda$。

<!-- eng start -->
The equation $(A - \lambda I)\bv = \bzero$ has a nonzero solution only when $\det(A - \lambda I) = 0$. Use this fact to find all possible $\lambda$.
<!-- eng end -->

##### Exercise 6(c)

對每一個 $\lambda$ 解出相對應的 $\bv$。
向量 $\bv$ 的選擇可能很多﹐把它的長度縮為 $1$。

<!-- eng start -->
For a given number $\lambda$, there might be many choices of $\bv$. Find one with length $1$.
<!-- eng end -->

##### Exercise 6(d)

找出一個可逆矩陣 $Q$ 和一個對角矩陣使得 $D = Q^{-1} AQ$。

<!-- eng start -->
Find an invertibile matrix $Q$ and a diagonal matrix $D$ such that $D = Q^{-1} AQ$.
<!-- eng end -->