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
from linspace import QR
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.
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.
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
執行以下程式碼。
Run the code below.### code
set_random_seed(0)
print_ans = False
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())
求 $A$ 的所有特徵值及其對應的特徵向量。
Find the spectrum of $A$ and the corresponding eigenvectors.求 $A$ 的譜分解。
Find the spectral decomposition of $A$.求以下矩陣的譜分解。
For each of the following matrices, find its spectral decomposition.令 $\bu$ 為一長度為 $1$ 的實向量。
令 $P = \bu\bu\trans$。
說明 $P$ 為垂直投影到 $\vspan\{\bu\}$ 的投影矩陣。
Explain why $P$ is the projection matrix onto $\vspan\{\bu\}$.證明 $\tr(P\trans P) = \rank(P) = 1$。
Show that $\tr(P\trans P) = \rank(P) = 1$.令 $\{\bu_1, \ldots, \bu_d\}$ 為一群互相垂直且長度均為 $1$ 的實向量。
令 $P = \bu_1\bu_1\trans + \cdots + \bu_d\bu_d\trans$。
說明 $P$ 為垂直投影到 $\vspan\{\bu_1,\ldots, \bu_d\}$ 的投影矩陣。
Explain why $P$ is the projection matrix onto $\vspan\{\bu_1,\ldots, \bu_d\}$.證明 $\tr(P\trans P) = \rank(P) = d$。
Show that $\tr(P\trans P) = \rank(P) = d$.一個 垂直投影矩陣 指的是一個可以被垂直矩陣對角化且特徵值均是 $1$ 或 $0$ 的矩陣。
令 $P$ 為一實方陣。
證明以下敘述等價:
雖然譜分解裡的條件沒有明顯說明 $P_i$ 是垂直投影矩陣,
依照以下步驟證明下列條件
足以說明每一個 $P_i$ 都是垂直投影矩陣。
Although the statements in the spectral decomposition do not explicitly mention that $P_i$ is an orthogonal projection matrix. Use the given instructions to show that the conditions 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$. are enough to guarantee $P_i$ is an orthogonal projection matrix.驗證
$$ \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$ 都是對稱矩陣。
說明每一個 $P_i$ 都是垂直投影矩陣。
Show that each $P_i$ is an orthogonal projection matrix.依照以下步驟證明下述定理。
若 $A$ 為一 $n\times n$ 實對稱矩陣。
其特徵值為 $\lambda_1,\ldots,\lambda_n$ 且某一個 $\lambda_i$ 只出現一次沒有重覆。
令 $\bv_1,\ldots, \bv_n$ 為其相對應的特徵向量,且其形成一垂直標準基。
則
說明當 $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). $$ Show that when $x$ is not an eigenvalue of $A$, we have $$ \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} $$ where $$ p_j(x) = \prod_{k \neq j}(\lambda_k - x). $$將 $x$ 趨近到 $\lambda_i$ 並證明特徵向量-特徵值定理。
Prove the eigenvector-eigenvalue identity by letting $x$ go to $\lambda_i$.