Ch 4.2. Eigendecomposition and diagonalisation

• Prev: matrix-decompositions

Summary:

• Eigenvalues and Eigenvectors
  • Eigenvectors are the vectors that does not change its orientation when multiplied by the transition matrix, but it just scales by a factor of corresponding eigenvalues.
• Diagonalization & Eigendecomposition
  • A few applications of eigenvalues and eigenvectors that are very useful when handing the data in a matrix form because you could decompose them into matrices that are easy to manipulate.
• Underlying assumption behind the diagonalization and eigendecomposition
  • Make sure that the matrix you are trying to decompose is a square matrix and has linearly independent eigenvectors (different eigenvalues).

Eigenvalue Problem and the Characteristic Polynomial

A non-zero vector $\text{v}$ of dim. ${\mathbb{R}}^n$ is an eigenvector of square matrix $\text{A}:\text{A}\in {\mathbb{R}}^{n\times n}$

• if it satisfies a linear equation of the form: $\text{Av}=\lambda \text{v}$; for some scalar $\lambda$ which we are solving for
  • This is called the eigenvalue equation/problem
  • Geometric intuition: The eigenvector(s) of $\text{A}$ are the vector(s) ($\text{v}$) which $\text{A}$ only elongates/shrinks, and never takes off it’s span(s).
    • The amount of this elongation/shrink is $\lambda$, a scalar value
• Rearranging the eigenvalue problem:

$$\begin{array}{rl}\text{Av}& =\lambda \text{v}\\ \text{Av}& =(\lambda \text{I})\text{v}=\left[\begin{array}{cccc}\lambda & 0& \dots & 0\\ 0& \lambda & \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & \lambda \end{array}\right]\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right]\\ (\text{A}-\lambda \text{I})\text{v}& =\text{0}\end{array}$$

$\text{Since }\text{v}\ne \text{0}\text{, solve for:}$

$$\begin{array}{rl}p(\lambda )=\text{det}(\text{A}-\lambda \text{I})& =\text{0}\end{array}$$

• The only way for $(\text{A}-\lambda \text{I})\text{v}=\text{0}$ to be possible (given non-zero $\text{v}$) is if $\text{det}(\text{A}-\lambda \text{I})=\text{0}$
  • i.e. The matrix $(\text{A}-\lambda \text{I}$) represents a linear transformation of the vector space which “reduces” its dimensionality (at least 1 dim is lost)
  • A matrix cannot squish non-zero vectors into the $\vec{0}$ vector, except when their determinant is 0
• By computing the determinant, we get the eigenvalues ${\lambda }_1,{\lambda }_2(,...,{\lambda }_n)$ (1 for each dimension of the square matrix).
  • Computing $\text{det}(\text{A}-\lambda \text{I})$ requires solving a characteristic polynomial whose roots are the $\lambda$(s)

Why the $\text{det}(\text{A}-\lambda \text{I})=\text{0}$ observation matters

• The observation that $\text{det}(\text{A}-\lambda \text{I})\equiv \text{0}$ is only useful because solving it yields the eigenvalues $\lambda$s.
  • Those helps us solve for the eigenvectors $\text{v}$‘s (i.e. those vectors that this diagonally altered matrix $(\text{A}-\lambda \text{I})$ “shrinks” to 0)

# A = np.random.randn(4,4)
# A = np.array([[3,1],
#              [0,2]])
 
import numpy as np
 
A = np.array([[4, 2, 2], [2, 4, 2], [2, 2, 4]])
# A = np.diag((1,2,3))
detA = np.linalg.det(A)
 
print("A:\n", A)
print("determinant(A):", detA)
 
eig_vals, eig_vecs = np.linalg.eig(A)
# eig_vals,eig_vecs = np.linalg.eigh(A)
# eig_vals,eig_vecs = scipy.linalg.eig(A)
 
print("\nEigenvalues - shape:", eig_vals.shape, "values:", np.round(eig_vals, 0))
print(
    "\nEigenvectors - shape:", eig_vecs.shape, "values:\n", np.round(eig_vecs.T, 2)
)  # not sure why this is so different to Wolfram and others
 
# Link 1: https://www.wolframalpha.com/input?i=eigenvectors+of+%7B%7B4%2C2%2C2%7D%2C%7B2%2C4%2C2%7D%2C%7B2%2C2%2C4%7D%7D
# Link 2: https://matrixcalc.org/vectors.html#eigenvectors%28%7B%7B4,2,2%7D,%7B2,4,2%7D,%7B2,2,4%7D%7D%29
 
# But let's test it against the eigenvalue problem: Av = λv (
print("Check against the Eigenvalue Problem Av = λv")
print("\nAv:\n", A @ eig_vecs)
print("\nλv:\n", eig_vals * eig_vecs)
 

A:
 [[4 2 2]
 [2 4 2]
 [2 2 4]]
determinant(A): 32.0
 
Eigenvalues - shape: (3,) values: [2. 8. 2.]
 
Eigenvectors - shape: (3, 3) values:
 [[-0.82  0.41  0.41]
 [ 0.58  0.58  0.58]
 [ 0.51 -0.81  0.3 ]]
Check against the Eigenvalue Problem Av = λv
 
Av:
 [[-1.63299316  4.61880215  1.01339709]
 [ 0.81649658  4.61880215 -1.61564839]
 [ 0.81649658  4.61880215  0.6022513 ]]
 
λv:
 [[-1.63299316  4.61880215  1.01339709]
 [ 0.81649658  4.61880215 -1.61564839]
 [ 0.81649658  4.61880215  0.6022513 ]]

Eigenbasis, Diagonalisation, and Eigen-decomposition

Eigenbasis

• If our basis vectors ($\hat{i}=\left[\begin{array}{c}1\\ 0\end{array}\right],\hat{j}=\left[\begin{array}{c}0\\ 1\end{array}\right],\dots$) are themselves eigenvectors, it is called an eigenbasis.
• Then if we inspect $\text{A}$, the transformation matrix, it will have the form known as a Diagonal Matrix:

${\text{A}}_{\text{diag}}=\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right]$

• Its form is (diagonal) because recall $\text{A}$ only scales (stretch/shrink) its eigenvectors, which in this case are the basis vectors
  • It is very easy to compute large powers of diagonal matrices (they simply scale vectors by the eigenvalues)

Diagonalisation: Using the Eigenbasis to Diagonalise any non-diagonal $\text{A}$

1. Find the eigenvectors of $\text{A}$
2. Make a change of basis matrix $\text{S}$ whose columns are the eigenvectors of $\text{A}$. We’ll use this to switch the coordinate system of $\text{A}$
3. Diagonalise $\text{A}$ to get $\Lambda$ by doing this: $\Lambda ={\text{S}}^{-1}\text{AS}$
4. The new matrix $\Lambda$ is guaranteed to be diagonal, with its eigenvalues on the main diagonal

Derivation: Why is diagonalisation $\Lambda ={\text{S}}^{-1}\text{AS}$ possible in the first place?

Show that $\text{AS=S}\Lambda$

• Suppose we have $m$ linearly independent eigenvectors of $\text{A}$;
  • then $\text{S}$ is a matrix, where each column is an eigenvector of $\text{A}$, ${\text{v}}_{1\dots m}$
  • $\text{AS = A}\left[\begin{array}{cccc}{v}_1& v_2& \dots & v_m\end{array}\right]=\left[\begin{array}{cccc}\text{A}{v}_1& \text{A}{v}_2& \dots & \text{A}{v}_m\end{array}\right]=\left[\begin{array}{cccc}{\lambda }_1{v}_1& {\lambda }_2{v}_2& \dots & {\lambda }_m{v}_m\end{array}\right]$ (final step because recall $\text{Av}=\lambda$)
• And so $\left[\begin{array}{cccc}{\lambda }_1{v}_1& {\lambda }_2{v}_2& \dots & {\lambda }_m{v}_m\end{array}\right]$ = $\left[\begin{array}{cccc}{v}_1& v_2& \dots & v_m\end{array}\right]\left[\begin{array}{cccc}{\lambda }_1& 0& \dots & 0\\ 0& {\lambda }_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & {\lambda }_m\end{array}\right]$ which is $\text{S}\Lambda$

Assumptions:

The matrix $\text{A}$ you are trying to decompose must:

• be a square matrix
• have linearly independent eigenvectors (different eigenvalues, 1 for each row of the matrix)

print("Recall A:\n", A)
print("\nAnd as calculated earlier for A:")
print("\nEigenvalues:", np.round(eig_vals, 0))
print("\nEigenvectors:\n", np.round(eig_vecs.T, 2))
print("\n------\n")
 
# Define a change of basis matrix S, and then diagonalise A using Lambda = S^(-1) A S
S = eig_vecs
Lambda = np.linalg.inv(S) @ A @ S
 
print("Lambda = S^-1 @ A @ S:\n", np.round(Lambda, 2))
 

Recall A:
 [[4 2 2]
 [2 4 2]
 [2 2 4]]
 
And as calculated earlier for A:
 
Eigenvalues: [2. 8. 2.]
 
Eigenvectors:
 [[-0.82  0.41  0.41]
 [ 0.58  0.58  0.58]
 [ 0.51 -0.81  0.3 ]]
 
------
 
Lambda = S^-1 @ A @ S:
 [[ 2.  0. -0.]
 [ 0.  8. -0.]
 [-0. -0.  2.]]

Now that we know $\text{AS=S}\Lambda$, we can do:

Diagonalisation:

• Takes $\text{A}$ matrix to produce $\Lambda$, a diagonal matrix with eigenvalues on the main diagonal
• Multiply both sides by ${\text{S}}^{-1}$ from the left.

$$\begin{array}{rl}{\text{S}}^{-1}\times \text{AS}& ={\text{S}}^{-1}\times S\Lambda \\ {\text{S}}^{-1}\text{AS}& ={\text{S}}^{-1}\text{S}\Lambda \\ {\text{S}}^{-1}\text{AS}& =\Lambda \\ & \\ \Lambda & ={\text{S}}^{-1}\text{AS}\end{array}$$

Eigendecomposition

• After diagonalising $\text{A}$ to get $\Lambda$, we can use eigendecomposition to do quick matrix multiplications of $\text{A}$
• Multiply both sides by ${\text{S}}^{-1}$ from the right

$$\begin{array}{rl}\text{AS}\times {\text{S}}^{-1}& =\text{S}\Lambda \times {\text{S}}^{-1}\\ {\text{ASS}}^{-1}& =\text{S}\Lambda {\text{S}}^{-1}\\ \text{A}& =\text{S}\Lambda {\text{S}}^{-1}\end{array}$$

$\text{Now note, if we raise A to arbitrary powers}$

$$\begin{array}{rl}{\text{A}}^2& =(\text{S}\Lambda {\text{S}}^{-1})(\text{S}\Lambda {\text{S}}^{-1})\\ & =\text{S}\Lambda ({\text{S}}^{-1}\text{S})\Lambda {\text{S}}^{-1}=\text{S}{\Lambda }^2{\text{S}}^{-1}\\ & \\ \text{In general }{\text{A}}^k& =\text{S}{\Lambda }^k{\text{S}}^{-1}\end{array}$$

# Perform eigendecomposition to recover A from its eigenvectors and eigenvalues
A_eig_decomp = S @ Lambda @ np.linalg.inv(S)
print("A_eigendecomposed = S @ Lambda @ S^-1:\n", A_eig_decomp)
 

A_eigendecomposed = S @ Lambda @ S^-1:
 [[4. 2. 2.]
 [2. 4. 2.]
 [2. 2. 4.]]

Questions

• When exactly do we use decompositions?
• What is the intuition behind an eigenvalue and eigenvector?
• Some interesting edge cases (what are the eigenvalues and eigenvectors for):
  • A rotation-only matrix like $\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$ has only imaginary $\lambda =i$. No eigenvectors, as each vector is rotated
  • A shear matrix like $\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]$: only 1 eigenvalue ($\lambda =1$), so only 1 eigenvector (all vectors on the $x$-axis are eigenvectors)
  • A scaling-only matrix like $\left[\begin{array}{cc}2& 0\\ 0& 2\end{array}\right]$: only 1 eigenvalue ($\lambda =2$), but all vectors in the plane are eigenvectors, and scaled by a factor of $2$