體驗譜分解

Understanding the spectral decomposition

This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.

$\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

執行以下程式碼。

Run the code below.

### 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$ 的特徵向量﹐並找出相對應的特徵值。

Verify that $\bv_1, \ldots, \bv_3$ are eigenvectors of $A$ and find the corresponding eigenvalues.

Exercise 1(b)

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

Write $A\bb$ as a linear combination of $\{\bv_1, \ldots, \bv_3\}$.

Exercise 1(c)

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

Find an orthogonal matrix $Q$ and a diagonal matrix $D$ such that $D = Q\trans AQ$.

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$ 的線性組合。

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$.

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} $$

的行向量集合。

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}. $$

Exercise 3(a)

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

Find $[f_A]_\beta^\beta$ and describe the effect of $f_A$.

Exercise 3(b)

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

Find an orthogonal matrix $Q$ and a diagonal matrix $D$ such that $D = Q\trans AQ$.

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$。

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$.

Exercise 3(d)

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

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)?

Exercise 4

令

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

Let

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

Exercise 4(a)

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

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$.

Exercise 4(b)

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

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$.

Exercise 4(c)

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

For a given number $\lambda$, there might be many choices of $\bv$. Find one with length $1$.

Exercise 4(d)

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

Find an orthogonal matrix $Q$ and a diagonal matrix $D$ such that $D = Q\trans AQ$.

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}. $$

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}. $$

Exercise 5(a)

驗證 $Q\trans AQ = D$。

Verify that $Q\trans AQ = D$.

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$ 的圖形是雙曲線。

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.

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$ 是任意常數。）
解原方程。

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.

Exercise 6

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

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

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}. $$

Exercise 6(a)

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

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$.

Exercise 6(b)

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

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$.

Exercise 6(c)

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

For a given number $\lambda$, there might be many choices of $\bv$. Find one with length $1$.

Exercise 6(d)

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

Find an invertibile matrix $Q$ and a diagonal matrix $D$ such that $D = Q^{-1} AQ$.