Matrix Powers Through Diagonalization

1. The Power of Diagonalization

Let's start by exploring what happens when we want to compute $A^2$. If $A$ is diagonalizable, we can write:

$A^2=(PD{P}^{-1})(PD{P}^{-1})$

Notice what happens in the middle. We have $P^{-1}P$. Since $P$ is an invertible matrix, this product is simply the identity matrix, $I$. This leads to a beautiful simplification:

$A^2=PD(P^{-1}P)D{P}^{-1}=PDID{P}^{-1}=P{D}^2{P}^{-1}$

The problem of squaring $A$ has been transformed into the much simpler problem of squaring the diagonal matrix $D$. We can extend this pattern. For $A^3$:

$A^3=A^{2}A=(P{D}^2{P}^{-1})(PD{P}^{-1})=P{D}^2(P^{-1}P)D{P}^{-1}=P{D}^3{P}^{-1}$

This reveals a general and powerful rule.

To see this cancellation trick explained visually, let's watch a short segment from a helpful video.

As the video shows, the general formula for any positive integer power $k$ is:

$A^k=P{D}^k{P}^{-1}$

2. Why is this so much easier?

The formula $A^k=P{D}^k{P}^{-1}$ is a huge computational shortcut for two reasons:

1. Computing $D^k$ is trivial. If $D$ is a diagonal matrix, its $k$-th power is found by simply raising each diagonal entry to the $k$-th power. $$D=\left(\begin{array}{cccc}{\lambda }_1& 0& \dots & 0\\ 0& {\lambda }_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & {\lambda }_n\end{array}\right)⟹D^k=\left(\begin{array}{cccc}{\lambda }_1^k& 0& \dots & 0\\ 0& {\lambda }_2^k& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & {\lambda }_n^k\end{array}\right)$$
2. It replaces many matrix multiplications with just two. Instead of performing $k-1$ expensive matrix-matrix multiplications to find $A^k$, we only need to perform the two multiplications in $P{D}^k{P}^{-1}$, regardless of how large $k$ is. The main work is in the initial diagonalization and finding $P^{-1}$, which you only have to do once.

From your computer science background, you can appreciate the algorithmic efficiency here. The direct computation of $A^k$ is far more costly than the one-time cost of diagonalization followed by this simple three-step process.

3. A Complete Worked Example

Let's walk through the full procedure to compute $A^k$:

1. Diagonalize $A$: Find the eigenvector matrix $P$ and the eigenvalue matrix $D$ such that $A=PD{P}^{-1}$.
2. Compute $D^k$: Raise the diagonal elements of $D$ to the $k$-th power.
3. Find $P^{-1}$: Compute the inverse of the eigenvector matrix.
4. Multiply: Calculate the final result by multiplying the three matrices: $A^k=P(D^k)(P^{-1})$.

The following video provides a complete, step-by-step calculation of $A^{100}$ for a 2x2 matrix. It will tie together everything from the last lesson and this one.

4. Formalizing the Concept and an Application

To reinforce what you've just seen, let's turn to a more formal text resource. It concisely states the proposition for computing matrix powers and presents a fascinating example.

The example in the reading concerning population movement is a simple case of a Markov chain. As $k$ gets large, the term with the smaller eigenvalue ($0.2^k$) vanishes, and the system's state is dominated by the eigenvector associated with the largest eigenvalue ($\lambda =1$). This idea of a system evolving towards a steady state governed by its dominant eigenvalue/eigenvector is a recurring theme in many areas, including Google's PageRank algorithm and the analysis of dynamical systems.

Conclusion

You have now learned one of the most practical applications of eigenvalues and eigenvectors. By leveraging diagonalization, you can compute high powers of a matrix efficiently, a task that would otherwise be computationally intensive or intractable.

Key Takeaways:

• The formula to compute the $k$-th power of a diagonalizable matrix $A$ is $A^k=P{D}^k{P}^{-1}$.
• This method is efficient because computing $D^k$ involves simply raising the individual eigenvalues on the diagonal to the $k$-th power.
• The entire process involves three main stages: diagonalize $A$ to find $P$ and $D$, compute $D^k$, and then multiply the matrices $P$, $D^k$, and $P^{-1}$ to get the result.

Preview of the Next Lesson:

So far, we've noted that not all matrices are diagonalizable. In the next module, we will begin exploring a special, and very important, class of matrices that are always diagonalizable and possess other beautiful properties. We will start by learning to define and identify symmetric (for real numbers) and Hermitian (for complex numbers) matrices. These matrices are the bedrock of quantum mechanics and appear in crucial machine learning applications like Principal Component Analysis (PCA).