2.8 Eigenvalues and eigenvectors

Some directions are only stretched by a linear map, never turned. Finding them (the eigenvectors) turns a hard-looking map into a list of stretch factors, and turns "apply it 100 times" into powers of ordinary numbers.

In 2.5 a matrix moved the whole plane: most directions got turned and stretched at the same time, which is hard to read. But a few directions are special. The map sends them along their own line and only stretches, shrinks or flips them. Those directions are the eigenvectors (“eigen” is German for “own”). This chapter finds them, shows when they are enough to rebuild the whole map, and uses them to compute $A^{100}$ in one line.

Before you start

You need four earlier ideas: the null space of a linear map, linear independence, the matrix of a map with change of basis and similar matrices (2.5), and the determinant (2.7). Three quick checks:

Quick checkA linear map

T

sends a non-zero vector

x

O

. Which statement is true?

Quick checkAre

(1, 2)

and

(3, 6)

linearly independent in

\mathbb R^2

Quick checkA square matrix has determinant

0

. Which statement is true?

The picture

This is the map with matrix $A = \begin{bmatrix}3 & 1\\ 0 & 2\end{bmatrix}$ . Its first column $(3, 0)$ is where $\hat\imath$ lands and its second column $(1, 2)$ is where $\hat\jmath$ lands. Press “Apply the map”. The two dashed orange lines are the special directions. Every point on the horizontal line moves along that line to three times its distance from the origin. Every point on the other line, the one through $(1, -1)$ , moves along that line to twice its distance. A point anywhere else leaves the line it started on.

Try the presets. “Stretch” has two dashed lines (the axes). “Shear” has exactly one. “Rotate 90°” has none, because a quarter turn sends every direction to a different direction. Those three behaviours (two special lines, one, none) are the whole story of this chapter. Counting the special lines is how we decide whether a map can be understood by stretching alone.

Where this came from· From spinning bodies to the word 'eigen'

Eigenvectors first appeared in mechanics, before matrix theory existed. By the 1760s Euler had shown that every rigid body has three perpendicular axes (its principal axes) about which it can spin steadily. Lagrange later recognised those axes as the eigenvectors of the body’s inertia matrix. He and Laplace met the same kind of equation for the small vibrations of coupled systems and for the slow drifts of the planets’ orbits. Changes that build up over centuries are called “secular”, so the equation was long known as the secular equation. In 1829 Cauchy proved that for a symmetric array of numbers all the roots of that equation are real, and he introduced the name “characteristic root”, which survives in “characteristic equation”. The word “eigen” came last: in 1904 Hilbert became the first to use the German “eigen” (own) for the special values in his work on integral equations.

The idea, in words

Let $T$ be a linear map from a space to itself. We ask for vectors $x$ that $T$ does not turn: $T(x)$ lies on the same line as $x$ , so $T(x) = \lambda x$ for some number $\lambda$ . If we find $n$ independent such vectors in an $n$ -dimensional space, they form a basis. In that basis every vector is a combination of directions that $T$ merely stretches, so the matrix of $T$ is diagonal. The hard map has become a list of $n$ stretch factors.

Why· Why this is worth the trouble

Applying the same map again and again is what recurrences, population models, Markov chains and differential equations all do. If $T(x) = 3x$ then $T(T(x)) = 9x$ and $T^{100}(x) = 3^{100}x$ . No matrix is multiplied 100 times. So if a basis of such vectors exists, every vector is a sum of pieces, and each piece is multiplied by a power of its own number. Spagnolie opens Lecture 16 with exactly this: “A x = b” and “A x = λ x” are the two most important equations of linear algebra, and the second one controls repeated application.

Definitions and theorems

Eigenvectors and eigenvalues

Definition T

Eigenvector

Let $T: V \to V$ be a linear map from a vector space to itself. (The input and output space must be the same, otherwise “stays on its own line” has no meaning.) A scalar is an ordinary number, real unless we say complex. A vector $x$ in $V$ is an eigenvector of $T$ if

x \ne O \quad\text{and}\quad T(x) = \lambda x \quad\text{for some scalar } \lambda.

For a square matrix $A$ this reads $Ax = \lambda x$ .

In one lineA non-zero vector $x$ that a map $T$ from a space to itself only stretches: $T(x) = \lambda x$ for some scalar $\lambda$ .

Why it existsIt is a direction on which the map is as plain as it can be: multiplication by a number.

Definition T

Eigenvalue

A scalar $\lambda$ is an eigenvalue of $T$ if there is an eigenvector $x$ with $T(x) = \lambda x$ . We say $x$ belongs to $\lambda$ . A negative $\lambda$ flips the direction. $\lambda = 0$ means the vector is sent to $O$ . $\lambda = 1$ means the vector does not move.

In one lineThe scalar $\lambda$ in $T(x) = \lambda x$ : the stretch factor along an eigenvector.

Why it existsThe eigenvalues are the numbers that describe the map once the directions are chosen well.

The condition $x \ne O$ is not a technicality. Since $T(O) = O = \lambda O$ for every $\lambda$ , the zero vector would satisfy the equation for all $\lambda$ and every number would be an “eigenvalue”. Excluding $O$ is what makes the question meaningful. The eigenvalue itself may be $0$ , and that happens exactly when the map destroys something: $T(x) = 0x = O$ for a non-zero $x$ means $x$ is a non-zero vector in the null space.

Worked example Spagnolie Lecture 16, new numbers

Is (1, -1) an eigenvector of the matrix with rows (3, 1) and (0, 2)? Is (1, 1)?

Solution.

Apply the matrix to the vector. $A\begin{bmatrix}1\\-1\end{bmatrix} = \begin{bmatrix}3\cdot 1 + 1\cdot(-1)\\ 0\cdot 1 + 2\cdot(-1)\end{bmatrix} = \begin{bmatrix}2\\-2\end{bmatrix}$ . An eigenvector test is: apply the map and see whether the output lies on the input’s line.
Compare output with input. $(2, -2) = 2\,(1, -1)$ . This is $Ax = \lambda x$ with $\lambda = 2$ , and $(1,-1) \ne O$ , so both conditions of the definition hold.
Repeat for $(1, 1)$ . $A\begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix}4\\2\end{bmatrix}$ . If this were $c\,(1, 1)$ , the first coordinate would force $c = 4$ and the second $c = 2$ . One single number $c$ must work for every coordinate at once.

Answer. $(1, -1)$ is an eigenvector with eigenvalue $2$ . $(1, 1)$ is not an eigenvector.

Three more examples, each checked by multiplying.

The swap matrix $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ (Spagnolie’s Lecture 16) sends $(x, y)$ to $(y, x)$ , a mirror in the line $y = x$ . Then $(1, 1)$ is fixed, so $\lambda = 1$ , and $(-1, 1) \mapsto (1, -1) = -1\cdot(-1, 1)$ , so $\lambda = -1$ .
Differentiation $D(f) = f'$ on the infinitely differentiable functions (so that $f'$ is again in the space): $D(e^{\lambda t}) = \lambda e^{\lambda t}$ . So every real number $\lambda$ is an eigenvalue, and $e^{\lambda t}$ is an eigenfunction (an eigenvector that is a function).
The identity map: $I(x) = 1\cdot x$ , so every non-zero vector is an eigenvector with eigenvalue $1$ .

Quick checkWhich is true of the zero vector

O

and the number

0

in the definition of an eigenvector?

Fact T Spagnolie Lecture 16

An eigenvector has only one eigenvalue

If $x \ne O$ , $T(x) = \lambda x$ and $T(x) = \mu x$ , then $\lambda = \mu$ .

In one lineIf $T(x) = \lambda x$ and $T(x) = \mu x$ with $x \ne O$ , then $\lambda = \mu$ .

Why it is trueSubtract the two equations. What is left is a scalar times a non-zero vector equal to $O$ .

ProofSpagnolie Lecture 16

The idea: Both equations give the same T(x). Set them equal, move everything to one side, and use that a non-zero vector times a scalar is zero only for the scalar zero.

\lambda x = \mu x

Both right-hand sides equal

T(x)

(\lambda - \mu)x = O

Axiom 9 of 2.1 (distributivity over scalars) gives

\lambda x - \mu x = (\lambda - \mu)x

\lambda - \mu = 0

\lambda - \mu \ne 0

, multiply by

1/(\lambda - \mu)

to get

x = O

, which was excluded.

The reverse statement is false: an eigenvalue does not have only one eigenvector. One eigenvalue has many eigenvectors: if $x$ belongs to $\lambda$ then so does $2x$ , since $T(2x) = 2T(x) = 2\lambda x = \lambda(2x)$ . The next definition collects all of them.

Definition T

Eigenspace

For an eigenvalue $\lambda$ of $T$ , the eigenspace is

E(\lambda) = \{x \in V : T(x) = \lambda x\} = N(T - \lambda I).

(Here $N(\cdot)$ is the null space from 2.3, and $T - \lambda I$ is the map $x \mapsto T(x) - \lambda x$ .) The zero vector is put in by hand, because it is not an eigenvector but must be in any subspace.

In one lineAll vectors $x$ with $T(x) = \lambda x$ , together with $O$ : the eigenvectors of $\lambda$ plus the zero vector. It equals the null space of $T - \lambda I$ .

Why it existsIt turns 'the eigenvectors of $\lambda$ ' into a subspace, so dimension and bases make sense for it.

Theorem T Spagnolie Lecture 16

Eigenspaces are subspaces

For every scalar $\lambda$ , $E(\lambda)$ is a subspace of $V$ . Its dimension is at least $1$ exactly when $\lambda$ is an eigenvalue.

In one line $E(\lambda)$ is a subspace, because it is the null space of the linear map $T - \lambda I$ .

Why it is trueBeing a null space is the whole proof. The work is checking that $T - \lambda I$ is linear.

In the picture above, $E(3)$ is the whole horizontal dashed line and $E(2)$ is the other dashed line. Each is a line through the origin, which is what a one-dimensional subspace of the plane looks like. The proof says this is no accident.

ProofSpagnolie Lecture 16; Apostol 4.2

The idea: Show that T − λI is a linear map and that its null space is E(λ). Then the null space theorem from 2.3 finishes.

S = T - \lambda I

, that is

S(x) = T(x) - \lambda x

, is linear. Check:

S(x + y) = T(x) + T(y) - \lambda x - \lambda y = S(x) + S(y)

and

S(cx) = cT(x) - \lambda c x = cS(x)

Linearity of

T

, and

c(\lambda x) = \lambda(cx)

from the vector-space axioms.

S(x) = O

exactly when

T(x) = \lambda x

. So

N(S) = E(\lambda)

Add

\lambda x

to both sides of

T(x) - \lambda x = O

, and back.In the picture: the dashed line for 3 is exactly the set of points the map

A - 3I

sends to the origin.

E(\lambda)

is a subspace.

The null space of a linear map is a subspace (2.3).

\dim E(\lambda) \ge 1

exactly when

\lambda

is an eigenvalue.

\lambda

is an eigenvalue exactly when some non-zero

x

has

T(x) = \lambda x

, that is, when

N(S)

contains a non-zero vector.

For the eigenvalue $0$ the eigenspace is the null space of $T$ itself. For the identity map on $\mathbb R^n$ , $E(1) = \mathbb R^n$ .

Quick checkTake the set of all eigenvectors that belong to one eigenvalue

\lambda

, without adding

O

. Is it a subspace?

Eigenvectors for different eigenvalues are independent

Two eigenvectors on different lines are certainly independent. The theorem says the same holds for any number of them, as long as their eigenvalues are all different. It is the reason eigenvectors can form a basis at all.

Theorem T Apostol Thm 4.2; Spagnolie Lecture 16

Eigenvectors of distinct eigenvalues are independent

Let $u_1, \dots, u_k$ be eigenvectors of a linear map $T$ with eigenvalues $\lambda_1, \dots, \lambda_k$ , where $\lambda_i \ne \lambda_j$ whenever $i \ne j$ . Then $u_1, \dots, u_k$ are linearly independent.

In one lineEigenvectors that belong to different eigenvalues are linearly independent.

Why it is trueApply $T$ to a supposed dependence and subtract $\lambda_k$ times the original. The last vector disappears, and induction handles the rest.

Why· The picture behind the proof

For $k = 2$ look at the two dashed lines in the picture. If $u_1$ and $u_2$ were dependent they would lie on one line, and a vector on that single line would be stretched by $3$ and by $2$ at the same time. We showed an eigenvector has only one eigenvalue, so that is impossible. The written proof below does the same job for any number of vectors. Its trick (apply $T$ , then subtract $\lambda_k$ times the original) is a way to separate the pieces by how much each is stretched.

The theorem needs eigenvectors to be non-zero: the set $\{O\}$ is dependent. The proof is Spagnolie’s induction, and it echoes the elimination from the $k + 1$ theorem of 2.2: use one equation to cancel one unknown and reduce to a smaller case.

ProofSpagnolie Lecture 16; Apostol 4.3

The idea: Induction on k. Suppose a combination of the k eigenvectors is zero. Apply T to it, and also multiply it by λ_k, then subtract: the u_k terms cancel, leaving a zero-combination of the first k−1 eigenvectors. Those are independent by the induction hypothesis, which forces the first k−1 coefficients to be zero, and then the last one is zero too.

For

k = 1

\{u_1\}

is independent.

Base case

k = 1

u_1 \ne O

because it is an eigenvector. If

c_1u_1 = O

with

c_1 \ne 0

, multiplying by

1/c_1

would give

u_1 = O

Assume the theorem holds for

k - 1

vectors. Suppose

c_1u_1 + \dots + c_ku_k = O

. Call this equation (E).

The induction hypothesis is the theorem for

k - 1

eigenvectors with distinct eigenvalues. We prove it for

k

Apply

T

to (E):

c_1\lambda_1u_1 + \dots + c_k\lambda_ku_k = O

Linearity passes

T

through the combination.

T(u_i) = \lambda_i u_i

, and

T(O) = O

(2.3).

Multiply (E) by

\lambda_k

c_1\lambda_ku_1 + \dots + c_k\lambda_ku_k = O

Scaling the zero vector gives the zero vector. We choose to multiply by

\lambda_k

because it makes the last coefficient match the line above.

c_1(\lambda_1 - \lambda_k)u_1 + \dots + c_{k-1}(\lambda_{k-1} - \lambda_k)u_{k-1} = O

Subtract the second line from the first, vector by vector. The

u_k

terms are

c_k\lambda_ku_k - c_k\lambda_ku_k = O

, which is why we multiplied by

\lambda_k

c_i(\lambda_i - \lambda_k) = 0

for every

i < k

This is a zero-combination of

u_1, \dots, u_{k-1}

, which are independent by the induction hypothesis. So each coefficient is

0

c_1 = \dots = c_{k-1} = 0

The eigenvalues are distinct, so

\lambda_i - \lambda_k \ne 0

. Divide by it.

c_ku_k = O

, so

c_k = 0

. All coefficients are zero, so

u_1, \dots, u_k

are independent.

Put these into (E). Only the last term remains, and

u_k \ne O

forces

c_k = 0

as in the base case.

Proof workshopRebuild the proof that eigenvectors of distinct eigenvalues are independent

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Quick checkIn the proof above, where is it used that the eigenvalues are different from each other?

Theorem T Apostol Thms 4.3 and 4.10; Spagnolie Lecture 16

Distinct eigenvalues give an eigenbasis

Let $\dim V = n$ and let $T: V \to V$ be linear. Then $T$ has at most $n$ distinct eigenvalues. If it has exactly $n$ , then one eigenvector for each of them gives a basis of $V$ .

In one lineOn an $n$ -dimensional space a linear map has at most $n$ distinct eigenvalues, and if it has $n$ , their eigenvectors are a basis.

Why it is trueIndependent vectors cannot outnumber the dimension, and $n$ independent vectors in an $n$ -dimensional space are a basis.

ProofApostol 4.2

The idea: Pick one eigenvector per eigenvalue. They are independent by the last theorem. The dimension count from 2.2 does the rest.

T

had

m

distinct eigenvalues, there would be

m

independent vectors in

V

Choose one eigenvector for each distinct eigenvalue. They are independent by the previous theorem.

m \le n

The

k + 1

theorem of 2.2: more than

n

vectors in an

n

-dimensional space are dependent.

m = n

, the

n

chosen eigenvectors are a basis.

2.2:

n

independent vectors in an

n

-dimensional space form a basis.

Finding eigenvalues: the characteristic polynomial

So far we had to guess the eigenvalues. Here is a method. From now on $A$ is an $n$ by $n$ matrix and $T(x) = Ax$ . The equation $Ax = \lambda x$ is the same as $\lambda x - Ax = O$ , and since $\lambda x = (\lambda I)x$ it is the same as

(\lambda I - A)x = O.

We want a non-zero solution $x$ , which means the null space of $\lambda I - A$ must contain more than $O$ . Spagnolie’s shortcut: that happens exactly when $\lambda I - A$ is not invertible, and a matrix is not invertible exactly when its determinant is $0$ .

Definition T

Characteristic polynomial

For an $n$ by $n$ matrix $A$ , the characteristic polynomial is $p_A(\lambda) = \det(\lambda I - A)$ , regarded as a function of the number $\lambda$ (the shape theorem below shows it is a polynomial of degree $n$ ). The equation $p_A(\lambda) = 0$ is the characteristic equation. (Apostol and Spagnolie use $\det(\lambda I - A)$ . Many other books use $\det(A - \lambda I)$ . The two differ by the factor $(-1)^n$ and have the same roots.)

In one lineThe polynomial $p_A(\lambda) = \det(\lambda I - A)$ . Its roots are exactly the eigenvalues of $A$ .

Why it existsIt converts the search for the right $\lambda$ into solving one polynomial equation, with no vectors involved.

For $n = 2$ , $A = \begin{bmatrix}a&b\\c&d\end{bmatrix}$ :

\det\begin{bmatrix}\lambda - a & -b\\ -c & \lambda - d\end{bmatrix} = (\lambda - a)(\lambda - d) - bc = \lambda^2 - (a + d)\lambda + (ad - bc).

For the matrix in the picture: $\lambda^2 - 5\lambda + 6 = (\lambda - 3)(\lambda - 2)$ . The roots $3$ and $2$ are the stretch factors we saw.

Theorem T Apostol Thm 4.5; Spagnolie Lecture 16

Eigenvalues are roots of the characteristic polynomial

A number $\lambda$ is an eigenvalue of the square matrix $A$ if and only if $\det(\lambda I - A) = 0$ .

In one line $\lambda$ is an eigenvalue of $A$ exactly when $\det(\lambda I - A) = 0$ .

Why it is trueAn eigenvector is a non-zero vector in the null space of $\lambda I - A$ , and such a vector exists exactly when that matrix is not invertible.

ProofSpagnolie Lecture 16; Apostol 4.5

The idea: Each statement is equivalent to the next: eigenvalue, non-zero null vector, not one-to-one, not invertible, determinant zero.

\lambda

is an eigenvalue

\iff

there is

x \ne O

with

Ax = \lambda x

The definition of eigenvalue.

\iff

there is

x \ne O

with

(\lambda I - A)x = O

Move

\lambda x = (\lambda I)x

to the left. Matrix multiplication distributes (2.5).

\iff N(\lambda I - A) \ne \{O\}

That is what it means for the null space to contain a non-zero vector.In the picture:

\lambda I - A

squashes the plane onto a line exactly when

\lambda

is 3 or 2, and the squashed-away line is the dashed eigenline.

\iff

\lambda I - A

is not invertible.

A linear map is one-to-one exactly when its null space is

\{O\}

, and a one-to-one linear map from

\mathbb R^n

\mathbb R^n

is also onto, by rank–nullity (2.3). One-to-one and onto together mean invertible.

\iff \det(\lambda I - A) = 0

A square matrix is invertible exactly when its determinant is not zero (2.7).

Worked example Spagnolie Lecture 16

Find the eigenvalues and eigenvectors of the matrix with rows (3, 4, 2), (0, 1, 2), (0, 0, 0).

Solution.

Write $\lambda I - A$ . $\lambda I - A = \begin{bmatrix}\lambda-3 & -4 & -2\\ 0 & \lambda-1 & -2\\ 0 & 0 & \lambda\end{bmatrix}$ . The eigenvalues are the roots of $\det(\lambda I - A)$ .
Take the determinant. The matrix is upper triangular, so the determinant is the product of the diagonal entries: $p_A(\lambda) = (\lambda - 3)(\lambda - 1)\lambda$ . Expanding along the first column leaves one term, and the same happens for the smaller matrix that remains, again and again.
Read off the eigenvalues. $\lambda = 3, 1, 0$ . They are the roots. A check we prove below: the eigenvalues add up to the sum of the diagonal entries of $A$ ( $3 + 1 + 0 = 4$ ) and multiply to $\det A = 0$ (the matrix has a zero row).
Eigenvector for $\lambda = 3$ . Solve $(3I - A)x = O$ , rows $(0,-4,-2)$ , $(0,2,-2)$ , $(0,0,3)$ . The last row gives $z = 0$ , then the middle row gives $y = 0$ . The first coordinate is free: take $x = (1, 0, 0)$ . A free variable means a whole line of solutions, so we pick one non-zero member.
Eigenvector for $\lambda = 1$ . Solve $(I - A)x = O$ , rows $(-2,-4,-2)$ , $(0,0,-2)$ , $(0,0,1)$ . So $z = 0$ and $-2x - 4y = 0$ , which gives $x = -2y$ . Take $y = 1$ : $(-2, 1, 0)$ . Same method, a different matrix for each eigenvalue.
Eigenvector for $\lambda = 0$ . Solve $-Ax = O$ , rows $(-3,-4,-2)$ , $(0,-1,-2)$ , $(0,0,0)$ . The middle row gives $y = -2z$ , and then $-3x + 8z - 2z = 0$ gives $x = 2z$ . Take $z = 1$ : $(2, -2, 1)$ . The eigenvalue $0$ gets no special treatment, but its eigenspace is the null space of $A$ .
Check each. $A(1,0,0) = (3,0,0)$ . $A(-2,1,0) = (-6+4, 1, 0) = (-2,1,0)$ . $A(2,-2,1) = (6-8+2, -2+2, 0) = (0,0,0)$ . Multiplying back is the only reliable check, because a sign slip in elimination is easy to make.

Answer. Eigenvalues $3, 1, 0$ with eigenvectors $(1,0,0)$ , $(-2,1,0)$ , $(2,-2,1)$ . The eigenvalues are distinct, so these three vectors are a basis of $\mathbb R^3$ .

Trace, and the shape of the characteristic polynomial

Definition T

Trace

The trace of an $n$ by $n$ matrix $A$ is $\operatorname{tr} A = a_{11} + a_{22} + \dots + a_{nn}$ .

In one lineThe sum of the diagonal entries of a square matrix, $\operatorname{tr} A = a_{11} + a_{22} + \dots + a_{nn}$ .

Why it existsIt is a quick number that, as the next theorems show, equals the sum of the eigenvalues and does not change when the basis changes.

The trace of $\begin{bmatrix}3&1\\0&2\end{bmatrix}$ is $5$ , which is $3 + 2$ . The determinant is $6 = 3 \times 2$ . This is no accident, and the proof also tells us what the characteristic polynomial looks like in general. For $n = 2$ we computed it: $\lambda^2 - (\operatorname{tr} A)\lambda + \det A$ . Spagnolie’s Lecture 17 does the general case.

Theorem T Apostol Thm 4.4 and section 4.7; Spagnolie Lecture 17

Shape of the characteristic polynomial

For an $n$ by $n$ matrix $A$ , the characteristic polynomial has degree $n$ , and

p_A(\lambda) = \lambda^n - (\operatorname{tr} A)\,\lambda^{n-1} + (\text{terms of degree at most } n - 2).

Its constant term is $p_A(0) = (-1)^n\det A$ .

In one line $\det(\lambda I - A) = \lambda^n - (\operatorname{tr} A)\lambda^{n-1} + \dots + (-1)^n\det A$ .

Why it is trueEach time we expand the determinant, only the diagonal can contribute high powers of $\lambda$ .

ProofSpagnolie Lecture 17; Apostol 4.4

The idea: Induction on n. Expand the determinant along the first row. The (1,1) term is (λ − a₁₁) times the same kind of determinant for a smaller matrix, which supplies the top two coefficients. Every other term loses two λ's from the diagonal, so its degree drops by at least two.

Claim:

\det(\lambda I - A) = \lambda^n - (a_{11} + \dots + a_{nn})\lambda^{n-1} + (\text{degree} \le n-2)

. For

n = 1

this is

\lambda - a_{11}

The first claim, proved for all

n

by induction. The determinant is

\lambda - a_{11}

when

n = 1

, which has the claimed form:

\lambda^1 - (\operatorname{tr}A)\lambda^0

Assume the claim for size

n - 1

. Expanding along row 1:

\det(\lambda I - A) = (\lambda - a_{11})\det M_{11} + \sum_{j \ge 2}\pm(-a_{1j})\det M_{1j}

Cofactor expansion along row 1 (2.7).

M_{1j}

\lambda I - A

with row 1 and column

j

deleted. The entry in position

(1, j)

\lambda I - A

-a_{1j}

when

j \ge 2

\det M_{11} = \lambda^{n-1} - (a_{22} + \dots + a_{nn})\lambda^{n-2} + (\text{degree} \le n - 3)

M_{11} = \lambda I_{n-1} - A'

, where

A'

A

with row 1 and column 1 deleted. This is the same kind of matrix one size smaller, so the induction hypothesis applies to it.

(\lambda - a_{11})\det M_{11} = \lambda^n - (a_{11} + a_{22} + \dots + a_{nn})\lambda^{n-1} + (\text{degree} \le n - 2)

Multiply

(\lambda - a_{11})

by the line above.

\lambda

times

\lambda^{n-1}

gives

\lambda^n

\lambda

times the

\lambda^{n-2}

term and

-a_{11}

times the

\lambda^{n-1}

term both give

\lambda^{n-1}

terms. Everything else has degree at most

n - 2

. (For

n = 2

the part of degree at most

n - 3

0

M_{1j}

, only

n - 2

entries contain

\lambda

(each to the first power).

The matrix

M_{1j}

for

j \ge 2

has had row 1 and column

j

removed. The only entries containing

\lambda

are the diagonal entries

\lambda - a_{ii}

of the original matrix. The ones at positions

(1,1)

and

(j,j)

are gone, so at most

n - 2

entries of

M_{1j}

contain

\lambda

\det M_{1j}

has degree at most

n - 2

, and so does

\mp a_{1j}\det M_{1j}

The determinant is a sum of products of

n - 1

entries, one from each row and column (2.7). A product contains at most

n - 2

of the

\lambda

-entries.

The claim holds for size

n

Add the first term and the others. The extra terms do not touch degrees

n

and

n - 1

p_A(0) = \det(-A) = (-1)^n\det A

Put

\lambda = 0

\det(\lambda I - A)

to get

\det(-A)

. Multiplying one row by

-1

multiplies the determinant by

-1

, and

-A

has all

n

rows multiplied by

-1

Over the real numbers a polynomial may have no roots (for example $\lambda^2 + 1$ ). Over the complex numbers it always has: this is the fundamental theorem of algebra, which we quote without proof (it belongs to complex analysis). It says that a polynomial of degree $n$ with leading coefficient $1$ factors as $(\lambda - \lambda_1)(\lambda - \lambda_2)\cdots(\lambda - \lambda_n)$ , where the $\lambda_i$ are complex numbers, listed with repeats. We call the $\lambda_i$ the eigenvalues of $A$ counted with multiplicity.

Theorem T Spagnolie Lecture 17

Trace and determinant from the eigenvalues

Let $\lambda_1, \dots, \lambda_n$ be the eigenvalues of $A$ (complex numbers, counted with multiplicity). Then

\operatorname{tr}A = \lambda_1 + \dots + \lambda_n, \qquad \det A = \lambda_1\lambda_2\cdots\lambda_n.

In one lineThe trace is the sum of the eigenvalues and the determinant is their product, each counted with multiplicity.

Why it is trueMultiply out $(\lambda - \lambda_1)\cdots(\lambda - \lambda_n)$ and compare it with the shape theorem. The coefficient of $\lambda^{n-1}$ and the constant term are the two matching places.

ProofSpagnolie Lecture 17

The idea: The characteristic polynomial has two descriptions: one from the matrix entries, one as a product of (λ − λᵢ). Two polynomials that are equal as functions have equal coefficients, so compare the λⁿ⁻¹ coefficients and the constant terms.

p_A(\lambda) = (\lambda - \lambda_1)\cdots(\lambda - \lambda_n)

The fundamental theorem of algebra, quoted above.

Multiplying out:

p_A(\lambda) = \lambda^n - (\lambda_1 + \dots + \lambda_n)\lambda^{n-1} + \dots + (-1)^n\lambda_1\cdots\lambda_n

Choosing

-\lambda_i

from

n - 1

of the factors and

\lambda

from the last one gives a

\lambda^{n-1}

term, in

n

ways. Choosing

-\lambda_i

from all factors gives the constant term.

Compare

\lambda^{n-1}

\operatorname{tr}A = \lambda_1 + \dots + \lambda_n

The shape theorem gives

-\operatorname{tr}A

as the coefficient of

\lambda^{n-1}

Compare constants:

(-1)^n\det A = (-1)^n\lambda_1\cdots\lambda_n

, so

\det A = \lambda_1\cdots\lambda_n

The shape theorem gives

(-1)^n\det A

as the constant term.

Spagnolie’s $3 \times 3$ example: $3 + 1 + 0 = 4 = \operatorname{tr}A$ , and $3 \cdot 1 \cdot 0 = 0 = \det A$ . The characteristic polynomial is $\lambda^3 - 4\lambda^2 + 3\lambda - 0$ . Spagnolie left the middle coefficient as a blank box in class. It is $3$ , because the roots $3, 1, 0$ give $(\lambda - 3)(\lambda - 1)\lambda = \lambda^3 - 4\lambda^2 + 3\lambda$ . A useful consequence: a matrix is invertible if and only if $0$ is not an eigenvalue, because $\det A = \lambda_1\cdots\lambda_n$ is non-zero exactly when no $\lambda_i$ is $0$ .

Worked example

A 2 by 2 matrix has trace 6 and determinant 8. What are its eigenvalues?

Solution.

Write the characteristic polynomial from trace and determinant. For $n = 2$ the shape theorem says $p_A(\lambda) = \lambda^2 - (\operatorname{tr}A)\lambda + \det A = \lambda^2 - 6\lambda + 8$ . We do not know the entries of the matrix, but the polynomial only needs these two numbers.
Solve $p_A(\lambda) = 0$ . $\lambda^2 - 6\lambda + 8 = (\lambda - 2)(\lambda - 4)$ , so $\lambda = 2$ or $4$ . Two numbers that add to the trace $6$ and multiply to the determinant $8$ are exactly the eigenvalues, by the trace and determinant theorem.

Answer. The eigenvalues are $2$ and $4$ . (Many different matrices have these, for example $\operatorname{diag}(2, 4)$ and $\begin{bmatrix}3&1\\1&3\end{bmatrix}$ , so the eigenvalues do not determine the matrix.)

Your answerA

2\times2

matrix has trace

7

and determinant

10

. What is its larger eigenvalue?

Same idea elsewhere· JEE: the characteristic equation you already know

In JEE you met the rule that a $2 \times 2$ matrix satisfies $A^2 - (\operatorname{tr}A)A + (\det A)I = O$ (the Cayley–Hamilton theorem). That is the characteristic polynomial $\lambda^2 - (\operatorname{tr}A)\lambda + \det A$ with the matrix $A$ put in place of the number $\lambda$ . You will prove it in the problems below for matrices that have a basis of eigenvectors (called diagonalizable, defined shortly). The reason it holds: on each eigenvector $A$ acts as the number $\lambda_i$ , and $p(\lambda_i) = 0$ .

Same map, different basis

The matrix of a map depends on the basis (2.5). If $A$ and $B$ are matrices of the same map in two bases, then $B = C^{-1}AC$ for the change-of-basis matrix $C$ ; this is what it means for $A$ and $B$ to be similar matrices. The eigenvalues belong to the map, so they must not depend on the basis. This is Apostol’s Theorem 4.9.

Theorem T Apostol Thm 4.9; Spagnolie Lecture 17

If $A$ and $B$ are $n$ by $n$ and $B = C^{-1}AC$ for some invertible $C$ , then $p_B(\lambda) = p_A(\lambda)$ .

In one lineIf $B = C^{-1}AC$ then $B$ and $A$ have the same characteristic polynomial, hence the same eigenvalues, trace and determinant.

Why it is trueFactor $C^{-1}$ and $C$ out of $\lambda I - B$ . The determinants of $C^{-1}$ and $C$ multiply to $1$ .

ProofSpagnolie Lecture 17 ('Behold!')

The idea: Rewrite λI as C⁻¹(λI)C so that C⁻¹ and C can be pulled out of the whole expression. Then the determinant of a product is a product of determinants, and det C⁻¹ · det C = 1.

\lambda I - B = C^{-1}(\lambda I)C - C^{-1}AC

C^{-1}(\lambda I)C = \lambda C^{-1}C = \lambda I

. The scalar

\lambda

slides past matrices.

= C^{-1}(\lambda I - A)C

Distributivity of matrix multiplication (2.5).

\det(\lambda I - B) = \det(C^{-1})\det(\lambda I - A)\det(C)

The determinant of a product is the product of the determinants (2.7).

= \det(\lambda I - A)

\det(C^{-1})\det(C) = \det(C^{-1}C) = \det I = 1

. These are numbers, so they can be reordered.

So the characteristic polynomial of a linear map $T$ on a finite-dimensional space is well defined: compute it from the matrix of $T$ in any basis. The same goes for the trace and the determinant of $T$ . This answers a question you may have had: why would anyone care about the sum of diagonal entries? Because that sum does not depend on the basis.

Worked example Apostol 4.8 #10; MATH 375 HW9

Prove that A and its transpose have the same characteristic polynomial. Do they have the same eigenvectors?

Solution.

Transpose the matrix $\lambda I - A$ . $(\lambda I - A)^{\mathsf T} = \lambda I^{\mathsf T} - A^{\mathsf T} = \lambda I - A^{\mathsf T}$ . The transpose of a difference is the difference of the transposes, and $I^{\mathsf T} = I$ .
Use the determinant of a transpose. $\det(\lambda I - A^{\mathsf T}) = \det\big((\lambda I - A)^{\mathsf T}\big) = \det(\lambda I - A)$ . A matrix and its transpose have the same determinant (2.7).
Conclude for eigenvalues. $p_{A^{\mathsf T}} = p_A$ , so the eigenvalues, with multiplicity, agree. Eigenvalues are the roots of the characteristic polynomial.
Test eigenvectors on an example. For $A = \begin{bmatrix}3&1\\0&2\end{bmatrix}$ the eigenvector for $3$ is $(1, 0)$ . For $A^{\mathsf T} = \begin{bmatrix}3&0\\1&2\end{bmatrix}$ we get $A^{\mathsf T}(1, 0) = (3, 1)$ , which is not a multiple of $(1, 0)$ , while $A^{\mathsf T}(1, 1) = (3, 3) = 3(1, 1)$ . One example is enough to show that “same eigenvectors” is false in general. Only the eigenvalues carry over.

Answer. The characteristic polynomials are equal. The eigenvectors can differ.

Worked example supports Apostol 4.9

Prove that tr(AB) = tr(BA) for n by n matrices, and deduce that tr(C⁻¹AC) = tr A.

Solution.

Write the diagonal entry of $AB$ . $(AB)_{ii} = \sum_{j}a_{ij}b_{ji}$ . Entry $(i, i)$ of a product is row $i$ of $A$ times column $i$ of $B$ .
Sum over the diagonal. $\operatorname{tr}(AB) = \sum_i\sum_ja_{ij}b_{ji}$ . The trace is the sum of the diagonal entries.
Do the same for $BA$ . $\operatorname{tr}(BA) = \sum_j\sum_ib_{ji}a_{ij}$ . Now the roles are swapped: $(BA)_{jj} = \sum_ib_{ji}a_{ij}$ , summed over $j$ .
Compare. The two are the same finite double sum, in a different order, with each product’s two factors written in the other order. A finite sum can be added in any order, and real numbers commute.
Deduce the second claim. Apply the first part to the matrices $C^{-1}$ and $AC$ : $\operatorname{tr}\big(C^{-1}(AC)\big) = \operatorname{tr}\big((AC)C^{-1}\big) = \operatorname{tr}A$ . $(AC)C^{-1} = A(CC^{-1}) = A$ .

Answer. $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ , so similar matrices have the same trace. (Note that $AB \ne BA$ in general. Only the traces agree.)

Diagonalization

Definition T

Diagonalizable

A diagonal matrix has zeros everywhere except possibly on the diagonal. We write $\operatorname{diag}(d_1, \dots, d_n)$ for the one with $d_1, \dots, d_n$ down the diagonal. A linear map $T: V \to V$ on a finite-dimensional space is diagonalizable if $V$ has a basis in which the matrix of $T$ is diagonal. A square matrix $A$ is diagonalizable if the map $x \mapsto Ax$ is, equivalently if $A$ is similar to a diagonal matrix.

In one lineA map or matrix is diagonalizable if some basis makes its matrix diagonal; equivalently, if there is a basis of eigenvectors.

Why it existsDiagonalizable maps are exactly the ones that can be understood as independent stretches along $n$ directions.

Here is the same picture again, because the next theorem is about it. The two dashed lines are the two basis vectors we would choose. In that basis the grid is not the square grid but a grid made of lines parallel to the dashed lines, and the map only stretches that grid, by $3$ in one direction and $2$ in the other.

Theorem T Apostol Thm 4.1

Diagonal form means an eigenbasis

Let $e_1, \dots, e_n$ be a basis of $V$ . The matrix of $T$ in this basis is $\operatorname{diag}(d_1, \dots, d_n)$ if and only if $T(e_k) = d_ke_k$ for every $k$ . So $T$ is diagonalizable if and only if $V$ has a basis of eigenvectors of $T$ .

In one lineA map has a diagonal matrix in a basis exactly when every vector of that basis is an eigenvector. The diagonal entries are the eigenvalues.

Why it is trueColumn $k$ of the matrix is the coordinates of $T(e_k)$ . It is a multiple of the $k$ -th basis vector exactly when $e_k$ is an eigenvector.

ProofApostol 4.1; Spagnolie Lecture 18

The idea: Recall how the matrix is built: column k holds the coordinates of T(e_k). Then compare.

The matrix

(a_{ik})

T

satisfies

T(e_k) = a_{1k}e_1 + \dots + a_{nk}e_n

Definition of the matrix of a map in a basis (2.5):

T(e_k) = \sum_i a_{ik}e_i

, and column

k

of the matrix is

(a_{1k}, \dots, a_{nk})

The matrix is

\operatorname{diag}(d_1, \dots, d_n)

\iff

T(e_k) = d_ke_k

for every

k

Coordinates in a basis are unique (2.2), so the equation below says

a_{ik} = 0

for

i \ne k

and

a_{kk} = d_k

.In the picture:

e_k

is a point on a dashed line, and

T(e_k)

stays on that same line.

That says each

e_k

is an eigenvector of

T

with eigenvalue

d_k

e_k \ne O

because it is a basis vector. The equation

T(e_k) = d_ke_k

is the definition of an eigenvector.

In matrix language: put the eigenvectors in as the columns of a matrix $C$ , and the eigenvalues down the diagonal of $D$ .

Theorem T Apostol Thm 4.10; Spagnolie Lecture 18

Diagonalization as a factorization

Let $A$ be an $n$ by $n$ matrix with independent eigenvectors $u_1, \dots, u_n$ and eigenvalues $\lambda_1, \dots, \lambda_n$ . Let $C$ be the matrix whose $k$ -th column is $u_k$ and let $D = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ . Then $C$ is invertible and

A = CDC^{-1}, \qquad\text{equivalently}\qquad D = C^{-1}AC, \qquad\text{equivalently}\qquad AC = CD.

In one lineIf $A$ has $n$ independent eigenvectors, then $A = CDC^{-1}$ , where the columns of $C$ are those eigenvectors and $D$ is diagonal with the matching eigenvalues.

Why it is trueMultiplying by $C$ turns the $k$ -th standard basis vector into the $k$ -th eigenvector, and $A$ then multiplies that vector by its eigenvalue.

ProofSpagnolie Lecture 18 ('because...' note); Apostol 4.10

The idea: Compare the two matrices AC and CD column by column. Both have column k equal to λₖuₖ. Then use that C is invertible, because its columns are independent.

Column

k

AC

Au_k

, which is

\lambda_ku_k

Column

k

of a product

AC

A

times column

k

C

(matrix multiplication, 2.5).

Column

k

CD

\lambda_ku_k

Column

k

CD

C

times column

k

D

, and column

k

D

\lambda_k

in position

k

and

0

elsewhere. So it is

\lambda_k

times column

k

C

AC = CD

Two matrices with the same columns are equal.

C

is invertible.

Cx = O

means a combination of the columns of

C

O

. The columns are independent, so

x = O

. So

N(C) = \{O\}

, hence

C

is one-to-one, hence onto by rank–nullity, hence invertible (2.3, 2.4).

A = CDC^{-1}

Multiply

AC = CD

on the right by

C^{-1}

Why· Reading A = C D C⁻¹: change to the eigenbasis

Read it from right to left, applied to a vector $x$ . First $C^{-1}x$ gives the coordinates of $x$ in the eigenbasis (this is the change of basis of 2.5). Then $D$ stretches each coordinate by its own eigenvalue, the easy step. Then $C$ turns those coordinates back into ordinary ones. So $A$ does the same thing as $D$ , seen in the right coordinates. This is exactly what “similar matrices represent the same map” meant. And for powers, the middle pairs $C^{-1}C$ cancel:

A^k = (CDC^{-1})(CDC^{-1})\cdots(CDC^{-1}) = CD^kC^{-1}, \qquad D^k = \operatorname{diag}(\lambda_1^k, \dots, \lambda_n^k).

Worked example Spagnolie Lecture 18 method; this matrix is the picture above

Diagonalize the matrix with rows (3, 1) and (0, 2), then compute A^5.

Solution.

Find the eigenvalues. $\det(\lambda I - A) = (\lambda - 3)(\lambda - 2)$ , so $\lambda_1 = 3$ and $\lambda_2 = 2$ . The roots of the characteristic polynomial are the eigenvalues. Check with the trace theorem: $3 + 2 = 5 = \operatorname{tr}A$ and $3\cdot2 = 6 = \det A$ .
Find an eigenvector for $3$ . Solve $(A - 3I)x = O$ : the rows are $(0, 1)$ and $(0, -1)$ , so $y = 0$ and $x$ is free. Take $u_1 = (1, 0)$ . A free variable gives a whole line of solutions, so we choose one non-zero member.
Find an eigenvector for $2$ . Solve $(A - 2I)x = O$ : the rows are $(1, 1)$ and $(0, 0)$ , so $y = -x$ . Take $u_2 = (1, -1)$ . The same method with the other eigenvalue. The two eigenvalues differ, so $u_1, u_2$ are independent and are a basis of $\mathbb R^2$ .
Build $C$ and $D$ . $C = \begin{bmatrix}1&1\\0&-1\end{bmatrix}$ has the eigenvectors as columns, and $D = \operatorname{diag}(3, 2)$ has the eigenvalues in the same order. Column 1 of $C$ must go with the first diagonal entry of $D$ .
Find $C^{-1}$ and verify. $C\cdot C = I$ , so $C^{-1} = C$ , and $CDC^{-1} = \begin{bmatrix}3&2\\0&-2\end{bmatrix}\begin{bmatrix}1&1\\0&-1\end{bmatrix} = \begin{bmatrix}3&1\\0&2\end{bmatrix} = A$ . Multiplying back is the only reliable check on a sign slip.
Take the power. $A^5 = CD^5C^{-1}$ with $D^5 = \operatorname{diag}(243, 32)$ , so $A^5 = \begin{bmatrix}243&32\\0&-32\end{bmatrix}\begin{bmatrix}1&1\\0&-1\end{bmatrix} = \begin{bmatrix}243&211\\0&32\end{bmatrix}$ . In $(CDC^{-1})\cdots(CDC^{-1})$ every inner $C^{-1}C$ cancels, so only the diagonal matrix is raised to the power.

The step-through below shows the same computation with every product written out.

Answer. $A = CDC^{-1}$ with $C = \begin{bmatrix}1&1\\0&-1\end{bmatrix}$ , $D = \operatorname{diag}(3, 2)$ , and $A^5 = \begin{bmatrix}243&211\\0&32\end{bmatrix}$ . In general $A^k = \begin{bmatrix}3^k&3^k - 2^k\\0&2^k\end{bmatrix}$ .

Your answerFor the same

A = \begin{bmatrix}3&1\\0&2\end{bmatrix}

, the top right entry of

A^k

3^k - 2^k

. What is the top right entry of

A^{10}

Worked example Apostol 4.4 #2

Prove: if Ax = λx with x non-zero, then A^k x = λ^k x for every k ≥ 1.

Solution.

Base case. For $k = 1$ this is the hypothesis $Ax = \lambda x$ . Induction needs a first case to start from.
Assume the case $k - 1$ . Suppose $A^{k-1}x = \lambda^{k-1}x$ . This is the induction hypothesis.
Apply $A$ once more. $A^kx = A(A^{k-1}x) = A(\lambda^{k-1}x) = \lambda^{k-1}Ax = \lambda^{k-1}\lambda x = \lambda^kx$ . Linearity of $A$ lets the scalar $\lambda^{k-1}$ come out, then $Ax = \lambda x$ is used again.

Answer. By induction the statement holds for all $k \ge 1$ . So $x$ is an eigenvector of $A^k$ with eigenvalue $\lambda^k$ . This one line is why $A = CDC^{-1}$ gives $A^k = CD^kC^{-1}$ .

Your answer

A

has the eigenvector

x

with eigenvalue

-2

. What is the eigenvalue of

A^5

for the same

x

Quick check

x

is an eigenvector of

A

with eigenvalue

3

. What does

A + 2I

do to

x

Worked example Apostol 4.4 #2; MATH 375 HW9

Prove: if A is invertible and Ax = λx with x non-zero, then λ is not 0 and A⁻¹x = λ⁻¹x.

Solution.

Show $\lambda \ne 0$ . Suppose $\lambda = 0$ . Then $Ax = O$ with $x \ne O$ . We argue by contradiction, using what an invertible matrix cannot do.
Reach the contradiction. A non-zero vector sent to $O$ means $A$ is not one-to-one, so $A$ is not invertible. An invertible map has null space $\{O\}$ (2.4). This contradicts the hypothesis, so $\lambda \ne 0$ .
Apply $A^{-1}$ to the equation. $A^{-1}(Ax) = A^{-1}(\lambda x)$ gives $x = \lambda A^{-1}x$ . $A^{-1}A = I$ on the left, and linearity pulls the scalar $\lambda$ out on the right.
Divide by $\lambda$ . $A^{-1}x = \lambda^{-1}x$ . This division is allowed only because step 2 showed $\lambda \ne 0$ .

Answer. $x$ is an eigenvector of $A^{-1}$ with eigenvalue $1/\lambda$ . For example $A = \begin{bmatrix}3&1\\0&2\end{bmatrix}$ has $E(2)$ spanned by $(1, -1)$ , and $A^{-1}(1, -1) = \tfrac12(1, -1)$ .

Worked example Apostol 4.4 #4; MATH 375 HW9

Prove: if λ² is an eigenvalue of T² = T∘T for a real number λ, then λ or −λ is an eigenvalue of T.

Solution.

Start from the hypothesis. Take $x \ne O$ with $T^2x = \lambda^2x$ . This is what ” $\lambda^2$ is an eigenvalue of $T^2$ ” means.
Factor. $T^2 - \lambda^2I = (T - \lambda I)(T + \lambda I)$ . The usual difference of squares. It is valid for maps because $T$ commutes with $I$ , so the cross terms $\lambda T$ and $-\lambda T$ cancel.
Apply the factorisation to $x$ . Let $y = (T + \lambda I)x$ . Then $(T - \lambda I)y = T^2x - \lambda^2x = O$ . The right side is zero by step 1.
Case $y = O$ . Then $Tx + \lambda x = O$ , so $Tx = -\lambda x$ with $x \ne O$ . That is the definition of $-\lambda$ being an eigenvalue.
Case $y \ne O$ . Then $(T - \lambda I)y = O$ says $Ty = \lambda y$ with $y \ne O$ . That is the definition of $\lambda$ being an eigenvalue, with eigenvector $y$ .

Answer. In either case one of $\lambda$ , $-\lambda$ is an eigenvalue of $T$ . $\blacksquare$

Theorem T Apostol Thm 4.10; Spagnolie Lecture 17

Distinct roots give a diagonalizable matrix

If $A$ is $n$ by $n$ and $p_A$ has $n$ distinct roots (in the scalars being used), then $A$ is diagonalizable.

In one lineIf the characteristic polynomial has $n$ different roots, the matrix is diagonalizable.

Why it is trueEach root is an eigenvalue, the eigenvectors are independent because the roots differ, and $n$ independent vectors in $n$ dimensions are a basis.

This is a corollary of two theorems already proved: the roots are eigenvalues (so each has an eigenvector), and eigenvectors for distinct eigenvalues are independent. By the “distinct eigenvalues give an eigenbasis” theorem they form a basis, and the factorization theorem gives $A = CDC^{-1}$ . In practice this settles most matrices you will meet.

Beyond the course: for understanding· Complex scalars

Everything above (null spaces, independence, determinants, every proof in this chapter) works unchanged if the scalars are complex numbers instead of real ones. Vectors then have complex entries. Spagnolie switches to complex scalars in Lecture 18 for exactly this reason: a real matrix can have complex eigenvalues (the rotation below), and over the complex numbers the fundamental theorem of algebra guarantees $n$ eigenvalues with multiplicity. When we say a real matrix is diagonalizable “over $\mathbb R$ ” we also require the roots to be real. “Over $\mathbb C$ ” only requires enough eigenvectors.

When diagonalization fails: multiplicities

A repeated root can go either way. Both $I = \begin{bmatrix}1&0\\0&1\end{bmatrix}$ and the shear $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ have characteristic polynomial $(\lambda - 1)^2$ . The identity is already diagonal; the shear is not diagonalizable (details in the examples). To tell them apart we need two counts for each eigenvalue $\lambda_0$ of an $n$ by $n$ matrix $A$ .

The algebraic multiplicity $m(\lambda_0)$ is the number of times $\lambda_0$ appears as a root of $p_A$ , that is, the exponent of $(\lambda - \lambda_0)$ in the factorization of $p_A$ . It is found from the polynomial. Example: if $p_A = (\lambda - 3)^2(\lambda - 1)$ then $m(3) = 2$ and $m(1) = 1$ .
The geometric multiplicity $g(\lambda_0)$ is the dimension of the eigenspace $E(\lambda_0)$ : how many independent eigenvectors $\lambda_0$ has. It is found from the matrix, by solving $(\lambda_0 I - A)x = O$ .

For $I$ these are $m = 2$ and $g = 2$ . For the shear they are $m = 2$ and $g = 1$ . Spagnolie states the general relation without proof (" $1 \le \dim E(\lambda) \le m(\lambda)$ "). Here it is with a proof.

Theorem T Spagnolie Lecture 16 (stated); proof added here

Geometric multiplicity is at most algebraic multiplicity

If $\lambda_0$ is an eigenvalue of the $n$ by $n$ matrix $A$ and $g = \dim E(\lambda_0)$ , then $(\lambda - \lambda_0)^g$ divides $p_A(\lambda)$ . So $1 \le g \le m(\lambda_0)$ .

In one lineAn eigenvalue never has more independent eigenvectors than its multiplicity as a root: $1 \le g(\lambda_0) \le m(\lambda_0)$ .

Why it is trueUse the eigenvectors of $\lambda_0$ as the first columns of a new basis. In that basis the matrix has $\lambda_0$ on the diagonal $g$ times, which puts $(\lambda - \lambda_0)^g$ in the characteristic polynomial.

Proofadded here; Spagnolie states it in Lecture 16

The idea: Build a basis whose first g vectors are eigenvectors of λ₀. The matrix in that basis has a block shape with λ₀ down the first g diagonal places and zeros below them. Expanding the determinant of λI − (that matrix) along the first column g times pulls out (λ − λ₀)^g. Similar matrices share the characteristic polynomial.

Let

u_1, \dots, u_g

be a basis of

E(\lambda_0)

E(\lambda_0)

is a subspace of dimension

g

(the eigenspace theorem), so it has a basis.

g \ge 1

because

\lambda_0

is an eigenvalue.

Extend it to a basis

u_1, \dots, u_n

\mathbb R^n

and let

C

have these as columns.

Any independent set extends to a basis (2.2).

B = C^{-1}AC = \begin{bmatrix}\lambda_0I_g & X\\ O & Y\end{bmatrix}

for some matrices

X

and

Y

B = C^{-1}AC

is the matrix of the same map in the new basis (2.5). For

k \le g

Au_k = \lambda_0u_k

, so column

k

B

\lambda_0

in position

k

and

0

elsewhere.

\lambda I - B = \begin{bmatrix}(\lambda - \lambda_0)I_g & -X\\ O & \lambda I - Y\end{bmatrix}

Subtract

B

from

\lambda I

block by block.

Expand along column 1, then repeat

g

times:

\det(\lambda I - B) = (\lambda - \lambda_0)^g\det(\lambda I - Y)

Column 1 has only one non-zero entry,

\lambda - \lambda_0

in the top place, so cofactor expansion along column 1 gives

(\lambda - \lambda_0)

times the determinant of what is left. What is left has the same shape with

g - 1

in place of

g

p_A(\lambda) = (\lambda - \lambda_0)^g\det(\lambda I - Y)

. So

\lambda_0

is a root at least

g

times:

g \le m(\lambda_0)

Similar matrices share a characteristic polynomial (previous theorem).

Theorem B Apostol Thm 4.10 and Spagnolie Lecture 18; the iff is added here

Diagonalizable exactly when the eigenspaces fill the space

Let $A$ be $n$ by $n$ and suppose all $n$ roots of $p_A$ lie in the scalars (always true over $\mathbb C$ ). Let $\lambda_1, \dots, \lambda_r$ be the distinct eigenvalues, with multiplicities $m_i$ and $g_i$ . Then $A$ is diagonalizable if and only if $g_i = m_i$ for every $i$ .

In one lineWith all roots among the scalars, $A$ is diagonalizable if and only if $g(\lambda) = m(\lambda)$ for every eigenvalue, that is, if and only if the dimensions of the eigenspaces add up to $n$ .

Why it is trueEigenspaces for different eigenvalues are independent of each other, and $g \le m$ with $\sum m = n$ . So the eigenspace dimensions reach $n$ only if each one reaches its $m$ .

Proofadded here

The idea: Join bases of all the eigenspaces into one list. That list is independent (by the independence theorem), and it has g₁ + … + g_r vectors, which is at most m₁ + … + m_r = n. It is a basis exactly when it has n vectors, which needs every g to equal its m.

Claim: the joined list is linearly independent.

Choose a basis of each

E(\lambda_i)

and join the lists. Suppose a combination of the whole list is

O

. Group it as

v_1 + \dots + v_r = O

, where

v_i

is the part from the basis of

E(\lambda_i)

, so

v_i \in E(\lambda_i)

If some

v_i

were non-zero, the non-zero ones would be independent, contradicting

v_1 + \dots + v_r = O

. So every

v_i = O

Each non-zero

v_i

is an eigenvector for

\lambda_i

. Eigenvectors with distinct eigenvalues are independent, so a combination of them with every coefficient equal to

1

cannot be

O

So all coefficients are zero and the claim holds. The list has

g_1 + \dots + g_r

vectors.

v_i

is a combination of an independent list (the basis of

E(\lambda_i)

) and equals

O

, so all its coefficients are

0

g_1 + \dots + g_r \le m_1 + \dots + m_r = n

, with equality exactly when every

g_i = m_i

g_i \le m_i

by the previous theorem, and the multiplicities of all roots add up to the degree

n

(

\Leftarrow

) If

g_i = m_i

for all

i

, we have an eigenbasis.

If every

g_i = m_i

the joined list has

n

independent vectors, a basis of eigenvectors.

A

is diagonalizable.

(

\Rightarrow

) If an eigenbasis exists, then

g_i = m_i

for all

i

Sort an eigenbasis by eigenvalue. The

n_i

basis vectors with eigenvalue

\lambda_i

are independent and lie in

E(\lambda_i)

, so

n_i \le g_i

. Then

n = \sum n_i \le \sum g_i \le \sum m_i = n

, so all the inequalities are equalities.

Quick checkOver

\mathbb R

, which of these matrices is NOT diagonalizable?

Examples and non-examples

A recurrence in closed form. Fibonacci’s numbers $0, 1, 1, 2, 3, 5, 8, \dots$ come from “add the last two”. That rule does not look like a matrix, yet it becomes one, and then the machinery of this chapter gives a formula for the $k$ -th term with no recursion at all.

Where this came from· Rabbits, and a formula with several owners

The sequence first appears in Fibonacci’s Liber Abaci (1202), where it counts pairs of rabbits month by month under a simple breeding rule. The closed formula below carries the name of Jacques Binet (1843), but Euler, de Moivre and Daniel Bernoulli knew it about a century earlier. The matrix method gives the formula without any guessing. The golden ratio shows up because it is the larger root of the characteristic polynomial of the “add the last two” matrix. So a rule that repeats (“add the last two, again and again”) is controlled by the eigenvalues of one matrix.

Worked example the method of Spagnolie Lecture 18 applied to a recurrence (Binet's formula)

Find a closed formula for the Fibonacci numbers F_k, where F_0 = 0, F_1 = 1 and F_(k+1) = F_k + F_(k-1).

Solution.

Turn the rule into a matrix. Put two consecutive terms in a vector $u_k = (F_{k+1}, F_k)$ . Then $u_{k+1} = Au_k$ with $A = \begin{bmatrix}1&1\\1&0\end{bmatrix}$ , so $u_k = A^ku_0$ and $u_0 = (1, 0)$ . The new top entry is $F_{k+2} = F_{k+1} + F_k$ and the new bottom entry is $F_{k+1}$ . A rule that needs the last two terms becomes a rule on one vector.
Find the eigenvalues. $p_A(\lambda) = \lambda^2 - \lambda - 1$ , with roots $\varphi = \frac{1 + \sqrt5}{2}$ and $\psi = \frac{1 - \sqrt5}{2}$ . The trace is $1$ and the determinant is $-1$ . The roots add to $1$ and multiply to $-1$ , as the trace and determinant theorem says. They differ, so $A$ is diagonalizable.
Find the eigenvectors. $v_\varphi = (\varphi, 1)$ and $v_\psi = (\psi, 1)$ . The second row of $(A - \lambda I)x = O$ is $x - \lambda y = 0$ , so $x = \lambda y$ . The first row then reads $\lambda^2 = \lambda + 1$ , which both roots satisfy.
Write $u_0$ in the eigenbasis. $(1, 0) = \frac1{\sqrt5}(v_\varphi - v_\psi)$ . Solving $c_1v_\varphi + c_2v_\psi = (1, 0)$ : the second coordinate gives $c_1 + c_2 = 0$ and the first gives $c_1(\varphi - \psi) = 1$ , with $\varphi - \psi = \sqrt5$ .
Apply $A^k$ piece by piece. $u_k = \frac1{\sqrt5}(\varphi^kv_\varphi - \psi^kv_\psi)$ . $A$ multiplies $v_\varphi$ by $\varphi$ and $v_\psi$ by $\psi$ , so $A^k$ multiplies them by $\varphi^k$ and $\psi^k$ . No matrix power is computed.
Read off the bottom entry. $F_k = \dfrac{\varphi^k - \psi^k}{\sqrt5}$ . The bottom entry of $u_k = (F_{k+1}, F_k)$ is $F_k$ , and both eigenvectors have bottom entry $1$ .
Check. For $k = 10$ : $\varphi^{10} \approx 122.99187$ and $\psi^{10} \approx 0.00813$ , so $F_{10} = \frac{122.98374}{2.23607} = 55$ . That is the tenth Fibonacci number. Since $|\psi| < 1$ , $\psi^k$ dies away and $F_k$ is the whole number nearest to $\varphi^k/\sqrt5$ .

The step-through below shows the same argument with every line written out.

Answer. $F_k = \dfrac{\varphi^k - \psi^k}{\sqrt5}$ with $\varphi = \tfrac{1+\sqrt5}{2}$ and $\psi = \tfrac{1-\sqrt5}{2}$ .

Your answerUse

F_k \approx \varphi^k/\sqrt5

with

\varphi \approx 1.618034

to estimate

F_{15}

, then give the exact whole number it rounds to.

Non-example 1: the shear has too few eigenvectors. In the picture, “Shear” shows a single dashed line.

Worked example Spagnolie Lectures 16 and 18; Apostol 4.10 #1

Is the shear with rows (1, 1) and (0, 1) diagonalizable?

Solution.

Find the characteristic polynomial. $\det\begin{bmatrix}\lambda-1&-1\\0&\lambda-1\end{bmatrix} = (\lambda-1)^2$ . The matrix is triangular, so the determinant is the product of the diagonal entries. So $\lambda = 1$ is the only eigenvalue, with algebraic multiplicity $m = 2$ .
Find the eigenspace. $(I - A)x = \begin{bmatrix}0&-1\\0&0\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = \begin{bmatrix}-y\\0\end{bmatrix} = O$ forces $y = 0$ . So $E(1) = \{(x, 0)\}$ , the horizontal line, and $g = 1$ . The geometric multiplicity is the dimension of this null space.
Compare. $g = 1 < 2 = m$ . By the iff theorem, a matrix is diagonalizable only if $g = m$ for every eigenvalue. Equivalently, we need 2 independent eigenvectors in $\mathbb R^2$ and there is only one line of them.
Second argument (Spagnolie). If $A = CDC^{-1}$ , $D$ would have both eigenvalues equal to $1$ , so $D = I$ and $A = CIC^{-1} = I$ . But $A \ne I$ . The only diagonalizable matrix whose eigenvalues are all equal to $a$ is $aI$ .

Answer. No. The shear is not diagonalizable. It has the same characteristic polynomial as $I$ , yet $I$ is diagonalizable, so the characteristic polynomial alone does not decide it.

Your answerLet

A = \begin{bmatrix}2&1&0\\0&2&0\\0&0&2\end{bmatrix}

. Its only eigenvalue is

2

. What is

\dim E(2)

, the number of independent eigenvectors?

Non-example 2: rotation has no real eigenvectors, but has complex ones.

Worked example Spagnolie Lecture 18

Find the eigenvalues and eigenvectors of the quarter turn with rows (0, -1) and (1, 0).

Solution.

Characteristic polynomial. $\det\begin{bmatrix}\lambda&1\\-1&\lambda\end{bmatrix} = \lambda^2 + 1$ . Expand the $2\times2$ determinant: $\lambda\cdot\lambda - (1)(-1)$ .
Real roots? $\lambda^2 + 1 = 0$ has none, so over $\mathbb R$ there is no eigenvalue and no eigenvector. This matches the preset “Rotate 90°”: no dashed line, because every direction is turned.
Allow complex numbers. The roots are $\lambda = i$ and $\lambda = -i$ , where $i$ is the number with $i^2 = -1$ . Over $\mathbb C$ (the complex numbers) every polynomial has its roots. We now let the vector entries be complex too.
Eigenvector for $i$ . $(iI - A)x = \begin{bmatrix}i&1\\-1&i\end{bmatrix}x = O$ . The first row says $ix + y = 0$ , so $y = -ix$ . Take $x = 1$ : $u_1 = (1, -i)$ . Check: $Au_1 = (0\cdot1 + (-1)(-i),\ 1\cdot 1 + 0) = (i, 1) = i\,(1, -i)$ . Spagnolie writes $(-1, i)$ , which is $-1$ times this vector and lies on the same line.
Eigenvector for $-i$ . Similarly $u_2 = (1, i)$ . Check: $Au_2 = (-i, 1) = -i\,(1, i)$ . Same method with $-i$ in place of $i$ .
Cross-check. $i + (-i) = 0 = \operatorname{tr}A$ and $i\cdot(-i) = 1 = \det A$ . The trace and determinant theorem holds with complex eigenvalues.

Answer. No real eigenvalues. Over $\mathbb C$ : $i$ with $(1, -i)$ and $-i$ with $(1, i)$ . So $A = CDC^{-1}$ with $D = \operatorname{diag}(i, -i)$ , and $A^2 = CD^2C^{-1} = -I$ : two quarter turns make a half turn, which is $-I$ .

A rotation by an angle $\theta$ has eigenvalues $\cos\theta \pm i\sin\theta$ . A complex diagonal matrix is how a rotation is written once the right complex basis is chosen.

Eigenfunctions: the same idea in a function space. Here $V$ is infinite-dimensional, so there is no characteristic polynomial and no determinant, but the definition of eigenvector still works.

Worked example Apostol 4.4 #5, MATH 375 HW9

Find all eigenvalues and eigenfunctions of T(f)(t) = t f'(t) on the infinitely differentiable functions on (0, 1).

Solution.

Write the eigen-equation. $T(f) = \lambda f$ means $t f'(t) = \lambda f(t)$ for all $t$ in $(0, 1)$ . This is the definition, with a non-zero function $f$ .
Find a quantity with derivative zero. $\dfrac{d}{dt}\big(t^{-\lambda}f(t)\big) = t^{-\lambda}f' - \lambda t^{-\lambda-1}f = t^{-\lambda-1}\big(tf' - \lambda f\big) = 0$ . The product rule. We multiply by $t^{-\lambda}$ because it turns the equation into “something has zero derivative”. (Dividing by $f$ instead would fail where $f$ is zero.)
Conclude it is constant. A function with zero derivative on an interval is constant, so $t^{-\lambda}f(t) = K$ and $f(t) = Kt^\lambda$ . Mean value theorem from calculus. $f \ne O$ means $K \ne 0$ .
Check the converse. $T(t^\lambda) = t\cdot\lambda t^{\lambda-1} = \lambda t^\lambda$ , and $t^\lambda$ is differentiable on $(0, 1)$ for every real $\lambda$ . We must make sure our answers are really in the space and really satisfy the equation.

Answer. Every real number $\lambda$ is an eigenvalue, and $E(\lambda) = \{Kt^\lambda\}$ , a one-dimensional space.

Where it is used

Used inside maths· Inside maths: differential equations y' = Ay

In MATH 376 you solve one equation $y' = ay$ by $y = y(0)\,e^{at}$ . A system $y' = Ay$ , with $A$ a matrix and $y(t)$ a vector, can be solved the same way. Try a solution that keeps its direction: $y(t) = e^{\lambda t}v$ for a fixed vector $v$ . Then $y' = \lambda e^{\lambda t}v$ and $Ay = e^{\lambda t}Av$ , and the two are equal exactly when $Av = \lambda v$ . So eigenvectors are exactly the solutions that keep their shape. Because the equation is linear, sums of such solutions are also solutions.

Take $A = \begin{bmatrix}2&-4\\0&-2\end{bmatrix}$ (MATH 375 HW10). Its eigenvalues are $2$ with $v = (1, 0)$ and $-2$ with $v = (1, 1)$ . The solution with $y(0) = (p, q)$ is

y(t) = (p - q)\,e^{2t}\begin{bmatrix}1\\0\end{bmatrix} + q\,e^{-2t}\begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix}(p - q)e^{2t} + qe^{-2t}\\ qe^{-2t}\end{bmatrix}.

(We found the two weights by writing $(p, q) = (p - q)(1, 0) + q(1, 1)$ , which is coordinates in the eigenbasis.) Check: at $t = 0$ it gives $(p, q)$ , and differentiating the second coordinate gives $-2qe^{-2t} = -2\cdot(\text{second coordinate})$ , as $y' = Ay$ requires, because the second row of $A$ is $(0, -2)$ . Start at $(3, 1)$ and you get $(2e^{2t} + e^{-2t},\ e^{-2t})$ . One piece grows like $e^{2t}$ , the other dies like $e^{-2t}$ . The eigenvalue signs predict the long-term behaviour at once. In general $y(t) = Ce^{tD}C^{-1}y(0)$ , where $e^{tD}$ is $\operatorname{diag}(e^{\lambda_1t}, \dots, e^{\lambda_nt})$ .

Used in the real world· Engineering: vibration modes of two coupled carts

Two carts of mass $1$ kg sit on a track. A spring of stiffness $100$ N/m joins the left cart to a wall, another joins the carts, and a third joins the right cart to a wall. If $x_1, x_2$ are the displacements from rest, Newton’s law gives $x_1'' = -200x_1 + 100x_2$ and $x_2'' = 100x_1 - 200x_2$ , that is, $x'' = -Kx$ with $K = \begin{bmatrix}200&-100\\-100&200\end{bmatrix}$ . Try a motion where both carts oscillate at the same frequency: $x(t) = v\cos\omega t$ . Then $x'' = -\omega^2v\cos\omega t$ , and the equation becomes $Kv = \omega^2v$ . This is an eigenvalue problem.

The characteristic polynomial is $(\lambda - 200)^2 - 100^2$ , with roots $\lambda = 100$ and $300$ . The eigenvector for $100$ is $(1, 1)$ : the carts move together, $\omega = \sqrt{100} = 10$ rad/s (1.59 Hz). The eigenvector for $300$ is $(1, -1)$ : the carts move in opposite directions, $\omega = \sqrt{300} \approx 17.32$ rad/s (2.76 Hz). These two are the normal modes. Every motion is a combination of them. Pull the left cart $1$ cm and release both from rest: $(1, 0) = \tfrac12(1, 1) + \tfrac12(1, -1)$ , so

x_1(t) = \tfrac12\big(\cos 10t + \cos 17.32t\big), \qquad x_2(t) = \tfrac12\big(\cos 10t - \cos 17.32t\big)\ \text{cm}.

By the product formula for cosines, $x_1 = \cos(13.66\,t)\cos(3.66\,t)$ and $x_2 = \sin(13.66\,t)\sin(3.66\,t)$ . The slow factor $\cos(3.66t)$ is zero at $t = \pi/(2\cdot 3.66) \approx 0.43$ s, when the left cart’s swing has died down and the right cart is moving with almost full amplitude. The energy sloshes from one cart to the other. Engineers compute these eigenvalues for bridges and buildings to keep the natural frequencies away from the frequency of wind or footsteps.

Used in the real world· Biology: a population model (Leslie matrix)

A fish population has three age groups: young, adult and old, counted once a year. Each adult produces $1.5$ young per year and each old fish produces $1$ . Of the young, $60\%$ survive to become adults. Of the adults, $50\%$ survive to become old, and old fish die within the year. With $x = (\text{young}, \text{adult}, \text{old})$ , next year’s population is $Lx$ with

L = \begin{bmatrix}0 & 1.5 & 1\\ 0.6 & 0 & 0\\ 0 & 0.5 & 0\end{bmatrix}, \qquad p_L(\lambda) = \lambda^3 - 0.9\lambda - 0.3.

The roots are $1.0847$ , $-0.6749$ and $-0.4098$ . Check with the trace theorem: they add to $0 = \operatorname{tr}L$ and multiply to $0.3 = \det L$ . Write the starting population in the eigenbasis: after $k$ years each piece has been multiplied by $\lambda_i^k$ . The two negative eigenvalues have size less than $1.0847$ , so their pieces fade relative to the first. Start with $100$ young fish. After $12$ years the population is $(119.6,\ 64.9,\ 30.8)$ , total $215.3$ . In year $13$ the total grows by a factor $1.079$ , already near $1.0847$ , and the factor settles at $1.0847$ : the population grows about $8.5\%$ a year in the long run. The eigenvector for $1.0847$ is proportional to $(1,\ 0.6/\lambda,\ 0.3/\lambda^2)$ , which as fractions of the total is $(0.553,\ 0.306,\ 0.141)$ . The simulated year-12 fractions are $(0.555, 0.301, 0.143)$ . So the dominant eigenvalue gives the long-run growth rate and the dominant eigenvector gives the stable age mix. (For matrices with no negative entries this behaviour is guaranteed by the Perron–Frobenius theorem; here we saw it by computing.)

Used in the real world· The web: PageRank is an eigenvector (preview of 2.11)

Take a web of three pages. Page 1 links to pages 2 and 3, page 2 links to page 3, and page 3 links to page 1. Let each page split one unit of “importance” equally among the pages it links to. The vector $r$ of importances must be reproduced by this sharing: $r = Mr$ , where column $j$ of $M$ shows how page $j$ shares its vote,

M = \begin{bmatrix}0&0&1\\ \tfrac12&0&0\\ \tfrac12&1&0\end{bmatrix}.

So $r$ is an eigenvector of $M$ with eigenvalue $1$ . Solving gives $r = (0.4, 0.2, 0.4)$ . Check: $Mr = (0.4,\ 0.2,\ 0.2 + 0.2) = r$ . Pages 1 and 3 are twice as important as page 2, because page 3 receives all of page 2’s vote and half of page 1’s. The other two eigenvalues of $M$ are $(-1 \pm i)/2$ , of size $0.707$ , which is less than $1$ . So repeated multiplication $M^kx$ shrinks everything except the eigenvalue- $1$ part: starting from $(1, 0, 0)$ , forty multiplications give $(0.4000, 0.2000, 0.4000)$ . That is how a real search engine finds the ranking of billions of pages, without diagonalizing anything. The original Google method also mixes in a $15\%$ chance of jumping to a random page, so that the process cannot get stuck. Chapter 2.11 builds this properly.

Used in the real world· Data and geometry: principal axes (preview of 3.2 and PCA)

The set of points with $5x^2 + 4xy + 5y^2 = 1$ is an ellipse tilted at $45°$ . The matrix of this quadratic expression is $S = \begin{bmatrix}5&2\\2&5\end{bmatrix}$ , with $p_S = \lambda^2 - 10\lambda + 21 = (\lambda - 7)(\lambda - 3)$ . The eigenvectors are $(1, 1)$ for $7$ and $(1, -1)$ for $3$ , and they are perpendicular. In the coordinates $u = (x + y)/\sqrt2$ and $v = (x - y)/\sqrt2$ along these directions, the equation becomes $7u^2 + 3v^2 = 1$ , because $5x^2 + 4xy + 5y^2 = 3.5(x+y)^2 + 1.5(x-y)^2$ . The semi-axes are $1/\sqrt7 \approx 0.378$ along $(1, 1)$ and $1/\sqrt3 \approx 0.577$ along $(1, -1)$ . These are the principal axes, and the eigenvalues say how steeply the expression grows in each direction (a bigger eigenvalue gives a shorter axis). If $S$ were the covariance matrix of two correlated measurements, the same eigenvectors would be the directions of greatest and least spread, with variances $7$ and $3$ . That is principal component analysis (PCA), which keeps the directions with the largest eigenvalues. The fact that the two eigenvectors are perpendicular is not luck: it holds for every symmetric matrix (you can prove it in 2.9, and the spectral theorem in 3.1 makes it complete).

Used in the real world· Physics (B): quantum energy levels are eigenvalues

In quantum mechanics a particle is described by a function $\psi$ , and its possible energies are the eigenvalues of an operator $H$ (the Hamiltonian): $H\psi = E\psi$ . For a particle trapped in a box $[0, L]$ with $\psi(0) = \psi(L) = 0$ , $H = -\dfrac{\hbar^2}{2m}\dfrac{d^2}{dx^2}$ . This is the second-derivative operator from Apostol 4.4 #9 (see the stretch problem below). Its eigenfunctions are $\psi_n = \sin(n\pi x/L)$ , because $\psi_n'' = -(n\pi/L)^2\psi_n$ , and its eigenvalues are

E_n = \frac{n^2\pi^2\hbar^2}{2mL^2}, \qquad n = 1, 2, 3, \dots

Only these energies are allowed. For an electron ( $m = 9.109\times10^{-31}$ kg) in a box $1$ nm wide, $E_1 = 6.02\times10^{-20}$ J $= 0.376$ eV, $E_2 = 4E_1 = 1.50$ eV, $E_3 = 9E_1 = 3.38$ eV. A jump from level $2$ to level $1$ releases $3E_1 = 1.128$ eV, a photon of wavelength about $1240/1.128 \approx 1100$ nm (infrared). A quantum dot is a tiny box of this kind, and shrinking it increases $E_n$ (it grows like $1/L^2$ ), which is why its colour depends on its size.

A preview· Preview: what the later chapters do with this

Three failures happened above: a repeated eigenvalue with too few eigenvectors (the shear), complex eigenvalues (the rotation), and in general a basis of eigenvectors that is not perpendicular. Chapter 3.6 (Jordan form) repairs the first: every matrix over $\mathbb C$ is similar to a matrix that is diagonal except for a few $1$ s directly above the diagonal, and the shear is the smallest example. Chapter 3.1 (the spectral theorem) says that a real symmetric matrix always has real eigenvalues and a perpendicular eigenbasis, as in the ellipse above. Spagnolie also stated the Schur decomposition: every square matrix is $A = QTQ^{\mathsf H}$ with $Q$ having perpendicular unit columns (unitary, so $Q^{\mathsf H}$ , its conjugate transpose, is its inverse) and $T$ upper triangular, with the eigenvalues on its diagonal. It is a weaker form of diagonalization that always works. A defective matrix such as $\begin{bmatrix}\tfrac12&-\tfrac12\\ \tfrac12&\tfrac32\end{bmatrix}$ (repeated eigenvalue $1$ , one eigenvector) has $A^{99} = \tfrac12\begin{bmatrix}-97&-99\\99&101\end{bmatrix}$ , found from $A = I + N$ with $N^2 = O$ . The Cayley–Hamilton theorem ( $p_A(A) = O$ for every square matrix) is proved in the problems below for diagonalizable matrices only. And chapter 2.11 uses the eigenvalue $1$ of a Markov matrix to find where a random process settles.

Traps

Watch out· The zero vector is never an eigenvector, but 0 can be an eigenvalue

If you solve $(A - \lambda I)x = O$ and get only $x = O$ , then $\lambda$ is not an eigenvalue. If the eigenvalue $\lambda = 0$ appears, it is a real eigenvalue and it means $A$ is not invertible (its eigenvectors are the non-zero null space vectors).

Watch out· 'The' eigenvector is a whole line, so answers differ and both are right

If you get $(1, -1)$ and a classmate gets $(-2, 2)$ , you may both be right. Multiples of an eigenvector are eigenvectors. To check your own answer, never compare with someone else’s: multiply $A$ times your vector and see whether you get $\lambda$ times it. As Spagnolie wrote on Piazza (@92), if your steps were sound and your arithmetic correct, you are guaranteed the right form, but it is always worth the check if you have time.

Watch out· Order matters in C D C⁻¹

The $k$ -th column of $C$ must be the eigenvector for the $k$ -th diagonal entry of $D$ . Swap two eigenvalues in $D$ and you must swap the same two columns of $C$ . The inverse goes on the right in $A = CDC^{-1}$ . Apostol writes the same thing as $B = C^{-1}AC$ (so his $B$ is our $D$ ). Spagnolie writes $U\Lambda U^{-1}$ . They are all the same statement.

Watch out· A repeated eigenvalue does not decide anything

Repeated eigenvalue does not mean “not diagonalizable” (the identity is diagonal) and it does not mean “diagonalizable” (the shear is not). Count eigenvectors: the geometric multiplicity must equal the algebraic multiplicity for every eigenvalue. Distinct eigenvalues, on the other hand, are a guarantee that the matrix is diagonalizable.

Watch out· Same eigenvalues does not mean similar

The identity and the shear both have only the eigenvalue $1$ (twice), but they are not similar: if $A = CIC^{-1}$ then $A = I$ . Similar matrices must share their characteristic polynomial (so trace, determinant and eigenvalues), but sharing them is not enough. To show two matrices are not similar, Spagnolie’s method (Piazza @87, @90, HW10) is to assume $AC = CB$ for an unknown $C$ and show $C$ must be singular.

Watch out· Eigenvalues of A + B and AB are not sums and products

The trace theorem is about one matrix. For $A = \begin{bmatrix}1&1\\0&1\end{bmatrix}$ and $B = \begin{bmatrix}1&0\\1&1\end{bmatrix}$ both eigenvalues are $1$ and $1$ . But $AB = \begin{bmatrix}2&1\\1&1\end{bmatrix}$ has trace $3$ , not $1 + 1 = 2$ , and eigenvalues $\tfrac{3 \pm \sqrt5}{2}$ . Eigenvalues combine nicely only when the matrices share eigenvectors.

Watch out· Real matrix, complex eigenvalues

‘No real eigenvalue’ does not mean ‘no eigenvalue’. A rotation by $90°$ has the eigenvalues $\pm i$ . When the question says ‘over $\mathbb R$ ’ and the characteristic polynomial has no real roots, the answer is that no real eigenvector exists, and you should not force one.

Watch out· Two characteristic polynomials in the books

Apostol and Spagnolie use $\det(\lambda I - A)$ , which starts with $+\lambda^n$ . Other books (and some calculators) use $\det(A - \lambda I)$ , which starts with $(-1)^n\lambda^n$ . The roots are identical, so eigenvalues are unaffected, but the constant term has the opposite sign when $n$ is odd.

Problems

check

Which of $(2, -2)$ , $(0, 0)$ , $(1, 1)$ are eigenvectors of $A = \begin{bmatrix}3&1\\0&2\end{bmatrix}$ ? Give the eigenvalue where there is one.

Solution

$A(2, -2) = (6 - 2, -4) = (4, -4) = 2\,(2, -2)$ : yes, with $\lambda = 2$ . $(0, 0)$ is never an eigenvector, by definition. $A(1, 1) = (4, 2)$ is not a multiple of $(1, 1)$ : no.

checkLecture 16

Find the eigenvalues of $\begin{bmatrix}2&5&7\\0&3&1\\0&0&-1\end{bmatrix}$ without expanding anything. What are its trace and determinant?

Solution

The matrix is upper triangular, so $\det(\lambda I - A) = (\lambda - 2)(\lambda - 3)(\lambda + 1)$ and the eigenvalues are the diagonal entries $2, 3, -1$ . The trace is $2 + 3 - 1 = 4$ and the determinant is $2\cdot3\cdot(-1) = -6$ , which are the sum and product of the eigenvalues.

checkMATH 375 HW9 (Apostol 3.17 #3a)

The matrix $A = \begin{bmatrix}0&3\\2&-1\end{bmatrix}$ has trace $-1$ and determinant $-6$ . Write down its characteristic polynomial and its eigenvalues without computing $\det(\lambda I - A)$ directly.

Solution

For a $2\times2$ matrix, $p_A(\lambda) = \lambda^2 - (\operatorname{tr}A)\lambda + \det A = \lambda^2 + \lambda - 6 = (\lambda + 3)(\lambda - 2)$ . The eigenvalues are $-3$ and $2$ . Direct check: $\det\begin{bmatrix}\lambda&-3\\-2&\lambda+1\end{bmatrix} = \lambda(\lambda + 1) - 6$ , the same.

check

Does the rotation by $90°$ , $\begin{bmatrix}0&-1\\1&0\end{bmatrix}$ , have an eigenvector in $\mathbb R^2$ ? Explain in one sentence using the picture.

Solution

No. Its characteristic polynomial $\lambda^2 + 1$ has no real root. In the picture, a quarter turn sends every direction to a different direction, so no line stays on itself.

useApostol 4.10 #2(b), MATH 375 HW10

Diagonalize $A = \begin{bmatrix}1&2\\5&4\end{bmatrix}$ : find $C$ and $D$ with $A = CDC^{-1}$ .

Solution

Trace $5$ , determinant $4 - 10 = -6$ , so $p_A = \lambda^2 - 5\lambda - 6 = (\lambda - 6)(\lambda + 1)$ . For $\lambda = 6$ : $A - 6I = \begin{bmatrix}-5&2\\5&-2\end{bmatrix}$ , so $5x = 2y$ and $u_1 = (2, 5)$ . For $\lambda = -1$ : $A + I = \begin{bmatrix}2&2\\5&5\end{bmatrix}$ , so $x = -y$ and $u_2 = (-1, 1)$ . Then $C = \begin{bmatrix}2&-1\\5&1\end{bmatrix}$ (determinant $7$ ), $D = \operatorname{diag}(6, -1)$ and $C^{-1} = \tfrac17\begin{bmatrix}1&1\\-5&2\end{bmatrix}$ . Check: $CD = \begin{bmatrix}12&1\\30&-1\end{bmatrix}$ and $CDC^{-1} = \tfrac17\begin{bmatrix}7&14\\35&28\end{bmatrix} = \begin{bmatrix}1&2\\5&4\end{bmatrix}$ .

useApostol 4.10 #2(d), MATH 375 HW10

Is $A = \begin{bmatrix}2&1\\-1&0\end{bmatrix}$ diagonalizable?

Solution

Trace $2$ , determinant $1$ , so $p_A = \lambda^2 - 2\lambda + 1 = (\lambda - 1)^2$ and $m(1) = 2$ . $A - I = \begin{bmatrix}1&1\\-1&-1\end{bmatrix}$ gives $x + y = 0$ , so $E(1)$ is spanned by $(1, -1)$ and $g(1) = 1$ . Since $g < m$ , $A$ is not diagonalizable.

useMATH 375 Lecture 18

For $A = \begin{bmatrix}7&-8\\4&-5\end{bmatrix}$ find a formula for $A^k$ , and then $A^{100}$ .

Solution

Trace $2$ , determinant $-35 + 32 = -3$ , so $p_A = \lambda^2 - 2\lambda - 3 = (\lambda - 3)(\lambda + 1)$ . For $3$ : $3I - A = \begin{bmatrix}-4&8\\-4&8\end{bmatrix}$ gives $u_1 = (2, 1)$ . For $-1$ : $-I - A = \begin{bmatrix}-8&8\\-4&4\end{bmatrix}$ gives $u_2 = (1, 1)$ . With $C = \begin{bmatrix}2&1\\1&1\end{bmatrix}$ , $C^{-1} = \begin{bmatrix}1&-1\\-1&2\end{bmatrix}$ , and $D^k = \operatorname{diag}(3^k, (-1)^k)$ :

A^k = CD^kC^{-1} = \begin{bmatrix}2\cdot3^k - (-1)^k & -2\cdot3^k + 2(-1)^k\\ 3^k - (-1)^k & -3^k + 2(-1)^k\end{bmatrix}.

Check $k = 1$ : $\begin{bmatrix}7&-8\\4&-5\end{bmatrix}$ . Check $k = 2$ : $\begin{bmatrix}17&-16\\8&-7\end{bmatrix}$ , which equals $A\cdot A$ . For $k = 100$ , $(-1)^{100} = 1$ : $A^{100} = \begin{bmatrix}2\cdot3^{100} - 1 & 2 - 2\cdot3^{100}\\ 3^{100} - 1 & 2 - 3^{100}\end{bmatrix}$ .

useApostol 4.4 #7, MATH 375 HW9

Let $V$ be the continuous functions on $\mathbb R$ for which $\int_{-\infty}^x f(t)\,dt$ exists for every $x$ , and let $T(f)(x) = \int_{-\infty}^x f(t)\,dt$ . Show that every positive $\lambda$ is an eigenvalue of $T$ , meaning there is a non-zero $f$ in $V$ with $T(f) = \lambda f$ .

Solution

Fix $\lambda > 0$ and let $f(x) = e^{x/\lambda}$ . It is continuous. Then $\int_{-\infty}^x e^{t/\lambda}\,dt = \lambda e^{x/\lambda}$ , which exists because $1/\lambda > 0$ makes $e^{t/\lambda} \to 0$ as $t \to -\infty$ . So $f \in V$ and $T(f) = \lambda f$ , with $f \ne O$ . (Conversely, if $Tf = \lambda f$ then $f = \lambda^{-1}\int f$ is differentiable with $\lambda f' = f$ , so $f = Ke^{x/\lambda}$ , and for $\lambda < 0$ this blows up at $-\infty$ so the integral does not exist. So only positive $\lambda$ occur.)

proveApostol 4.8 #10, MATH 375 HW9

Prove that $A$ and $A^{\mathsf T}$ have the same characteristic polynomial. Do they have the same eigenvectors?

Solution

$(\lambda I - A)^{\mathsf T} = \lambda I^{\mathsf T} - A^{\mathsf T} = \lambda I - A^{\mathsf T}$ , because $I^{\mathsf T} = I$ and the transpose of a difference is the difference of transposes. A matrix and its transpose have the same determinant (2.7). So $\det(\lambda I - A^{\mathsf T}) = \det((\lambda I - A)^{\mathsf T}) = \det(\lambda I - A)$ . The eigenvectors can differ: for $A = \begin{bmatrix}3&1\\0&2\end{bmatrix}$ the eigenvector for $3$ is $(1, 0)$ , but $A^{\mathsf T} = \begin{bmatrix}3&0\\1&2\end{bmatrix}$ has $(1, 1)$ for $3$ , since $A^{\mathsf T}(1,1) = (3, 3)$ .

proveApostol 4.4 #2, MATH 375 HW9

Let $Ax = \lambda x$ with $x \ne O$ . (a) For a polynomial $q(t) = c_0 + c_1t + \dots + c_mt^m$ , prove $q(A)x = q(\lambda)x$ , where $q(A) = c_0I + c_1A + \dots + c_mA^m$ . (b) If $A$ is invertible, prove $\lambda \ne 0$ and $A^{-1}x = \lambda^{-1}x$ .

Solution

(a) By the worked example above, $A^jx = \lambda^jx$ for $j \ge 1$ , and $A^0x = Ix = x = \lambda^0x$ . Then $q(A)x = c_0x + c_1\lambda x + \dots + c_m\lambda^mx = q(\lambda)x$ by linearity.

(b) If $\lambda = 0$ then $Ax = O$ with $x \ne O$ , so $A$ is not one-to-one, contradicting invertibility. So $\lambda \ne 0$ . Apply $A^{-1}$ to $Ax = \lambda x$ : $x = \lambda A^{-1}x$ . Divide by $\lambda$ : $A^{-1}x = \lambda^{-1}x$ .

proveApostol 4.10 #1, MATH 375 HW10

Prove that $A = \begin{bmatrix}1&1\\0&1\end{bmatrix}$ and $I$ have the same eigenvalues but are not similar.

Solution

Both have characteristic polynomial $(\lambda - 1)^2$ , so the eigenvalues coincide ( $1$ , twice). Suppose $A = CIC^{-1}$ for some invertible $C$ . Then $A = CC^{-1} = I$ , which is false. So no such $C$ exists, and $A$ is not similar to $I$ . (In general the identity is similar only to itself.)

provesupports Apostol 4.9

Prove that $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ for $n\times n$ matrices, and deduce $\operatorname{tr}(C^{-1}AC) = \operatorname{tr}A$ .

Solution

The $(i, i)$ entry of $AB$ is $\sum_j a_{ij}b_{ji}$ , so $\operatorname{tr}(AB) = \sum_i\sum_j a_{ij}b_{ji}$ . Likewise $\operatorname{tr}(BA) = \sum_j\sum_i b_{ji}a_{ij}$ . These are the same double sum with the order of summation exchanged and the factors in the other order, so they are equal. Then $\operatorname{tr}\big(C^{-1}(AC)\big) = \operatorname{tr}\big((AC)C^{-1}\big) = \operatorname{tr}A$ , applying the first part with the matrices $C^{-1}$ and $AC$ .

proveApostol 4.4 #4, MATH 375 HW9

Let $T$ be a linear map from $V$ to $V$ . If $\lambda^2$ is an eigenvalue of $T^2 = T\circ T$ (for a real number $\lambda$ ), prove that $\lambda$ or $-\lambda$ is an eigenvalue of $T$ .

Solution

Let $x \ne O$ with $T^2x = \lambda^2x$ . Since $T$ commutes with $I$ , $(T - \lambda I)(T + \lambda I) = T^2 - \lambda^2I$ , so $(T - \lambda I)\big((T + \lambda I)x\big) = O$ . Let $y = (T + \lambda I)x$ . If $y = O$ , then $Tx = -\lambda x$ with $x \ne O$ , so $-\lambda$ is an eigenvalue. If $y \ne O$ , then $(T - \lambda I)y = O$ says $Ty = \lambda y$ with $y \ne O$ , so $\lambda$ is an eigenvalue. Either way one of them is.

stretchApostol 4.4 #9, MATH 375 HW9 (the answer key shows only one half of the argument)

Let $V = \{f \in C^2[0, \pi] : f(0) = f(\pi) = 0\}$ (twice continuously differentiable functions that vanish at both ends) and $T(f) = f''$ . Here $f''$ is only continuous and need not vanish at the ends, so $T(f)$ may leave $V$ . An eigenfunction here means a non-zero $f$ in $V$ with $f'' = \lambda f$ . Prove that the eigenvalues of $T$ are exactly $-n^2$ for $n = 1, 2, 3, \dots$ , with eigenfunctions $c\sin nt$ .

Solution

Each $\sin nt$ is in $V$ (it vanishes at $0$ and $\pi$ ) and $(\sin nt)'' = -n^2\sin nt$ , so $-n^2$ is an eigenvalue. (The key’s printed pair $(n^2, \sin nt)$ has the wrong sign.) Now suppose $f \ne O$ , $f \in V$ , $f'' = \lambda f$ . The solutions of this equation are known from MATH 376.

$\lambda > 0$ , $w = \sqrt\lambda$ : $f = Ae^{wt} + Be^{-wt}$ . $f(0) = 0$ gives $B = -A$ . $f(\pi) = A(e^{w\pi} - e^{-w\pi}) = 0$ and $e^{w\pi} \ne e^{-w\pi}$ force $A = 0$ , so $f = O$ . No eigenvalue.
$\lambda = 0$ : $f = a + bt$ . $f(0) = 0$ gives $a = 0$ and $f(\pi) = b\pi = 0$ gives $b = 0$ . No eigenvalue.
$\lambda = -w^2$ , $w > 0$ : $f = c_1\cos wt + c_2\sin wt$ . $f(0) = 0$ gives $c_1 = 0$ . Then $f(\pi) = c_2\sin w\pi = 0$ with $c_2 \ne 0$ (else $f = O$ ) forces $\sin w\pi = 0$ , so $w$ is a positive integer $n$ .

So the eigenvalues are exactly $-n^2$ , and $E(-n^2)$ is spanned by $\sin nt$ . This same computation gives the quantum energy levels $E_n \propto n^2$ above.

stretchMATH 375 Lecture 17 (Cayley–Hamilton bonus)

Let $A$ be a diagonalizable $n\times n$ matrix with characteristic polynomial $p$ . Prove $p(A) = O$ . Then check it for $A = \begin{bmatrix}1&2\\5&4\end{bmatrix}$ .

Solution

Let $u_1, \dots, u_n$ be an eigenbasis with eigenvalues $\lambda_1, \dots, \lambda_n$ . By part (a) of the problem on polynomials, $p(A)u_k = p(\lambda_k)u_k = 0\cdot u_k = O$ , because each $\lambda_k$ is a root of $p$ . So $p(A)$ sends every basis vector to $O$ . Every $x$ is $\sum c_ku_k$ , and $p(A)$ is linear, so $p(A)x = \sum c_kp(A)u_k = O$ . Hence $p(A) = O$ . (The theorem is true for every square matrix, but the general proof needs more. Spagnolie said it was “harder, later in the book”; Apostol proves it in section 7.)

For $A = \begin{bmatrix}1&2\\5&4\end{bmatrix}$ we have $p = \lambda^2 - 5\lambda - 6$ and $A^2 = \begin{bmatrix}11&10\\25&26\end{bmatrix}$ . So $A^2 - 5A - 6I = \begin{bmatrix}11-5-6&10-10\\25-25&26-20-6\end{bmatrix} = O$ .

Summary

An eigenvector of $T$ is a non-zero $x$ with $T(x) = \lambda x$ , a direction that is only stretched. $\lambda$ is its eigenvalue. The vectors for one $\lambda$ , plus $O$ , form the eigenspace $E(\lambda) = N(T - \lambda I)$ , a subspace.
Eigenvectors for different eigenvalues are independent (proof: apply $T$ , subtract $\lambda_k$ times the original, induct). So $n$ distinct eigenvalues give a basis.
Eigenvalues are the roots of the characteristic polynomial $\det(\lambda I - A)$ , because $\lambda I - A$ must have a non-zero null vector, so be non-invertible. Its form is $\lambda^n - (\operatorname{tr}A)\lambda^{n-1} + \dots + (-1)^n\det A$ .
With multiplicity, the trace is the sum of the eigenvalues and the determinant is the product. Similar matrices share all of these, so they belong to the map and not to the basis.
$A$ is diagonalizable iff there is a basis of eigenvectors, iff $A = CDC^{-1}$ . Then $A^k = CD^kC^{-1}$ : powers are easy, which gives Fibonacci’s closed form, population growth rates and solutions of $y' = Ay$ .
It fails when an eigenvalue has fewer independent eigenvectors than its multiplicity as a root ( $g < m$ , the shear), and over $\mathbb R$ when the roots are complex (the rotation). Diagonalizable iff $g = m$ for every eigenvalue.
The same idea works on function spaces: $e^{\lambda t}$ for $d/dt$ , $\sin nt$ for $d^2/dt^2$ with fixed ends (quantum energy levels).
Coming later: Jordan form (3.6) repairs the shear, and the spectral theorem (3.1) says symmetric matrices have a perpendicular eigenbasis.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture

The idea, in words

Definitions and theorems

Eigenvectors and eigenvalues

Eigenvector

Eigenvalue

An eigenvector has only one eigenvalue

Eigenspace

Eigenspaces are subspaces

Eigenvectors for different eigenvalues are independent

Eigenvectors of distinct eigenvalues are independent

Distinct eigenvalues give an eigenbasis

Finding eigenvalues: the characteristic polynomial

Characteristic polynomial

Eigenvalues are roots of the characteristic polynomial

Trace, and the shape of the characteristic polynomial

Trace

Shape of the characteristic polynomial

Trace and determinant from the eigenvalues

Same map, different basis

Diagonalization

Diagonalizable

Diagonal form means an eigenbasis

Diagonalization as a factorization

Distinct roots give a diagonalizable matrix

When diagonalization fails: multiplicities

Geometric multiplicity is at most algebraic multiplicity

Diagonalizable exactly when the eigenspaces fill the space

Examples and non-examples

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere