Chapter 12Eigenvalues, Eigenvectors, and Diagonalization of Matrices

At the beginning of Chapter 8, we saw that the powers $A^n$ of three kinds of matrices—the diagonal matrix $A=\mathrm{diag}(\alpha,\beta)$, the upper triangular matrix $A=\begin{bmatrix}1&\alpha\\0&1\end{bmatrix}$, and the rotation matrix $A=\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}$—can be found in very simple forms by mathematical induction (namely $\mathrm{diag}(\alpha^n,\beta^n)$, $\begin{bmatrix}1&n\alpha\\0&1\end{bmatrix}$, and the rotation matrix through the angle $n\theta$, respectively). At that time we were content to say “that is because these three are special,” but in fact many general square matrices $A$ can also be “remade” into a diagonal matrix $P^{-1}AP$ by means of a suitable matrix $P$, and then $A^n$ can be found easily by the same mechanism. This remaking operation is called diagonalization, and the key to finding the matrix $P$ that makes it possible is the pair of protagonists of this chapter, the eigenvalue and the eigenvector.

An eigenvector is a special vector $\bm x$ whose direction does not change when the matrix $A$ acts on it ($A\bm x=\lambda\bm x$; it is merely stretched or shrunk by a factor of $\lambda$). The equation $\det(A-\lambda E)=0$ (the characteristic equation) for finding the eigenvalue $\lambda$ is in fact nothing more than an application of the “condition for a homogeneous system of linear equations to have a solution other than the trivial one” that we learned in Chapter 9—here again, all the tools we have obtained so far (determinants, rank, linear independence) are brought into play. In this chapter, building on the definition of eigenvalues and eigenvectors and the first computational example (Section 12.1) in Yasuhide Mochizuki's “Mathematics Notes: Linear Algebra,” we write out, as original content of this book, everything from Section 12.2 onward: the test for diagonalizability, the procedure for diagonalization, and the application to the computation of powers. At the end we resolve the mystery left at the beginning: “why could only those three matrices be raised to powers so easily?”

What you will learn in this chapter

The definition of eigenvalues and eigenvectors: the $\lambda$ and $\bm x$ satisfying $A\bm x=\lambda\bm x$ ($\bm x\neq\bm 0$), and the rewriting $A\bm x=\lambda\bm x \iff (A-\lambda E)\bm x=\bm 0$
The fact that the characteristic equation $\det(A-\lambda E)=0$ is derived as an application of the condition for a homogeneous system of linear equations to have a nontrivial solution (Theorems 9.1 and 9.5 of Chapter 9)
The eigenspace $\mathrm{Ker}(A-\lambda E)$ (reusing the idea of $\mathrm{Ker}\,f$ from Chapter 11), and the difference between algebraic multiplicity and geometric multiplicity
A proof that eigenvectors corresponding to distinct eigenvalues are linearly independent (an application of the discussion of linear independence in Chapter 10)
The definition of diagonalizability (the existence of an invertible matrix $P$ for which $P^{-1}AP$ is a diagonal matrix) and its necessary and sufficient condition (the existence of $n$ linearly independent eigenvectors, which is equivalent to the algebraic and geometric multiplicities agreeing for every eigenvalue)
The concrete procedure for diagonalization (arranging eigenvectors as columns to form $P$), and an example that cannot be diagonalized (the case of a repeated eigenvalue whose eigenspace is “thin”)
An application of diagonalization: a proof that $A^n=PD^nP^{-1}$ when $A=PDP^{-1}$, and a final summary of how the three power patterns of Chapter 8 (diagonal, upper triangular, rotation) are positioned from the viewpoint of diagonalization

Prerequisites: Chapter 8 (Matrices and Determinants: determinants, invertibility, the three power patterns), Chapter 9 (Systems of Linear Equations: rank, degrees of freedom, conditions for invertibility), Chapter 10 (Vector Spaces (Linear Spaces): linear independence and linear dependence, bases and dimension), Chapter 11 (Linear Maps: the kernel $\mathrm{Ker}\,f$). The quadratic formula and the basics of complex numbers from high school mathematics (used in Section 12.4, which treats the complex eigenvalues of a rotation matrix; complex numbers are briefly explained to the extent needed in this chapter).
Source notes: Yasuhide Mochizuki, Mathematics Notes: Linear Algebra, pp. 29–30.

12.1 Definition of Eigenvalues and Eigenvectors

First, let us see with concrete numbers what “a vector whose direction does not change when it is multiplied by a matrix” looks like. Consider the matrix $A=\begin{bmatrix}4&-2\\1&1\end{bmatrix}$. Multiplying an arbitrary vector, for example $\bm x_0=(1,0)$, by $A$ gives

$$ A\bm x_0=\begin{bmatrix}4&-2\\1&1\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}4\\1\end{bmatrix} $$

so the direction (as seen from the origin) differs greatly from that of the original $(1,0)$. Now, however, if we multiply a different vector, $\bm x_1=(1,1)$, by the same $A$, we obtain

$$ A\bm x_1=\begin{bmatrix}4&-2\\1&1\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix}=\begin{bmatrix}4-2\\1+1\end{bmatrix}=\begin{bmatrix}2\\2\end{bmatrix}=2\begin{bmatrix}1\\1\end{bmatrix}=2\bm x_1 $$

so $A\bm x_1$ points in exactly the same direction as $\bm x_1$ (it lies on the line through the origin and $\bm x_1$), and only its length has been doubled. Trying $\bm x_2=(2,1)$ as well, we get

$$ A\bm x_2=\begin{bmatrix}4&-2\\1&1\end{bmatrix}\begin{bmatrix}2\\1\end{bmatrix}=\begin{bmatrix}8-2\\2+1\end{bmatrix}=\begin{bmatrix}6\\3\end{bmatrix}=3\begin{bmatrix}2\\1\end{bmatrix}=3\bm x_2 $$

so this time the vector is merely stretched by a factor of three, and again the direction does not change. Even for the same matrix $A$, there are vectors such as $\bm x_0$ whose direction changes, and there are special vectors such as $\bm x_1,\bm x_2$ that merely stretch or shrink while keeping their direction—these special directions are precisely the theme of this chapter. Figure 12.1 shows these three vectors together with their images $A\bm x_0,A\bm x_1,A\bm x_2$.

Figure 12.1: Images of three vectors under $A=\begin{bmatrix}4&-2\\1&1\end{bmatrix}$. The vectors $\bm x_1=(1,1)$ and $\bm x_2=(2,1)$ have their images $A\bm x_1=2\bm x_1$ and $A\bm x_2=3\bm x_2$ on their own lines through the origin (the dashed lines)—only the length changes, while the direction is preserved. In contrast, the image $A\bm x_3=(4,1)$ of the general vector $\bm x_3=(1,0)$ lies on neither dashed line; its direction itself changes.

Let us formally define the property possessed by vectors such as $\bm x_1,\bm x_2$, namely “the direction does not change when multiplied by $A$; the vector is only multiplied by a scalar.”

Definition 12.1: Eigenvectors and eigenvalues

For a square matrix $A$ of order $n$, if there exist an $n$-dimensional vector $\bm x$ and a number $\lambda$ (real or complex) satisfying

$$ A\bm x=\lambda\bm x \qquad (\bm x\neq\bm 0) $$

then $\bm x$ is called an eigenvector of $A$ and $\lambda$ an eigenvalue of $A$. The word “eigen” (it comes from German, where it means “own” or “characteristic”) expresses the fact that the direction of $\bm x$ is intrinsically tied to the transformation $A$—even after multiplying by $A$, the direction of $\bm x$ itself, at least, does not change.

In Mochizuki's original notes, $\lambda$ is defined as a real number, but in this book we have defined it from the outset so as to allow complex numbers. This extension is necessary in order to treat, in Section 12.4, the fact that the eigenvalues of a rotation matrix are complex (when $\theta\neq0,\pi$); as long as we are working only within the real numbers, there is no harm in thinking of $\lambda$ as real.

Caution: Do not drop the assumption $\bm x\neq\bm 0$

If we allowed $\bm x=\bm 0$, then $A\bm 0=\bm0=\lambda\bm0$ would hold automatically for every $A,\lambda$, and the word “eigenvalue” would lose all meaning. For this reason, Definition 12.1 states the condition $\bm x\neq\bm0$ (a nontrivial $\bm x$) explicitly from the start. On the other hand, $\lambda=0$ itself is not prohibited (an eigenvector with $A\bm x=\bm0$ is also a perfectly good eigenvector for the eigenvalue $0$, as long as $\bm x\neq\bm0$; we will relate this to $\mathrm{Ker}\,f$ of Chapter 11 in Section 12.2).

From the equation in Definition 12.1, let us derive a method for actually computing $\lambda$ and $\bm x$. Moving the right-hand side of $A\bm x=\lambda\bm x$ to the left-hand side gives

$$ A\bm x-\lambda\bm x=\bm 0 $$

but on the left-hand side, $A\bm x$ and $\lambda\bm x$ are a product with a matrix and a product with a scalar, respectively, so we cannot simply “factor out the common factor.” We therefore rewrite $\lambda\bm x=\lambda E\bm x$ ($E$ is the identity matrix of order $n$; since multiplying any vector by $E$ leaves it unchanged, $\lambda\bm x=\lambda(E\bm x)=(\lambda E)\bm x$), and obtain

$$ A\bm x-(\lambda E)\bm x=(A-\lambda E)\bm x=\bm 0 $$

so that $\bm x$ can now be factored out as a common factor on the right. In this way, the equation for eigenvalues and eigenvectors can be rewritten in the form of a homogeneous system of linear equations.

\begin{equation} (A-\lambda E)\bm x=\bm 0 \label{eq:12-eigeneq} \end{equation}

Here $\bm x$ is not identically $\bm 0$ (by the assumption in Definition 12.1), so Eq. \eqref{eq:12-eigeneq} is a homogeneous system of linear equations that has a solution other than the trivial solution $\bm x=\bm0$ (a nontrivial solution). As we learned in Theorem 9.1 (including its restatement for the case of square matrices) of Section 9.3 (Chapter 9), for the homogeneous system of linear equations $B\bm x=\bm 0$ whose coefficient matrix is a square matrix $B$ of order $n$, the following are all equivalent: the system has a solution other than the trivial solution; $B$ has positive degrees of freedom; and $B$ is not invertible ($\rank B\lt n$, or equivalently $|B|=0$). Applying this fact to $B=A-\lambda E$, we obtain the following important conclusion.

Theorem 12.1: Characteristic equation

For a square matrix $A$ of order $n$, a number $\lambda$ is an eigenvalue of $A$ (that is, there exists $\bm x\neq\bm0$ satisfying $A\bm x=\lambda\bm x$) if and only if

$$ \underline{\det(A-\lambda E)=0} $$

holds. This equation is called the characteristic equation of $A$, and its left-hand side $\varphi_A(\lambda):=\det(A-\lambda E)$ (a polynomial of degree $n$ in $\lambda$) is called the characteristic polynomial of $A$.

Proof

($\Rightarrow$) If $\lambda$ is an eigenvalue, there exists $\bm x\neq\bm0$ satisfying Eq. \eqref{eq:12-eigeneq}. That is, $(A-\lambda E)\bm x=\bm0$ has a solution other than the trivial solution. By Theorem 9.1 of Chapter 9 (more precisely, the restatement for square matrices given within it), this is equivalent to $A-\lambda E$ being not invertible, that is, to $\det(A-\lambda E)=0$. ($\Leftarrow$) Conversely, if $\det(A-\lambda E)=0$, then by the same Theorem 9.1, $(A-\lambda E)\bm x=\bm0$ has positive degrees of freedom, and so it has a solution $\bm x_0\neq\bm0$ other than the trivial solution $\bm x=\bm0$. For this $\bm x_0$ we have $A\bm x_0=\lambda\bm x_0$, so $\lambda$ is an eigenvalue and $\bm x_0$ is an eigenvector belonging to it.

Theorem 12.1 itself tells us the procedure for computing eigenvalues and eigenvectors—first solve the characteristic equation $\det(A-\lambda E)=0$ (an equation of degree $n$ in $\lambda$) to find the eigenvalues $\lambda$; then substitute each $\lambda$ found into Eq. \eqref{eq:12-eigeneq} and solve the homogeneous system of linear equations $(A-\lambda E)\bm x=\bm0$ anew to find the eigenvectors $\bm x$. This is a two-step procedure. Let us carry this procedure through to the end with the following example from the original notes.

Illustration 12.1: Eigenvalues and eigenvectors of a $2\times2$ matrix

Find the eigenvalues and eigenvectors of $A=\begin{bmatrix}4&-2\\1&1\end{bmatrix}$, writing $\bm x=\begin{bmatrix}x_1\\x_2\end{bmatrix}$.

Solution. First we form the characteristic equation.

$$ A-\lambda E=\begin{bmatrix}4-\lambda&-2\\1&1-\lambda\end{bmatrix} $$

Computing this determinant (according to the definition $ad-bc$ of a $2\times2$ determinant), we get

$$ \det(A-\lambda E)=(4-\lambda)(1-\lambda)-(-2)\cdot1=(\lambda-4)(\lambda-1)+2=0 $$

(The rewriting $(4-\lambda)(1-\lambda)=(\lambda-4)(\lambda-1)$ holds because multiplying the contents of both pairs of parentheses by $-1$ changes the sign twice and so restores the original.) Expanding the right-hand side gives

$$ \lambda^2-5\lambda+4+2=\lambda^2-5\lambda+6=(\lambda-2)(\lambda-3)=0 $$

so the eigenvalues are $\lambda=2,3$ (both have multiplicity 1).

(i) The case $\lambda=2$. Writing out $A\bm x=2\bm x$, that is, $(A-2E)\bm x=\bm0$, in components, we have

$$ \begin{cases}4x_1-2x_2=2x_1\\x_1+x_2=2x_2\end{cases} $$

We solve this system. The first equation $4x_1-2x_2=2x_1$ gives $2x_1=2x_2$, that is, $x_1=x_2$. The second equation $x_1+x_2=2x_2$ again gives $x_1=x_2$, so the two equations reduce to the same condition (as is to be expected, since the $\rank$ of $A-2E$ is 1). Setting $x_1=k$ ($k$ an arbitrary real number), we also have $x_2=k$, and so we obtain

$$ \bm x=\begin{bmatrix}k\\k\end{bmatrix}=k\begin{bmatrix}1\\1\end{bmatrix}\qquad(k\neq0) $$

Note that taking $k=1$ gives $\begin{bmatrix}1\\1\end{bmatrix}$, which coincides with $\bm x_1$ in Figure 12.1.

(ii) The case $\lambda=3$. Writing out $A\bm x=3\bm x$, that is, $(A-3E)\bm x=\bm0$, in components, we have

$$ \begin{cases}4x_1-2x_2=3x_1\\x_1+x_2=3x_2\end{cases} $$

The first equation $4x_1-2x_2=3x_1$ gives $x_1=2x_2$. The second equation $x_1+x_2=3x_2$ also gives $x_1=2x_2$, so again the two equations reduce to the same condition. Setting $x_2=\ell$ ($\ell$ an arbitrary real number), we have $x_1=2\ell$, and so we obtain

$$ \bm x=\begin{bmatrix}2\ell\\\ell\end{bmatrix}=\ell\begin{bmatrix}2\\1\end{bmatrix}\qquad(\ell\neq0) $$

Taking $\ell=1$ gives $\begin{bmatrix}2\\1\end{bmatrix}$, which coincides with $\bm x_2$ in Figure 12.1. (SymPy check: the eigenvalues of $A$ are $2,3$, and the eigenvectors coincide with constant multiples of $(1,1)^{\mathsf T},(2,1)^{\mathsf T}$, respectively.)

As Illustration 12.1 shows, an eigenvector is determined only as a single direction (a line), and its length is not determined—a $k$-fold or $\ell$-fold multiple, whichever we take, is an eigenvector. It is also important that the two equations of $(A-\lambda E)\bm x=\bm0$ always reduce to the same condition (as long as $\lambda$ is an eigenvalue). This is a direct consequence of the fact that $A-\lambda E$ is not invertible ($\rank\lt2$); if the two equations were to give independent conditions, we would have $\rank(A-\lambda E)=2$, and $\bm x=\bm0$ would be the only solution, so that no eigenvector would exist at all. In the next example, we carry out the same procedure for a $3\times3$ matrix and look at a case in which the computation of a determinant of order $3$ (cofactor expansion, Section 8.4 of Chapter 8) is needed.

Example 12.1: Eigenvalues and eigenvectors of a $3\times3$ matrix

Find all the eigenvalues and eigenvectors of $A=\begin{bmatrix}-2&1&2\\-4&3&2\\-5&1&5\end{bmatrix}$.

Solution. We form the characteristic equation.

$$ A-\lambda E=\begin{bmatrix}-\lambda-2&1&2\\-4&3-\lambda&2\\-5&1&5-\lambda\end{bmatrix} $$

We compute the determinant of this matrix using Theorem 8.2 of Chapter 8 (cofactor expansion, expansion along the first row). Finding the minors of the $3\times3$ matrix (those obtained by deleting the first row and each column in turn), we have

$$ M_{11}=\begin{vmatrix}3-\lambda&2\\1&5-\lambda\end{vmatrix}=(3-\lambda)(5-\lambda)-2=\lambda^2-8\lambda+13 $$ $$ M_{12}=\begin{vmatrix}-4&2\\-5&5-\lambda\end{vmatrix}=-4(5-\lambda)-2\cdot(-5)=4\lambda-10 $$ $$ M_{13}=\begin{vmatrix}-4&3-\lambda\\-5&1\end{vmatrix}=-4\cdot1-(3-\lambda)(-5)=11-5\lambda $$

Since each cofactor carries the sign $(-1)^{i+j}$, the expansion along the first row takes the following form (the sign for columns $1$ and $3$ is $+$, and the sign for column $2$ is $-$).

$$ \det(A-\lambda E)=(-\lambda-2)M_{11}-1\cdot M_{12}+2\cdot M_{13} $$

Substituting, we get

$$ \det(A-\lambda E)=(-\lambda-2)(\lambda^2-8\lambda+13)-(4\lambda-10)+2(11-5\lambda) $$

First, expanding $(-\lambda-2)(\lambda^2-8\lambda+13)$ gives

$$ -\lambda^3+8\lambda^2-13\lambda-2\lambda^2+16\lambda-26=-\lambda^3+6\lambda^2+3\lambda-26 $$

The remaining two terms give

$$ -(4\lambda-10)+2(11-5\lambda)=-4\lambda+10+22-10\lambda=-14\lambda+32 $$

Adding these together, we obtain

$$ \det(A-\lambda E)=-\lambda^3+6\lambda^2+3\lambda-26-14\lambda+32=-\lambda^3+6\lambda^2-11\lambda+6=0 $$

Multiplying both sides by $-1$ gives $\lambda^3-6\lambda^2+11\lambda-6=0$, and substituting $\lambda=1$ gives $1-6+11-6=0$, so we have found one of the roots. Dividing the left-hand side by $(\lambda-1)$ (using the factor theorem and synthetic division from high school mathematics), we obtain $\lambda^2-5\lambda+6=(\lambda-2)(\lambda-3)$, and therefore

$$ \lambda^3-6\lambda^2+11\lambda-6=(\lambda-1)(\lambda-2)(\lambda-3)=0 \qquad\therefore\ \lambda=1,2,3 $$

All three eigenvalues are distinct real numbers. Next, we find the eigenvector for each of them in turn.

The case $\lambda=1$. Writing $(A-E)\bm x=\bm0$ in components, we obtain

$$ \begin{cases}-3x_1+x_2+2x_3=0\\-4x_1+2x_2+2x_3=0\\-5x_1+x_2+4x_3=0\end{cases} $$

Subtracting the second equation from the first equation $\times2$, we get

$$ -6x_1+2x_2+4x_3-(-4x_1+2x_2+2x_3)=-2x_1+2x_3=0 $$

That is, $x_1=x_3$. Substituting this into the first equation gives

$$ -3x_1+x_2+2x_1=-x_1+x_2=0 $$

That is, $x_2=x_1$. Hence, letting $x_1=k$, we obtain $\bm x=k(1,1,1)^{\mathsf T}$. (Indeed, the third equation also holds, since $-5k+k+4k=0$, so we can confirm that the conditions do not contradict one another.)

The case $\lambda=2$. $(A-2E)\bm x=\bm0$:

$$ \begin{cases}-4x_1+x_2+2x_3=0\\-4x_1+x_2+2x_3=0\\-5x_1+x_2+3x_3=0\end{cases} $$

(The first and second equations are identical.) From the first equation, $x_2=4x_1-2x_3$. Substituting this into the third equation gives

$$ -5x_1+(4x_1-2x_3)+3x_3=-x_1+x_3=0 $$

That is, $x_3=x_1$. Therefore $x_2=4x_1-2x_1=2x_1$. Letting $x_1=k$, we obtain $\bm x=k(1,2,1)^{\mathsf T}$.

The case $\lambda=3$. $(A-3E)\bm x=\bm0$:

$$ \begin{cases}-5x_1+x_2+2x_3=0\\-4x_1+2x_3=0\\-5x_1+x_2+2x_3=0\end{cases} $$

(The first and third equations are identical.) From the second equation, $x_3=2x_1$. Substituting this into the first equation gives

$$ -5x_1+x_2+4x_1=-x_1+x_2=0 $$

That is, $x_2=x_1$. Letting $x_1=k$, we obtain $\bm x=k(1,1,2)^{\mathsf T}$.

To summarize, the eigenvalues are $\lambda=1,2,3$ (each with multiplicity one), and the corresponding eigenvectors are, respectively, $(1,1,1)^{\mathsf T}$, $(1,2,1)^{\mathsf T}$, and $(1,1,2)^{\mathsf T}$ (or constant multiples of them). (SymPy check: we have directly confirmed each of $A(1,1,1)^{\mathsf T}=(1,1,1)^{\mathsf T}$, $A(1,2,1)^{\mathsf T}=(2,4,2)^{\mathsf T}=2(1,2,1)^{\mathsf T}$, and $A(1,1,2)^{\mathsf T}=(3,3,6)^{\mathsf T}=3(1,1,2)^{\mathsf T}$.)

12.2 Properties of Eigenvalues and Eigenspaces

In Section 12.1, for a given matrix $A$ we solved the characteristic equation $\det(A-\lambda E)=0$ to find the eigenvalues $\lambda$, and then, for each $\lambda$, we solved the homogeneous system of linear equations $(A-\lambda E)\bm x=\bm0$ to find the eigenvectors. Two questions arise naturally here. One is, “For a single eigenvalue $\lambda$, how many linearly independent eigenvectors (up to constant multiples) can we choose?” The other is, “For a square matrix of order $n$ as a whole, how many eigenvalues are there (counting multiplicity)?” In this section we prepare the vocabulary that answers these two questions—eigenspace, algebraic multiplicity, and geometric multiplicity. These will be the deciding factors for judging “whether a matrix can be diagonalized” in the next section, Section 12.3.

First, let us recast the set of eigenvectors in the language of vector spaces. If we fix a single eigenvalue $\lambda$, then the set of all $\bm x$ satisfying $A\bm x=\lambda\bm x$ (including the case $\bm x=\bm0$) can be handled by reusing, just as it is, the idea of the kernel ($\mathrm{Ker}\,f$) that we learned in Chapter 11.

Definition 12.2: Eigenspace

For a square matrix $A$ of order $n$ and an eigenvalue $\lambda$ of that matrix, the set

$$ W(\lambda):=\mathrm{Ker}(A-\lambda E)=\{\bm x\in\R^n\mid (A-\lambda E)\bm x=\bm0\} $$

is called the eigenspace of $A$ associated with the eigenvalue $\lambda$. Removing $\bm0$ from $W(\lambda)$ leaves exactly the set of all eigenvectors corresponding to $\lambda$.

Why is $W(\lambda)$ a subspace?

Since $A-\lambda E$ is also a square matrix of order $n$, the map $\bm x\mapsto(A-\lambda E)\bm x$ is a linear map (with representation matrix $A-\lambda E$). Therefore, by Theorem 11.3 of Chapter 11 ($\mathrm{Ker}\,f$ is a subspace), $W(\lambda)=\mathrm{Ker}(A-\lambda E)$ is a subspace of $\R^n$. In particular, if $\bm x_1,\bm x_2\in W(\lambda)$ (or $\bm0$), then their linear combination $c_1\bm x_1+c_2\bm x_2$ also belongs to $W(\lambda)$—that is, even if we add several eigenvectors together or multiply them by constants, the result is still an eigenvector for the same eigenvalue $\lambda$ (or $\bm0$).

For example, in Illustration 12.1 (Section 12.1), the eigenspace for $\lambda=2$ was $W(2)=\{k(1,1)^{\mathsf T}\mid k\in\R\}$ (one-dimensional), and the eigenspace for $\lambda=3$ was $W(3)=\{\ell(2,1)^{\mathsf T}\mid \ell\in\R\}$ (one-dimensional). The dimension of $W(\lambda)$ is a natural number determined for each eigenvalue $\lambda$, and it has a special name. Before defining that name, let us first check what the degree of the characteristic equation $\det(A-\lambda E)=0$ actually is as an equation in $\lambda$.

Degree of the characteristic polynomial

For a square matrix $A=(a_{ij})$ of order $n$, applying the definition of the determinant from Chapter 8 (Definition 8.9, the sum over permutations weighted by their signs) to $A-\lambda E$, we obtain

$$ \varphi_A(\lambda)=\det(A-\lambda E)=\sum_{\sigma}\sgn\sigma\prod_{i=1}^n\big(a_{i\sigma(i)}-\lambda\delta_{i\sigma(i)}\big) $$

(Here $\delta_{i\sigma(i)}$ is a symbol that takes the value $1$ when $i=\sigma(i)$ and $0$ otherwise—it is called the Kronecker delta—and it expresses the fact that $-\lambda$ is attached only to the diagonal entries.) The term corresponding to the identity permutation $\sigma=\mathrm{id}$ (the permutation with $\sigma(i)=i$ for all $i$) is $\prod_{i=1}^n(a_{ii}-\lambda)$, which is a polynomial of degree $n$ in $\lambda$ whose highest-degree term is $(-\lambda)^n$. On the other hand, a permutation $\sigma$ other than the identity satisfies $\sigma(i)\neq i$ for at least two indices $i$ (a permutation cannot move just one place and fix all the others—if one place is moved, the element at the place it is moved to must also move somewhere, so at least two places move). Therefore the product $\prod_i(a_{i\sigma(i)}-\lambda\delta_{i\sigma(i)})$ in the term for such a $\sigma$ contains at least two factors with $\delta_{i\sigma(i)}=0$ (the $-\lambda$ part disappears), and so it is of degree at most $n-2$ in $\lambda$. Hence the coefficients of $\lambda^n,\lambda^{n-1}$ in $\varphi_A(\lambda)$ are determined by the term of the identity permutation alone, and $\varphi_A(\lambda)$ is a polynomial in $\lambda$ of degree exactly $n$ (with leading coefficient $(-1)^n$).

Math Note: Over the complex numbers there are always $n$ roots

As you learned in high school mathematics, a quadratic equation may have no roots among the real numbers (when the discriminant is negative). But if we allow complex numbers, an equation of degree $n$ has exactly $n$ roots, counted with multiplicity—this is called the fundamental theorem of algebra (a proof requires tools from complex function theory, so we accept it here as a fact; the proof is treated in the Mochizuki Research Group's advanced resource “Complex Analysis”). Therefore the characteristic equation $\varphi_A(\lambda)=0$ of a square matrix $A$ of order $n$ has exactly $n$ roots (eigenvalues) over the complex numbers, counted with multiplicity. Note that even for a real matrix, the eigenvalues may be complex numbers (the rotation matrix in Section 12.4 is an example).

Definition 12.3: Algebraic multiplicity and geometric multiplicity

For an eigenvalue $\lambda_0$ of a square matrix $A$ of order $n$:

The number of times $\lambda_0$ occurs as a root of the characteristic polynomial $\varphi_A(\lambda)$ (that is, the number $k$ for which we can write $\varphi_A(\lambda)=(\lambda-\lambda_0)^k\times g(\lambda)$ using a function $g$ with $g(\lambda_0)\neq0$) is called the algebraic multiplicity of $\lambda_0$.
$\dim W(\lambda_0)$ (the dimension of the eigenspace) is called the geometric multiplicity of $\lambda_0$.

These two quantities share the same name, “multiplicity,” but in general their values can differ. The next theorem tells us how they compare in size.

Theorem 12.2: The geometric multiplicity does not exceed the algebraic multiplicity

If $g$ is the geometric multiplicity and $a$ is the algebraic multiplicity of an eigenvalue $\lambda_0$ of $A$, then

$$ 1\le g\le a $$

holds.

Outline of the proof

$g\ge1$ is clear from the definition ($\lambda_0$ being an eigenvalue means, by Definition 12.1, precisely that $W(\lambda_0)$ has an element other than $\bm0$, that is, $\dim W(\lambda_0)\ge1$).

In the proof of $g\le a$, we rely on an external fact only for the very last step; everything else is checked concretely. That last step is the fact that “similar matrices (matrices that are carried into one another in the form $P^{-1}AP$) have exactly the same characteristic polynomial.” This uses the product formula for determinants, $\det(XY)=\det X\cdot\det Y$ (another general property of determinants, which this book does not treat), and so it is a somewhat advanced argument—interested readers may consult, for example, Masahiko Saito, “Senkei Daisū Nyūmon [Introduction to Linear Algebra].” The idea is as follows. Take a basis $\bm v_1,\ldots,\bm v_g$ of $W(\lambda_0)$, extend it to a basis $\bm v_1,\ldots,\bm v_g,\bm v_{g+1},\ldots,\bm v_n$ of $\R^n$ (of $\C^n$ if the eigenvalue is complex), and form the invertible matrix $P=[\bm v_1\ \cdots\ \bm v_n]$ whose columns are these vectors.

Since $A\bm v_i=\lambda_0\bm v_i$ ($i\le g$), the $i$th column of $AP$ (for $i\le g$) is $A\bm v_i=\lambda_0\bm v_i$, that is, “$\lambda_0$ times the $i$th column of $P$.” Therefore the $i$th column of $P^{-1}AP$ (for $i\le g$) coincides exactly with $\lambda_0\bm e_i$ (the vector whose $i$th component alone is $\lambda_0$ and whose remaining components are all $0$). What matters here is not only that “the upper-left $g\times g$ block is $\lambda_0 E_g$” but also that in those columns, the entries from row $g+1$ through row $n$ are all $0$ (this block-triangular form is precisely what produces the factor $(\lambda-\lambda_0)^g$ in the later computation). In summary, $P^{-1}AP$ is a block upper triangular matrix of the following form.

$$ P^{-1}AP=\begin{bmatrix}\lambda_0 E_g & B \\ O & C\end{bmatrix} $$

($B$ is some $g\times(n-g)$ matrix, $C$ is some $(n-g)\times(n-g)$ matrix, and the $O$ at the lower left is the $(n-g)\times g$ zero matrix.)

Let us check, with the concrete example $n=3$, $g=2$, $\lambda_0=2$, why this form produces the factor $(\lambda-\lambda_0)^g$. For example, consider the matrix

$$ P^{-1}AP=\begin{bmatrix}2&0&3\\0&2&-1\\0&0&5\end{bmatrix} $$

(whose upper-left $2\times2$ block is $2E_2$ and whose lower-left $1\times2$ block is $0$). Computing the characteristic polynomial by cofactor expansion along the first column (which is easy because the first column contains one $0$), we obtain

$$ \det(P^{-1}AP-\lambda E)=(2-\lambda)\begin{vmatrix}2-\lambda&-1\\0&5-\lambda\end{vmatrix}=(2-\lambda)\cdot(2-\lambda)(5-\lambda)=(2-\lambda)^2(5-\lambda) $$

and indeed exactly $g=2$ factors corresponding to $\lambda_0=2$ appear, and the remaining factor $(5-\lambda)$ is the characteristic polynomial of the lower-right block, which in this example is $1\times1$ and so is simply its single entry (SymPy check: expanding gives $-\lambda^3+9\lambda^2-24\lambda+20$, which was confirmed to agree with the expansion of $(2-\lambda)^2(5-\lambda)$). Even for general $n,g$ the same mechanism repeats—since the lower-left block is all $0$, repeating the same cofactor expansion $g$ times, along the first column, the second column, …, the $g$th column, we can pull out one diagonal entry $(\lambda_0-\lambda)$ each time, and in the end we obtain

$$ \det(P^{-1}AP-\lambda E)=(\lambda_0-\lambda)^g\det(C-\lambda E_{n-g}) $$

Therefore the characteristic polynomial of $P^{-1}AP$ is divisible by $(\lambda-\lambda_0)^g$ (up to a constant multiple). Since the characteristic polynomial does not depend on the choice of basis (similarity invariance, the fact stated in the last step), the characteristic polynomial of the original $A$ is also divisible by $(\lambda-\lambda_0)^g$; that is, the algebraic multiplicity satisfies $a\ge g$.

Example 12.2: Finding the dimension of an eigenspace (the geometric multiplicity)

Find the eigenvalues of $A=\begin{bmatrix}2&1&0\\0&2&0\\0&0&-1\end{bmatrix}$, and the algebraic multiplicity and the geometric multiplicity of each.

Solution. Since $A-\lambda E=\begin{bmatrix}2-\lambda&1&0\\0&2-\lambda&0\\0&0&-1-\lambda\end{bmatrix}$ is an upper triangular matrix, the fact verified in Chapter 8 (the determinant of an upper triangular matrix is the product of its diagonal entries) shows that the characteristic equation is

$$ \det(A-\lambda E)=(2-\lambda)^2(-1-\lambda)=0 $$

Hence the eigenvalues are $\lambda=2$ (algebraic multiplicity $a=2$) and $\lambda=-1$ (algebraic multiplicity $a=1$).

The eigenspace for $\lambda=2$. Writing out the entries of $(A-2E)\bm x=\bm0$ gives $\begin{bmatrix}0&1&0\\0&0&0\\0&0&-3\end{bmatrix}\bm x=\bm0$, that is, $x_2=0$ and $x_3=0$ ($x_1$ is free). Hence $W(2)=\{(t,0,0)^{\mathsf T}\mid t\in\R\}$ is one-dimensional, and the geometric multiplicity is $g=1$. Here $g=1\lt a=2$, so we have found an example in which the inequality in Theorem 12.2 is strict (a proper inequality).

The eigenspace for $\lambda=-1$. Writing out the entries of $(A+E)\bm x=\bm0$ gives $\begin{bmatrix}3&1&0\\0&3&0\\0&0&0\end{bmatrix}\bm x=\bm0$. The second equation $3x_2=0$ gives $x_2=0$, and substituting this into the first equation gives $3x_1=0$, so $x_1=0$ ($x_3$ is free). Hence $W(-1)=\{(0,0,u)^{\mathsf T}\mid u\in\R\}$ is one-dimensional, and $g=a=1$ (the case where equality holds). (SymPy check: we confirmed that $W(2)$ is the one-dimensional space spanned by $(1,0,0)^{\mathsf T}$, and that $W(-1)$ is the one-dimensional space spanned by $(0,0,1)^{\mathsf T}$.)

If there is an eigenvalue whose geometric multiplicity is strictly smaller than its algebraic multiplicity, like $\lambda=2$ in Example 12.2, then, as we will see later in Section 12.3, the matrix cannot be diagonalized. In the next example we change the subject and confirm an advanced fact, intended for precocious readers, about the eigenvalues of symmetric matrices ($A^{\mathsf T}=A$; matrices that do not change when transposed), which often appear in physics and materials science.

Example 12.3: The eigenvalues of a symmetric matrix are real (Advanced)

Show that the eigenvalues of the $2\times2$ real symmetric matrix $S=\begin{bmatrix}a&b\\b&d\end{bmatrix}$ ($a,b,d$ are real numbers; note that the matrix does not change when transposed, since the $(1,2)$ entry and the $(2,1)$ entry are both $b$) are always real, whatever real numbers are chosen for $a,b,d$. Also, find the eigenvalues explicitly in the case $S=\begin{bmatrix}2&3\\3&2\end{bmatrix}$.

Solution. Forming the characteristic equation, we obtain a quadratic equation in $\lambda$:

$$ \det(S-\lambda E)=(a-\lambda)(d-\lambda)-b^2=\lambda^2-(a+d)\lambda+(ad-b^2)=0 $$

By the quadratic formula from high school mathematics, whether this equation has real roots is determined by the sign of the discriminant

$$ D=(a+d)^2-4(ad-b^2) $$

Expanding the right-hand side and simplifying, we get

$$ D=a^2+2ad+d^2-4ad+4b^2=a^2-2ad+d^2+4b^2=(a-d)^2+4b^2 $$

The last expression is the sum of the square of a real number, $(a-d)^2$, and four times the square of a real number, $4b^2$, so $D\ge0$ whatever real numbers $a,b,d$ are (a square is always at least $0$). Therefore the discriminant of the characteristic equation is never negative, and the eigenvalues of $S$ are always real (they can never be complex numbers).

In the concrete case $S=\begin{bmatrix}2&3\\3&2\end{bmatrix}$ ($a=d=2,b=3$), we have $D=(2-2)^2+4\cdot3^2=36$ and $\sqrt D=6$, so the eigenvalues are given by

$$ \lambda=\frac{(a+d)\pm\sqrt D}{2}=\frac{4\pm6}{2}=5,\ -1 $$

(SymPy check: we confirmed that the discriminant of a general two-by-two symmetric matrix agrees with $(a-d)^2+4b^2$, and that the eigenvalues of $S=\begin{bmatrix}2&3\\3&2\end{bmatrix}$ are $5,-1$.)

Application: Why symmetric matrices are everywhere in materials science

When we express the properties of crystals and materials mathematically, symmetric matrices appear surprisingly often—for example, the inertia tensor, which describes how hard it is to rotate an object, the stress tensor, which describes the balance of internal forces when a force is applied to a crystal, and the elastic modulus tensor, which describes how easily a crystal deforms, can all be written as symmetric matrices (or generalizations of them). The fact confirmed in Example 12.3 that “the eigenvalues of a symmetric matrix are real” guarantees that these physical quantities are meaningful as real values (as physical quantities that can actually be measured) rather than as complex numbers. Moreover, the directions of the eigenvectors of a symmetric matrix are called principal axes; for example, the principal-axis directions of the stress tensor indicate “special directions along which only a perpendicular (normal) force acts (pure tension or compression, with no shear force)”—this is one of the basic ideas of materials science, linking the symmetry of a crystal structure to its physical properties.

Finally, we prepare one more important tool for deciding diagonalizability in Section 12.3. It is the fact that “eigenvectors corresponding to distinct eigenvalues are never linearly dependent on one another.”

Theorem 12.3: Eigenvectors corresponding to distinct eigenvalues are linearly independent

Let $\lambda_1,\ldots,\lambda_m$ be distinct eigenvalues of $A$ ($\lambda_i\neq\lambda_j$ whenever $i\neq j$), and let $\bm v_1,\ldots,\bm v_m$ ($A\bm v_i=\lambda_i\bm v_i$, $\bm v_i\neq\bm0$) be eigenvectors corresponding to them, respectively. Then $\bm v_1,\ldots,\bm v_m$ are linearly independent.

Proof

We prove this by mathematical induction on $m$.

The case $m=1$. If $c_1\bm v_1=\bm0$, then $c_1=0$ must hold, because $\bm v_1\neq\bm0$ (by the definition of an eigenvector). Hence $\bm v_1$ alone is linearly independent.

Assuming that the theorem is true for $m-1$ vectors (eigenvectors corresponding to $m-1$ distinct eigenvalues are linearly independent), we prove the case of $m$ vectors. Suppose that the linear relation

\begin{equation} c_1\bm v_1+c_2\bm v_2+\cdots+c_m\bm v_m=\bm0 \label{eq:12-indep-relation} \end{equation}

holds. Multiply both sides of this on the left by the matrix $A-\lambda_m E$. Since $A\bm v_i=\lambda_i\bm v_i$, we have

$$ (A-\lambda_m E)\bm v_i=A\bm v_i-\lambda_m\bm v_i=\lambda_i\bm v_i-\lambda_m\bm v_i=(\lambda_i-\lambda_m)\bm v_i $$

and therefore

$$ c_1(\lambda_1-\lambda_m)\bm v_1+c_2(\lambda_2-\lambda_m)\bm v_2+\cdots+c_{m-1}(\lambda_{m-1}-\lambda_m)\bm v_{m-1}+c_m(\lambda_m-\lambda_m)\bm v_m=\bm0 $$

The last term vanishes because $\lambda_m-\lambda_m=0$, and there remains a linear relation among $\bm v_1,\ldots,\bm v_{m-1}$ (eigenvectors corresponding to the $m-1$ distinct eigenvalues $\lambda_1,\ldots,\lambda_{m-1}$):

$$ c_1(\lambda_1-\lambda_m)\bm v_1+\cdots+c_{m-1}(\lambda_{m-1}-\lambda_m)\bm v_{m-1}=\bm0 $$

By the induction hypothesis (the theorem for $m-1$ vectors), $\bm v_1,\ldots,\bm v_{m-1}$ are linearly independent, so every coefficient in this relation must be $0$: $c_i(\lambda_i-\lambda_m)=0$ ($i=1,\ldots,m-1$). Now $\lambda_i\neq\lambda_m$ (since the eigenvalues are distinct for $i\lt m$), so $\lambda_i-\lambda_m\neq0$, and we therefore conclude that $c_i=0$ ($i=1,\ldots,m-1$). Substituting this back into Eq. \eqref{eq:12-indep-relation} leaves $c_m\bm v_m=\bm0$, and since $\bm v_m\neq\bm0$, it follows that $c_m=0$ as well. Thus $c_1=c_2=\cdots=c_m=0$, and $\bm v_1,\ldots,\bm v_m$ are linearly independent.

∎

12.3 Diagonalization of Matrices

In Section 12.2 we looked, within a single eigenvalue, at “whether the geometric multiplicity and the algebraic multiplicity agree.” From here on we widen our viewpoint to the matrix as a whole and ask: “when we gather up eigenvectors across all $n$ eigenvalues, do we get $n$ linearly independent eigenvectors?” If we do, the matrix $A$ can be diagonalized—and the strategy for making powers easy to compute that we described at the outset can be carried out. First, let us extend Theorem 12.3 (eigenvectors for distinct eigenvalues are linearly independent) to a form that deals not with one eigenvector at a time but with a whole basis of each eigenspace at once.

Theorem 12.4: Bases of the eigenspaces, collected eigenvalue by eigenvalue, are linearly independent

Let the distinct eigenvalues of $A$ be $\lambda_1,\ldots,\lambda_r$, and for the respective eigenspaces $W(\lambda_1),\ldots,W(\lambda_r)$ let $\{\bm u_{1,1},\ldots,\bm u_{1,g_1}\}$, $\ldots$, $\{\bm u_{r,1},\ldots,\bm u_{r,g_r}\}$ be bases ($g_k=\dim W(\lambda_k)$, the geometric multiplicity). Then the $g_1+g_2+\cdots+g_r$ vectors obtained by putting all of these together are linearly independent as a whole.

Proof

We write the overall linear relation, grouping the terms eigenspace by eigenspace.

\begin{equation} \underbrace{\sum_{j=1}^{g_1}c_{1,j}\bm u_{1,j}}_{=:\,\bm w_1\in W(\lambda_1)}+\underbrace{\sum_{j=1}^{g_2}c_{2,j}\bm u_{2,j}}_{=:\,\bm w_2\in W(\lambda_2)}+\cdots+\underbrace{\sum_{j=1}^{g_r}c_{r,j}\bm u_{r,j}}_{=:\,\bm w_r\in W(\lambda_r)}=\bm0 \label{eq:12-union-relation} \end{equation}

Each $\bm w_k$ is a linear combination of the basis of $W(\lambda_k)$ and hence an element of $W(\lambda_k)$; either $\bm w_k=\bm0$, or else it is an eigenvector for the eigenvalue $\lambda_k$. Suppose, for the sake of argument, that two or more of $\bm w_1,\ldots,\bm w_r$ are different from $\bm0$. Since these are eigenvectors corresponding to distinct eigenvalues, they must be linearly independent by Theorem 12.3. But Eq. \eqref{eq:12-union-relation} is a relation saying that the sum of these vectors (together with the terms whose value is $\bm0$) is exactly $\bm0$, with all the coefficients equal to $1$ (nontrivial) if we look only at the terms corresponding to the vectors different from $\bm0$, and this contradicts the definition of linear independence. Hence at most one of $\bm w_1,\ldots,\bm w_r$ can be different from $\bm0$. On the other hand, by Eq. \eqref{eq:12-union-relation} we have $\bm w_1+\cdots+\bm w_r=\bm0$, so it also cannot happen that exactly one of them is different from $\bm0$ (that one would then itself equal $\bm0$, contradicting the definition, by which an eigenvector is never equal to $\bm0$). Therefore we must have $\bm w_1=\bm w_2=\cdots=\bm w_r=\bm0$.

Because $\{\bm u_{k,1},\ldots,\bm u_{k,g_k}\}$ is linearly independent (being, by definition, a basis of $W(\lambda_k)$), each equation $\bm w_k=\sum_j c_{k,j}\bm u_{k,j}=\bm0$ means that the coefficients $c_{k,j}$ are all $0$. Since this holds for every $k=1,\ldots,r$, all the coefficients in the overall relation are $0$; that is, the combined $g_1+\cdots+g_r$ vectors are linearly independent.

∎

At last we define diagonalization itself and prove a criterion for it.

Definition 12.4: Diagonalizability

For a square matrix $A$ of order $n$, if there exists an invertible matrix $P$ such that

\begin{equation} P^{-1}AP=D\qquad(D\ \text{is a diagonal matrix}) \label{eq:12-diag-def} \end{equation}

then $A$ is said to be diagonalizable. Multiplying both sides of Eq. \eqref{eq:12-diag-def} by $P$ on the left and by $P^{-1}$ on the right, we can rewrite the same statement in the form $A=PDP^{-1}$ as well.

Figure 12.2: A diagram illustrating the meaning of $P^{-1}AP=D$. Applying $A$ directly to a vector $\bm x$ in standard coordinates (the upper path) and, alternatively, first switching to the coordinates $\bm c=P^{-1}\bm x$ whose axes are the eigenvectors, then applying the diagonal matrix $D$ (a simple transformation that merely stretches or shrinks along each axis direction) and viewing the result as $Dc$ (the lower path), express essentially the same transformation. By choosing the eigenvectors as the coordinate axes, the action of $A$, which looks complicated, comes to appear as the simple axis-by-axis stretching $D$; this is the meaning of diagonalization.

Theorem 12.5: A necessary and sufficient condition for diagonalizability

The necessary and sufficient condition for a square matrix $A$ of order $n$ to be diagonalizable is that $A$ have $n$ linearly independent eigenvectors.

Proof

($\Leftarrow$) Suppose that $A$ has $n$ linearly independent eigenvectors $\bm v_1,\ldots,\bm v_n$ ($A\bm v_i=\lambda_i\bm v_i$, where the $\lambda_i$ may repeat). Form the matrix $P=[\bm v_1\ \bm v_2\ \cdots\ \bm v_n]$ whose columns are these vectors; since the columns are linearly independent, $P$ is invertible (Theorem 10.1 of Chapter 10, or the invertibility conditions in Chapter 9). Computing $AP$ column by column, we obtain

$$ AP=[A\bm v_1\ A\bm v_2\ \cdots\ A\bm v_n]=[\lambda_1\bm v_1\ \lambda_2\bm v_2\ \cdots\ \lambda_n\bm v_n]=[\bm v_1\ \cdots\ \bm v_n]\begin{bmatrix}\lambda_1& & \\ &\ddots& \\ & &\lambda_n\end{bmatrix}=PD $$

Here the second-to-last equality rests on a fact that can be read off directly from the definition of the matrix product: multiplying on the right by the diagonal matrix $D=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)$ is the same as “scaling each column by the diagonal entry corresponding to that column.” Multiplying both sides of $AP=PD$ by $P^{-1}$ on the left gives $P^{-1}AP=D$, so $A$ is diagonalizable.

($\Rightarrow$) Conversely, suppose that $A$ is diagonalizable, so that there exists an invertible matrix $P$ with $P^{-1}AP=D=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)$. Multiplying both sides by $P$ on the left gives $AP=PD$; let $\bm v_1,\ldots,\bm v_n$ be the columns of $P$ ($P=[\bm v_1\ \cdots\ \bm v_n]$). Retracing the same computation as above in reverse, the $i$th column of $AP$ is $A\bm v_i$ and the $i$th column of $PD$ is $\lambda_i\bm v_i$, so for each $i$ the equation

$$ A\bm v_i=\lambda_i\bm v_i $$

holds. Since $P$ is invertible, its columns $\bm v_1,\ldots,\bm v_n$ are linearly independent, and in particular none of the $\bm v_i$ is $\bm0$ (if $\bm v_i=\bm0$, then together with the remaining $n-1$ columns they could span a space of dimension at most $n-1$, contradicting the invertibility of $P$—that is, the fact that its $n$ columns span an $n$-dimensional space). Hence each $\bm v_i$ is an eigenvector of $A$ (for the eigenvalue $\lambda_i$) in the sense of Definition 12.1. Therefore $A$ has $n$ linearly independent eigenvectors $\bm v_1,\ldots,\bm v_n$.

∎

Restating in terms of multiplicities

By Theorem 12.4 (bases of the eigenspaces, collected together, remain linearly independent), if from the eigenspace of each eigenvalue $\lambda_k$ we choose a basis of $g_k=\dim W(\lambda_k)$ vectors (the geometric multiplicity) and put them all together, we obtain a total of $g_1+g_2+\cdots+g_r$ linearly independent vectors. The condition of Theorem 12.5 ($n$ linearly independent eigenvectors) is satisfied if and only if this number is $n$. On the other hand, the sum $a_1+\cdots+a_r$ of the algebraic multiplicities is always $n$, because the characteristic polynomial has exactly $n$ roots, counted with multiplicity (over the complex numbers). Combining this with Theorem 12.2 ($g_k\le a_k$ for each eigenvalue), we obtain

$$ g_1+g_2+\cdots+g_r\ \le\ a_1+a_2+\cdots+a_r=n $$

and equality (that is, a full set of $n$ linearly independent eigenvectors is available) holds if and only if, for every eigenvalue $\lambda_k$, we have $g_k=a_k$ (geometric multiplicity = algebraic multiplicity). In this way, diagonalizability can also be restated in the language of Section 12.2 as “the two multiplicities agree for every eigenvalue.”

A concrete procedure for diagonalization

The procedure for diagonalizing a given square matrix $A$ of order $n$ is as follows.

(i) Solve the characteristic equation $\det(A-\lambda E)=0$ to find all the (distinct) eigenvalues $\lambda_1,\ldots,\lambda_r$ and their algebraic multiplicities $a_k$.
(ii) For each eigenvalue $\lambda_k$, find a basis of the eigenspace $W(\lambda_k)=\mathrm{Ker}(A-\lambda_k E)$ and determine its dimension (the geometric multiplicity) $g_k$.
(iii) Check whether $g_k=a_k$ for every $k$. If even one eigenvalue has $g_k\lt a_k$, then $A$ is not diagonalizable (by Theorem 12.5, because $n$ linearly independent eigenvectors cannot be gathered).
(iv) If $g_k=a_k$ holds for all the eigenvalues, form $P$ by arranging as its columns the $n$ vectors obtained by putting together the bases of all the eigenspaces (linearly independent by Theorem 12.4). In this case, let $D=\mathrm{diag}(\lambda_1,\ldots,\lambda_1,\lambda_2,\ldots,\lambda_2,\ldots)$ (the diagonal matrix in which each eigenvalue is listed as many times as its algebraic multiplicity), with the diagonal entries arranged to match the order of the columns of $P$; then $P^{-1}AP=D$.

Figure 12.3: Flowchart of the procedure for determining diagonalizability. If the geometric and algebraic multiplicities agree for every eigenvalue, the matrix is diagonalizable; if even one eigenvalue has multiplicities that disagree, it is not diagonalizable (Theorem 12.5 and its restatement in terms of multiplicities).

Example 12.4: Diagonalizable and non-diagonalizable cases

Each of the following two matrices has only the eigenvalue $2$ (of multiplicity two). Determine whether each is diagonalizable. (a) $A=\begin{bmatrix}2&0\\0&2\end{bmatrix}$. (b) $B=\begin{bmatrix}2&1\\0&2\end{bmatrix}$.

Solution. (a) $A-\lambda E=\begin{bmatrix}2-\lambda&0\\0&2-\lambda\end{bmatrix}$ (which is both a diagonal matrix and an upper triangular matrix), so the characteristic equation is $(2-\lambda)^2=0$, and the eigenvalue is $\lambda=2$ (algebraic multiplicity $a=2$). The eigenspace is given by $(A-2E)\bm x=\begin{bmatrix}0&0\\0&0\end{bmatrix}\bm x=\bm0$, which holds for every $\bm x\in\R^2$, so $W(2)=\R^2$ and the geometric multiplicity is $g=2$. Since $g=a=2$, the matrix is diagonalizable—in fact, $A$ itself is already a diagonal matrix, so taking $P=E$ (the identity matrix) gives $P^{-1}AP=A$.

(b) $B-\lambda E=\begin{bmatrix}2-\lambda&1\\0&2-\lambda\end{bmatrix}$ is also upper triangular, so the characteristic equation is again $(2-\lambda)^2=0$, and the eigenvalue is $\lambda=2$ (algebraic multiplicity $a=2$). The eigenspace is determined by $(B-2E)\bm x=\begin{bmatrix}0&1\\0&0\end{bmatrix}\bm x=\bm0$, that is, by $x_2=0$ ($x_1$ is free). Hence $W(2)=\{(t,0)^{\mathsf T}\mid t\in\R\}$ is one-dimensional, and the geometric multiplicity is $g=1\lt a=2$. By Theorem 12.5 (in its restatement in terms of multiplicities), $B$ is not diagonalizable—the eigenvectors of $B$ are only the constant multiples of $(1,0)^{\mathsf T}$, and since there is no other eigenvector linearly independent of this one, we cannot collect $2$ independent eigenvectors. (SymPy check: we confirmed that the eigenspace of $A$ is two-dimensional and that the eigenspace of $B$ is one-dimensional.)

12.4 An Application of Diagonalization — Powers of Matrices

The greatest benefit of diagonalization is that powers of a matrix can be computed easily. In this section we unravel the mystery of the three patterns we saw at the beginning of Chapter 8 (diagonal matrices, upper triangular matrices, and rotation matrices).

Theorem 12.6: Formula for powers of a matrix via diagonalization

If $A$ is diagonalizable and can be written as $A=PDP^{-1}$ ($D$ a diagonal matrix), then for every natural number $n$ we have

\begin{equation} A^n=PD^nP^{-1} \label{eq:12-power-diag} \end{equation}

In particular, if $D=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)$, then $D^n=\mathrm{diag}(\lambda_1^n,\ldots,\lambda_n^n)$ (since multiplying diagonal matrices merely multiplies the corresponding diagonal entries, to take a power of a diagonal matrix it suffices to raise each diagonal entry to that power separately).

Proof

We prove this by mathematical induction on $n$. For $n=1$ the claim holds trivially, since $A^1=A=PDP^{-1}=PD^1P^{-1}$. Assume that $A^k=PD^kP^{-1}$ holds for $n=k$. Then

$$ A^{k+1}=A^k\cdot A=(PD^kP^{-1})(PDP^{-1})=PD^k(P^{-1}P)DP^{-1}=PD^k\,E\,DP^{-1}=PD^kDP^{-1}=PD^{k+1}P^{-1} $$

(we used $P^{-1}P=E$, the identity matrix, which changes nothing when multiplied, and $D^kD=D^{k+1}$, in that order). Hence the claim also holds for $n=k+1$, and by mathematical induction Eq. \eqref{eq:12-power-diag} holds for all natural numbers $n$.

∎

With this formula, even a computation that multiplies a matrix by itself 100 or 1000 times reduces to $D^n$ (just raising each diagonal entry to the $n$th power) and two matrix multiplications involving $P,P^{-1}$. Let us check this in practice in the next example, using the matrix from Section 12.1.

Example 12.5: Computing a high power using diagonalization

For the matrix $A=\begin{bmatrix}4&-2\\1&1\end{bmatrix}$ of Illustration 12.1, find $A^{10}$.

Solution. By Illustration 12.1, the eigenvalues of $A$ are $\lambda=2,3$, with corresponding eigenvectors $(1,1)^{\mathsf T},(2,1)^{\mathsf T}$. Since these correspond to distinct eigenvalues, they are linearly independent by Theorem 12.3, and $A$ is diagonalizable by Theorem 12.5. Arranging the eigenvectors as columns, we set

$$ P=\begin{bmatrix}1&2\\1&1\end{bmatrix} $$

Since $\det P=1\cdot1-2\cdot1=-1\neq0$, $P$ is invertible, and a direct check shows that

$$ P^{-1}=\begin{bmatrix}-1&2\\1&-1\end{bmatrix} $$

(indeed,

$$ PP^{-1}=\begin{bmatrix}1\cdot(-1)+2\cdot1&1\cdot2+2\cdot(-1)\\1\cdot(-1)+1\cdot1&1\cdot2+1\cdot(-1)\end{bmatrix}=\begin{bmatrix}1&0\\0&1\end{bmatrix} $$

so the product agrees with the identity matrix, which confirms the result). As in the proof of Theorem 12.5, $P^{-1}AP=D=\begin{bmatrix}2&0\\0&3\end{bmatrix}$, so by Theorem 12.6 we have

$$ A^{10}=PD^{10}P^{-1}=\begin{bmatrix}1&2\\1&1\end{bmatrix}\begin{bmatrix}2^{10}&0\\0&3^{10}\end{bmatrix}\begin{bmatrix}-1&2\\1&-1\end{bmatrix} $$

Substituting $2^{10}=1024$ and $3^{10}=59049$, we first compute the product of the left two matrices:

$$ PD^{10}=\begin{bmatrix}1\cdot1024&2\cdot59049\\1\cdot1024&1\cdot59049\end{bmatrix}=\begin{bmatrix}1024&118098\\1024&59049\end{bmatrix} $$

and multiplying this by $P^{-1}$ gives

$$ A^{10}=\begin{bmatrix}1024&118098\\1024&59049\end{bmatrix}\begin{bmatrix}-1&2\\1&-1\end{bmatrix}=\begin{bmatrix}1024\cdot(-1)+118098\cdot1&1024\cdot2+118098\cdot(-1)\\1024\cdot(-1)+59049\cdot1&1024\cdot2+59049\cdot(-1)\end{bmatrix}=\begin{bmatrix}117074&-116050\\58025&-57001\end{bmatrix} $$

Instead of multiplying the matrix ten times, we obtained the result using only the powers of the two numbers $2^{10},3^{10}$ and two products of $2\times2$ matrices. (SymPy check: both the result of multiplying $A$ by itself ten times directly and the result of $PD^{10}P^{-1}$ were confirmed to agree with $\begin{bmatrix}117074&-116050\\58025&-57001\end{bmatrix}$.)

Math Note: To diagonalize rotation matrices—a quick review of complex numbers

Let us find the eigenvalues of the rotation matrix $R(\theta)=\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}$ (the matrix treated in Chapter 8 that rotates by the angle $\theta$ about the origin). The characteristic equation is

$$ \det(R(\theta)-\lambda E)=(\cos\theta-\lambda)^2+\sin^2\theta=\lambda^2-2\lambda\cos\theta+1=0 $$

(expanding and using $\cos^2\theta+\sin^2\theta=1$, this form comes out of the computation of the coefficient of $\lambda^2$). By the quadratic formula from high school mathematics, we obtain

$$ \lambda=\cos\theta\pm\sqrt{\cos^2\theta-1}=\cos\theta\pm\sqrt{-\sin^2\theta}=\cos\theta\pm i\sin\theta $$

Here $i$ is the imaginary unit (the number satisfying $i^2=-1$, which is not a real number). When $\theta\neq0,\pi$ we have $\sin\theta\neq0$, so the quantity under the radical, $-\sin^2\theta$, is negative, the square root cannot be taken within the real numbers, and $i$ is needed. In other words, as long as $\theta\neq0,\pi$, the eigenvalues of a rotation matrix are not real numbers but complex numbers (numbers of the form $a+bi$ with $a,b$ real). If we look only for real eigenvectors, a rotation matrix cannot be diagonalized—only when we widen the search to the complex numbers learned in high school mathematics does diagonalization first become possible.

We write $\C^n$ for the set of all $n$-dimensional vectors whose components are complex numbers, and we compute sums and scalar multiples of vectors, and matrix products, by exactly the same rules as in the real case (except that the scalars may now be complex numbers). The definition of eigenvalues and eigenvectors (Definition 12.1) and the criterion for diagonalizability (Theorem 12.5) remain valid as they are, without changing any step of the proofs, if we work in $\C^n$ instead of $\R^n$.

Also, since the complex number $\cos\theta+i\sin\theta$ will appear repeatedly in later chapters (in particular in the advanced resource “Fourier Series and Transforms”), we introduce the abbreviation using an exponent

$$ e^{i\theta}:=\cos\theta+i\sin\theta $$

(this is called Euler's formula). Proving that this expression really satisfies the properties of an exponential function (for example, $e^{i\theta_1}e^{i\theta_2}=e^{i(\theta_1+\theta_2)}$) requires an argument with Taylor expansions that extends the exponential function to the complex numbers, so we leave it to the advanced resource “Complex Analysis” and use it here merely as a convenient abbreviation. With this notation, the eigenvalues of a rotation matrix can be written concisely as $\lambda=e^{\pm i\theta}=\cos\theta\pm i\sin\theta$.

Example 12.6: Complex eigenvalues of a rotation matrix and its diagonalization

Consider the rotation matrix for $\theta=\pi/3$ ($60°$),

$$ R=\begin{bmatrix}\cos60°&-\sin60°\\\sin60°&\cos60°\end{bmatrix}=\begin{bmatrix}1/2&-\sqrt3/2\\\sqrt3/2&1/2\end{bmatrix} $$

Find its eigenvalues and eigenvectors, and diagonalize it over the complex numbers.

Solution. By the computation in the Math Note above, the eigenvalues are as follows.

$$ \lambda_1=e^{i\pi/3}=\cos60°+i\sin60°=\dfrac12+i\dfrac{\sqrt3}2,\qquad \lambda_2=e^{-i\pi/3}=\dfrac12-i\dfrac{\sqrt3}2 $$

To find the eigenvectors, we write $(R-\lambda_1E)\bm x=\bm0$ in components, which gives the system

$$ \begin{cases}(\cos\theta-\lambda_1)x_1-\sin\theta\, x_2=0\\ \sin\theta\, x_1+(\cos\theta-\lambda_1)x_2=0\end{cases} $$

Now,

$$ \cos\theta-\lambda_1=\cos\theta-(\cos\theta+i\sin\theta)=-i\sin\theta $$

so the first equation is $-i\sin\theta\,x_1-\sin\theta\,x_2=0$, that is (since $\sin\theta\neq0$, dividing both sides by $-\sin\theta$) $x_2=-ix_1$. Taking $x_1=1$, we obtain the eigenvector $\bm v_1=(1,-i)^{\mathsf T}$ (for the second equation as well, we have

$$ \sin\theta\cdot1+(-i\sin\theta)\cdot(-i)=\sin\theta+i^2\sin\theta=\sin\theta-\sin\theta=0 $$

so it is indeed satisfied). Similarly, for $\lambda_2=\cos\theta-i\sin\theta$ we have $\cos\theta-\lambda_2=i\sin\theta$, and by the same procedure we obtain $\bm v_2=(1,i)^{\mathsf T}$.

Since $\bm v_1,\bm v_2$ correspond to distinct eigenvalues, they are linearly independent (Theorem 12.3 holds over the complex numbers as well, without changing any step of its proof), so $P=\begin{bmatrix}1&1\\-i&i\end{bmatrix}$ ($\det P=1\cdot i-1\cdot(-i)=2i\neq0$) is invertible. Therefore $R$ is diagonalizable over the complex numbers, and following the procedure constructed in the proof of Theorem 12.5, we obtain

$$ P^{-1}RP=D=\begin{bmatrix}e^{i\theta}&0\\0&e^{-i\theta}\end{bmatrix} $$

(SymPy check: for the numerical value $\theta=\pi/3$, we confirmed that $R\bm v_1=\lambda_1\bm v_1$ and $R\bm v_2=\lambda_2\bm v_2$ hold, and that actually computing $PDP^{-1}$ gives back exactly the original real matrix $R$, the expressions containing the imaginary unit canceling out cleanly.)

Why can't a rotation matrix be diagonalized over the real numbers?

If we insist on the real numbers, then for $\theta\neq0,\pi$ the eigenvalues of a rotation matrix are not even real in the first place (the characteristic equation has no real roots), so the very notion of a real eigenvector does not exist. Therefore, before we can even ask “whether it can be diagonalized,” we find that over the real numbers there is not a single eigenvalue or eigenvector. This is a completely different type of reason for “not being diagonalizable” from the one we saw in Section 12.3, namely that “the eigenspace is thin (the geometric multiplicity falls short of the algebraic multiplicity), so the matrix cannot be diagonalized” (Example 12.4(b))—the reason in Example 12.4(b) is not removed even by extending to the complex numbers (the geometric multiplicity stays 1 even when considered over the complex numbers), whereas in the case of a rotation matrix, the obstacle is resolved cleanly once we widen the search to the complex numbers.

12.4.1 Looking back at the three patterns of Chapter 8

Here we settle the mystery posed at the beginning of this chapter—why only the three patterns of diagonal, upper triangular, and rotation matrices allowed their powers to be computed easily. Table 12.1 summarizes the matter from the viewpoint of diagonalization.

Table 12.1: The three power patterns of Chapter 8 and their relation to diagonalization
Type of matrix	Eigenvalues	Diagonalizable?	Power $A^n$
Diagonal matrix $\mathrm{diag}(\alpha,\beta)$	$\alpha,\beta$ (real; even if they coincide, for each eigenvalue the multiplicities satisfy $g_k=a_k$)	Diagonal from the start (diagonalizable with $P=E$)	$\mathrm{diag}(\alpha^n,\beta^n)$
Rotation matrix $\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}$	$e^{\pm i\theta}$ (distinct complex numbers if $\theta\neq0,\pi$)	Impossible over the real numbers, possible over the complex numbers (Example 12.6)	Rotation matrix through the angle $n\theta$ (computing $PD^nP^{-1}$ returns it to a real form by Euler's formula)
Upper triangular matrix $\begin{bmatrix}1&\alpha\\0&1\end{bmatrix}$ ($\alpha\neq0$)	$1$ (algebraic multiplicity 2)	Impossible (geometric multiplicity $1\lt$ algebraic multiplicity $2$, the same reason as in Example 12.4(b))	$\begin{bmatrix}1&n\alpha\\0&1\end{bmatrix}$ (proved directly by mathematical induction in Chapter 8, without relying on diagonalization)

Thus, the question at the beginning of Chapter 8, “why could only these three be raised to powers so easily?”, has been settled in this chapter—there were three different reasons: a diagonal matrix is already diagonalized from the start; a rotation matrix can be diagonalized over the complex numbers; and an upper triangular matrix cannot be diagonalized, but because its original form was simple, direct mathematical induction sufficed. The single framework of eigenvalues, eigenvectors, and diagonalization explains in a unified way all three computations that looked unrelated at first—this is one of the real pleasures of linear algebra.

12.5 Summary and Exercises

12.5.1 Summary

Eigenvalues and eigenvectors: a number $\lambda$ and a vector $\bm x$ satisfying $A\bm x=\lambda\bm x$ ($\bm x\neq\bm0$). After rewriting this as $(A-\lambda E)\bm x=\bm0$, they are found by solving the characteristic equation $\det(A-\lambda E)=0$ (Theorem 12.1).
Eigenspace $W(\lambda)=\mathrm{Ker}(A-\lambda E)$ (Definition 12.2; an application of $\mathrm{Ker}\,f$ from Chapter 11). The characteristic polynomial has degree exactly $n$ in $\lambda$ (over the complex numbers, there are exactly $n$ eigenvalues counted with multiplicity). The multiplicity of an eigenvalue as a root of this polynomial is its algebraic multiplicity, and the dimension of its eigenspace is its geometric multiplicity (Definition 12.3); one always has $1\le$ geometric multiplicity $\le$ algebraic multiplicity (Theorem 12.2).
Eigenvectors corresponding to distinct eigenvalues are linearly independent (Theorem 12.3), and the vectors obtained by collecting bases of the eigenspaces, eigenvalue by eigenvalue, are also linearly independent (Theorem 12.4).
Diagonalizability: the existence of an invertible matrix $P$ such that $P^{-1}AP=D$, a diagonal matrix (Definition 12.4). A necessary and sufficient condition is that there exist $n$ linearly independent eigenvectors, which amounts to the same thing as the geometric multiplicity being equal to the algebraic multiplicity for every eigenvalue (Theorem 12.5).
If the matrix can be diagonalized, then $A^n=PD^nP^{-1}$ (Theorem 12.6), and computing $D^n$ only requires raising each diagonal entry to that power separately.
The three power patterns of Chapter 8 (diagonal, rotation, upper triangular) occupy different positions when viewed from the standpoint of diagonalization (Table 12.1)—the diagonal matrix is diagonal from the start, the rotation matrix is diagonalizable over the complex numbers, and the upper triangular matrix is not diagonalizable but can be computed directly by mathematical induction.

This chapter is based on the definition of eigenvalues and eigenvectors and the first worked computation (Section 12.1, Illustration 12.1 of this chapter) in Yasuhide Mochizuki's “Mathematics Notes: Linear Algebra.” In order to carry the theme of diagonalization through to the end, the material from Section 12.2 onward (eigenspaces, multiplicities, the test for diagonalizability, the procedure for diagonalization, and the application to powers) has been supplied as original content of this book, and the whole has been arranged into one coherent flow that reaches all the way back to the mystery posed at the beginning (Table 12.1).

$$ A\bm x=\lambda\bm x\ (\bm x\neq\bm0)\ \Longleftrightarrow\ \det(A-\lambda E)=0, \qquad A=PDP^{-1}\ \Longrightarrow\ A^n=PD^nP^{-1} $$

12.5.2 Exercises

Exercise 12.1: Eigenvalues and the characteristic equation of a 3×3 matrix

Find the characteristic equation and all eigenvalues of $A=\begin{bmatrix}1&0&0\\1&0&2\\-1&2&0\end{bmatrix}$, and find one eigenvector corresponding to each eigenvalue.

Hint: Compute by the same procedure as in Example 12.1 (evaluate the $3\times3$ determinant by cofactor expansion, find one root with the factor theorem, and then reduce the remaining part to a quadratic equation).

→ Solution

Exercise 12.2: Determining diagonalizability

Is $A=\begin{bmatrix}4&1&0\\0&4&0\\0&0&-1\end{bmatrix}$ diagonalizable? Give reasons for your answer.

Hint: Since this is an upper triangular matrix, the eigenvalues can be read off immediately from the diagonal entries. For each repeated eigenvalue, find the dimension of the eigenspace $W(\lambda)$ (the geometric multiplicity) and compare it with the algebraic multiplicity.

→ Solution

Exercise 12.3: Powers of a matrix via diagonalization

For $A=\begin{bmatrix}0&1\\-4&5\end{bmatrix}$, find the eigenvalues and eigenvectors, diagonalize it, and find a general formula for $A^n$ ($n$ a natural number). Then use that formula to compute $A^5$ explicitly.

Hint: Proceed in exactly the same way as in Example 12.5. Both eigenvalues are integers.

→ Solution

Exercise 12.4: The relation between the eigenvalue 0 and Ker f

Let $A=\begin{bmatrix}1&2\\2&4\end{bmatrix}$. (1) Show that $\lambda=0$ is an eigenvalue of $A$, and find a corresponding eigenvector. (2) Explain why, for a square matrix $A$ of order $n$ in general, the statement “$\lambda=0$ is an eigenvalue of $A$” is equivalent to the statement “the kernel $\mathrm{Ker}\,f$ of the linear map $f(\bm x)=A\bm x$ whose representation matrix is $A$ is strictly larger than $\{\bm0\}$ (that is, $A$ is not invertible).”

Hint: For (2), it suffices to compare Definition 12.1 and Definition 12.2—what is the eigenspace $W(0)$ when $\lambda=0$?

→ Solution

Exercise 12.5: Directly checking linear independence

Verify that the three eigenvectors found in Exercise 12.1 are linearly independent by computing a determinant directly, without relying on Theorem 12.3.

Hint: Form the $3\times3$ matrix whose columns are the three vectors, and check that its determinant is not $0$ (Theorem 10.1 of Chapter 10).

→ Solution

Exercise 12.6: Constructing a non-diagonalizable matrix yourself

Construct a $2\times2$ matrix of your own that is not diagonalizable, and explain, in terms of algebraic multiplicity and geometric multiplicity, why it cannot be diagonalized.

Hint: Use the same mechanism as in Example 12.4(b)—an upper triangular matrix with a repeated eigenvalue—and build your own by changing the eigenvalue.

→ Solution

12.5.3 References

Yasuhide Mochizuki, Mathematics Notes: Linear Algebra (handwritten lecture notes, in Japanese). The source of this chapter.
Masahiko Saito, Senkei Daisū Nyūmon [Introduction to Linear Algebra], University of Tokyo Press, 1966 (in Japanese).
Ichiro Satake, Senkei Daisūgaku [Linear Algebra], Shōkabō, 1958 (in Japanese).