Revision as of 00:31, 14 November 2015

Eigen Decomposition

Eigen Decomposition or, sometimes, Eigenvalue Decomposition (shortcut EVD)

• is a way of diagonalizing a square $n \times n$ matrix $A$

We can turn a matrix into a diagonal one by using eigenvectors

• $A$ is square

Eigenvalue decomposition is a decomposition of a matrix into a "canonical form"

• we want to constrict a diagonal matrix from a given one
• a matrix $A$ is diagonalizable if it's similar to a diagonal matrix
  • (a matrix $A$ is similar to $B$ if there exists an invertible $M$ s.t. $B = M^{-1} A \, M$)
• $A$ is diagonalizable if there exists invertible matrix $P$ s.t. $P^{-1} A \, P$ is diagonal

Why can we do it?

• if all eigenvalues $\lambda_1, \ ... \ , \lambda_n$ are different
• then all eigenvalues $\mathbf x_1, \ ... \ , \mathbf x_n$ are linearly independent
• so any matrix with distinct eigenvalues can be decomposed by eigenvalue decomposition
• see proof in Eigenvalues and Eigenvectors

Diagonalization:

• $S^{-1} A S = \Lambda$
• $\Lambda = \text{diag } (\lambda_1, \ ... \ , \lambda_n)$

Eigenvalue Decomposition:

• if $A$ is symmetric, then there exists $S$ and $\Lambda$ s.t.
• $A = S \Lambda S^T$
• because for symmetric $A$ the eigenvectors in $S$ are orthonormal, so $S$ is Orthogonal

Intuition

Suppose we have $n$ linearly independent eigenvectors $\mathbf x_i$ of $A$

• let's put them in columns of a matrix $S$ - eigenvector matrix
• [math]S = \begin{bmatrix} | & & | \\ \mathbf x_1 & ... & \mathbf x_n \\ | & & | \\ \end{bmatrix}[/math]

Now what if we multiply $AS$?

• since all these $\mathbf x_i$ are eigenvectors, $A \mathbf x_i = \lambda_i \mathbf x_i$
• thus, [math]AS = A \begin{bmatrix} | & | & & | \\ \mathbf x_1 & \mathbf x_2 & ... & \mathbf x_n \\ | & | & & | \\ \end{bmatrix} = \begin{bmatrix} | & | & & | \\ \lambda_1 \, \mathbf x_1 & \lambda_2 \, \mathbf x_2 & ... & \lambda_m \, \mathbf x_n \\ | & | & & | \\ \end{bmatrix}[/math]
• ok, now let's take the $\lambda_i$'s out: [math]\begin{bmatrix} | & & | \\ \lambda_1 \, \mathbf x_1 & \lambda_2 \, \mathbf x_2 & ... & \lambda_m \, \mathbf x_n \\ | & & | \\ \end{bmatrix} = \begin{bmatrix} | & | & & | \\ \mathbf x_1 & \mathbf x_2 & ... & \mathbf x_n \\ | & | & & | \\ \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \\ \end{bmatrix}[/math]
• let's call this diagonal matrix [math]\Lambda = \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \\ \end{bmatrix}[/math]
• so $AS = S \Lambda$

Decomposition

• if $S$ is invertible (or all $\mathbf x_i$ are independent), then
• $\Lambda = S^{-1} A \, S$ - this is called diagonalization of $A$
• and $A = S \Lambda S^{-1}$ - another factorization of $A$
• if $A$ is diagonal, then $\Lambda = A$, but if it's triangular, we still need to calculate $\Lambda$

Symmetric Matrices

For symmetric $A$

• its eigenvalues are orthonormal,
• so the matrix $S$ is orthogonal
• thus, $A = S \Lambda S^{-1} = S \Lambda S^T$
• So we write $A = Q \Lambda Q^T$, where $Q$ is orthogonal

Use Cases

Calculating Powers: $A^k$

• if $A \mathbf x = \lambda \mathbf x$ then
• $A^2 \mathbf x = \lambda A \mathbf x = \lambda^2 \mathbf x$
• so $\lambda$s are squared when $A$ is squared

same for diagonalizable matrices:

• $A^2 = A A = (S \Lambda S^{-1}) (S \Lambda S^{-1}) = S \Lambda^2 S^{-1}$
• and $A^k = S \Lambda^k S^{-1}$
• so this factorization is better for powers than LU Factorization

This is useful for calculating the steady state probabilities of Markov Chains - by calculating the powers of Stochastic Matrices - matrix representation of a Markov Chain

Recurrence Equation

Suppose you are given a vector $\mathbf u_0$ and a recurrent formula $\mathbf u_{k+1} = A \mathbf u_{k}$

• how would you find $\mathbf u_{100}$?
• can repeat it 100 times
• or, note that $\mathbf u_{100} = A \mathbf u_{99} = A^2 \mathbf u_{98} = \ ... \ = A^{100} \mathbf u_{0}$

• Suppose $A$ is invertible.
• Then one possible basis for $A$ is its eigenvectors $\mathbf v_i$
• let's express $\mathbf u_0$ in this basis: $\mathbf u_0 = c_1 \mathbf v_1 + \ ... \ + c_n \mathbf v_n = S \mathbf c$
• now let's multiply both parts by $A$:
  • $A \mathbf u_0 = A c_1 \mathbf v_1 + \ ... \ + A c_n \mathbf v_n = A S \mathbf c$
  • $A \mathbf u_0 = c_1 \lambda_1 \mathbf v_1 + \ ... \ + c_n \lambda_n \mathbf v_n = \Lambda S \mathbf c$
• then $\mathbf u_{100} = c_1 \lambda_1^{100} \mathbf v_1 + \ ... \ + c_n \lambda_n^{100} \mathbf v_n = \Lambda^{100} S \mathbf c$

Fibonacci Numbers

• Fibonacci numbers is a sequence 0, 1, 1, 2, 3, 5, 8, 13...
• $F_{k + 2} = F_{k+ 1} + F_{k}$
• it's a second order Recurrence Equation
• Let's build a system: [math]\begin{cases} F_{k+2} = F_{k+1} + F_{k} \\ F_{k+1} = F_{k+1} \\ \end{cases}[/math]
• so let $\mathbf u_k = \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}$,
• then $\mathbf u_{k + 1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix} = A \, \mathbf u_k$
• so we have the recurrence equation $\mathbf u_{k+1} = A \mathbf u_k$
• note that $A$ is symmetric, so it's diagonalizable
• let's find eigenvalues:
  • [math]| A - \lambda I | = \begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix} = \lambda^2 - \lambda - 1 = 0[/math]
  • or $\lambda_{1,2} = \cfrac{1 \pm \sqrt{1+4}}{2} = \cfrac{1 \pm \sqrt{5}}{2}$
  • $\lambda_1 = 0.5 \, (1 + \sqrt{5}) \approx 1.618$
  • $\lambda_1 = 0.5 \, (1 - \sqrt{5}) \approx -0.618$
• so, $\mathbf u_{100} = c_1 \lambda_1^{100} \mathbf v_1 + c_2 \lambda_2^{100} \mathbf v_2$
  • $\lambda_1 > 1$ so powers of it grow faster, and $|\lambda_2| < 1$, so its powers decay
  • thus $\lambda_1$ controls everything
• and we can approximate $F_{100} \approx c_1 \lambda_1^{100}$

Sources

• Linear Algebra MIT 18.06 (OCW)
• http://en.wikipedia.org/wiki/Diagonalizable_matrix
• Strang, G. Introduction to linear algebra.