Matrix Diagonalization: Conditions and Proofs

Hello! Welcome to the next lesson in our journey through linear algebra.

Introduction

In our last lesson, we mastered the procedure for finding eigenvectors by solving the homogeneous system $(A-\lambda I)\mathbf{x}=0$. We also introduced the crucial concepts of algebraic and geometric multiplicity and saw a preview of what happens when a matrix has a "shortage" of linearly independent eigenvectors.

Today, we will build directly on that foundation to explore one of the most powerful concepts in linear algebra: diagonalization. The central goal of this lesson is to perform the diagonalization of a matrix and prove the conditions under which a matrix is diagonalizable. We will formally define what it means for a matrix to be similar to a diagonal matrix, derive the famous diagonalization equation $A=PD{P}^{-1}$, and, most importantly, establish the rigorous mathematical conditions that guarantee a matrix can be diagonalized.

This process is not just an abstract exercise; it forms the basis for many advanced techniques in AI and data science, including the Principal Component Analysis (PCA) we will study next.

1. The Diagonalization Equation

At its core, diagonalization is about changing our coordinate system. We want to find a basis, composed of the matrix's eigenvectors, in which the linear transformation represented by $A$ becomes simple—a mere scaling along the basis vectors.

A matrix $A$ is diagonalizable if it is similar to a diagonal matrix $D$. This means there exists an invertible matrix $P$ such that:
$D=P^{-1}AP$
Rearranging this gives the more common form, known as the eigendecomposition of $A$:
$A=PD{P}^{-1}$
Let's see how this equation naturally arises from the eigenvalue-eigenvector relations we already know.

Suppose our $n\times n$ matrix $A$ has $n$ linearly independent eigenvectors, ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n$, with corresponding eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$. We have $n$ separate equations:
$A{\mathbf{x}}_1={\lambda }_1{\mathbf{x}}_1$
$A{\mathbf{x}}_2={\lambda }_2{\mathbf{x}}_2$
$⋮$
$A{\mathbf{x}}_n={\lambda }_n{\mathbf{x}}_n$

We can consolidate these $n$ equations into a single, elegant matrix equation.

As shown in the video, by creating a matrix $P$ whose columns are the eigenvectors and a diagonal matrix $D$ whose diagonal entries are the corresponding eigenvalues, we arrive at:
$AP=PD$
Since we assumed the $n$ eigenvectors were linearly independent, the matrix $P$ is invertible. This allows us to multiply by $P^{-1}$ on the right to isolate $A$, or on the left to isolate $D$:
$A=PD{P}^{-1}\text{and}D=P^{-1}AP$

This image provides a clear visual summary of the components.

The Power of Diagonalization

Why is this useful? One immediate application is in computing powers of a matrix. If we need to compute $A^k$, the calculation can be tedious. However, with the diagonalized form, it becomes trivial.

As you saw, computing $A^k$ simplifies beautifully:
$A^k=(PD{P}^{-1})(PD{P}^{-1})\dots (PD{P}^{-1})=PD(P^{-1}P)D\dots D{P}^{-1}=P{D}^k{P}^{-1}$
Since $D$ is diagonal, $D^k$ is just the diagonal matrix with each entry raised to the $k$-th power. This is computationally far more efficient and is fundamental to analyzing systems that evolve over time (discrete dynamical systems).

2. The Condition for Diagonalizability: The Proof

We began our derivation by assuming we had $n$ linearly independent eigenvectors for our $n\times n$ matrix $A$. It turns out this is not just a convenient starting point; it is the fundamental condition for diagonalizability. This leads to a crucial theorem.

Theorem: An $n\times n$ matrix $A$ is diagonalizable if and only if $A$ has $n$ linearly independent eigenvectors.

A set of $n$ linearly independent eigenvectors in ${\mathbb{R}}^n$ forms a basis for ${\mathbb{R}}^n$. Such a basis is called an eigenbasis. So, we can restate the theorem as: A matrix is diagonalizable if and only if it has an eigenbasis.

This is an "if and only if" statement, so the proof requires two parts:

1. If $A$ is diagonalizable, then it has $n$ linearly independent eigenvectors.
2. If $A$ has $n$ linearly independent eigenvectors, then it is diagonalizable.

To solidify your understanding of this proof, let's briefly review the logic here, which is also laid out in the Harvard lecture notes.

This theorem provides the definitive answer to our question. A matrix is diagonalizable precisely when we can find a basis for the entire space ${\mathbb{R}}^n$ consisting of that matrix's eigenvectors. The "shortage" of eigenvectors we discussed in the last lesson is exactly what makes a matrix non-diagonalizable.

3. How to Determine if a Matrix is Diagonalizable

The theorem is clear, but how do we check for $n$ linearly independent eigenvectors in practice? There are two key conditions we can use.

A. A Sufficient Condition: Distinct Eigenvalues

A straightforward shortcut exists if all eigenvalues are unique.

Theorem: If an $n\times n$ matrix $A$ has $n$ distinct eigenvalues, then it is diagonalizable.

Proof Sketch: The proof for this relies on another theorem stating that eigenvectors corresponding to distinct eigenvalues are always linearly independent. Since we have $n$ distinct eigenvalues, we are guaranteed to find $n$ corresponding linearly independent eigenvectors, which satisfies the main condition for diagonalizability.

Important: This condition is sufficient, but not necessary. A matrix with repeated eigenvalues can still be diagonalizable. The identity matrix $I$, for example, is already diagonal, but all its eigenvalues are 1.

B. The Necessary and Sufficient Condition: Multiplicities

This brings us to the most complete and powerful criterion, which connects back to the concepts from our previous lesson.

Theorem (Diagonalization Variant): An $n\times n$ matrix $A$ is diagonalizable if and only if for every eigenvalue $\lambda$:
$\text{Geometric Multiplicity}(\lambda )=\text{Algebraic Multiplicity}(\lambda )$

Recall:

• Algebraic Multiplicity (AM): The number of times $\lambda$ appears as a root in the characteristic polynomial.
• Geometric Multiplicity (GM): The dimension of the eigenspace for $\lambda$, which is the number of linearly independent eigenvectors for that $\lambda$.

We know that for any eigenvalue, $1\le \text{GM}\le \text{AM}$. A matrix is diagonalizable if and only if the geometric multiplicity "reaches" the algebraic multiplicity for all eigenvalues. If for any eigenvalue the GM is strictly less than the AM, the matrix is not diagonalizable because there is a "shortage" of eigenvectors.

Test your understanding!

Let's say a 5x5 matrix $A$ has the characteristic polynomial $p(\lambda )=(\lambda -3{)}^2(\lambda -2{)}^3$.

1. What are the eigenvalues and their algebraic multiplicities?
2. To check if $A$ is diagonalizable, what must you find, and what specific conditions must be met?

Show answer

1. The eigenvalues are ${\lambda }_1=3$ and ${\lambda }_2=2$.

   • The algebraic multiplicity of ${\lambda }_1=3$ is 2.
   • The algebraic multiplicity of ${\lambda }_2=2$ is 3.

2. To check for diagonalizability, you must find the geometric multiplicity for each eigenvalue.

   • Find the dimension of the null space of $(A-3I)$. This is the geometric multiplicity of ${\lambda }_1=3$. For $A$ to be diagonalizable, this dimension must be 2.
   • Find the dimension of the null space of $(A-2I)$. This is the geometric multiplicity of ${\lambda }_2=2$. For $A$ to be diagonalizable, this dimension must be 3.

   If both of these conditions are met, the matrix is diagonalizable. If even one of them fails (e.g., if the GM of $\lambda =3$ is only 1), the matrix is not diagonalizable.

4. The Diagonalization Procedure: An Example

Let's synthesize everything into a concrete procedure and walk through an example.

Steps to Diagonalize an $n\times n$ Matrix $A$:

1. Find the eigenvalues of $A$ by solving the characteristic equation $\det (A-\lambda I)=0$. Note their algebraic multiplicities.
2. Find a basis for each eigenspace. For each distinct eigenvalue $\lambda$, find a basis for the null space of $(A-\lambda I)$. The dimension of this basis is the geometric multiplicity of $\lambda$.
3. Check for diagonalizability. Does the geometric multiplicity equal the algebraic multiplicity for every eigenvalue? Equivalently, do you have a total of $n$ linearly independent eigenvectors from all the eigenspaces combined?
   • If no, the matrix is not diagonalizable.
   • If yes, proceed to the next step.
4. Construct $P$ and $D$.
   • Create the matrix $P$ whose columns are the $n$ linearly independent eigenvectors you found.
   • Create the diagonal matrix $D$ whose diagonal entries are the eigenvalues corresponding to the eigenvectors in $P$, in the same order.
5. You now have the diagonalization $A=PD{P}^{-1}$. You can verify your work by checking if $AP=PD$.

Conclusion

Today, we have delved into the theory and practice of matrix diagonalization. We established that this powerful technique is fundamentally linked to the eigenvector structure of a matrix.

Key Takeaways:

• A matrix $A$ is diagonalizable if it can be written as $A=PD{P}^{-1}$, where $P$ is an invertible matrix of eigenvectors and $D$ is a diagonal matrix of corresponding eigenvalues.
• The necessary and sufficient condition for an $n\times n$ matrix to be diagonalizable is that it must possess $n$ linearly independent eigenvectors.
• This condition is equivalent to requiring that for every eigenvalue, its geometric multiplicity (the dimension of its eigenspace) must be equal to its algebraic multiplicity (its multiplicity as a root of the characteristic polynomial).
• If a matrix has $n$ distinct eigenvalues, it is guaranteed to be diagonalizable.

Preview of the Next Lesson:
The eigendecomposition $A=PD{P}^{-1}$ is the first major matrix factorization we have studied in depth. It is exceptionally useful when $A$ is a square matrix that represents a mapping from a vector space to itself. In our next lesson, we will apply this concept to a specific, highly important matrix in data science: the covariance matrix. By performing an eigendecomposition on the covariance matrix of a dataset, we will derive the formulation of Principal Component Analysis (PCA), a cornerstone of dimensionality reduction.