Matrix Diagonalization

Hello! Welcome to your next lesson in our journey through the mathematical foundations of machine learning.

In the last lesson, we built a strong geometric intuition for eigenvalues and eigenvectors. We defined them through the equation $A x = λ x$ and understood eigenvectors as the special "axes" of a linear transformation that remain pointed in the same direction, only being scaled by their corresponding eigenvalue.

Today, we move from the what to the how and why. Our goal is to perform eigendecomposition on a matrix to diagonalize it. This means we will learn how to break down a matrix into three simpler parts: a matrix of its eigenvectors, a diagonal matrix of its eigenvalues, and the inverse of the eigenvector matrix. This process, also known as diagonalization, is a cornerstone of linear algebra and unlocks powerful analytical and computational tools that are essential for many machine learning algorithms, including those used in computer vision.

1. From Definition to Decomposition

Let's start where we left off. We have a square matrix $A$ and a set of its eigenvectors $v_{1}, v_{2}, \dots, v_{n}$ with corresponding eigenvalues $λ_{1}, λ_{2}, \dots, λ_{n}$ . We can write a separate equation for each eigenvector-eigenvalue pair:

A v_{1} = λ_{1} v_{1} A v_{2} = λ_{2} v_{2} ⋮ A v_{n} = λ_{n} v_{n}

Now, imagine we "stack" all the eigenvectors side-by-side to form a matrix $W$ , and do the same for the eigenvalues, placing them on the diagonal of a matrix $Σ$ .

W = ∣ v_{1} ∣ ∣ v_{2} ∣ \dots ∣ v_{n} ∣ Σ = λ_{1} 0 ⋮ 0 0 λ_{2} ⋮ 0 \dots \dots ⋱ \dots 00 ⋮ λ_{n}

The set of individual equations can be elegantly consolidated into a single matrix equation.

22.2. Eigendecompositions

The following resource from 'Dive into Deep Learning' explains how to combine the individual eigenvector equations into a single, compact matrix equation, which is the key step toward understanding decomposition. It also introduces the final decomposition formula.

Please read the subsection '22.2.2. Decomposing Matrices'. Focus on how the equation A * W = W * Σ is formed and how it's rearranged to get the final decomposition A = W * Σ * W⁻¹.

As you've just read, combining the equations gives us:

A W = W Σ

This equation shows that applying matrix $A$ to its eigenvectors is the same as scaling the eigenvectors by their eigenvalues.

If the eigenvectors are linearly independent (which is true for many, but not all, matrices), the matrix $W$ is invertible. We can then multiply both sides by $W^{- 1}$ on the right to isolate $A$ :

A = W Σ W^{- 1}

This is the eigendecomposition of $A$ . It breaks the matrix $A$ down into its fundamental components: its eigenvectors ( $W$ ) and eigenvalues ( $Σ$ ). This process is also called diagonalization because we have found a way to represent the transformation $A$ by a simple diagonal matrix $Σ$ . The matrices $W$ and $W^{- 1}$ act as a change of basis—they transform vectors into and out of the eigenvector basis, where the action of $A$ is just simple scaling.

2. A Step-by-Step Guide to Eigendecomposition

To perform the decomposition, we first need to find the eigenvalues and eigenvectors. Let's briefly review the algebraic procedure for this.

Find Eigenvalues: Solve the characteristic equation $det (A - λ I) = 0$ for $λ$ . The roots of this polynomial are the eigenvalues.
Find Eigenvectors: For each eigenvalue $λ$ , solve the system of linear equations $(A - λ I) v = 0$ to find the corresponding eigenvector(s) $v$ .

The following reading provides a clear, worked-out example of this entire process.

Eigendecomposition: Beginner's Guide to Matrix ...

This guide from DataCamp walks through a complete example of eigendecomposition for a 2x2 matrix, from finding the characteristic polynomial to constructing the final decomposed form.

Read the sections 'What is Eigendecomposition?' and 'The Mathematics Behind Eigendecomposition'. Follow the example for the matrix A carefully. Note how they first find the eigenvalues (λ=14, 4), then the corresponding eigenvectors, and finally assemble the matrices P (same as our W) and D (same as our Σ).

After following that example, you should be comfortable with the analytical steps required to decompose a simple matrix.

Test your understanding!

Let's say you have performed eigendecomposition and found that $A = W Σ W^{- 1}$ . You want to compute $A^{3}$ . How can the decomposition help you do this efficiently? (Hint: think about what happens when you write out $A \cdot A \cdot A$ ).

Show answer

If we write out $A^{3}$ , we get:
$A^{3} = (W Σ W^{- 1}) (W Σ W^{- 1}) (W Σ W^{- 1})$
The adjacent $W^{- 1} W$ terms cancel out (since $W^{- 1} W = I$ ), leaving:
$A^{3} = W Σ (W^{- 1} W) Σ (W^{- 1} W) Σ W^{- 1} = W Σ I Σ I Σ W^{- 1} = W Σ^{3} W^{- 1}$
Raising a diagonal matrix to a power is extremely easy—you just raise each diagonal element (the eigenvalues) to that power. So, instead of performing two matrix multiplications, you only need to cube the eigenvalues. This principle extends to any power $n$ , making $A^{n} = W Σ^{n} W^{- 1}$ a very efficient way to compute matrix powers.

3. Eigendecomposition in Python with NumPy

While performing eigendecomposition by hand is crucial for understanding the mechanics, in practice, we rely on numerical libraries. Your experience in Python will be very helpful here. We will use the popular NumPy library.

The function numpy.linalg.eig() takes a matrix and returns a tuple containing two elements:

An array of the eigenvalues.
A matrix whose columns are the corresponding eigenvectors.

Let's see how to use it and, most importantly, how to verify that the decomposition is correct.

Eigendecomposition: Beginner's Guide to Matrix ...

This part of the DataCamp article shows the practical implementation of eigendecomposition in Python. Crucially, it demonstrates how to reconstruct the original matrix from the results, confirming the A = PDP⁻¹ relationship.

Read the subsection 'Eigendecomposition in Python'. Pay close attention to the code block where the original matrix A is reconstructed from the eigenvalues and eigenvectors. The @ symbol in Python is used for matrix multiplication.

Let's break down the Python code from the resource.

import numpy as np

# 1. Define the matrix A
A = np.array([[6, 8], [2, 12]])

# 2. Perform eigendecomposition
eigVals, eigVecs = np.linalg.eig(A)

# eigVals is an array of eigenvalues: [ 4. 14.]
# eigVecs is a matrix where columns are eigenvectors
# [[-0.9701425  -0.70710678]
#  [ 0.24253563 -0.70710678]]

# Let's rename for clarity
W = eigVecs
# We need to construct the diagonal matrix Sigma from the eigenvalues
Sigma = np.diag(eigVals)

# 3. Verify the decomposition A = W * Sigma * W^-1
W_inv = np.linalg.inv(W)
A_reconstructed = W @ Sigma @ W_inv

# Let's print the reconstructed matrix
print("Original Matrix A:\n", A)
print("\nReconstructed Matrix A:\n", A_reconstructed)

# The output will show that A_reconstructed is identical to A
# (allowing for tiny floating-point inaccuracies)

This short program demonstrates the entire cycle: decomposing a matrix and then recomposing it to verify the result. This verification step is a powerful way to solidify your understanding of what numpy.linalg.eig provides.

Conclusion

In this lesson, we have connected the definition of eigenvalues and eigenvectors to the powerful factorization method of eigendecomposition.

Key Takeaways:

Eigendecomposition factors a square matrix $A$ into the product of its eigenvector matrix $W$ , a diagonal eigenvalue matrix $Σ$ , and the inverse eigenvector matrix $W^{- 1}$ , such that $A = W Σ W^{- 1}$ .
This process is also known as diagonalization because it represents the action of $A$ via a simple diagonal matrix, using the eigenvectors as a new basis.
The procedure involves first finding the eigenvalues by solving $det (A - λ I) = 0$ , then finding the corresponding eigenvectors by solving $(A - λ I) v = 0$ .
In Python, numpy.linalg.eig(A) computes the eigenvalues and eigenvectors, which can then be used to verify the decomposition.

Preview of the Next Lesson:

So far, we've treated functions like np.linalg.eig and np.linalg.inv as black boxes. To deepen your understanding from first principles, our next lesson will be to implement vector and matrix operations from scratch in Python. We'll write our own functions for basic operations like matrix multiplication, which will give you a much more solid grasp of what's happening under the hood. Following that, we will explore the breadth of NumPy's capabilities more systematically.

Recommended resources

1. From Definition to Decomposition

2. A Step-by-Step Guide to Eigendecomposition

3. Eigendecomposition in Python with NumPy

Conclusion