Eigenvalues and Eigenvectors

8.1 Definitions and examples

So far in Linear Transformations we have studied linear maps $T:V\to W$ where the domain and codomain could be completely different spaces. In this chapter we specialise to the case $T:V\to V$, where a vector and its image live in the same space, so that it actually makes sense to ask how $T(\mathbf{v})$ compares to $\mathbf{v}$ itself. Two questions drive everything that follows:

1. Given a map $T$, are there vectors $\mathbf{v}\in V$ that are related in a very simple way to their images $T(\mathbf{v})$?
2. [X] Is there a choice of basis for $V$ that makes the matrix representing $T$ take a very simple form?

The answer to both is yes, and remarkably it is the same answer. The simplest possible relationship between $\mathbf{v}$ and $T(\mathbf{v})$ is that they are parallel; $T$ does nothing to $\mathbf{v}$ except stretch it.

Basically, an eigenvector is a direction that the map leaves alone; every other vector gets rotated or sheared off into some new direction, but an eigenvector just gets scaled by $\lambda$. The whole power of the subject comes from the fact that if you can find enough of these directions to build a basis, then the map is nothing but a collection of independent stretches, which is about as simple as a linear map can get.

It is important to note the asymmetry in the definition: an eigenvector must be non-zero, but zero is perfectly allowed to be an eigenvalue. The reason for banning $0$ is that $T(0)=\lambda 0$ holds for every scalar $\lambda$, so if we allowed it then every number would be an eigenvalue of every map and the definition would say nothing at all. On the other hand $\lambda =0$ is genuinely informative; it says exactly that $\ker T\ne \{0\}$, i.e. that $T$ is not one-to-one.

Example. For infinitely differentiable real-valued functions $f$, the derivative

$$D(f)=f^{\prime },\text{where }{f}^{\prime }(x)=\frac{df}{dx}\text{ for }x\in \mathbb{R},$$

defines a linear map $D$ (we checked in Section 7.5 that differentiation is linear). The exponential function satisfies

$$D(e^{\lambda x})=\lambda e^{\lambda x},$$

so $e^{\lambda x}$ is an eigenvector of $D$ with eigenvalue $\lambda$. Notice that this is not a curiosity; the enormous importance of exponentials in calculus is precisely that they are the only functions whose derivative is a multiple of themselves. Every time you solved $\frac{dy}{dx}=ay$ in Ordinary Differential Equations and wrote down $y=C{e}^{ax}$, you were computing an eigenvector of $D$.

Calculus is a very rich source of eigenvalue problems, but in this course we are mainly concerned with algebraic problems on finite-dimensional spaces. Those maps can always be represented by matrices, so from here on "eigenvalue" means "eigenvalue of a matrix".

There is one important piece of housekeeping first. When dealing with eigenvalues of matrices we are forced to use $\mathbb{C}$ as our field of scalars. The reason is that eigenvalues turn out to be the zeroes of a polynomial, and we can only be certain of finding zeroes when the polynomial is complex. So the natural scalar field here is $\mathbb{C}$ and the natural vector spaces are the complex spaces ${\mathbb{C}}^n$ from Section 6.1. Real matrices are still allowed; we just have to accept that a perfectly innocent real matrix can have complex eigenvalues, and refusing to look at them would leave the theory full of holes.

Example. For the diagonal $2\times 2$ matrix

$$A=\left(\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right),$$

the standard basis vectors ${\mathbf{e}}_1=\left(\begin{array}{c}1\\ 0\end{array}\right)$ and ${\mathbf{e}}_2=\left(\begin{array}{c}0\\ 1\end{array}\right)$ satisfy

$$\begin{array}{rl}A{\mathbf{e}}_1& =\left(\begin{array}{c}{\lambda }_1\\ 0\end{array}\right)={\lambda }_1{\mathbf{e}}_1,\\ A{\mathbf{e}}_2& =\left(\begin{array}{c}0\\ {\lambda }_2\end{array}\right)={\lambda }_2{\mathbf{e}}_2.\end{array}$$

Therefore ${\mathbf{e}}_1$ is an eigenvector with eigenvalue ${\lambda }_1$ and ${\mathbf{e}}_2$ is an eigenvector with eigenvalue ${\lambda }_2$. Geometrically, if ${\lambda }_1=3$ and ${\lambda }_2=-2$, then this matrix stretches everything on the $x$-axis by a factor of $3$ and flips everything on the $y$-axis while doubling its length; the two axes are the two eigen-directions. For a diagonal matrix the eigenvalues are just the diagonal entries and the standard basis vectors are the eigenvectors; there is nothing to calculate. This is the whole reason we will spend Section 8.2 trying to turn other matrices into diagonal ones.

Example. For the matrix and vector

$$A=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 20& -24& 9\end{array}\right),\mathbf{v}=\left(\begin{array}{c}1\\ 5\\ 25\end{array}\right),$$

direct multiplication gives

$$\begin{array}{rl}A\mathbf{v}& =\left(\begin{array}{c}0(1)+1(5)+0(25)\\ 0(1)+0(5)+1(25)\\ 20(1)-24(5)+9(25)\end{array}\right)\\ & =\left(\begin{array}{c}5\\ 25\\ 20-120+225\end{array}\right)\\ & =\left(\begin{array}{c}5\\ 25\\ 125\end{array}\right)\\ & =5\mathbf{v}.\end{array}$$

Therefore $\mathbf{v}$ is an eigenvector of $A$ for the eigenvalue $\lambda =5$. Notice how cheap verifying an eigenvector is compared to finding one; it is one matrix-vector product. If a question hands you a candidate eigenvector, never go through the characteristic polynomial — just multiply.

8.1.1 Some fundamental results

We now need a way of finding eigenvalues rather than checking them. The trick is to turn the eigenvector equation into a statement about a kernel, which is something we already know how to compute by row reduction.

Proof. By definition, an eigenvalue $\lambda$ and corresponding eigenvector $\mathbf{v}$ satisfy $A\mathbf{v}=\lambda \mathbf{v}$ with $\mathbf{v}\ne 0$. Rearranging,

$$\begin{array}{rl}0& =A\mathbf{v}-\lambda \mathbf{v}\\ & =A\mathbf{v}-\lambda I\mathbf{v}(\text{inserting }I\text{ so we can factor})\\ & =(A-\lambda I)\mathbf{v},\end{array}$$

where $I$ is the identity matrix of the same size as $A$. Now $A-\lambda I$ is a square matrix, and a square homogeneous system has a non-zero solution if and only if its determinant vanishes. Hence $\lambda$ is an eigenvalue if and only if $\det (A-\lambda I)=0$. Given that, $\mathbf{v}$ is an eigenvector precisely when it is a non-zero solution of that homogeneous system, i.e. precisely when $\mathbf{v}\in \ker (A-\lambda I)\setminus \{0\}$. $■$

The insertion of $I$ in the second line is the single most important step in this chapter, and it is the step students most often get wrong. You cannot write $A\mathbf{v}-\lambda \mathbf{v}=(A-\lambda )\mathbf{v}$, because $A-\lambda$ is a matrix minus a scalar, which is meaningless. You must turn $\lambda$ into $\lambda I$ first.

Basically, this theorem converts an eigenvalue problem into two things we already know how to do: computing a determinant, and computing a kernel. It also tells us something structurally nice. The set of eigenvectors for $\lambda$, together with $0$, is exactly $\ker (A-\lambda I)$, and a kernel is a subspace by the theorem in Section 7.4.1.

So an eigenvalue never has just one eigenvector; it has a whole subspace of them (minus the origin), and in particular there are always infinitely many. When we "write down the eigenvector for $\lambda$" we are really recording a basis for the eigenspace, and any non-zero multiple of it would have done just as well. Do not be alarmed if your eigenvector is a different multiple from the answer in the back of the book; check whether the two are parallel before assuming you are wrong.

This can be proved by direct expansion of the determinant; it is straightforward but tedious, so we will just look at the $n=3$ case to see why it happens. We have

$$A-\lambda I=\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)-\lambda \left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)=\left(\begin{array}{ccc}{a}_{11}-\lambda & a_{12}& a_{13}\\ a_{21}& a_{22}-\lambda & a_{23}\\ a_{31}& a_{32}& a_{33}-\lambda \end{array}\right),$$

and expanding along the first column,

$$\begin{array}{rl}\det (A-\lambda I)& =(a_{11}-\lambda )[(a_{22}-\lambda )(a_{33}-\lambda )-a_{32}{a}_{23}]\\ & -a_{21}[a_{12}(a_{33}-\lambda )-a_{32}{a}_{13}]+a_{31}[a_{12}{a}_{23}-(a_{22}-\lambda )a_{13}]\\ & =-{\lambda }^3+(\text{terms in }{\lambda }^2,\lambda \text{ and constants}).\end{array}$$

Notice where the ${\lambda }^3$ comes from: only the product of the three diagonal entries contributes a ${\lambda }^3$ term, and it arrives with a sign of $(-1{)}^3$. In general the leading term is $(-1{)}^n{\lambda }^n$, which is why the degree is exactly $n$ and never less.

Example. Find the characteristic polynomial of

$$A=\left(\begin{array}{ccc}1& -1& 2\\ 3& -4& -1\\ 5& 1& 2\end{array}\right).$$

Subtracting $\lambda$ from each diagonal entry and expanding along the first row,

$$\begin{array}{rl}p(\lambda )& =\left|\begin{array}{ccc}1-\lambda & -1& 2\\ 3& -4-\lambda & -1\\ 5& 1& 2-\lambda \end{array}\right|\\ & =(1-\lambda )[(-4-\lambda )(2-\lambda )+1]+1[3(2-\lambda )+5]+2[3+5(4+\lambda )]\\ & =(1-\lambda )({\lambda }^2+2\lambda -7)+(11-3\lambda )+(46+10\lambda )\\ & =-{\lambda }^3-{\lambda }^2+9\lambda -7+57+7\lambda \\ & =-{\lambda }^3-{\lambda }^2+16\lambda +50.\end{array}$$

Therefore the characteristic polynomial is $p(\lambda )=-{\lambda }^3-{\lambda }^2+16\lambda +50$. A useful sanity check at this point: the coefficient of ${\lambda }^{n-1}$ is always $(-1{)}^{n-1}\mathrm{tr}(A)$, the sum of the diagonal entries, and $p(0)=\det A$. Here $\mathrm{tr}(A)=1-4+2=-1$, matching the $-{\lambda }^2$ term, and $p(0)=50=\det A$. If either check fails you have made an arithmetic slip; this catches errors far faster than redoing the expansion.

This is where the insistence on complex scalars pays off. Over $\mathbb{R}$ the statement is simply false — a rotation matrix has no real eigenvalues at all — but over $\mathbb{C}$ every $n\times n$ matrix has its full complement of $n$ eigenvalues, no exceptions.

Example. For the matrix $A$ of the previous example, the roots of $-{\lambda }^3-{\lambda }^2+16\lambda +50=0$ are, to four significant figures, $4.688$, $-2.844+1.605i$ and $-2.844-1.605i$, and these are the three eigenvalues of $A$.

You are not expected to solve nasty cubics like that by hand; note the complex pair appearing as conjugates, which always happens when the matrix has real entries. The theorem is of enormous theoretical importance because it guarantees eigenvalues exist, but with the exception of $2\times 2$ matrices and specially constructed larger ones, modern numerical methods for finding eigenvalues do not go anywhere near the characteristic polynomial — they are iterative, and vastly more stable.

8.1.2 Calculation of eigenvalues and eigenvectors

The working method is now fixed, and every exam question in this chapter follows it:

• Form $A-\lambda I$ by subtracting $\lambda$ from each diagonal entry.
• Compute $p(\lambda )=\det (A-\lambda I)$ and solve $p(\lambda )=0$ for the eigenvalues.
• For each eigenvalue ${\lambda }_i$ in turn, row reduce $A-{\lambda }_{i}I$ and find a basis for $\ker (A-{\lambda }_{i}I)$.

Example. Find the eigenvalues and eigenvectors of $A=\left(\begin{array}{cc}2& 2\\ 2& 2\end{array}\right)$.
The characteristic polynomial is

$$\begin{array}{rl}p(\lambda )& =\left|\begin{array}{cc}2-\lambda & 2\\ 2& 2-\lambda \end{array}\right|\\ & =(2-\lambda {)}^2-4\\ & ={\lambda }^2-4\lambda \\ & =\lambda (\lambda -4),\end{array}$$

so the eigenvalues are ${\lambda }_1=0$ and ${\lambda }_2=4$. As promised, a $2\times 2$ matrix has two of them.

For ${\lambda }_1=0$ the eigenvectors are the non-zero vectors of $\ker (A-0I)=\ker A$. Row reducing,

$$\left(\begin{array}{cccc}2& 2& |& 0\\ 2& 2& |& 0\end{array}\right)\stackrel{R_2=R_2-R_1}{\to }\left(\begin{array}{cccc}2& 2& |& 0\\ 0& 0& |& 0\end{array}\right),$$

so $2v_1+2v_2=0$, giving $v_1=-v_2$ and

$$\ker A=\mathrm{span}\left\{\left(\begin{array}{c}-1\\ 1\end{array}\right)\right\}.$$

For ${\lambda }_2=4$ we have $A-4I=\left(\begin{array}{cc}-2& 2\\ 2& -2\end{array}\right)$, which row reduces to a single equation $-2v_1+2v_2=0$, so $v_1=v_2$ and

$$\ker (A-4I)=\mathrm{span}\left\{\left(\begin{array}{c}1\\ 1\end{array}\right)\right\}.$$

Therefore the eigenvalues are $0$ and $4$, with eigenvectors $t\left(\begin{array}{c}-1\\ 1\end{array}\right)$ and $t\left(\begin{array}{c}1\\ 1\end{array}\right)$ respectively, for any $t\ne 0$. Notice that $\lambda =0$ being an eigenvalue is exactly the statement that $A$ is singular, which it obviously is — its two rows are identical.

Since $0$ turning up as an eigenvalue keeps happening, it is worth boxing the general principle:

$$\boxed{\lambda =0\text{ is an eigenvalue of }A⟺\ker A\ne \{0\}⟺\det A=0⟺A\text{ is not invertible.}}$$

Example. Find the eigenvalues and eigenvectors of $A=\left(\begin{array}{cc}2& 1\\ -1& 4\end{array}\right)$.
The characteristic equation is

$$\begin{array}{rl}\left|\begin{array}{cc}2-\lambda & 1\\ -1& 4-\lambda \end{array}\right|& =(2-\lambda )(4-\lambda )+1\\ & ={\lambda }^2-6\lambda +9\\ & =(\lambda -3{)}^2=0,\end{array}$$

so there is a single eigenvalue $\lambda =3$, of multiplicity $2$. For its eigenvectors,

$$A-3I=\left(\begin{array}{cc}-1& 1\\ -1& 1\end{array}\right),$$

whose rows are identical, so the system collapses to $-v_1+v_2=0$ and

$$\ker (A-3I)=\mathrm{span}\left\{\left(\begin{array}{c}1\\ 1\end{array}\right)\right\}.$$

Therefore the only eigenvalue is $3$ and its eigenvectors are $t\left(\begin{array}{c}1\\ 1\end{array}\right)$ for $t\ne 0$. Here the eigenvalue has multiplicity $2$ as a root, but its eigenspace is only $1$-dimensional; there is nowhere near enough eigenvectors to build a basis for ${\mathbb{C}}^2$.

The two multiplicities involved here have names, and telling them apart is the single most examinable distinction in the chapter.

Basically, the algebraic multiplicity is how many times the eigenvalue was promised to you by the characteristic polynomial, and the geometric multiplicity is how many independent eigenvectors actually turned up. It is always true that

$$1\le \text{geometric multiplicity}\le \text{algebraic multiplicity},$$

and a matrix is defective exactly when the inequality on the right is strict for at least one eigenvalue. In the example above, $\lambda =3$ had algebraic multiplicity $2$ but geometric multiplicity $1$, so the matrix is defective.

A repeated eigenvalue does not automatically mean the matrix is defective. The next two examples show both outcomes, and the only way to tell is to actually compute the eigenspace.

Example. The matrix $A=\left(\begin{array}{cc}3& 0\\ 0& 3\end{array}\right)=3I$ has characteristic polynomial $(3-\lambda {)}^2$, so $\lambda =3$ with algebraic multiplicity $2$. But $A-3I$ is the zero matrix, so $\ker (A-3I)={\mathbb{C}}^2$ and

$$\ker (A-3I)=\mathrm{span}\left\{\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right)\right\}$$

is $2$-dimensional. Therefore the geometric and algebraic multiplicities agree at $2$ and the matrix is not defective — indeed every non-zero vector is an eigenvector, since $3I$ scales everything equally.

Example. Find the eigenvalues and eigenspaces of

$$A=\left(\begin{array}{ccc}2& -1& -1\\ -1& 2& -1\\ -1& -1& 2\end{array}\right),$$

and determine whether $A$ is defective.
Rather than expand a $3\times 3$ determinant, notice that $A=3I-J$ where $J$ is the $3\times 3$ matrix of all ones. Every row of $A$ sums to $0$, so

$$A\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)=0\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),$$

giving the eigenvalue ${\lambda }_1=0$ with eigenvector $(1,1,1{)}^T$ for free. For the rest, $A-3I=-J$, so

$$\ker (A-3I)=\ker J=\left\{\mathbf{v}:v_1+v_2+v_3=0\right\},$$

which is a single equation in three unknowns and hence a $2$-dimensional subspace with basis

$$\left(\begin{array}{c}1\\ -1\\ 0\end{array}\right),\left(\begin{array}{c}1\\ 0\\ -1\end{array}\right).$$

Checking one of them, $A(1,-1,0{)}^T=(2+1+0,-1-2+0,-1+1+0{)}^T=(3,-3,0{)}^T=3(1,-1,0{)}^T$, as required. So the eigenvalues are $0$ (algebraic and geometric multiplicity $1$) and $3$ (algebraic and geometric multiplicity $2$), and since we have found $1+2=3$ linearly independent eigenvectors, $A$ is not defective. Therefore $A$ has a repeated eigenvalue and is still perfectly well behaved; contrast this with the earlier $\left(\begin{array}{cc}2& 1\\ -1& 4\end{array}\right)$, where the repeated eigenvalue only produced one direction.

Example. Find all eigenvalues and eigenvectors of $A=\left(\begin{array}{cc}1& 2\\ -2& 1\end{array}\right)$.
The characteristic equation is

$$\begin{array}{rl}\left|\begin{array}{cc}1-\lambda & 2\\ -2& 1-\lambda \end{array}\right|& =(1-\lambda {)}^2+4\\ & ={\lambda }^2-2\lambda +5=0,\end{array}$$

whose roots are

$$\lambda =\frac{2\pm \sqrt{4-20}}{2}=\frac{2\pm 4i}{2}=1\pm 2i.$$

So ${\lambda }_1=1+2i$ and ${\lambda }_2=1-2i$. For ${\lambda }_1$,

$$A-(1+2i)I=\left(\begin{array}{cc}-2i& 2\\ -2& -2i\end{array}\right),$$

and row reducing (multiply row 1 by $\frac{-1}{i}=i$ to get $(2,2i)$, which is $-1$ times row 2) gives the single equation $-2i{v}_1+2v_2=0$, i.e. $v_2=i{v}_1$. Taking $v_1=-i$ gives $v_2=i(-i)=1$, so

$${\mathbf{v}}_1=\left(\begin{array}{c}-i\\ 1\end{array}\right).$$

Checking, $A{\mathbf{v}}_1=(-i+2,2i+1{)}^T$ and $(1+2i)(-i,1{)}^T=(-i-2i^2,1+2i{)}^T=(2-i,1+2i{)}^T$, which agree. Therefore the eigenvectors for $1+2i$ are $t(-i,1{)}^T$, and for $1-2i$ they are $t(i,1{)}^T$ — taking complex conjugates of both the eigenvalue and the eigenvector, which always works for a real matrix and saves you doing the second calculation.

Example. Find the eigenvalues and eigenvectors of the lower triangular matrix

$$A=\left(\begin{array}{ccc}2& 0& 0\\ 1& 3& 0\\ 0& 1& 4\end{array}\right).$$

Since $A-\lambda I$ is still lower triangular, its determinant is just the product of the diagonal entries:

$$p(\lambda )=(2-\lambda )(3-\lambda )(4-\lambda ),$$

so the eigenvalues are $2,3,4$. For any triangular matrix — upper or lower — the eigenvalues are exactly the diagonal entries, so never expand the determinant. For the eigenvectors:

For $\lambda =4$: $A-4I=\left(\begin{array}{ccc}-2& 0& 0\\ 1& -1& 0\\ 0& 1& 0\end{array}\right)$. Row 1 gives $v_1=0$, then row 2 gives $v_2=v_1=0$, and $v_3$ is free; so $\mathbf{v}=(0,0,1{)}^T$.

For $\lambda =3$: $A-3I=\left(\begin{array}{ccc}-1& 0& 0\\ 1& 0& 0\\ 0& 1& 1\end{array}\right)$. Row 1 gives $v_1=0$ and row 3 gives $v_3=-v_2$; so $\mathbf{v}=(0,1,-1{)}^T$.

For $\lambda =2$: $A-2I=\left(\begin{array}{ccc}0& 0& 0\\ 1& 1& 0\\ 0& 1& 2\end{array}\right)$. Row 2 gives $v_1=-v_2$ and row 3 gives $v_2=-2v_3$; taking $v_3=1$ gives $v_2=-2$, $v_1=2$, so $\mathbf{v}=(2,-2,1{)}^T$.

Checking the last one, $A(2,-2,1{)}^T=(4,2-6,-2+4{)}^T=(4,-4,2{)}^T=2(2,-2,1{)}^T$. Therefore the eigenvalues are $2,3,4$ with eigenvectors $(2,-2,1{)}^T$, $(0,1,-1{)}^T$ and $(0,0,1{)}^T$.

Before moving on it is worth cataloguing what can happen for a real $2\times 2$ matrix, since the characteristic polynomial is then a real quadratic and there are only three possibilities:

Notice that the middle row splits further depending on whether the matrix is defective, which the discriminant alone cannot tell you.

8.2 Eigenvectors, bases, and diagonalisation

In every example of the last section except the defective one, a $2\times 2$ matrix gave us two linearly independent eigenvectors — and two independent vectors in ${\mathbb{C}}^2$ form a basis for ${\mathbb{C}}^2$, by the results of Section 6.6. That is exactly the situation we want, so let us find out when it happens.

[X] Proof. Let the distinct eigenvalues be ${\lambda }_1,\dots ,{\lambda }_n$ with corresponding eigenvectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$, and suppose

$${\mu }_1{\mathbf{v}}_1+{\mu }_2{\mathbf{v}}_2+\cdots +{\mu }_n{\mathbf{v}}_n=0.\text{\hspace{1em}(∗)}$$

We show ${\mu }_1=0$; the same argument with the indices permuted gives ${\mu }_2=\cdots ={\mu }_n=0$, which is exactly linear independence.

Apply the matrix $(A-{\lambda }_{2}I)(A-{\lambda }_{3}I)\cdots (A-{\lambda }_{n}I)$ to both sides of $(\ast )$. For any eigenvector ${\mathbf{v}}_j$ we have $(A-{\lambda }_{i}I){\mathbf{v}}_j=({\lambda }_j-{\lambda }_i){\mathbf{v}}_j$, so the whole product acts on ${\mathbf{v}}_j$ as multiplication by $({\lambda }_j-{\lambda }_2)({\lambda }_j-{\lambda }_3)\cdots ({\lambda }_j-{\lambda }_n)$. If $j\ne 1$ then one of those brackets is $({\lambda }_j-{\lambda }_j)=0$, so every term except the first is annihilated. What survives is

$${\mu }_1({\lambda }_1-{\lambda }_2)({\lambda }_1-{\lambda }_3)\cdots ({\lambda }_1-{\lambda }_n){\mathbf{v}}_1=0.$$

The eigenvalues are distinct, so every bracket is non-zero, and ${\mathbf{v}}_1\ne 0$ because it is an eigenvector. Hence ${\mu }_1=0$. $■$

The converse of this theorem is false, and assuming otherwise is the classic error. Distinct eigenvalues are sufficient for a full set of independent eigenvectors but not necessary — the matrix $3I-J$ above had a repeated eigenvalue and still gave three independent eigenvectors. What we actually need is stated next.

[X] Proof. Let ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ be $n$ linearly independent eigenvectors and form the matrix $M$ with these as its columns,

$$M=\left(\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right).$$

Multiplying a matrix on the right by $M$ acts column by column, so

$$\begin{array}{rl}AM& =\left(\begin{array}{cccc}A{\mathbf{v}}_1& A{\mathbf{v}}_2& \cdots & A{\mathbf{v}}_n\end{array}\right)\\ & =\left(\begin{array}{cccc}{\lambda }_1{\mathbf{v}}_1& {\lambda }_2{\mathbf{v}}_2& \cdots & {\lambda }_n{\mathbf{v}}_n\end{array}\right)(\text{using }A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i)\\ & =\left(\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right)\left(\begin{array}{cccc}{\lambda }_1& & & \\ & {\lambda }_2& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right)\\ & =MD.\end{array}$$

Since the columns of $M$ are a basis for ${\mathbb{C}}^n$, the system $M\mathbf{x}=\mathbf{b}$ has a unique solution for every $\mathbf{b}$, so $M$ is invertible. Multiplying $AM=MD$ on the left by $M^{-1}$ gives $M^{-1}AM=D$.

Conversely, if $M^{-1}AM=D$ then $AM=MD$, and comparing the $j$​th columns of each side gives $A{\mathbf{v}}_j={\lambda }_j{\mathbf{v}}_j$; so each column of $M$ is an eigenvector. Finally, the columns of an invertible matrix are always linearly independent. $■$

Look carefully at the third line of that proof, because it is where the ordering rule comes from. The $j$​th column of $M$ must be an eigenvector for the $j$​th diagonal entry of $D$; if you shuffle the eigenvalues in $D$ without shuffling the columns of $M$ to match, the result is simply wrong. This is the most common way to lose marks in this chapter.

Combining the two theorems gives the practical criterion:

$$\boxed{A\text{ is diagonalisable}⟺A\text{ has }n\text{ linearly independent eigenvectors}⟺A\text{ is not defective.}}$$

In terms of the two multiplicities, $A$ is diagonalisable precisely when the geometric multiplicity equals the algebraic multiplicity for every eigenvalue, since the geometric multiplicities are exactly the number of independent eigenvectors each eigenvalue contributes and the algebraic ones always add up to $n$.

Example. Show that $A=\left(\begin{array}{cc}3& 2\\ 2& 3\end{array}\right)$ is diagonalisable and find $M$ and $D$ with $M^{-1}AM=D$.
The characteristic equation is

$$\begin{array}{rl}(3-\lambda {)}^2-4& =0\\ {\lambda }^2-6\lambda +5& =0\\ (\lambda -5)(\lambda -1)& =0,\end{array}$$

so ${\lambda }_1=5$ and ${\lambda }_2=1$. For ${\lambda }_1=5$, $A-5I=\left(\begin{array}{cc}-2& 2\\ 2& -2\end{array}\right)$ gives $v_1=v_2$, so ${\mathbf{v}}_1=(1,1{)}^T$. For ${\lambda }_2=1$, $A-I=\left(\begin{array}{cc}2& 2\\ 2& 2\end{array}\right)$ gives $v_1=-v_2$, so ${\mathbf{v}}_2=(1,-1{)}^T$. These are linearly independent — guaranteed in advance by the distinct-eigenvalues theorem, since $5\ne 1$ — so $A$ is diagonalisable with

$$D=\left(\begin{array}{cc}5& 0\\ 0& 1\end{array}\right),M=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right).$$

Checking directly, $\det M=-2$ so $M^{-1}=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$, and

$$\begin{array}{rl}{M}^{-1}AM& =\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{cc}3& 2\\ 2& 3\end{array}\right)\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\\ & =\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{cc}5& 1\\ 5& -1\end{array}\right)\\ & =\frac{1}{2}\left(\begin{array}{cc}10& 0\\ 0& 2\end{array}\right)\\ & =\left(\begin{array}{cc}5& 0\\ 0& 1\end{array}\right)=D.\end{array}$$

Therefore $A$ is diagonalisable with the $M$ and $D$ above.

The choice of $M$ and $D$ is never unique. We could have listed the eigenvalues the other way round, taking

$$D=\left(\begin{array}{cc}1& 0\\ 0& 5\end{array}\right),M=\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right),$$

and any non-zero multiple of any column of $M$ also works, since non-zero multiples of eigenvectors are eigenvectors. So there are infinitely many correct answers; what is not free is the pairing between column $j$ of $M$ and entry $j$ of $D$.

Example. Is $A=\left(\begin{array}{cc}2& 1\\ -1& 4\end{array}\right)$ diagonalisable?
We found earlier that its only eigenvalue is $3$, with a $1$-dimensional eigenspace spanned by $(1,1{)}^T$. So $A$ has only one linearly independent eigenvector, not two, and is defective. Therefore $A$ is not diagonalisable. Notice we did not need to try and fail to construct $M$; counting the dimension of the eigenspaces settles it immediately.

8.3 Applications of eigenvalues and eigenvectors

Many of the applications listed at the start of this chapter arise from studying dynamical systems — essentially any system that changes over time. An electrical network, a bridge oscillating in wind, the population of a city, an ant colony, an atomic nucleus and the Australian economy are all dynamical systems. The common thread in what follows is that a system evolving by repeated application of a matrix is hard to understand directly, but becomes trivial once you look at it in a basis of eigenvectors, where the coordinates simply evolve independently of one another.

8.3.1 Powers of $A$

A typical problem is to compute $A^k$ for large $k$. Multiplying $A$ by itself $k$ times is hopeless for large $k$; two propositions rescue us.

Proof. By induction on $k$. The result is obvious for $k=1$. Assume it holds for $k=m$. Then multiplying out,

$$D^{m+1}=D{D}^m=\left(\begin{array}{ccc}{\lambda }_1& & \\ & \ddots & \\ & & {\lambda }_n\end{array}\right)\left(\begin{array}{ccc}{\lambda }_1^m& & \\ & \ddots & \\ & & {\lambda }_n^m\end{array}\right)=\left(\begin{array}{ccc}{\lambda }_1^{m+1}& & \\ & \ddots & \\ & & {\lambda }_n^{m+1}\end{array}\right),$$

since off-diagonal entries of a product of diagonal matrices are all zero. So the result holds for $m+1$, and hence for all positive integers $k$. $■$

Proof. By induction on $k$. Multiplying the diagonalisation equation $M^{-1}AM=D$ on the left by $M$ and the right by $M^{-1}$ gives $A=MD{M}^{-1}$, which is the case $k=1$. Assuming the result for $k=m$,

$$\begin{array}{rl}{A}^{m+1}& =A{A}^m\\ & =(MD{M}^{-1})(M{D}^m{M}^{-1})\\ & =MD(M^{-1}M)D^m{M}^{-1}\\ & =MD{D}^m{M}^{-1}(\text{the inner }{M}^{-1}M\text{ collapses to }I)\\ & =M{D}^{m+1}{M}^{-1},\end{array}$$

so the result holds for $m+1$ and hence for all $k\ge 1$. $■$

Basically, the telescoping in the middle of that proof is the entire point of diagonalisation. Every adjacent pair $M^{-1}M$ cancels, so a product of $k$ copies of $A$ costs you only one $M$, one $M^{-1}$, and $k$ powers of scalars.

Example. Find $A^k$ for $A=\left(\begin{array}{cc}3& 2\\ 2& 3\end{array}\right)$.
From the previous section $A$ is diagonalisable with

$$D=\left(\begin{array}{cc}5& 0\\ 0& 1\end{array}\right),M=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),M^{-1}=\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& -\frac{1}{2}\end{array}\right).$$

Then

$$\begin{array}{rl}{A}^k& =M{D}^k{M}^{-1}\\ & =\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{cc}{5}^k& 0\\ 0& 1\end{array}\right)\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& -\frac{1}{2}\end{array}\right)\\ & =\left(\begin{array}{cc}{5}^k& 1\\ 5^k& -1\end{array}\right)\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& -\frac{1}{2}\end{array}\right)\\ & =\left(\begin{array}{cc}\frac{1}{2}(5^k+1)& \frac{1}{2}(5^k-1)\\ \frac{1}{2}(5^k-1)& \frac{1}{2}(5^k+1)\end{array}\right).\end{array}$$

As a check, substituting $k=0$ gives $I$ and substituting $k=1$ gives $\left(\begin{array}{cc}3& 2\\ 2& 3\end{array}\right)=A$; and $k=2$ gives $\left(\begin{array}{cc}13& 12\\ 12& 13\end{array}\right)$, which agrees with $A^2$ computed directly. Therefore $A^k=\frac{1}{2}\left(\begin{array}{cc}{5}^k+1& 5^k-1\\ 5^k-1& 5^k+1\end{array}\right)$. Always run the $k=0$ and $k=1$ checks; they cost one line each and catch a transposed $M$ or a swapped eigenvalue instantly.

Example. (Fibonacci.) Let $F_0=0$, $F_1=1$ and $F_{n+2}=F_{n+1}+F_n$. Show that the Fibonacci numbers can be extracted from powers of a matrix, and hence explain where the golden ratio comes from.
The recurrence says exactly that

$$\left(\begin{array}{c}{F}_{n+1}\\ F_{n+2}\end{array}\right)=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right),$$

so with $A=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)$ we get $\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)=A^n\left(\begin{array}{c}0\\ 1\end{array}\right)$. The characteristic equation of $A$ is

$$\begin{array}{rl}\left|\begin{array}{cc}-\lambda & 1\\ 1& 1-\lambda \end{array}\right|& =-\lambda (1-\lambda )-1\\ & ={\lambda }^2-\lambda -1=0,\end{array}$$

whose roots are $\phi =\frac{1+\sqrt{5}}{2}$ and $\psi =\frac{1-\sqrt{5}}{2}$. Since $\phi \ne \psi$ the matrix is diagonalisable, so $A^n=M{D}^n{M}^{-1}$ where $D$ has ${\phi }^n$ and ${\psi }^n$ on its diagonal; every entry of $A^n$ is therefore a fixed linear combination of ${\phi }^n$ and ${\psi }^n$. Carrying this through gives Binet's formula

$$F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}.$$

As a check, $A^8=\left(\begin{array}{cc}13& 21\\ 21& 34\end{array}\right)=\left(\begin{array}{cc}{F}_7& F_8\\ F_8& F_9\end{array}\right)$, as the recurrence demands. Therefore the golden ratio is not a mystical constant that happens to show up in the Fibonacci numbers; it is simply the dominant eigenvalue of the recurrence matrix, and since $|\psi |<1$ the ${\psi }^n$ term dies away and consecutive Fibonacci numbers approach a ratio of $\phi$.

[X] As an aside, diagonalisation also lets us make sense of the exponential of a matrix. Substituting $A$ into the power series

$$e^x=1+x+\frac{1}{2!}{x}^2+\frac{1}{3!}{x}^3+\cdots ,$$

replacing $1$ by $I$, and writing $A=MD{M}^{-1}$, the same telescoping as before gives

$$I+MD{M}^{-1}+\frac{1}{2!}(MD{M}^{-1}{)}^2+\cdots =M\left(I+D+\frac{1}{2!}{D}^2+\cdots \right)M^{-1},$$

and the bracket is diagonal with entries $e^{{\lambda }_i}$. So for a diagonalisable matrix,

$$\boxed{e^A=M\left(\begin{array}{ccc}{e}^{{\lambda }_1}& & \\ & \ddots & \\ & & e^{{\lambda }_n}\end{array}\right)M^{-1}.}$$

One can define $\sin A$, $\cos A$ and so on in exactly the same way. This is not a party trick; the matrix exponential is precisely what solves the systems of differential equations in the next section.

8.3.2 Solution of first-order linear differential equations

A very common problem is to solve a pair of coupled first-order linear ODEs with constant coefficients,

$$\begin{array}{rl}\frac{d{y}_1}{dt}& =a_{11}{y}_1+a_{12}{y}_2,\\ \frac{d{y}_2}{dt}& =a_{21}{y}_1+a_{22}{y}_2,\end{array}$$

with $y_1(0)$ and $y_2(0)$ given. In Ordinary Differential Equations we could only handle one equation at a time; the difficulty here is that the two are coupled, since each derivative depends on both unknowns. Writing

$$\mathbf{y}=\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right),A=\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right),$$

the system becomes the single matrix equation

$$\frac{d\mathbf{y}}{dt}=A\mathbf{y},\mathbf{y}(0)\text{ given}.$$

In this form nothing restricts us to two components, and equations of this type are important enough in dynamical systems to have a name — state-space equations, with $\mathbf{y}$ called the state vector.

This is the obvious generalisation of the scalar equation $\frac{dy}{dt}=ay$ with $y(0)=y_0$, whose solution you already know to be $y=y_0{e}^{at}$. So it is entirely plausible to guess an exponential solution of the form $\mathbf{y}=\mathbf{v}{e}^{\lambda t}$ for a constant scalar $\lambda$ and constant vector $\mathbf{v}$. Substituting the guess,

$$\begin{array}{rl}\frac{d\mathbf{y}}{dt}=\lambda \mathbf{v}{e}^{\lambda t}& =A\mathbf{v}{e}^{\lambda t}\\ e^{\lambda t}(A\mathbf{v}-\lambda \mathbf{v})& =0,\end{array}$$

and since $e^{\lambda t}\ne 0$ for all $t$, the guess works exactly when $(A-\lambda I)\mathbf{v}=0$.

Basically, the eigenvectors are the directions in which the coupled system decouples; along an eigenvector the whole vector just grows or decays exponentially at the rate given by its eigenvalue, exactly as in the one-dimensional case.

Proof. Let $\mathbf{y}(t)={\alpha }_1{\mathbf{u}}_1(t)+{\alpha }_2{\mathbf{u}}_2(t)$ for scalars ${\alpha }_1,{\alpha }_2$. Then

$$\begin{array}{rl}\frac{d}{dt}({\alpha }_1{\mathbf{u}}_1+{\alpha }_2{\mathbf{u}}_2)& ={\alpha }_1\frac{d{\mathbf{u}}_1}{dt}+{\alpha }_2\frac{d{\mathbf{u}}_2}{dt}\\ & ={\alpha }_{1}A{\mathbf{u}}_1+{\alpha }_{2}A{\mathbf{u}}_2(\text{each }{\mathbf{u}}_i\text{ solves the equation})\\ & =A({\alpha }_1{\mathbf{u}}_1+{\alpha }_2{\mathbf{u}}_2),\end{array}$$

which is what we needed. $■$

This is the same superposition principle you met for second order linear ODEs, and for the same reason — the equation is linear.

Example. Find the general solution of $\frac{d\mathbf{y}}{dt}=A\mathbf{y}$ where $A=\left(\begin{array}{cc}3& 2\\ 2& 3\end{array}\right)$, and then the particular solution with $\mathbf{y}(0)=\left(\begin{array}{c}1\\ -2\end{array}\right)$.
We already know the eigenvalues and eigenvectors of this matrix:

$${\lambda }_1=5,{\mathbf{v}}_1=\left(\begin{array}{c}1\\ 1\end{array}\right),{\lambda }_2=1,{\mathbf{v}}_2=\left(\begin{array}{c}1\\ -1\end{array}\right).$$

So two solutions are ${\mathbf{u}}_1(t)=e^{5t}\left(\begin{array}{c}1\\ 1\end{array}\right)$ and ${\mathbf{u}}_2(t)=e^t\left(\begin{array}{c}1\\ -1\end{array}\right)$, and by superposition the general solution is

$$\mathbf{y}(t)={\alpha }_1{e}^{5t}\left(\begin{array}{c}1\\ 1\end{array}\right)+{\alpha }_2{e}^t\left(\begin{array}{c}1\\ -1\end{array}\right).$$

(That this is the general solution — that every solution has this form — is true but not proved here.) Substituting $t=0$ and matching the initial condition,

$$\begin{array}{rl}{\alpha }_1\left(\begin{array}{c}1\\ 1\end{array}\right)+{\alpha }_2\left(\begin{array}{c}1\\ -1\end{array}\right)& =\left(\begin{array}{c}1\\ -2\end{array}\right),\\ {\alpha }_1+{\alpha }_2& =1,\\ {\alpha }_1-{\alpha }_2& =-2.\end{array}$$

Adding gives $2{\alpha }_1=-1$, so ${\alpha }_1=-\frac{1}{2}$ and ${\alpha }_2=\frac{3}{2}$. Therefore

$$\mathbf{y}(t)=-\frac{1}{2}{e}^{5t}\left(\begin{array}{c}1\\ 1\end{array}\right)+\frac{3}{2}{e}^t\left(\begin{array}{c}1\\ -1\end{array}\right).$$

Checking at $t=0$: $-\frac{1}{2}(1,1{)}^T+\frac{3}{2}(1,-1{)}^T=(1,-2{)}^T$, as required.

One reason for caring about first-order systems is that every linear differential equation can be turned into one, by introducing the derivatives as new variables.

Example. Convert $\frac{d^{2}y}{d{t}^2}+4\frac{dy}{dt}-5y=0$ into a system of first-order equations, and solve it both ways.
Define $y_1=y$ and $y_2=\frac{d{y}_1}{dt}=\frac{dy}{dt}$. Differentiating $y_2$ and using the original equation,

$$\frac{d{y}_2}{dt}=\frac{d^{2}y}{d{t}^2}=5y-4\frac{dy}{dt}=5y_1-4y_2,$$

so the second-order equation is equivalent to

$$\begin{array}{rl}\frac{d{y}_1}{dt}& =y_2,\\ \frac{d{y}_2}{dt}& =5y_1-4y_2,\end{array}\text{that is}\frac{d\mathbf{y}}{dt}=A\mathbf{y},A=\left(\begin{array}{cc}0& 1\\ 5& -4\end{array}\right).$$

Matrix method. The characteristic equation is

$$\begin{array}{rl}\left|\begin{array}{cc}-\lambda & 1\\ 5& -4-\lambda \end{array}\right|& =-\lambda (-4-\lambda )-5\\ & ={\lambda }^2+4\lambda -5=0,\end{array}$$