Objectives: Topics
-
Similar matrices
-
Diagonal, similar, and diagonalizable matrices
-
Diagonalizing matrices
Print preview
Section 5.3 Diagonalization
Handout 5.3 Diagonalization
Motivation: It can be useful to take large powers of matrices, for example \(A^k\) for large \(k\text{.}\)
But: Multiplying two \(n\times n\) matrices requires roughly \(n^3\) computations.
Question: Is there a more efficient way to compute \(A^k\text{?}\)
Objectives: Goals
-
Determine whether a matrix can be diagonalized, and if possible diagonalize a square matrix.
-
Apply diagonalization to compute matrix powers.
Definition 5.27 Similarity.
Two \(n\times n\) matrices \(A\) and \(B\) are similar if there exists an invertible matrix \(P\) such that \(A=PBP^{-1}.\)
Matrix similarity is an equivalence relation meaning:
-
Reflexive Property: Every matrix \(A\) is similar to itself.
Solution.
Proof: Let \(A\) be any \(n\times n\) matrix and let \(P = I_n\text{.}\) Then\begin{equation*} A = I_nAI_n = I_nAI_n^{-1} = PAP^{-1}\text{.} \end{equation*}Thus, \(A\) is similar to \(A\text{.}\) -
Symmetric Property: If \(A\) is similar to \(B\text{,}\) then \(B\) is similar to \(A\text{.}\)
Solution.
Proof: Suppose \(A = PBP^{-1}\) for some invertible matrix \(P\text{.}\) By multiplying both sides of the equation by \(P^{-1}\) on the left and \(P\) on the right we get \(P^{-1}AP = P^{-1}(PBP^{-1})P = B\text{.}\) Letting \(R = P^{-1}\text{,}\) we have that \(B = RAR^{-1}\text{,}\) so \(B\) is similar to \(A\text{.}\) -
Transitive Property: If \(A\) is similar to \(B\) and \(B\) is similar to \(C\text{,}\) then \(A\) is similar to \(C\text{.}\)
Solution.
Proof: Suppose \(A = PBP^{-1}\) and \(B = RCR^{-1}\text{.}\) Then we have that\begin{equation*} A = PBP^{-1} = P(RCR^{-1})P^{-1} = (PR)C(PR)^{-1}\text{,} \end{equation*}so \(A\) is similar to \(C\text{.}\)
Theorem 5.28 Characteristic Polynomial of Similar Matrices.
If \(A\) and \(B\) are similar, then they have the same characteristic polynomial.
Solution.
Recall that \(\det(A - \lambda I)\) and \(\det(B - \lambda I)\) are the characteristic polynomials of \(A\) and \(B\text{,}\) respectively. Since \(A\) and \(B\) are similar, we have that \(A = PBP^{-1}\) for some invertible matrix \(P\text{.}\) Note the following:
\(\begin{eqnarray*} \det(A - \lambda I) \amp = \amp \det (PBP^{-1} - \lambda I) \\ \amp = \amp \det(PBP^{-1} - \lambda PP^{-1}) \\ \amp = \amp \det(PBP^{-1} - P \lambda I P^{-1}) \\ \amp = \amp \det(P(B - \lambda I)P^{-1}) \\ \amp = \amp \det(P)\det(B - \lambda I)\det(P^{-1}) \\ \amp = \amp \det(P)\det(P^{-1})\det(B - \lambda I) \\ \amp = \amp \det(PP^{-1})\det(B - \lambda I) \\ \amp = \amp \det(I)\det(B - \lambda I) \\ \amp = \amp \det(B - \lambda I)\end{eqnarray*}\)
Thus, \(\det(A - \lambda I) = \det(B - \lambda I)\text{,}\) so \(A\) and \(B\) have the same characteristic polynomial.
Notes:
-
Similar matrices have exactly the same eigenvalues with exactly the same algebraic multiplicity for each eigenvalue and exactly the same geometric multiplicity for each eigenvalue.
-
The converse of Theorem 5.28 is not true; that is, just because two matrices have the same characterisitc polynomial, that does not mean that they are similar. For example,\begin{equation*} \begin{bmatrix} 0 \amp 1\\ 0 \amp 0 \end{bmatrix} \quad\text{and}\quad \begin{bmatrix} 0 \amp 0\\ 0 \amp 0 \end{bmatrix} \end{equation*}have the same characteristic polynomial, but are not similar because the eigenvalue \(\lambda = 0\) does not have the same geometric multiplicty for each matrix.
Example 5.29.
True or false: If \(A \) is similar to the identity matrix, then \(A\) is equal to the identity matrix.
Solution.
If \(A \) is similar to \(I\text{,}\) then there exists an invertible matrix \(P\) so that \(A = PIP^{-1} = PP^{-1} = I\text{.}\) Thus, \(A\) must be the identity matrix.
Definition 5.30 Diagonal Matrix.
A matrix is diagonal if the only nonzero entries (if any) lie on the main diagonal. In this course, we work only with square diagonal matrices.
Examples of diagonal matrices:
\begin{equation*}
\begin{bmatrix}2 \amp 0\\ 0 \amp 2\end{bmatrix},\quad
\begin{bmatrix}2\end{bmatrix},\quad
I_n,\quad
\begin{bmatrix}0 \amp 0\\ 0 \amp 0\end{bmatrix}.
\end{equation*}
If \(A\) is diagonal, then \(A^k\) is easy to compute by raising diagonal entries to the \(k\)-th power.
Example 5.31 Example: Powers of a Diagonal Matrix.
(a)
Let
\begin{equation*}
A=\begin{bmatrix} 3 \amp 0\\ 0 \amp 0.5 \end{bmatrix}\text{.}
\end{equation*}
Compute \(A^2\) and \(A^k\text{.}\)
Solution.
Note that
\begin{equation*}
A^2 = \begin{bmatrix} 3 \amp 0 \\ 0 \amp 0.5 \end{bmatrix}\begin{bmatrix} 3 \amp 0 \\ 0 \amp 0.5 \end{bmatrix} = \begin{bmatrix} 3^2 \amp 0 \\ 0 \amp 0.5^2 \end{bmatrix}\text{.}
\end{equation*}
It follows that
\begin{equation*}
A^k = \begin{bmatrix} 3^k \amp 0 \\ 0 \amp 0.5^k \end{bmatrix}.
\end{equation*}
(b)
Is this as easy to do if \(A\) is not diagonal?
Solution.
Let \(A = \begin{bmatrix} 1 \amp 2 \\ 3 \amp 4 \end{bmatrix}\text{.}\) Then
\begin{equation*}
A^2 = \begin{bmatrix} 1 \amp 2 \\ 3 \amp 4 \end{bmatrix}\begin{bmatrix} 1 \amp 2 \\ 3 \amp 4 \end{bmatrix} = \begin{bmatrix} 7 \amp 10 \\ 15 \amp 22 \end{bmatrix}\text{.}
\end{equation*}
There is no apparant pattern like there is when \(A\) is diagonal.
(c)
What about if \(A\) is similar to a diagonal matrix?
Solution.
Suppose \(A = PDP^{-1}\) for some invertible matrix \(P\) and some diagonal matrix \(D\text{.}\) Note that
\begin{equation*}
A^2 = (PDP^{-1})^2 = (PDP^{-1})(PDP^{-1}) = PDIDP^{-1} = PD^2P^{-1}\text{.}
\end{equation*}
It follows that \(A^k = PD^kP^{-1}\text{.}\) Therefore, if we know that \(A\) is similar to a diagonal matrix, then we can calculate power of \(A\) much faster than expected.
Definition 5.32 Diagonalizable Matrix.
A matrix \(A\in\mathbb{R}^{n\times n}\) is diagonalizable if it is similar to a diagonal matrix \(D\text{;}\) that is, there exists an invertible matrix \(P\) such that
\begin{equation*}
A=PDP^{-1}.
\end{equation*}
Solution.
First, let’s identify \(D\text{.}\) Since \(D\) is diagonal, every entry not on the diagonal must be zero. Therefore, to identify \(D\text{,}\) we need to identify the \(n\) entries on the diagonal. By Theorem 5.28, \(A\) and \(D\) must have the same characteristic polynomial. Thus, they must have the same eigenvalues. Since \(D\) is diagonal, it is both upper and lower triangular. Therefore, by Theorem 5.6, the eigenvalues of \(D\) are the entries on the diagonal. Hence, the eigenvalues of \(A\) must be the diagonal entries of \(D\text{.}\) So, if the eigenvalues of \(A\) are \(\lambda_1, \lambda_2, \dots, \lambda_n\) (listing repeated eigenvalues the appropriate number of times), then
\begin{equation*}
D = \begin{bmatrix} \lambda_1 \amp \amp \amp \\ \amp \lambda_2 \amp \amp \\ \amp \amp \ddots \amp \\ \amp \amp \amp \lambda_n \end{bmatrix}
\end{equation*}
Caution 1: The above reasoning assumes that the \(n \times n\) matrix \(A\) has \(n\) real eigenvalues (counting multiplicity). What if \(A\) has fewer than \(n\) eigenvalues. For example, if \(A = \begin{bmatrix} 0 \amp 1 \\ -1 \amp 0 \end{bmatrix}\text{,}\) then \(A\) has ZERO real eigenvalues (check this). If \(A\) has fewer than \(n\) eigenvalues, then we WILL NOT be able to fill all the missing entries of \(D\text{.}\) We couldn’t just fill the gaps with 0’s because that would imply that \(D\) had more 0 eigenvalues than \(A\text{.}\) Therefore, in the case where \(A\) has fewer than \(n\) eigenvalues; that is, when the algebraic multiplicities of the eigenvalues add up to less than \(n\text{,}\) then it is IMPOSSIBLE to form \(D\text{.}\) Thus, \(A\) would NOT be diagonalizable.
Assuming we can find \(D\text{,}\) we now need to find \(P\text{.}\) Let \(P = \begin{bmatrix} \vec v_1 \amp \cdots \amp \vec v_n \end{bmatrix}\text{.}\) Then, we can rearrange the equation \(A = PDP^{-1}\) my multiplying by \(P\) on the right of both sides to get \(AP = PD\text{.}\) Note that
\begin{equation*}
AP = A\begin{bmatrix} \vec v_1 \amp \cdots \amp \vec v_n\end{bmatrix} = \begin{bmatrix} A\vec v_1 \amp \cdots \amp A\vec v_n \end{bmatrix}
\end{equation*}
and
\begin{equation*}
PD = \begin{bmatrix}\vec v_1 \amp \cdots \amp \vec v_n \end{bmatrix} \begin{bmatrix} \lambda_1 \amp \amp \amp \\ \amp \lambda_2 \amp \amp \\ \amp \amp \ddots \amp \\ \amp \amp \amp \lambda_n \end{bmatrix} = \begin{bmatrix} \lambda_1\vec v_1 \amp \cdots \amp \lambda_n\vec v_n \end{bmatrix}\text{.}
\end{equation*}
Since \(AP = PD\text{,}\) we can set corresponding columns equal to each other to find \(A\vec v_i = \lambda_i\vec v_i\text{.}\) Since \(\vec v_i \neq \vec 0\) (else \(P\) would not be invertible) we have that the columns \(\vec v_i\) must be eigenvectors of \(A\) corresponding to \(\lambda_i\text{!}\)
Caution 2: Note that \(P\) would fail to be invertible if the columns were linearly independent. Therefore, we must have that the vectors \(\vec v_i\) are linearly independent. Are we guaranteed to be able to find \(n\) linearly independent eigenvectors? This is only possible if every eigenspace is as big as it is supposed to be. For example, if the eigenvalue \(\lambda = 2\) has algebraic multiplicity 3, then we expect the \(2\)-eigenspace to be 3-dimensional. If it is not, then it is impossible for us to find 3 linearly independent eigenvectors corresponding to \(\lambda = 2\text{.}\) Therefore, it would be impossible to form \(P\) since \(P\) must contain \(3\) linearly independent vectors to match with the \(3\) \(\lambda = 2\)’s which are on the diagonal of \(D\text{.}\) Recall that the dimension of the eigenspace is the geometric multiplicity. Therefore, we are unable to find an invertible \(P\) when any eigenvalue has geometric multiplicity less than its algebraic multiplicity. If that happens for any of the eigenvalues, then \(A\) is NOT diagonalizable.
Theorem 5.33 Diagonalization Criterion.
A matrix \(A\) is diagonalizable if and only if \(A\) has \(n\) linearly independent eigenvectors. Equivalently,
\begin{equation*}
A = \bigl[\vec v_1\ \vec v_2\ \cdots\ \vec v_n\bigr]\,
\begin{bmatrix}
\lambda_1 \amp \amp \amp \\
\amp \lambda_2 \amp \amp \\
\amp \amp \ddots \amp \\
\amp \amp \amp \lambda_n
\end{bmatrix}
\bigl[\vec v_1\ \vec v_2\ \cdots\ \vec v_n\bigr]^{-1},
\end{equation*}
where \(\vec v_1,\dots,\vec v_n\) are linearly independent eigenvectors and \(\lambda_1,\dots,\lambda_n\) are the corresponding eigenvalues (in order).
Theorem 5.34 Algebraic vs. Geometric Multiplicity.
Suppose:
-
\(A\) is \(n\times n\text{,}\)
-
\(A\) has distinct eigenvalues \(\lambda_1,\ldots,\lambda_k\) with \(k\le n\text{,}\)
-
\(a_i\) is the algebraic multiplicity of \(\lambda_i\text{,}\)
-
\(d_i\) is the geometric multiplicity (dimension of the \(\lambda_i\)-eigenspace).
Then:
-
\(d_i \le a_i\) for all \(i\text{.}\)
-
\(A\) is diagonalizable \(\ \iff \ \sum_i d_i = n \ \iff \ d_i=a_i\) for all \(i\text{.}\)
-
\(A\) is diagonalizable \(\iff\) the eigenvectors for all eigenvalues together form a basis of \(\mathbb{R}^n\text{.}\)
Theorem 5.35 Diagonalization with Distinct Eigenvalues.
If \(A\) is \(n\times n\) and has \(n\) distinct eigenvalues, then \(A\) is diagonalizable.
Example 5.36.
Diagonalize if possible:
\begin{equation*}
A = \begin{bmatrix}
3 \amp 1\\
0 \amp 3
\end{bmatrix}.
\end{equation*}
Solution.
First, note that by Theorem 5.6 we have that the eigenvalues of \(A\) are \(\lambda = 3\) with algebraic multiplicity 2. Since we have two eigenvalues (counting algebraic multiplicity) and since \(A\) is a \(2 \times 2\) matrix, we know that we can form \(D\text{.}\)
Next, we need to check if we can form \(P\) which, by Theorem 5.34, requires that the geometric multiplicity of \(\lambda = 3\) is the same as the algebraic multiplicity, so 2. Note that
\begin{equation*}
A - 3I = \begin{bmatrix} 0 \amp 1 \\ 0 \amp 0 \end{bmatrix}
\end{equation*}
which only has a single free variable. It follows that the geometric multiplicity of \(\lambda = 3\) is only 1. More precisely, we have that
\begin{equation*}
3\text{-eigenspace}(A) = \Nul(A - 3I) = \Span\left\{\begin{bmatrix} 1 \\ 0 \end{bmatrix}\right\}\text{.}
\end{equation*}
Notice, this does not give enough linearly independent eigenvectors to form \(P\text{.}\) Therefore, \(A\) is not diagonalizable.
Example 5.37.
Diagonalize if possible:
\begin{equation*}
A = \begin{bmatrix}
2 \amp 6\\
0 \amp -1
\end{bmatrix}.
\end{equation*}
Solution.
Again, we can use Theorem 5.6 to see that the eigenvalues of \(A\) are \(\lambda_1 = 2\) and \(\lambda_2 = -1\) with both having algebraic multiplicty of 1. By Theorem 5.9, we know that \(A\) must be diagonalizable. Let’s find linearly independent eigenvectors corresponding to each eigenvalue.
For \(\lambda_1 = 2\text{,}\) we see that
\begin{equation*}
A - 2I = \begin{bmatrix} 0 \amp 6 \\ 0 \amp -3 \end{bmatrix} \sim \begin{bmatrix} 0 \amp 1 \\ 0 \amp 0 \end{bmatrix}.
\end{equation*}
It follows that
\begin{equation*}
2\text{-eigenspace}(A) = \Nul(A - 2I) = \Span\left\{\begin{bmatrix} 1 \\ 0 \end{bmatrix}\right\}\text{.}
\end{equation*}
For \(\lambda_2 = -1\text{,}\) we see that
\begin{equation*}
A - (-1)I = \begin{bmatrix} 3 \amp 6 \\ 0 \amp 0 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 2 \\ 0 \amp 0 \end{bmatrix}.
\end{equation*}
It follows that
\begin{equation*}
-1\text{-eigenspace}(A) = \Nul(A - (-1)I) = \Span\left\{\begin{bmatrix} 2 \\ -1 \end{bmatrix}\right\}\text{.}
\end{equation*}
Since we have found 2 linearly independent eigenvectors, one corresponding to \(\lambda_1 = 2\) and one corresponding to \(\lambda_2 = -1\text{,}\) we can form \(D\) and \(P\text{.}\) Let
\begin{equation*}
D = \begin{bmatrix} 2 \amp 0 \\ 0 \amp -1 \end{bmatrix} \quad \text{and} \quad P = \begin{bmatrix} 1 \amp 2 \\ 0 \amp -1 \end{bmatrix}\text{.}
\end{equation*}
Note that there are many correct choices for \(P\text{.}\) The only criteria for \(P\) is that the first column contains an eigenvector corresponding to the first eigenvalue listed in \(D\) and the second column contains an eigenvector corresponding to the second eigenvalue listed in \(D\text{.}\) You don’t have to use the eigenvectors found above. Also, you are free to swap the order of the eigenvalues in \(D\text{,}\) this would just require that you also switch the columns of \(P\text{.}\)
We can check our solution by calculating \(A = PDP^{-1}\text{.}\) For a \(2 \times 2\) matrix, this isn’t so bad. However, if the matrices were \(3 \times 3\) or higher, calculating \(P^{-1}\) could be annoying. So, instead of checking \(A = PDP^{-1}\text{,}\) it is equivalent to check \(AP = PD\) as long as \(P\) is invertible (which it better be). Note that
\begin{equation*}
AP = \begin{bmatrix} 2 \amp 6 \\ 0 \amp -1 \end{bmatrix} \begin{bmatrix} 1 \amp 2 \\ 0 \amp -1 \end{bmatrix} = \begin{bmatrix} 2 \amp -2 \\ 0 \amp 1 \end{bmatrix}
\end{equation*}
and
\begin{equation*}
PD = \begin{bmatrix} 1 \amp 2 \\ 0 \amp -1 \end{bmatrix} \begin{bmatrix} 2 \amp 0 \\ 0 \amp -1 \end{bmatrix} = \begin{bmatrix} 2 \amp -2 \\ 0 \amp 1 \end{bmatrix}\text{.}
\end{equation*}
Since \(AP = PD\) and since \(D\) is diagonal and \(P\) is invertible, our choice of \(D\) and \(P\) is a valid diagonalization of \(A\text{.}\)
Example 5.38.
The eigenvalues of \(A\) are \(\lambda=3,1\text{.}\) If possible, construct \(P\) and \(D\) such that \(A=PDP^{-1}\text{.}\) Verify by checking that \(AP = PD\text{.}\)
\begin{equation*}
A=\begin{bmatrix}
7 \amp 4 \amp 16\\
2 \amp 5 \amp 8\\
-2 \amp -2 \amp -5
\end{bmatrix}.
\end{equation*}
Solution.
We are given that \(\lambda_1 = 3\) and \(\lambda_2 = 1\) are the eigenvalues of \(A\text{.}\) If both have algebraic multiplicity of 1, then \(A\) is NOT diagonalizable since \(A\) doesn’t have enough eigenvalues. Let’s calculate the geometric multiplicities of each eigenvalue and see if that sheds some light on the algebraic multiplicities.
For \(\lambda_1 = 3\text{,}\) note that
\begin{equation*}
A - 3I = \begin{bmatrix} 4 \amp 4 \amp 16 \\ 2 \amp 2 \amp 8 \\ -2 \amp -2 \amp -8 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 1 \amp 4 \\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \end{bmatrix}
\end{equation*}
which has two free variables. It follows that
\begin{equation*}
3\text{-eigenspace}(A) = \Nul(A - 3I) = \Span\left\{\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}, \begin{bmatrix} -4 \\ 0 \\ 1 \end{bmatrix}\right\}\text{.}
\end{equation*}
Thus, the geometric multiplicity of \(\lambda_1 = 3\) is 2, which means the algebraic multiplicity of \(\lambda_1 = 3\) is 2 as well.
For \(\lambda_2 = 1\text{,}\) note that
\begin{equation*}
A - I = \begin{bmatrix} 6 \amp 4 \amp 16 \\ 2 \amp 4 \amp 8 \\ -2 \amp -2 \amp -6 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 1 \amp 3 \\ 1 \amp 2 \amp 4 \\ 3 \amp 2 \amp 8 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 0 \amp 2 \\ 0 \amp 1 \amp 1 \\ 0 \amp 0 \amp 0 \end{bmatrix}\text{.}
\end{equation*}
It follows that
\begin{equation*}
1\text{-eigenspace}(A) = \Nul(A - I) = \Span\left\{\begin{bmatrix} 2 \\ 1 \\ -1 \end{bmatrix}\right\}\text{.}
\end{equation*}
Thus, we have that
\begin{equation*}
D = \begin{bmatrix} 3 \amp 0 \amp 0 \\ 0 \amp 3 \amp 0 \\ 0 \amp 0 \amp 1 \end{bmatrix} \quad \text{and} \quad P = \begin{bmatrix} 1 \amp -4 \amp 2 \\ -1 \amp 0 \amp 1 \\ 0 \amp 1 \amp -1 \end{bmatrix}
\end{equation*}
is a possible diagonalization of \(A\text{.}\) As mentioned in previous examples, this is not the only possible diagonalization of \(A\text{.}\) You could swap around the eigenvalues on the diagonal of \(D\) and the corresponding eigenvectors in \(P\) or you could replace some of the eigenvectors in \(P\) with other eigenvectors corresponding to the same eigenvalue as the previous and still linearly independent to the other columns. For example, the following is another possible diagonalization of \(A\text{:}\)
\begin{equation*}
D = \begin{bmatrix} 3 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 3 \end{bmatrix} \quad \text{and} \quad P = \begin{bmatrix} -3 \amp 6 \amp 2 \\ -1 \amp 3 \amp 2 \\ 1 \amp -3 \amp -1 \end{bmatrix}\text{.}
\end{equation*}
Checking, we see that
\begin{equation*}
AP = \begin{bmatrix} 7 \amp 4 \amp 16 \\ 2 \amp 5 \amp 8 \\ -2 \amp -2 \amp -5 \end{bmatrix}\begin{bmatrix} -3 \amp 6 \amp 2 \\ -1 \amp 3 \amp 2 \\ 1 \amp -3 \amp -1 \end{bmatrix} = \begin{bmatrix} -9 \amp 6 \amp 6 \\ -3 \amp 3 \amp 6 \\ 3 \amp -3 \amp -3 \end{bmatrix}
\end{equation*}
and
\begin{equation*}
PD = \begin{bmatrix} -3 \amp 6 \amp 2 \\ -1 \amp 3 \amp 2 \\ 1 \amp -3 \amp -1 \end{bmatrix}\begin{bmatrix} 3 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 3 \end{bmatrix} = \begin{bmatrix} -9 \amp 6 \amp 6 \\ -3 \amp 3 \amp 6 \\ 3 \amp -3 \amp -3 \end{bmatrix}\text{.}
\end{equation*}
Since \(AP = PD\text{,}\) this is a valid diagonalization of \(A\text{.}\)
Example 5.39.
Diagonalize the following matrix, if possible.
\begin{equation*}
A=\begin{bmatrix}
2 \amp 4 \amp 3\\
-4 \amp -6 \amp -3\\
3 \amp 3 \amp 1
\end{bmatrix}.
\end{equation*}
Solution.
First, we find the eigenvalues of \(A\text{.}\) Note that
\(\begin{eqnarray*}\det(A - \lambda I) \amp = \amp \begin{vmatrix} 2 - \lambda \amp 4 \amp 3 \\ -4 \amp -6 - \lambda \amp -3 \\ 3 \amp 3 \amp 1 - \lambda \end{vmatrix} \\ \amp \overset{R_2 + R_1 \rightarrow R_2}{=} \amp \begin{vmatrix} 2 - \lambda \amp 4 \amp 3 \\ -2 - \lambda \amp -2 - \lambda \amp 0 \\ 3 \amp 3 \amp 1 - \lambda \end{vmatrix}\end{eqnarray*}\)
Exanding across Row 2 yeilds:
\(\begin{eqnarray*}\det(A -\lambda I) \amp = \amp -(-2-\lambda)\begin{vmatrix} 4 \amp 3 \\ 3 \amp 1-\lambda \end{vmatrix} + (-2-\lambda)\begin{vmatrix} 2-\lambda \amp 3 \\ 3 \amp 1-\lambda \end{vmatrix} \\ \amp = \amp (-2-\lambda)[-(4(1-\lambda) - 9) + ((2-\lambda)(1-\lambda) - 9)] \\ \amp = \amp (-2-\lambda)[\lambda^2 + \lambda -2] \\ \amp = \amp -(\lambda + 2)(\lambda + 2)(\lambda-1) \\ \amp = \amp -(\lambda + 2)^2(\lambda - 1)\end{eqnarray*}\)
It follows that the eigenvalues of \(A\) are \(\lambda_1 = -2\) with algebraic multiplicity of 2 and \(\lambda_2 = 1\) with algebraic multiplicity of 1. Since \(A\) is a \(3 \times 3\) matrix and we found \(3\) eigenvalues (counting multiplicites), we can form \(D\text{.}\) Now let’s see if we can form \(P\text{.}\)
For \(\lambda_1 = -2\text{,}\) note that
\begin{equation*}
A - (-2)I = \begin{bmatrix} 4 \amp 4 \amp 3 \\ -4 \amp -4 \amp -3 \\ 3 \amp 3 \amp 3 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 1 \amp 1 \\ 0 \amp 0 \amp -1 \\ 0 \amp 0 \amp 0 \end{bmatrix}
\end{equation*}
which only has a single free variable. Therefore, the eigenvalue \(\lambda_1 = -2\) has algebraic multiplicity of 2 but geometric multiplicity of 1. Thus, \(A\) is NOT diagonalizable.
Example 5.40 Diagonalization and a Famous Sequence.
Note that
\begin{equation*}
\vec x_k=
\begin{bmatrix}
0 \amp 1\\
1 \amp 1
\end{bmatrix}\vec x_{k-1},\quad
\vec x_0=
\begin{bmatrix}
0\\
1
\end{bmatrix},\quad
k=1,2,3,\ldots
\end{equation*}
generates a well-known sequence of numbers. Use diagonalization to find a matrix expression that gives the \(n\)-th number in this sequence.
Solution.
First, let us generate several term so of the sequence \(\vec x_0, \vec x_1, \vec x_2, \dots\text{.}\) Let \(A = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix}\text{.}\) It follows that \(\vec x_i = A\vec x_{i-1}\) for all \(i = 1,2,3,\dots\text{.}\) Note the following:
\(\begin{eqnarray*} \vec x_1 \amp = \amp A\vec x_0 = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix}\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \\
\vec x_2 \amp = \amp A\vec x_1 = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix}\begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \\
\vec x_3 \amp = \amp A\vec x_2 = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix}\begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \end{bmatrix} \\
\vec x_4 \amp = \amp A\vec x_3 = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix}\begin{bmatrix} 2 \\ 3 \end{bmatrix} = \begin{bmatrix} 3 \\ 5 \end{bmatrix} \\
\vec x_5 \amp = \amp A\vec x_4 = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix}\begin{bmatrix} 3 \\ 5 \end{bmatrix} = \begin{bmatrix} 5 \\ 8 \end{bmatrix} \end{eqnarray*}\)
Notice that the top entry of \(\vec x_i\) is the bottom entry of \(\vec x_{i-1}\text{.}\) Writing down the entries, but removing that repetition, we obtain the sequence of integers
\begin{equation*}
0, 1, 1, 2, 3, 5, 8, \dots\text{.}
\end{equation*}
This is a very famous sequence called the Fibonacci Sequence, which is defined as the recursive sequence \(f_n = f_{n-1} + f_{n-2}\) with \(f_0 = 0\) and \(f_1 = 1\text{.}\) We see that
\begin{equation*}
\vec x_n = \begin{bmatrix} f_n \\ f_{n+1} \end{bmatrix}
\end{equation*}
and
\begin{equation*}
\vec x_{n+1} = A\vec x_n = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix} \begin{bmatrix} f_n \\ f_{n+1} \end{bmatrix} = \begin{bmatrix} f_{n+1} \\ f_n + f_{n+1} \end{bmatrix} = \begin{bmatrix} f_{n+1} \\ f_{n+2}\end{bmatrix}
\end{equation*}
since \(f_{n+2} = f_{n+1} + f_n\) by definition.
Suppose we are interested in finding \(f_{100}\text{.}\) Using either the recursive definition or the formula \(\vec x_n = A\vec x_{n-1}\) would require first finding \(f_{99}\) and \(f_{98}\text{,}\) which would in turn require finding \(f_{97}\) and \(f_{96}\) and so on and so forth. This is not fast nor practical for \(f_n\) when n is large. What we would prefer is to find an explicit formula for \(f_n\) which only depends on \(n\text{.}\) Thankfully, we can use diagonalization to accomplish this since
\begin{equation*}
\vec x_n = A\vec x_{n-1} = A(A\vec x_{n-2}) A^2\vec x_{n-2} = A^2 (A\vec x_{n-3}) = \cdots = A^n\vec x_0\text{.}
\end{equation*}
Note that if \(A\) is diagonalizable, then \(A = PDP^{-1}\) for some diagonal matrix \(D\) and invertible matrix \(P\text{.}\) Then we have that
\begin{equation*}
\vec x_n = A^n\vec x_0 = PD^nP^{-1}\vec x_0\text{.}
\end{equation*}
Let’s find \(D\) and \(P\text{.}\)
We start by finding the eigenvalues of \(A\text{.}\) Note that the characteristic polynomial of \(A\) is
\begin{equation*}
\det(A - \lambda I) = \begin{vmatrix} -\lambda \amp 1 \\ 1 \amp 1 - \lambda\end{vmatrix} = -\lambda(1-\lambda) - 1 = \lambda^2 - \lambda - 1\text{.}
\end{equation*}
Using the quadratic formula, we see that the roots of this polynomial, and therefore the eigenvalues of \(A\text{,}\) are
\begin{equation*}
\lambda_1 = \dfrac{1 + \sqrt{5}}{2} \quad \text{and} \quad \lambda_2 = \dfrac{1 - \sqrt{5}}{2}\text{.}
\end{equation*}
Next, we find eigenvectors corresponding to each eigenvalue. Note that
\begin{equation*}
A - \lambda_1 I = \begin{bmatrix} -\dfrac{1+\sqrt{5}}{2} \amp 1 \\ 1 \amp 1 - \dfrac{1+\sqrt{5}}{2} \end{bmatrix} \sim \begin{bmatrix} 1 \amp \dfrac{1-\sqrt{5}}{2} \\ 0 \amp 0 \end{bmatrix}\text{.}
\end{equation*}
Therefore, we see that \(\vec v_1 = \begin{bmatrix} 1 - \sqrt{5} \\ -2 \end{bmatrix}\) is an eigenvector of \(A\) corresponding to \(\lambda_1 = \dfrac{1+\sqrt{5}}{2}\text{.}\) We can check this. Note that
\begin{equation*}
A\vec v_1 = \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix}\begin{bmatrix} 1-\sqrt{5} \\ -2 \end{bmatrix} = \begin{bmatrix} -2 \\ -1-\sqrt{5} \end{bmatrix} = \dfrac{1+\sqrt{5}}{2}\begin{bmatrix} 1-\sqrt{5} \\ -2 \end{bmatrix}\text{.}
\end{equation*}
Now, we find an eigenvector for \(\lambda_2 = \dfrac{1-\sqrt{5}}{2}\text{.}\) Note that
\begin{equation*}
A - \lambda_2 I = \begin{bmatrix} -\dfrac{1-\sqrt{5}}{2} \amp 1 \\ 1 \amp 1 - \dfrac{1-\sqrt{5}}{2} \end{bmatrix} \sim \begin{bmatrix} 1 \amp \dfrac{1+\sqrt{5}}{2} \\ 0 \amp 0 \end{bmatrix}\text{.}
\end{equation*}
It follows that \(\vec v_2 = \begin{bmatrix} 1+\sqrt{5} \\ -2 \end{bmatrix}\) is an eigenvector of \(A\) corresponding to \(\lambda_2 = \dfrac{1-\sqrt{5}}{2}\text{.}\) Feel free to check this.
It follows that
\begin{equation*}
D = \begin{bmatrix} \dfrac{1+\sqrt{5}}{2} \amp 0 \\ 0 \amp \dfrac{1-\sqrt{5}}{2} \end{bmatrix} \qquad \text{and} \qquad P = \begin{bmatrix} 1 - \sqrt{5} \amp 1 + \sqrt{5} \\ -2 \amp -2 \end{bmatrix}
\end{equation*}
is a valid diagonalization of \(A\text{.}\) Before calculating \(P^{-1}\text{,}\) let’s simplify a bit by replacing all references of \(1 + \sqrt{5}\) with \(2\lambda_1\) and all references of \(1 - \sqrt{5}\) with \(2\lambda_2\text{.}\) Then, we have that our diagonalization is
\begin{equation*}
D = \begin{bmatrix} \lambda_1 \amp 0 \\ 0 \amp \lambda_2 \end{bmatrix} \qquad \text{and} \qquad P = \begin{bmatrix} 2\lambda_2 \amp 2\lambda_1 \\ -2 \amp -2 \end{bmatrix}\text{.}
\end{equation*}
It follows that
\begin{equation*}
P^{-1} = \dfrac{1}{4\lambda_1 - 4\lambda_2}\begin{bmatrix} -2 \amp -2\lambda_1 \\ 2 \amp 2\lambda_2\end{bmatrix}\text{.}
\end{equation*}
We can check our diagonalization before moving on. Note that
\(\begin{eqnarray*} PDP^{-1} \amp = \amp \begin{bmatrix} 2\lambda_2 \amp 2\lambda_1 \\ -2 \amp -2 \end{bmatrix}\begin{bmatrix} \lambda_1 \amp 0 \\ 0 \amp \lambda_2\end{bmatrix}\left(\dfrac{1}{4(\lambda_1 - \lambda_2)}\begin{bmatrix} -2 \amp -2\lambda_1 \\ 2 \amp 2\lambda_2\end{bmatrix}\right)\\ \amp = \amp \dfrac{1}{4(\lambda_1 - \lambda_2)}\begin{bmatrix} 2\lambda_1\lambda_2 \amp 2\lambda_1\lambda_2 \\ -2\lambda_1 \amp -2\lambda_2 \end{bmatrix}\begin{bmatrix} -2 \amp -2\lambda_1 \\ 2 \amp 2\lambda_2\end{bmatrix} \\ \amp = \amp \dfrac{1}{4(\lambda_1 - \lambda_2)}\begin{bmatrix} -4\lambda_1\lambda_2 + 4\lambda_1\lambda_2 \amp -4\lambda_1^2\lambda_2 + 4\lambda_1\lambda_2^2 \\ 4\lambda_1-4\lambda_2 \amp 4\lambda_1^2 - 4\lambda_2^2 \end{bmatrix} \\ \amp = \amp \begin{bmatrix} 0 \amp -4\lambda_1\lambda_2(\lambda_1 - \lambda_2) \\ 4(\lambda_1 - \lambda_2) \amp 4(\lambda_1 - \lambda_2)(\lambda_1 + \lambda_2) \end{bmatrix} \\ \amp = \amp \begin{bmatrix} 0 \amp -\lambda_1\lambda _2 \\ 1 \amp \lambda_1 + \lambda_2 \end{bmatrix} \\ \amp = \amp \begin{bmatrix} 0 \amp 1 \\ 1 \amp 1 \end{bmatrix} = A, \end{eqnarray*}\)
since \(-\lambda_1\lambda_2 = 1\) and \(\lambda_1 + \lambda_2 = 1\text{.}\)
Now, we find a formula for \(\vec x_n = A^n\vec x_0\text{.}\) Note that
\(\begin{eqnarray*} \begin{bmatrix} f_n \\ f_{n+1} \end{bmatrix} \amp = \amp A^n\begin{bmatrix} 0 \\ 1 \end{bmatrix} \\ \amp = \amp PD^nP^{-1}\begin{bmatrix} 0 \\ 1 \end{bmatrix} \\ \amp = \amp \begin{bmatrix} 2\lambda_2 \amp 2\lambda_1 \\ -2 \amp -2 \end{bmatrix}\left(\begin{bmatrix} \lambda_1 \amp 0 \\ 0 \amp \lambda_2\end{bmatrix}\right)^n\left(\dfrac{1}{4(\lambda_1 - \lambda_2)}\begin{bmatrix} -2 \amp -2\lambda_1 \\ 2 \amp 2\lambda_2\end{bmatrix}\right)\begin{bmatrix} 0 \\ 1 \end{bmatrix} \\ \amp = \amp \dfrac{1}{4(\lambda_1 - \lambda_2)}\begin{bmatrix} 2\lambda_2 \amp 2\lambda_1 \\ -2 \amp -2 \end{bmatrix}\begin{bmatrix} \lambda_1^n \amp 0 \\ 0 \amp \lambda_2^n\end{bmatrix}\begin{bmatrix}-2\lambda_1 \\ 2\lambda_2 \end{bmatrix} \\ \amp = \amp \dfrac{1}{4(\lambda_1 - \lambda_2)}\begin{bmatrix} 2\lambda_1^n\lambda_2 \amp 2\lambda_1\lambda_2^n \\ -2\lambda_1^n \amp -2\lambda_2^n \end{bmatrix} \begin{bmatrix} -2\lambda_1 \\ 2\lambda_2 \end{bmatrix} \\ \amp = \amp \dfrac{1}{4(\lambda_1 - \lambda_2)}\begin{bmatrix} -4\lambda_1^{n+1}\lambda_2 + 4\lambda_1\lambda_2^{n+1} \\ 4\lambda_1^{n+1} - 4\lambda_2^{n+1} \end{bmatrix}.\end{eqnarray*}\)
By comparing the top entries, we see that
\begin{equation*}
f_n = \dfrac{-4\lambda_1^{n+1}\lambda_2 + 4\lambda_1\lambda_2^{n+1}}{4(\lambda_1 - \lambda_2)} = \dfrac{-4\lambda_1\lambda_2(\lambda_1^n - \lambda_2^n)}{4(\lambda_1 - \lambda_2)}\text{.}
\end{equation*}
Since \(-4\lambda_1\lambda_2 = 4\) and \(4(\lambda_1 - \lambda_2) = 4\sqrt{5}\text{,}\) we find that
\begin{equation*}
f_n = \dfrac{\lambda_1^n - \lambda_2^n}{\sqrt{5}} = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1 + \sqrt{5}}{2}\right)^n - \left(\dfrac{1 - \sqrt{5}}{2}\right)^n\right)
\end{equation*}
is an explicit formula for \(f_n\text{.}\) Feel free to use Desmos and check this formula for various values of \(n\text{.}\)
