# Eigen-decomposition

Yao Yao on September 10, 2018

• 我们这里不考虑 $\mathbf{C}$ 的情况，只针对 $\mathbf{R}$

## 1. eigenvalue/eigenvector 数量的限定

### 1.1 限定一：eigenvector $\mathbf{v} \neq \mathbf{0}$

• 注意我们并没有要求 $\lambda \neq 0$

### 1.2 限定二：只研究 unit eigenvector

• 在谈及两个或以上的 eigenvector 时，要求它俩是 linearly independent 的。换言之，如果 $\mathbf{v}$ 是广义上的对应 $\lambda$ 的 eigenvector，我们只取 $\mathbf{v}$ 直线上的某一个 vector 作为这个方向上 eigenvector 的总代表
• 那这个总代表到底应该选谁？简单，我们选 $\mathbf{v}$ 直线上的 unit vector

### 1.3 限定三：只计入 unique 的 eigenvalue

• 只讨论 unique 的 eigenvalue。换言之，允许一个 eigenvalue 对应多个 eigenvector，但计算 eigenvalue 的个数时，这个 eigenvalue 只算一次

### 1.4 How many eigenvalues/eigenvectors can a general matrix have?

• $A$ 可以有 $0 \leq \cdot \leq n$ 个 unique 的 eigenvalue
• 如果 $A$ 有 $k$ 个 unique 的 eigenvalue，它可以有 $k \leq \cdot \leq n$ 个 linearly independent 的 eigenvector

• 同一个矩阵 $A$，如果我们限定 eigenvalue 的 field，比如说要求 $\lambda \in \mathbb{C}$ 或者 $\lambda \in \mathbb{Q}$，eigenvalue 的个数可能会有变化
• 同理，$A$ 如果是 $\mathbb{C}$ 或是 $\mathbb{Q}$ 上的矩阵，也是可以研究 eigenvalue/eigenvector 的
• 为什么不能有 $\geq n+1$ 个 eigenvector？因为你 $\mathbf{v}_i \in \mathbb{R}^n$ 且 linearly independent，那么你 $\mathbf{v}_{n+1}$ 一定可以写成 $\mathbf{v}_1, \dots, \mathbf{v}_n$ 的线性组合（抽屉原理？），与前面的限制冲突。

### 1.5 Determine the number of eigenvalues/eigenvectors of a given matrix

• 视 $\lambda$ 为未知数。行列式 $p_A(\lambda) = \vert \lambda I - A \vert$ 称为 characteristic polynomial of $A$
• 等式 $p_A(\lambda) = 0$ 称为 characteristic equation of $A$
• $p_A(\lambda) = 0$ 的解 (亦即 $p_A(\lambda)$ 的 root) 即 $A$ 的 eigenvalues
• 换言之，解的个数即 eigenvalues 的个数
• 再换言之，此时可以把 $p_A(\lambda)$ 写成 $p_A(\lambda) = (\lambda - \lambda_1)^{m_1} \times \dots \times (\lambda - \lambda_k)^{m_k}$

• 我们称 eigenvalue $\lambda^{\ast}$ 具有 algebraic multiplicity of $m$ 如果 $(\lambda - \lambda^{\ast})$ 在 $p_A(\lambda)$ 展开式中出现了 $m$ 次 (换言之 $p_A(\lambda)$ 展开式中有 $(\lambda - \lambda^{\ast})^m$)
• 假设我们有 $k$ 个 unique 的 eigenvalue，各自的 algebraic multiplicity 为 $m_i$，那么一定有 $\sum_{i=1}^{k} m_i = n$
• 因为你 $p_A(\lambda)$ 展开式的总次数一定是 $n$
• 我们称 eigenvalue $\lambda^{\ast}$ 具有 geometric multiplicity of $m$ 如果 $\lambda^{\ast}$ 对应 $m$ 个 linearly independent 的 eigenvector
• 对同一个 eigenvalue $\lambda^{\ast}$ 而言，它的 geometric multiplicity $\leq$ algebraic multiplicity
• 证明在此
• 这也从侧面说明，$k$ 个 unique 的 eigenvalue 不可能有 $> n$ 个 linearly independent 的 eigenvector

### 1.6 题外话：与 $\vert A \vert$ 的关系

• 如果 $\exists \lambda_i = 0$，则 $\vert A \vert = 0$，亦即 $A$ is a singular matrix
• 这个结果，$\vert A \vert = \prod_{i=1}^{k} (\lambda_i)^{m_i}$，与行列式的几何意义是吻合的

## 2. Eigen-decomposition

• $V = [\mathbf{v}_1 \, \dots \, \mathbf{v}_n]$ (这是个 $n \times n$)
• $\mathbf{\lambda} = [\lambda_1 \, \dots \, \lambda_n]^T$ ($\lambda_i$ 不一定 unique)

Then the eigen-decomposition of $A$ can be written as:

$A = V \operatorname{diag}(\mathbf{\lambda}) V^{-1}$

Proof:

\begin{align*} AV &= A [\mathbf{v}_1 \, \dots \, \mathbf{v}_n] \newline &= [A\mathbf{v}_1 \, \dots \, A\mathbf{v}_n] \newline &= [\lambda_1\mathbf{v}_1 \, \dots \, \lambda_n\mathbf{v}_n] \newline &= [\mathbf{v}_1 \, \dots \, \mathbf{v}_n] \operatorname{diag}(\mathbf{\lambda}) \newline &= V \operatorname{diag}(\mathbf{\lambda}) \,\,\,\, \blacksquare \end{align*}

• 先实施 $V^{-1}$ 变换，将 basis 换成 $V^{-1}$ 的 column vectors
• $\operatorname{diag}(\mathbf{\lambda})$ stretch 这个新的 basis
• 再实施 $V$ 变换将 basis 再变回来

Eigen-decomposable 的 matrix 也称为 diagonalizable 的。Generally 我们有：

Definition: $n \times n$ matrices $A$ and $B$ are said to be similar if there is an invertible $n \times n$ matrix $P$ such that $A = P B P^{−1}$.

Definition: $n \times n$ matrix $A$ is said to be diagonalizable if it is similar to a diagonal matrix $D$.

$A^n = (P D P^{−1})^n = P D (P^{−1} P) D (P^{−1} \cdots) \cdots (\cdots P) D P^{−1} = P D^n P^{−1}$

## 3. Sufficient conditions of Eigen-decomposition

Obvious.

Almost obvious.

### 3.3 Condition 3: $A$ is symmetric

Definition: A real square matrix $A$ is orthogonally diagonalizable if there exist an orthogonal matrix $U$ and a diagonal matrix $D$ such that $A=UDU^{-1}$

Theorem: (The Spectral Theorem) $A$ is symmetric $\iff$ $A$ is orthogonally diagonalizable

• 叫 Spectral Theorem 是因为：特征分解 (Eigen-decomposition) 又称谱分解 (Spectral decomposition)
• 矩阵的频谱 (spectrum) 即矩阵的 eigenvalues 的集合

#### 3.3.1 Fundamental theorem of algebra

The fundamental theorem of algebra states that every non-constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomials with real coefficients, since every real number is a complex number with an imaginary part equal to zero.

Equivalently (by definition), the theorem states that the field of complex numbers is algebraically closed.

The theorem is also stated as follows: every non-zero, single-variable, degree n polynomial with complex coefficients has, counted with multiplicity, exactly n complex roots. The equivalence of the two statements can be proven through the use of successive polynomial division.

In spite of its name, there is no purely algebraic proof of the theorem, since any proof must use some form of completeness, which is not an algebraic concept. Additionally, it is not fundamental for modern algebra; its name was given at a time when algebra was synonymous with theory of equations.

#### 3.3.2 每个 symmetric real matrix 至少有一个 unique 的 real eigenvalue

Theorem: If $A$ is a real matrix, then it has $n$ real eigenvalues (counted by their multiplicities; 即不考虑 uniqueness). For each eigenvalue, we can find a real eigenvector associated with it.

Proof: 首先说一个现象：对任意 complex vector $\mathbf{z} = [z_1 \, \dots \, z_n]^T \in \mathbb{C}^n$，scalar $q = \overline{\mathbf{z}}^T A \mathbf{z}$ 其实是个 real，因为 $q = \overline{q}$ 永远成立：

\begin{align} q &= \overline{\mathbf{z}}^T A \mathbf{z} \newline &= \mathbf{z}^T A \overline{\mathbf{z}} \, (\text{because } A \text{ is symmetric}) \newline &= \mathbf{z}^T \overline{A} \overline{\mathbf{z}} \, (\text{because } A \text{ is real}) \newline &= \overline{q} \end{align}

\begin{align} \overline{\mathbf{z}}^T A \mathbf{z} &= \overline{\mathbf{z}}^T \lambda \mathbf{z} \newline &= \lambda (\overline{\mathbf{z}}^T \mathbf{z}) \newline &= \lambda \sum_{i=1}^{n} \overline{z_i} z_i \newline &= \lambda \sum_{i=1}^{n} \vert z_i \vert^2 \end{align}

#### 3.3.3 Final Proof

Proof:

(1) $\Rightarrow$

• $P^{-1}AP$ is symmetric because $(P^{-1}AP)^T = (P^{T}AP)^T = P^T A^T (P^T)^T = P^T A P = P^{-1} A P$
• 它的 first column 是 $P^{-1}AP \mathbf{e}_1 = P^{-1}A \mathbf{v}_1 = P^{-1} \lambda_1 \mathbf{v}_1 = \lambda_1 \mathbf{e}_1$

\begin{align} U^{-1}AU &= (PR)^{-1} A (PR) \newline &= R^{-1} P^{-1} A P R \newline &= R^{-1} \begin{bmatrix} \lambda_1 & \mathbf{0} \\ \mathbf{0} & B \end{bmatrix} R \newline &= \begin{bmatrix} 1 & \mathbf{0} \\ \mathbf{0} & Q^{-1} \end{bmatrix} \begin{bmatrix} \lambda_1 & \mathbf{0} \\ \mathbf{0} & B \end{bmatrix} \begin{bmatrix} 1 & \mathbf{0} \\ \mathbf{0} & Q \end{bmatrix} \newline &= \begin{bmatrix} \lambda_1 & \mathbf{0} \\ \mathbf{0} & Q^{-1}BQ \end{bmatrix} \newline &= \begin{bmatrix} \lambda_1 & \mathbf{0} \\ \mathbf{0} & D' \end{bmatrix} \newline \end{align}

(注：其实还有有 $A = P^{-1} \begin{bmatrix} \lambda_1 & \mathbf{0} \\ \mathbf{0} & B \end{bmatrix} P$，这个式子可以把 $A,B$ 直接联系起来)

(2) $\Leftarrow$

Suppose $A = UDU^{-1} = UDU^{T}$ ($U$ is orthogonal). Then:

\begin{align} A^T &= (UDU^{T})^T \newline &= (U^T)^T D^T U^T \newline &= UDU^T \, \text{(} D \text{ is diagonal thus of course symmetric)} \newline &=A \end{align}

### 3.4 Condition 4: Minimal polynomial of $A$ has no repeated factors (i.e. no repeated roots)

Definition: A monic polynomial is a single-variable polynomial (that is, a univariate polynomial) in which the leading coefficient (the nonzero coefficient of highest degree) is 1. Therefore, a monic polynomial has the form

$x^{n} + c_{n-1}x^{n-1} + \cdots + c_{2}x^{2} + c_{1}x + c_{0}$

Definition: A minimal polynomial of $x$ is a monic polynomial $m(x)$ which:

1. satisfies $m(x) = 0$ and
• 此时也称 $m(x)$ 是 annihilating polynomial (零化多项式) for $x$
2. has the smallest possible degree (degree 即最高项的次数)

• 令 $A = I_{2 \times 2}$，$p_A(A) = (A - 1)^2$，但由于 $A - 1_{2 \times 2} = 0_{2 \times 2}$，所以 minimal polynomial 只需要 $m_A(A) = A - 1$ 就可以了，不需要到 degree 2
• 令 $A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$，同样有 $p_A(A) = (A - 1)^2$，但只有 $(A - 1_{2 \times 2})^2 = 0_{2 \times 2}$ 而 $A - 1_{2 \times 2} \neq 0_{2 \times 2}$，所以 minimal polynomial 需要到 degree 2，即 $m_A(A) = p_A(A) = (A - 1)^2$

Theorem: (Cayley-Hamilton theorem) Every square matrix over a commutative ring (such as the real or complex field) satisfies its own characteristic equation. I.e Substituting matrix $A$ for $\lambda$ in $A$’s characteristic polynomial results in the zero matrix. I.e.

\begin{align} p_A(\lambda) &= \vert \lambda I_n - A_{n \times n} \vert \newline p_A(A) &= 0_{n \times n} \end{align}
• 注意：实际计算时应该先把 $p_A(\lambda)$ 展开得到关于 $\lambda$ 的多项式，再将 $\lambda$ 替换成 $A$。直接去求 $\vert A I - A \vert$ 看起来有点 confusing
• When the ring is a field, Cayley–Hamilton theorem is equivalent to the statement that the minimal polynomial of a square matrix divides its characteristic polynomial. (即 $p_A(A)$ 可以被 $m_A(A)$ 整除)

Proposition: $m_A(x)$ has no repeated roots $\iff$ $A$ is diagonalizable.

• 令 $A = I_{2 \times 2}$，$m_A(x) = x - 1$，只有一个 root 1，所以 $A$ is diagonalizable
• 令 $A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$，$m_A(x) = (x - 1)^2$，root 1 是 repeated，所以 $A$ is not diagonalizable

Proposition: Any idempotent matrix is diagonalizable.

Proof:

Idempotent matrix $A$ 满足 $A^2 = A$，即 $A(A - I) = 0$，所以潜在的 $m_A(x)$ 可能是：

• $m_A(x) = x$，或者
• $m_A(x) = x - 1$，或者
• $m_A(x) = x(x-1)$