---
title: Linear Algebra Note 7
tags: Linear Algebra, 線性代數, 魏群樹, 大學, 國立陽明交通大學, 筆記
---

# Linear Algebra Note 7

## Eigenvectors & Eigenvalues (2021.12.22 ~ 2021.12.29)

### Singular Value Decomposition (SVD)

- Theorem
$A_{m \times n} = U_{m \times m} \Sigma_{m \times n} V_{n \times n}$
where $U$ and $V$ are orthogonal matrix (orthogonal columns) $\implies U^{-1} = U^T, V^{-1} = V^T$
$\Sigma = \left[\begin{array}{c c c c c c c}
\sigma_1 & & & & & & \\
& \sigma_2 & & & & & \\
& & \ddots & & & & \\
& & & \sigma_r & & & \\
& & & & 0 & & \\
& & & & & \ddots & \\
& & & & & & 0 \\
\end{array}\right]_{m \times n},\ \sigma = \text{ singular value},\ r = rank(A) \le min(m,\ n)$
$AV = U\Sigma V^TV = U\Sigma \\
A\vec{V_1} = \sigma_1\vec{u_1},\ A\vec{V_2} = \sigma_2\vec{u_2},\ \cdots,\ A\vec{V_r} = \sigma_r\vec{u_r}$
- Proof
Consider $A^TA$ , an $n \times n$ symmetric matrix $\implies A^TA$ is diagonalizable
Moreover, from spectral theorem $A^TA = Q\Lambda Q^T$ , the eigenvectors are orthonormal
Let $\vec{v_1},\ \vec{v_2},\ \cdots,\ \vec{v_n}$ be orthonormal eigenvectors of $A^TA$
$A^TA\vec{v_i} = \lambda_i\vec{v_i} \\
\begin{Vmatrix}
A\vec{v_i}
\end{Vmatrix}^2 = \vec{v_i}^TA^TA\vec{v_i} = \vec{v_i}^T\lambda_i\vec{v_i} = \lambda_i\underbrace{\vec{v_i}^T\vec{v_i}}_1 = \lambda_i \ge 0$
$rank(A^TA) = rank(A) = r =$ the number of non-zero eigenvalues for $A^TA$
Let $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_r,\ \sigma_i \triangleq \sqrt{\lambda_i}$
For $i=1,\ 2,\ \cdots,\ r$ , define $\vec{u_i} \triangleq {A\vec{v_i} \over \begin{Vmatrix}
A\vec{v_i}
\end{Vmatrix}} = {A\vec{v_i} \over \sigma_i}\cdots ①$
$\vec{u_i}^T\vec{u_j} = ({\vec{v_i}^TA^T \over \sigma_i})({A\vec{v_j} \over \sigma_j}) = {\vec{v_i}^T(A^TA\vec{v_j}) \over \sigma_i\sigma_j} = \left\{\begin{array}{c}
{\begin{Vmatrix}
A\vec{v_j}
\end{Vmatrix}^2 \over \sigma_j^2} = {\sigma_j^2 \over \sigma_j^2} = 1,\ i = j \\
{\vec{v_i}^T\lambda_j\vec{v_j} \over \sigma_i\sigma_j} = 0,\ i \not= j \\
\end{array}\right. \\
\therefore \{ \vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_r} \} \text{ is orthonormal}$
Since each $\vec{u_i}$ is $m \times 1$ , we can use the Gram-Schimdt process to extend this to an orthonormal basis $\{ \vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_r},\ \vec{u_{r+1}},\ \cdots,\ \vec{u_m} \} \cdots ②$
For ① ②, $A\vec{v_i} = \sigma_i\vec{u_i}$ for $i = 1,\ 2,\ \cdots,\ r$ and $A\vec{v_i} = 0\vec{u_i} = 0$
$A\left[\begin{array}{c c c c c c c}
\vec{v_1} & \vec{v_2} & \cdots & \vec{v_r} & \vec{v_{r+1}} & \cdots & \vec{v_n} \\
\end{array}\right] = \left[\begin{array}{c c c c c c c}
\vec{u_1} & \vec{u_2} & \cdots & \vec{u_r} & \vec{v_{u+1}} & \cdots & \vec{u_n} \\
\end{array}\right]\left[\begin{array}{c c c c c c c}
\sigma_1 & & & & & & \\
& \sigma_2 & & & & & \\
& & \ddots & & & & \\
& & & \sigma_r & & & \\
& & & & 0 & & \\
& & & & & \ddots & \\
& & & & & & 0 \\
\end{array}\right] \\
\therefore AV=U\Sigma \text{ where } U,\ V \text{ are orthogonal} \\
\therefore A = U_{m \times m}\Sigma_{m \times n}V^T_{n \times n} = U'_{m \times r}\Sigma_{r \times r}^{'}V'^T_{r \times n}$
- Example
$A = \left[\begin{array}{c c c}
2 & 2 & 0 \\
-1 & 1 & 0 \\
\end{array}\right],\ A^TA = \left[\begin{array}{c c}
2 & -1 \\
2 & 1 \\
0 & 0 \\
\end{array}\right]\left[\begin{array}{c c c}
2 & 2 & 0 \\
-1 & 1 & 0 \\
\end{array}\right] = \left[\begin{array}{c c c}
5 & 3 & 0 \\
3 & 5 & 0 \\
0 & 0 & 0 \\
\end{array}\right] \\
A^TA - \lambda I = \left[\begin{array}{c c c}
5-\lambda & 3 & 0 \\
3 & 5-\lambda & 0 \\
0 & 0 & -\lambda \\
\end{array}\right] \\
solve\ \begin{vmatrix}
A^TA - \lambda I
\end{vmatrix} \implies \lambda_1 = 8,\ \lambda_2 = 2,\ \lambda_3 = 0,\ \vec{x_1} = \left[\begin{array}{c}
1 \\
1 \\
0 \\
\end{array}\right],\ \vec{x_2} = \left[\begin{array}{c}
1 \\
-1 \\
0 \\
\end{array}\right],\ \vec{x_3} = \left[\begin{array}{c}
0 \\
0 \\
1 \\
\end{array}\right] \\
\therefore \vec{v_1} = {\vec{x_1} \over \begin{Vmatrix}
\vec{x_1}
\end{Vmatrix}} = {1 \over \sqrt{2}}\left[\begin{array}{c}
1 \\
1 \\
0 \\
\end{array}\right],\ \vec{v_2} = {\vec{x_2} \over \begin{Vmatrix}
\vec{x_2}
\end{Vmatrix}} = {1 \over \sqrt{2}}\left[\begin{array}{c}
1 \\
-1 \\
0 \\
\end{array}\right],\ \vec{v_3} = {\vec{x_3} \over \begin{Vmatrix}
\vec{x_3}
\end{Vmatrix}} = \left[\begin{array}{c}
0 \\
0 \\
1 \\
\end{array}\right] \\
\sigma_1 = \sqrt{\lambda_1} = \sqrt{8},\ \sigma_2 = \sqrt{\lambda_2} = \sqrt{2},\ \sigma_3 = \sqrt{\lambda_3} = 0 \\
\vec{u_1} = {A\vec{v_1} \over \sigma_1} = \left[\begin{array}{c c c}
2 & 2 & 0 \\
-1 & 1 & 0 \\
\end{array}\right]{1 \over \sqrt{2}}\left[\begin{array}{c}
1 \\
1 \\
0 \\
\end{array}\right]{1 \over \sqrt{8}} = {1 \over 4}\left[\begin{array}{c}
4 \\
0 \\
\end{array}\right] = \left[\begin{array}{c}
1 \\
0 \\
\end{array}\right] \\
\vec{u_2} = {A\vec{v_2} \over \sigma_2} = \left[\begin{array}{c c c}
2 & 2 & 0 \\
-1 & 1 & 0 \\
\end{array}\right]{1 \over \sqrt{2}}\left[\begin{array}{c}
1 \\
-1 \\
0 \\
\end{array}\right]{1 \over \sqrt{2}} = {1 \over 2}\left[\begin{array}{c}
0 \\
-2 \\
\end{array}\right] = \left[\begin{array}{c}
0 \\
-1 \\
\end{array}\right] \\
\therefore A=U\Sigma V^T = \left[\begin{array}{c c}
1 & 0 \\
0 & -1 \\
\end{array}\right]\left[\begin{array}{c c c}
\sqrt{8} & 0 & 0 \\
0 & \sqrt{2} & 0 \\
\end{array}\right]\left[\begin{array}{c c c}
{1 \over \sqrt{2}} & {1 \over \sqrt{2}} & 0 \\
{1 \over \sqrt{2}} & {-1 \over \sqrt{2}} & 0 \\
0 & 0 & 1 \\
\end{array}\right]$

- If $M$ is symmetric, $i.e.\ M^T = M$ , $\{ \sigma_i \}$ is the absolute value of $M$'s eigenvalues
$M = U\Sigma V^T \\
MM^T = (U\Sigma V^T)(V\Sigma^TU^T) = U\Sigma^2U^T \text{ where } U \text{ is orthogonal}$
Recall (EVD: Matrix diagonalization): $A = S\Lambda S^{-1}$
$MM^T = U\Sigma^2U^T \implies \Sigma^2 \text{ contains the eigenvalues of } MM^T \implies \Sigma \text{ has } M's \text{ absolute eigenvalues}$

- If $A$ is positive semidefinite, $\{ \sigma_i \}$ is the eigenvalues of $A$, i.e. SVD reduces to EVD

- Consider SVD of $AA^T,\ A = U\Sigma V^T = EV(AA^T) \times \sqrt{\lambda_i} \times EV(A^TA)$
$AA^T = (U\Sigma V^T)(V\Sigma^TU^T) = U\Sigma\Sigma^TU^T$
where $\Sigma\Sigma^T = \left[\begin{array}{c c c c c c c}
\sigma_1^2 & & & & & & \\
& \sigma_2^2 & & & & & \\
& & \ddots & & & & \\
& & & \sigma_r^2 & & & \\
& & & & 0 & & \\
& & & & & \ddots & \\
& & & & & & 0 \\
\end{array}\right] = \left[\begin{array}{c c c c c c c}
\lambda_1 & & & & & & \\
& \lambda_2 & & & & & \\
& & \ddots & & & & \\
& & & \lambda_r & & & \\
& & & & 0 & & \\
& & & & & \ddots & \\
& & & & & & 0 \\
\end{array}\right]$
$\therefore AA^T = U\Sigma\Sigma^TU^T$ is the EVD of $AA^T$ where $\Sigma\Sigma^T$ contains eigenvalues of $AA^T$ and $\vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_m}$ are eigenvectors
Note that $\{ \lambda_1,\ \lambda_2,\ \cdots,\ \lambda_r,\ \underbrace{0,\ \cdots,\ 0}_\text{n-r} \}$ are the eigenvalues of $A^TA$ with corresponding eigenvectors $\{ \vec{v_1},\ \vec{v_2},\ \cdots,\ \vec{v_n} \}$

- Example (Solving Fibonacci Numbers)
$F_{k+2} = F_{k+1} + F_k,\ for\ k=0,\ 1,\ 2, \cdots$
Let $\vec{u_k} = \left[\begin{array}{c}
F_{k+1} \\
F_k \\
\end{array}\right]$
$\vec{u_{k+1}} = \left[\begin{array}{c}
F_{k+2} \\
F_{k+1} \\
\end{array}\right] = \left[\begin{array}{c}
F_{k+1}+F_k \\
F_{k+1} \\
\end{array}\right] = \left[\begin{array}{c c}
1 & 1 \\
1 & 0 \\
\end{array}\right]\left[\begin{array}{c}
F_{k+1} \\
F_k \\
\end{array}\right] = \left[\begin{array}{c c}
1 & 1 \\
1 & 0 \\
\end{array}\right]\vec{u_k}$
$\vec{u_{k+1}} = A\vec{u_k}$ where $A = \left[\begin{array}{c c}
1 & 1 \\
1 & 0 \\
\end{array}\right] \implies \vec{u_{k+1}} = A^k\vec{u_0}$
Find the general form for $F_k$
$A = \left[\begin{array}{c c}
1 & 1 \\
1 & 0 \\
\end{array}\right]$ has eigenvalues obtained by solving $\begin{vmatrix}
A-\lambda I
\end{vmatrix} = 0$
$\begin{vmatrix}
A-\lambda I
\end{vmatrix} = \begin{vmatrix}
\left[\begin{array}{c c}
1-\lambda & 1 \\
1 & -\lambda \\
\end{array}\right]
\end{vmatrix} = \lambda^2-\lambda-1 = 0 \\
\lambda_1 = {1+\sqrt{5} \over 2},\ \lambda_2 = {1-\sqrt{5} \over 2}, \vec{x_1} = \left[\begin{array}{c}
{1+\sqrt{5} \over 2} \\
1 \\
\end{array}\right] = \left[\begin{array}{c}
\lambda_1 \\
1 \\
\end{array}\right],\ \vec{x_2} = \left[\begin{array}{c}
{1-\sqrt{5} \over 2} \\
1 \\
\end{array}\right] = \left[\begin{array}{c}
\lambda_2 \\
1 \\
\end{array}\right]$
$A = S\Lambda S^{-1} \ where\ S = \left[\begin{array}{c c}
\lambda_1 & \lambda_2 \\
1 & 1 \\
\end{array}\right],\ S^{-1} = {1 \over \lambda_1 - \lambda_2}\left[\begin{array}{c c}
1 & -\lambda_2 \\
-1 & \lambda_1 \\
\end{array}\right] \\
\Lambda = \left[\begin{array}{c c}
\lambda_1 & 0 \\
0 & \lambda_2 \\
\end{array}\right],\ A^k = A\Lambda^kS^{-1},\ \Lambda_k = \left[\begin{array}{c c}
\lambda_1^k & 0 \\
0 & \lambda_2^k \\
\end{array}\right] \\
\begin{split}\vec{u_{k+1}} =& A^k\vec{u_0} \\
=& \left[\begin{array}{c c}
\lambda_1 & \lambda_2 \\
1 & 1 \\
\end{array}\right]\left[\begin{array}{c c}
\lambda_1^k & 0 \\
0 & \lambda_2^k \\
\end{array}\right]{1 \over \lambda_1 - \lambda_2}\left[\begin{array}{c c}
1 & -\lambda_2 \\
-1 & \lambda_1 \\
\end{array}\right]\left[\begin{array}{c}
1 \\
0 \\
\end{array}\right] \\
=& {1 \over \lambda_1 - \lambda_2}\left[\begin{array}{c c}
\lambda_1 & \lambda_2 \\
1 & 1 \\
\end{array}\right]\left[\begin{array}{c c}
\lambda_1^k & 0 \\
0 & \lambda_2^k \\
\end{array}\right]\left[\begin{array}{c}
1 \\
-1 \\
\end{array}\right] \\
=& {1 \over \lambda_1 - \lambda_2}\left[\begin{array}{c c}
\lambda_1 & \lambda_2 \\
1 & 1 \\
\end{array}\right]\left[\begin{array}{c}
\lambda_1^k \\
-\lambda_2^k \\
\end{array}\right] \\
=& {1 \over \lambda_1 - \lambda_2}\left[\begin{array}{c}
\lambda_1^{k+1} - \lambda_2^{k+1} \\
\lambda_1^k - \lambda_2^k \\
\end{array}\right] = \left[\begin{array}{c}
F_{k+1} \\
F_k \\
\end{array}\right] \\
\implies &F_k = {\lambda_1^k - \lambda_2^k \over \lambda_1 - \lambda_2} = {\lambda_1^k - \lambda_2^k \over \sqrt{5}}\end{split}$
As $k \to \infty$
$\begin{split}\lim\limits_{k\to \infty} {F_{k+1} \over F_k} &= \lim\limits_{k\to \infty} {\lambda_1^{k+1}-\lambda_2^{k+1} \over \lambda_1^k - \lambda_2^k} \\
&= \lim\limits_{k\to \infty} {(\lambda_1 - \lambda_2)(\lambda_1^k+\cdots+\lambda_2^k) \over (\lambda_1 - \lambda_2)(\lambda_1^{k-1}+\cdots+\lambda_2^{k-1})} \\
&= \lim\limits_{k\to \infty} {\lambda_1^k \over \lambda_1^{k-1}}\ (\ \because\ \begin{vmatrix}
\lambda_1
\end{vmatrix} > 1,\ \begin{vmatrix}
\lambda_2
\end{vmatrix} < 1\ ) \\
&= \lambda_1 = {1+\sqrt{5} \over 2} \text{ (Golden ratio)}\end{split}$

- The matrices $U$ and $V$ contain orthonormal bases for all four subspaces:
$$\begin{split}&\text{first } r &\text{ columns of } V: C(A^T) \\
&\text{last } n-r &\text{ columns of } V: N(A) \\
&\text{first } r &\text{ columns of } U: C(A) \\
&\text{last } m-r &\text{ columns of } U: N(A^T)\end{split}$$
Note that $A^TA\vec{v_i} = \lambda_i\vec{v_i}\ for\ i = 1,\ \cdots,\ r\ \implies A^T{A\vec{v_i} \over \lambda_i} = \vec{v_i}$
$\text{Let } \vec{y_i} = {A\vec{v_i} \over \lambda_i} \implies A^T\vec{y_i} = \vec{v_i} \implies \vec{v_i} \in C(A^T),\ dim(C(A^T)) = r$
$\because\ \{ \vec{v_1},\ \vec{v_2},\ \cdots,\ \vec{v_r} \}$ is a set of orthonormal vectors
$\implies \{ \vec{v_1},\ \vec{v_2},\ \cdots,\ \vec{v_r} \}$ is a set of orthonormal basis of $C(A^T)$
when $(r+1) \le i \le n,\ A^TA\vec{v_i} = \vec{0} \implies \{ \vec{v_{r+1}},\ \cdots,\ \vec{v_n} \}$ are $n-r$ orthonormal vectors
$\because\ N(A)$ has dimension $n-r \implies \{ \vec{v_{r+1}},\ \cdots,\ \vec{v_n} \}$ is a set of orthonormal basis of $N(A)$
$A\vec{v_i} = \sigma_i\vec{u_i}\ for\ i=1,\ \cdots,\ r\ \implies A{\vec{v_i} \over sigma_i} = \vec{u_i}$
$\text{Let } \vec{x_i} = {\vec{v_i} \over sigma_i} \implies A\vec{x_i} = \vec{u_i} \implies \vec{u_i} \in C(A)$
$\{ \vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_r} \}$ is a set of orthonormal basis of $C(A)$
when $(r+1) \le i \le m,\ \{ \vec{u_{r+1}},\ \cdots,\ \vec{u_m} \}$ is a set of orthonormal basis of $N(A^T)$