Eigenbases (recap)

Last time, we discussed eigenbases and when they exist. Specifically, we figured out the following method for finding an eigenbasis for an \(n \times n\) matrix \(A\):

1. Find the eigenvalues of \(A.\)
2. Find a basis for each eigenspace of \(A.\)
3. Put those bases together; this will give a linearly independent list.
4. If this list has \(n\) vectors, then it spans \(\mathbb{R}^n\) (by the unifying theorem) and therefore it is an eigenbasis for \(A.\)
5. Otherwise, it has fewer than \(n\) vectors, and \(A\) has no eigenbasis.

Before we move on, let's look at a relatively common case in which an eigenbasis always exists:

Fact (eigenbases and \(n\) distinct eigenvalues)

Let \(A\) be an \(n \times n\) matrix. If \(A\) has \(n\) distinct eigenvalues, then \(A\) has an eigenbasis.

The reason for this is that, with \(n\) distinct eigenvalues, we are guaranteed to have "enough" eigenvectors to fill out a basis: each eigenspace must be at least \(1\)-dimensional, so we can take one (nonzero) vector from each eigenspace and get an eigenbasis. Note also that each of these eigenvalues must be simple (algebraic multiplicity equal to 1), since the characteristic polynomial \(p_A(\lambda)\) can only have \(n\) roots in total (counting with multiplicity).

Diagonalization

We now explore how eigenbases are useful. We will see that if a matrix \(A\) has an eigenbasis, then it can be expressed in a way that allows powers of \(A\) to be computed very easily. This can be extremely useful when the matrix represents some sort of transition from one time-step to the next, such as in the study of Markov chains or discrete dynamical systems. In such a situation, computing matrix powers is essential to understanding the long-term behavior of the system — what happens after a large number of time-steps.

First, we introduce some terminology:

Definition (diagonalizable, defective)

An \(n \times n\) matrix is called diagonalizable if it has an eigenbasis; otherwise, it is called defective.

For example, on Monday we computed the eigenvalues and eigenspaces of the matrix \[A = \begin{bmatrix} 2 & 3 \\ -1 & 6 \end{bmatrix}.\] The eigenspaces were \[E_3(A) = \text{span} \left( \begin{bmatrix} 3 \\ 1 \end{bmatrix} \right) \qquad \text{and} \qquad E_5(A) = \text{span} \left( \begin{bmatrix} 1 \\ 1 \end{bmatrix} \right).\] The sum of the dimensions of these eigenspaces is \(1 + 1 = 2,\) so \(A\) is diagonalizable, and we can take \(\begin{bmatrix} 3 \\ 1 \end{bmatrix},\) \(\begin{bmatrix} 1 \\ 1 \end{bmatrix}\) as an eigenbasis.

The reason for the term diagonalizable is that diagonalizable matrices can be "represented by" diagonal matrices in a particular way:

Theorem (diagonalization)

Suppose that \(A\) is a \(n \times n\) diagonalizable matrix. Let \(\{\mathbf{v}_1, \dots, \mathbf{v}_n\}\) be an eigenbasis for \(A\) with corresponding eigenvalues \(\lambda_1, \dots, \lambda_n.\) (These eigenvalues are not necessarily distinct.) Define \(n \times n\) matrices \(P\) and \(D\) by \[P = \begin{bmatrix} | & & | \\ \mathbf{v}_1 & \dotsm & \mathbf{v}_n \\ | & & | \end{bmatrix} \qquad \text{and} \qquad D = \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\  & & \lambda_n \end{bmatrix}.\] (That is, \(D\) is a diagonal matrix with \(\lambda_1, \dots, \lambda_n\) as the diagonal entries.) Then \[A = PDP^{-1}.\]

(Note that \(P\) is invertible because its columns form a basis for \(\mathbb{R}^n,\) so it makes sense to write \(P^{-1}.\))

When we speak of "diagonalizing" a matrix \(A,\) we mean writing \(A\) in this form, \[A = PDP^{-1},\] where \(P\) is an invertible matrix and \(D\) is a diagonal matrix.

Example (diagonalization)

For the matrix \(A = \begin{bmatrix} 2 & 3 \\ -1 & 6 \end{bmatrix},\) we have the eigenbasis \(\begin{bmatrix} 3 \\ 1 \end{bmatrix},\) \(\begin{bmatrix} 1 \\ 1 \end{bmatrix}\) with corresponding eigenvalues \(3\) and \(5.\) Then the diagonalization theorem says that \[\underbrace{\begin{bmatrix} 2 & 3 \\ -1 & 6 \end{bmatrix}}_{A} = \underbrace{\begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix}}_{P} \; \underbrace{\begin{bmatrix} 3 & 0 \\ 0 & 5 \end{bmatrix}}_{D} \; \underbrace{\begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix}^{-1}}_{P^{-1}}.\] Notice that the eigenvalues must appear in the same order in \(D\) as the eigenvectors appear in \(P,\) from left to right.

Note that the diagonalization of a matrix is not unique; there are many "arbitrary" choices we have to make during the process. For instance, we could have chosen a different order for the eigenvectors and eigenvalues, or we could have replaced some of the eigenvectors by scalar multiples. Additionally, in the case that some eigenspace has dimension greater than \(1,\) we could take a completely different basis of that eigenspace when constructing an eigenbasis.

Let's now prove the diagonalization theorem.

Proof of this theorem

There's not a great way to actually do the multiplication \(PDP^{-1}\) and compare it to \(A,\) so we'll have to reason more indirectly.

Claim: For each eigenvector \(\mathbf{v}_i,\) we have \[A\mathbf{v}_i = PDP^{-1}\mathbf{v}_i.\] To prove this claim, we manipulate both sides. Since \(\mathbf{v}_i\) is an eigenvector with eigenvalue \(\lambda_i,\) the left-hand side becomes \[A \mathbf{v}_i = \lambda_i \mathbf{v}_i.\] The right-hand side is tougher. Let's take it in steps: first consider \(P^{-1} \mathbf{v}_i.\) This is by definition the unique vector \(\mathbf{x}\) such that \(P\mathbf{x} = \mathbf{v}_i.\) Which vector is it? Well, notice that \(\mathbf{v}_i\) is the \(i\)th column of \(P\) by definition. This means that \(P\mathbf{e}_i = \mathbf{v}_i,\) so \(P^{-1} \mathbf{v}_i = \mathbf{e}_i.\) (Another way to think of this: remember that \(P^{-1}\) is the change-of-basis matrix from the standard basis to the basis \(\{\mathbf{v}_1, \dots, \mathbf{v}_n\}.\) Since \(\mathbf{v}_i\) is the \(i\)th vector in this basis, its coordinate representation in that basis is exactly \(\mathbf{e}_i.\)) Now let's multiply by the diagonal matrix \(D\) to get \[DP^{-1} \mathbf{v}_i = D\mathbf{e}_i = \lambda_i \mathbf{e}_i\] since \(D\mathbf{e}_i\) is the \(i\)th column of \(D.\) Finally, we multiply by \(P,\) which gives \[PDP^{-1} \mathbf{v}_i = \lambda_i P\mathbf{e}_i = \lambda_i \mathbf{v}_i\] since \(\mathbf{v}_i\) is the \(i\)th column of \(P.\) This matches what we found for \(A \mathbf{v}_i,\) so we've proved the claim.

To finish the proof, we use the fact that \(\mathbf{v}_1, \dots, \mathbf{v}_n\) is a basis for \(\mathbb{R}^n.\) We've shown that, for each eigenvector \(\mathbf{v}_i,\) multiplying it by \(A\) is the same as multiplying it by \(PDP^{-1}.\) Then by linearity, the same must be true for any linear combination of \(\mathbf{v}_1, \dots, \mathbf{v}_n\): that is, \[A(c_1 \mathbf{v}_1 + \dotsm + c_n \mathbf{v}_n) = PDP^{-1} (c_1 \mathbf{v}_1 + \dotsm + c_n \mathbf{v}_n).\] But \(\mathbf{v}_1, \dots, \mathbf{v}_n\) span \(\mathbb{R}^n,\) so every vector in \(\mathbb{R}^n\) is a linear combination of them. Thus, \[A \mathbf{v} = PDP^{-1} \mathbf{v} \] for all vectors \(\mathbf{v} \in \mathbb{R}^n,\) which means that \(A\) and \(PDP^{-1}\) must be the same matrix. (In case you're not convinced, note that we can take \(\mathbf{v}\) to be one of the standard basis vectors \(\mathbf{e}_i,\) which shows that \(A\) and \(PDP^{-1}\) have the same \(i\)th column for all \(i.\))

We'll revisit some of the ideas in this proof later when we interpret it using change of basis.

Diagonalization and matrix powers

As previously stated, one of the main reasons to diagonalize a matrix \(A\) is that it makes computing powers of \(A\) very easy. Let's see why.

Suppose we have a diagonalizable matrix \(A\) and we diagonalize it: that is, we write \[A = PDP^{-1}\] where \(P\) is invertible and \(D\) is diagonal. Let's use this formula to compute \(A^2\): we have \[A^2 = PDP^{-1} \cdot PDP^{-1}.\] (Remember that matrix multiplication is not commutative, so we need to write the exact string "\(PDP^{-1}\)" twice!) This may not look very nice, but in the middle we have \(P^{-1}\) and \(P\) next to each other, so they cancel out. Therefore, \[A^2 = PDDP^{-1} = PD^2 P^{-1}.\] How about \(A^3\)? We can take our expression for \(A^2\) and multiply by another copy of \(A\): \[A^3 = A^2 A = PD^2P^{-1} \cdot PDP^{-1} = PD^2 D P^{-1} = PD^3 P^{-1}.\] The same cancellation occurred! You can probably see the pattern now: all of the copies of \(P\) and \(P^{-1}\) in the "middle" of the right-hand side will cancel each other out, and we'll get \[A^k = PD^k P^{-1}\] for all \(k.\) The reason this is so nice is that \(D\) is a diagonal matrix, and it's really easy to take powers of a diagonal matrix! Indeed, if \(D = \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{bmatrix},\) then you can check that \[D^k = \begin{bmatrix} \lambda_1^k & & \\ & \ddots & \\ & & \lambda_n^k \end{bmatrix}.\] Therefore, \(A^k\) can be computed by multiplying \(PD^k P^{-1},\) which is the product of only three matrices (as opposed to having to multiply \(k\) copies of \(A\)).

Example (matrix powers via diagonalization)

Let's again consider the matrix \(A = \begin{bmatrix} 2 & 3 \\ -1 & 6 \end{bmatrix}.\) Suppose you were asked to compute \(A^{100}.\) You'd be absolutely miserable doing it manually! Luckily, \(A\) is diagonalizable, and we computed a diagonalization earlier: \[A = \underbrace{\begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix}}_{P} \; \underbrace{\begin{bmatrix} 3 & 0 \\ 0 & 5 \end{bmatrix}}_{D} \; \underbrace{\begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix}^{-1}}_{P^{-1}}.\] From what we just learned, we get \[\begin{aligned} A^{100} = PD^{100} P^{-1} &= \begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix} \; \begin{bmatrix} 3^{100} & 0 \\ 0 & 5^{100} \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix}^{-1} \\ &= \begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix} \; \begin{bmatrix} 3^{100} & 0 \\ 0 & 5^{100} \end{bmatrix} \; \frac{1}{2} \begin{bmatrix} 1 & -1 \\ -1 & 3 \end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix} \; \begin{bmatrix} 3^{100} & 0 \\ 0 & 5^{100} \end{bmatrix} \; \begin{bmatrix} 1 & -1 \\ -1 & 3 \end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix} 3 & 1 \\ 1 & 1 \end{bmatrix} \; \begin{bmatrix} 3^{100} & -3^{100} \\ -5^{100} & 3 \cdot 5^{100} \end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix} 3 \cdot 3^{100} - 5^{100} & -3 \cdot 3^{100} + 3 \cdot 5^{100} \\ 3^{100} - 5^{100} & -3^{100} + 3 \cdot 5^{100} \end{bmatrix}. \end{aligned}\] If you were doing it manually, you'd be far from done, and once (if) you did finish, you would have no idea the answer could be written in such a way! To underscore how much nicer this method is, my computer tells me that the above evaluates to \[A^{100} = \scriptsize \begin{bmatrix} -3944304526105059027057869760132833131369477483850466591942341492037311 & 11832913578315177081175155412960695428101541834940696639645130798677936 \\ -3944304526105059027058385137653565142700513944980232213215043599559312 & 11832913578315177081175670790481427439432578296070462260917832906199937 \end{bmatrix}.\]

Diagonalization and change of basis

Let's end our discussion of diagonalization on a conceptual note. The idea of diagonalization can be interpreted using change-of-basis. Suppose we have an \(n \times n\) matrix \(A.\) Take a vector \(\mathbf{x} \in \mathbb{R}^n\) with coordinates expressed in the standard basis \(\{\mathbf{e}_1, \dots, \mathbf{e}_n\}\) (as is usual). Multiplying \(\mathbf{x}\) by \(A\) will change its coordinates somehow, but it will be probably rather "messy": each coordinate of \(A\mathbf{x}\) may depend on all the coordinates of \(\mathbf{x}.\) For instance, in our running example \(A = \begin{bmatrix} 2 & 3 \\ -1 & 6 \end{bmatrix},\) we have \[A\mathbf{x} = \begin{bmatrix} 2 & 3 \\ -1 & 6 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 2x_1 + 3x_2 \\ -x_1 + 6x_2 \end{bmatrix}\] where each coordinate depends on both \(x_1\) and \(x_2.\) The reason this occurs is essentially that the standard basis is "arbitrary," and as such, it is not particularly well-suited to computations involving a specific matrix \(A.\)

However, suppose we were working entirely in a different basis for \(\mathbb{R}^n,\) specifically, an eigenbasis for \(A.\) Then computations become much easier! Let \(\mathcal{B} = \{\mathbf{v}_1, \dots, \mathbf{v}_n\}\) be the eigenbasis, with corresponding eigenvalues \(\lambda_1, \dots, \lambda_n.\) If we have a vector \[\mathbf{x} = c_1 \mathbf{v}_1 + \dotsm + c_n \mathbf{v}_n = \begin{bmatrix} c_1 \\ \vdots \\ c_n \end{bmatrix}_{\mathcal{B}},\] then because each \(\mathbf{v}_i\) is an eigenvector, we have \[A\mathbf{x} = c_1 \lambda_1 \mathbf{v}_1 + \dotsm + c_n \lambda_n \mathbf{v}_n = \begin{bmatrix} c_1 \lambda_1 \\ \vdots \\ c_n \lambda_n \end{bmatrix}_{\mathcal{B}}.\] In other words, multiplying by \(A\) just scales the coordinates of \(\mathbf{x},\) without any messiness! This is essentially the point of eigenvectors: they are certain vectors for which multiplying by \(A\) is particularly "nice." If we can write some other vector as a linear combination of eigenvectors, then multiplying that vector by \(A\) will also be "nice."

When we diagonalize a matrix, we are essentially expressing it in terms of an eigenbasis for that matrix. That is, when we write \[A = PDP^{-1},\] remember that \(P^{-1}\) is the change-of-basis matrix from the standard basis to the eigenbasis \(\mathcal{B},\) and \(P\) is the change-of-basis matrix from \(\mathcal{B}\) back to the standard basis. Therefore, the multiplication \(A \mathbf{x} = PDP^{-1} \mathbf{x}\) represents the following process:

1. Start with a vector \(\mathbf{x}\) expressed in the standard basis.
2. Multiply it by \(P^{-1}\) to "convert it" into the eigenbasis \(\mathcal{B}.\)
3. Now that our vector is written in terms of the eigenbasis, we know that multiplying by \(A\) simply scales each component by the corresponding eigenvalue; this is what the diagonal matrix \(D\) is doing.
4. To finish, we need to take our result, which is written in the eigenbasis coordinates, and convert back to the standard basis, so we multiply by \(P.\)

Below is a diagram that depicts this process.