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}{\mathrm{\Sigma }}_{m\times n}{V}_{n\times n}$
  where
  $U$ and
  $V$ are orthogonal matrix (orthogonal columns)
  $⟹U^{-1}=U^T,V^{-1}=V^T$
  
  $\mathrm{\Sigma }={\left[\begin{array}{ccccccc}{\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)$
  
  $$\begin{gathered} AV=U\mathrm{\Sigma }{V}^{T}V=U\mathrm{\Sigma } \\ A\overrightarrow{V_1}={\sigma }_1\overrightarrow{u_1},A\overrightarrow{V_2}={\sigma }_2\overrightarrow{u_2},\cdots ,A\overrightarrow{V_r}={\sigma }_r\overrightarrow{u_r} \end{gathered}$$
  • Proof
    Consider
    $A^{T}A$ , an
    $n\times n$ symmetric matrix
    $⟹A^{T}A$ is diagonalizable
    Moreover, from spectral theorem
    $A^{T}A=Q\mathrm{\Lambda }{Q}^T$ , the eigenvectors are orthonormal
    Let
    $\overrightarrow{v_1},\overrightarrow{v_2},\cdots ,\overrightarrow{v_n}$ be orthonormal eigenvectors of
    $A^{T}A$
    
    $$\begin{gathered} A^{T}A\overrightarrow{v_i}={\lambda }_i\overrightarrow{v_i} \\ {\Vert \begin{array}{c}A\overrightarrow{v_i}\end{array}\Vert }^2={\overrightarrow{v_i}}^T{A}^{T}A\overrightarrow{v_i}={\overrightarrow{v_i}}^T{\lambda }_i\overrightarrow{v_i}={\lambda }_i\underset{1}{\underbrace{{\overrightarrow{v_i}}^T\overrightarrow{v_i}}}={\lambda }_i\ge 0 \end{gathered}$$
    
    $rank(A^{T}A)=rank(A)=r=$ the number of non-zero eigenvalues for
    $A^{T}A$
    Let
    ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_r,{\sigma }_i\triangleq \sqrt{{\lambda }_i}$
    For
    $i=1,2,\cdots ,r$ , define
    $\overrightarrow{u_i}\triangleq \frac{A\overrightarrow{v_i}}{\Vert \begin{array}{c}A\overrightarrow{v_i}\end{array}\Vert }=\frac{A\overrightarrow{v_i}}{{\sigma }_i}\cdots \mathrm{①}$
    
    $$\begin{gathered} {\overrightarrow{u_i}}^T\overrightarrow{u_j}=(\frac{{\overrightarrow{v_i}}^T{A}^T}{{\sigma }_i})(\frac{A\overrightarrow{v_j}}{{\sigma }_j})=\frac{{\overrightarrow{v_i}}^T(A^{T}A\overrightarrow{v_j})}{{\sigma }_i{\sigma }_j}=\{\begin{array}{c}\frac{{\Vert \begin{array}{c}A\overrightarrow{v_j}\end{array}\Vert }^2}{{\sigma }_j^2}=\frac{{\sigma }_j^2}{{\sigma }_j^2}=1,i=j\\ \frac{{\overrightarrow{v_i}}^T{\lambda }_j\overrightarrow{v_j}}{{\sigma }_i{\sigma }_j}=0,i\ne j\end{array} \\ \therefore \{\overrightarrow{u_1},\overrightarrow{u_2},\cdots ,\overrightarrow{u_r}\}\text{ is orthonormal} \end{gathered}$$
    Since each
    $\overrightarrow{u_i}$ is
    $m\times 1$ , we can use the Gram-Schimdt process to extend this to an orthonormal basis
    $\{\overrightarrow{u_1},\overrightarrow{u_2},\cdots ,\overrightarrow{u_r},\overrightarrow{u_{r+1}},\cdots ,\overrightarrow{u_m}\}\cdots \mathrm{②}$
    For ① ②,
    $A\overrightarrow{v_i}={\sigma }_i\overrightarrow{u_i}$ for
    $i=1,2,\cdots ,r$ and
    $A\overrightarrow{v_i}=0\overrightarrow{u_i}=0$
    
    $$\begin{gathered} A\left[\begin{array}{ccccccc}\overrightarrow{v_1}& \overrightarrow{v_2}& \cdots & \overrightarrow{v_r}& \overrightarrow{v_{r+1}}& \cdots & \overrightarrow{v_n}\end{array}\right]=\left[\begin{array}{ccccccc}\overrightarrow{u_1}& \overrightarrow{u_2}& \cdots & \overrightarrow{u_r}& \overrightarrow{v_{u+1}}& \cdots & \overrightarrow{u_n}\end{array}\right]\left[\begin{array}{ccccccc}{\sigma }_1& & & & & & \\ & {\sigma }_2& & & & & \\ & & \ddots & & & & \\ & & & {\sigma }_r& & & \\ & & & & 0& & \\ & & & & & \ddots & \\ & & & & & & 0\end{array}\right] \\ \therefore AV=U\mathrm{\Sigma }\text{ where }U,V\text{ are orthogonal} \\ \therefore A=U_{m\times m}{\mathrm{\Sigma }}_{m\times n}{V}_{n\times n}^T=U_{m\times r}^{\prime }{\mathrm{\Sigma }}_{r\times r}^{{}^{\prime }}{V}_{r\times n}^{\prime T} \end{gathered}$$
  • Example
    
    $$\begin{gathered} A=\left[\begin{array}{ccc}2& 2& 0\\ -1& 1& 0\end{array}\right],A^{T}A=\left[\begin{array}{cc}2& -1\\ 2& 1\\ 0& 0\end{array}\right]\left[\begin{array}{ccc}2& 2& 0\\ -1& 1& 0\end{array}\right]=\left[\begin{array}{ccc}5& 3& 0\\ 3& 5& 0\\ 0& 0& 0\end{array}\right] \\ {A}^{T}A-\lambda I=\left[\begin{array}{ccc}5-\lambda & 3& 0\\ 3& 5-\lambda & 0\\ 0& 0& -\lambda \end{array}\right] \\ solve\left|\begin{array}{c}{A}^{T}A-\lambda I\end{array}\right|⟹{\lambda }_1=8,{\lambda }_2=2,{\lambda }_3=0,\overrightarrow{x_1}=\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],\overrightarrow{x_2}=\left[\begin{array}{c}1\\ -1\\ 0\end{array}\right],\overrightarrow{x_3}=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right] \\ \therefore \overrightarrow{v_1}=\frac{\overrightarrow{x_1}}{\Vert \begin{array}{c}\overrightarrow{x_1}\end{array}\Vert }=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],\overrightarrow{v_2}=\frac{\overrightarrow{x_2}}{\Vert \begin{array}{c}\overrightarrow{x_2}\end{array}\Vert }=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\\ 0\end{array}\right],\overrightarrow{v_3}=\frac{\overrightarrow{x_3}}{\Vert \begin{array}{c}\overrightarrow{x_3}\end{array}\Vert }=\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 \\ \overrightarrow{u_1}=\frac{A\overrightarrow{v_1}}{{\sigma }_1}=\left[\begin{array}{ccc}2& 2& 0\\ -1& 1& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]\frac{1}{\sqrt{8}}=\frac{1}{4}\left[\begin{array}{c}4\\ 0\end{array}\right]=\left[\begin{array}{c}1\\ 0\end{array}\right] \\ \overrightarrow{u_2}=\frac{A\overrightarrow{v_2}}{{\sigma }_2}=\left[\begin{array}{ccc}2& 2& 0\\ -1& 1& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\\ 0\end{array}\right]\frac{1}{\sqrt{2}}=\frac{1}{2}\left[\begin{array}{c}0\\ -2\end{array}\right]=\left[\begin{array}{c}0\\ -1\end{array}\right] \\ \therefore A=U\mathrm{\Sigma }{V}^T=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]\left[\begin{array}{ccc}\sqrt{8}& 0& 0\\ 0& \sqrt{2}& 0\end{array}\right]\left[\begin{array}{ccc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}& 0\\ \frac{1}{\sqrt{2}}& \frac{-1}{\sqrt{2}}& 0\\ 0& 0& 1\end{array}\right] \end{gathered}$$

• If

  $M$ is symmetric,
  $i.e.M^T=M$ ,
  $\{{\sigma }_i\}$ is the absolute value of
  $M$'s eigenvalues
  
  $$\begin{gathered} M=U\mathrm{\Sigma }{V}^T \\ M{M}^T=(U\mathrm{\Sigma }{V}^T)(V{\mathrm{\Sigma }}^T{U}^T)=U{\mathrm{\Sigma }}^2{U}^T\text{ where }U\text{ is orthogonal} \end{gathered}$$
  Recall (EVD: Matrix diagonalization):
  $A=S\mathrm{\Lambda }{S}^{-1}$
  
  $M{M}^T=U{\mathrm{\Sigma }}^2{U}^T⟹{\mathrm{\Sigma }}^2\text{ contains the eigenvalues of }M{M}^T⟹\mathrm{\Sigma }\text{ has }{M}^{\prime }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

  $A{A}^T,A=U\mathrm{\Sigma }{V}^T=EV(A{A}^T)\times \sqrt{{\lambda }_i}\times EV(A^{T}A)$
  
  $A{A}^T=(U\mathrm{\Sigma }{V}^T)(V{\mathrm{\Sigma }}^T{U}^T)=U\mathrm{\Sigma }{\mathrm{\Sigma }}^T{U}^T$
  where
  $\mathrm{\Sigma }{\mathrm{\Sigma }}^T=\left[\begin{array}{ccccccc}{\sigma }_1^2& & & & & & \\ & {\sigma }_2^2& & & & & \\ & & \ddots & & & & \\ & & & {\sigma }_r^2& & & \\ & & & & 0& & \\ & & & & & \ddots & \\ & & & & & & 0\end{array}\right]=\left[\begin{array}{ccccccc}{\lambda }_1& & & & & & \\ & {\lambda }_2& & & & & \\ & & \ddots & & & & \\ & & & {\lambda }_r& & & \\ & & & & 0& & \\ & & & & & \ddots & \\ & & & & & & 0\end{array}\right]$
  
  $\therefore A{A}^T=U\mathrm{\Sigma }{\mathrm{\Sigma }}^T{U}^T$ is the EVD of
  $A{A}^T$ where
  $\mathrm{\Sigma }{\mathrm{\Sigma }}^T$ contains eigenvalues of
  $A{A}^T$ and
  $\overrightarrow{u_1},\overrightarrow{u_2},\cdots ,\overrightarrow{u_m}$ are eigenvectors
  Note that
  $\{{\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_r,\underset{\text{n-r}}{\underbrace{0,\cdots ,0}}\}$ are the eigenvalues of
  $A^{T}A$ with corresponding eigenvectors
  $\{\overrightarrow{v_1},\overrightarrow{v_2},\cdots ,\overrightarrow{v_n}\}$

• Example (Solving Fibonacci Numbers)
  

  $F_{k+2}=F_{k+1}+F_k,fork=0,1,2,\cdots$
  Let
  $\overrightarrow{u_k}=\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]$
  
  $\overrightarrow{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}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\overrightarrow{u_k}$
  
  $\overrightarrow{u_{k+1}}=A\overrightarrow{u_k}$ where
  $A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]⟹\overrightarrow{u_{k+1}}=A^k\overrightarrow{u_0}$
  Find the general form for
  $F_k$
  
  $A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$ has eigenvalues obtained by solving
  $\left|\begin{array}{c}A-\lambda I\end{array}\right|=0$
  
  $$\begin{gathered} \left|\begin{array}{c}A-\lambda I\end{array}\right|=\left|\begin{array}{c}\left[\begin{array}{cc}1-\lambda & 1\\ 1& -\lambda \end{array}\right]\end{array}\right|={\lambda }^2-\lambda -1=0 \\ {\lambda }_1=\frac{1+\sqrt{5}}{2},{\lambda }_2=\frac{1-\sqrt{5}}{2},\overrightarrow{x_1}=\left[\begin{array}{c}\frac{1+\sqrt{5}}{2}\\ 1\end{array}\right]=\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right],\overrightarrow{x_2}=\left[\begin{array}{c}\frac{1-\sqrt{5}}{2}\\ 1\end{array}\right]=\left[\begin{array}{c}{\lambda }_2\\ 1\end{array}\right] \end{gathered}$$
  
  $$\begin{gathered} A=S\mathrm{\Lambda }{S}^{-1}whereS=\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right],S^{-1}=\frac{1}{{\lambda }_1-{\lambda }_2}\left[\begin{array}{cc}1& -{\lambda }_2\\ -1& {\lambda }_1\end{array}\right] \\ \mathrm{\Lambda }=\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right],A^k=A{\mathrm{\Lambda }}^k{S}^{-1},{\mathrm{\Lambda }}_k=\left[\begin{array}{cc}{\lambda }_1^k& 0\\ 0& {\lambda }_2^k\end{array}\right] \\ \begin{array}{rl}\overrightarrow{u_{k+1}}=& A^k\overrightarrow{u_0}\\ =& \left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\lambda }_1^k& 0\\ 0& {\lambda }_2^k\end{array}\right]\frac{1}{{\lambda }_1-{\lambda }_2}\left[\begin{array}{cc}1& -{\lambda }_2\\ -1& {\lambda }_1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\\ =& \frac{1}{{\lambda }_1-{\lambda }_2}\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\lambda }_1^k& 0\\ 0& {\lambda }_2^k\end{array}\right]\left[\begin{array}{c}1\\ -1\end{array}\right]\\ =& \frac{1}{{\lambda }_1-{\lambda }_2}\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]\left[\begin{array}{c}{\lambda }_1^k\\ -{\lambda }_2^k\end{array}\right]\\ =& \frac{1}{{\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]\\ ⟹& F_k=\frac{{\lambda }_1^k-{\lambda }_2^k}{{\lambda }_1-{\lambda }_2}=\frac{{\lambda }_1^k-{\lambda }_2^k}{\sqrt{5}}\end{array} \end{gathered}$$
  As
  $k\to \mathrm{\infty }$
  
  $\begin{array}{rl}\underset{k\to \mathrm{\infty }}{lim}\frac{F_{k+1}}{F_k}& =\underset{k\to \mathrm{\infty }}{lim}\frac{{\lambda }_1^{k+1}-{\lambda }_2^{k+1}}{{\lambda }_1^k-{\lambda }_2^k}\\ & =\underset{k\to \mathrm{\infty }}{lim}\frac{({\lambda }_1-{\lambda }_2)({\lambda }_1^k+\cdots +{\lambda }_2^k)}{({\lambda }_1-{\lambda }_2)({\lambda }_1^{k-1}+\cdots +{\lambda }_2^{k-1})}\\ & =\underset{k\to \mathrm{\infty }}{lim}\frac{{\lambda }_1^k}{{\lambda }_1^{k-1}}(\because \left|\begin{array}{c}{\lambda }_1\end{array}\right|>1,\left|\begin{array}{c}{\lambda }_2\end{array}\right|<1)\\ & ={\lambda }_1=\frac{1+\sqrt{5}}{2}\text{ (Golden ratio)}\end{array}$

• The matrices

  $U$ and
  $V$ contain orthonormal bases for all four subspaces:
  
  $$\begin{array}{rlr}& \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{array}$$
  Note that
  $A^{T}A\overrightarrow{v_i}={\lambda }_i\overrightarrow{v_i}fori=1,\cdots ,r⟹A^T\frac{A\overrightarrow{v_i}}{{\lambda }_i}=\overrightarrow{v_i}$
  
  $\text{Let }\overrightarrow{y_i}=\frac{A\overrightarrow{v_i}}{{\lambda }_i}⟹A^T\overrightarrow{y_i}=\overrightarrow{v_i}⟹\overrightarrow{v_i}\in C(A^T),dim(C(A^T))=r$
  
  $\because \{\overrightarrow{v_1},\overrightarrow{v_2},\cdots ,\overrightarrow{v_r}\}$ is a set of orthonormal vectors
  
  $⟹\{\overrightarrow{v_1},\overrightarrow{v_2},\cdots ,\overrightarrow{v_r}\}$ is a set of orthonormal basis of
  $C(A^T)$
  when
  $(r+1)\le i\le n,A^{T}A\overrightarrow{v_i}=\overrightarrow{0}⟹\{\overrightarrow{v_{r+1}},\cdots ,\overrightarrow{v_n}\}$ are
  $n-r$ orthonormal vectors
  
  $\because N(A)$ has dimension
  $n-r⟹\{\overrightarrow{v_{r+1}},\cdots ,\overrightarrow{v_n}\}$ is a set of orthonormal basis of
  $N(A)$
  
  $A\overrightarrow{v_i}={\sigma }_i\overrightarrow{u_i}fori=1,\cdots ,r⟹A\frac{\overrightarrow{v_i}}{sigm{a}_i}=\overrightarrow{u_i}$
  
  $\text{Let }\overrightarrow{x_i}=\frac{\overrightarrow{v_i}}{sigm{a}_i}⟹A\overrightarrow{x_i}=\overrightarrow{u_i}⟹\overrightarrow{u_i}\in C(A)$
  
  $\{\overrightarrow{u_1},\overrightarrow{u_2},\cdots ,\overrightarrow{u_r}\}$ is a set of orthonormal basis of
  $C(A)$
  when
  $(r+1)\le i\le m,\{\overrightarrow{u_{r+1}},\cdots ,\overrightarrow{u_m}\}$ is a set of orthonormal basis of
  $N(A^T)$