The polynomial whose roots are the stretches

A linear map turns almost every arrow it is handed. A few it leaves pointing where they started, longer or shorter but not turned, and those few decide what the map is like at large scale. That essay found them by looking: unit arrows were drawn, their images were drawn beside them, and the directions where the two were parallel were marked.

Looking does not scale, and looking cannot be trusted at the boundary. What is wanted is an equation.

What being left alone actually says #

An arrow $v$ is left alone by $A$, up to length, when $Av = \lambda v$ for some number $\lambda$. Rewriting that as $Av - \lambda v = 0$ and pulling out the arrow gives

$$(A - \lambda I)v = 0,$$

where $I$ is the map that does nothing and the subtraction is entry by entry. The equation now says something about the map $A - \lambda I$ rather than about $v$: there is an arrow, not the zero one, that this map sends to the origin.

A linear map that sends a non-zero arrow to the origin cannot be reversed — two different points now have the same image, so nothing can undo it. And there is already a number that measures exactly that: the determinant, which is the factor by which areas are multiplied. A map with a non-zero arrow in its kernel flattens the plane onto a line, and a line has no area.

So the condition is

$$\det(A - \lambda I) = 0,$$

and it is a condition on $\lambda$ alone. The arrow has disappeared from it entirely.

The equation, written out #

For a two-by-two matrix with entries $a$, $b$, $c$, $d$ the shifted matrix is

$$A - \lambda I = \begin{pmatrix} a - \lambda & b \\ c & d - \lambda \end{pmatrix},$$

whose determinant is $(a - \lambda)(d - \lambda) - bc$. Multiplying out,

$$\lambda^2 - (a + d)\lambda + (ad - bc).$$

Two numbers appear, and only two. The first, $a + d$, is the trace — the sum down the diagonal. The second is the determinant. Every other detail of the matrix has been thrown away, and what is left is a quadratic in $\lambda$ called the characteristic polynomial.

That is the first surprise. A two-by-two matrix has four numbers in it, and the question which directions does this map leave alone depends on only two combinations of them. Whatever else the four entries record, they record it somewhere the eigenvalues cannot see.

The figure above computes both routes at forty-one values of $\lambda$ and compares them, because a formula derived on paper and a formula implemented are different objects, and the site’s habit is to make them argue.

What the coefficients already know #

A quadratic’s roots and its coefficients are tied together: for $\lambda^2 - p\lambda + q$ with roots $\lambda_1$ and $\lambda_2$, expanding $(\lambda - \lambda_1)(\lambda - \lambda_2)$ gives $p = \lambda_1 + \lambda_2$ and $q = \lambda_1\lambda_2$. That is the elementary case of the relation between roots and coefficients that runs all the way up.

Read backwards, it says:

• the trace is the sum of the eigenvalues;
• the determinant is their product.

Both are worth pausing on. The determinant is the area factor, so the statement is that the total stretching a map does is the product of the stretches along its own two special directions — which is exactly what it ought to be, since in those directions the map is nothing but two stretches. The trace is harder to feel and easier to compute; it is the one number a matrix hands over without any work at all, and it is half of everything the eigenvalues know.

There is a working consequence. Given a matrix, the two eigenvalues can be read off by finding two numbers with the right sum and the right product, which for small whole-number matrices is faster than any formula. The map $\begin{pmatrix} 2 & 1 \\ 1 & 2\end{pmatrix}$ has trace 4 and determinant 3, so its eigenvalues are two numbers adding to 4 and multiplying to 3 — that is 1 and 3, with no algebra written down at all.

It also settles a question that would otherwise need the eigenvalues themselves. A map with a negative determinant has eigenvalues of opposite sign, because their product is negative, so it stretches along one invariant direction and reflects along the other. A map with determinant 1 and trace larger than 2 has two positive eigenvalues, one above 1 and one below, since they multiply to 1 and add to more than 2. Nothing has been computed; a pair of readings off the matrix has decided the qualitative behaviour, which is what a good invariant is for.

Three shapes, and only three #

A quadratic with real coefficients meets the axis twice, once, or not at all, and the discriminant $p^2 - 4q$ decides which. In the language of the map, $(a+d)^2 - 4(ad - bc)$ decides whether there are two invariant directions, one, or none.

The case with no real root is the honest one to draw first, because it is the case where searching for an invariant direction by eye can only ever produce a failure to find. The curve above is a proof that none exists: a parabola opening upwards whose lowest point is above the axis has no real root, and that is checkable arithmetic rather than an exhausted search.

The rotation is not an exotic example. Any map that turns everything by an angle other than a half turn has this shape of polynomial, and complex multiplication is exactly such a map — which is a hint about where the missing roots have gone, taken up in the essays on the complex plane rather than here.

The case that is not a case #

The middle possibility, one root twice over, looks like an edge case that will not matter. It matters more than either of the others, because it hides a distinction the polynomial cannot see.

A root of multiplicity two might mean two independent invariant directions that happen to be stretched by the same amount — which is what the map $2I$, a plain doubling, does, since every direction is invariant there. Or it might mean one direction and no more.

The shear is the second kind, and the way to tell is to go back to $(A - \lambda I)v = 0$ and count solutions.

For the shear, $A - I$ is the matrix with a single 1 in the top right and zeros elsewhere, which sends $(x, y)$ to $(y, 0)$. That is zero exactly when $y = 0$: one line of solutions, not two. The map has a repeated eigenvalue and a single invariant direction, and matrices like it are called defective.

This is why the figure counts the solutions by row-reducing the shifted matrix rather than by reading the multiplicity of the root. Reading the count off the polynomial is precisely the mistake the shear is there to catch — a formula that says two where the geometry says one, in the only case where anyone would be tempted to trust it.

The easy case, drawn to show it is easy #

When the matrix is triangular the polynomial factors before it is written down, because the determinant of a triangular matrix is the product of its diagonal.

That observation is small and it is the seed of a large programme. If every matrix could be rewritten as a triangular or diagonal one without changing what the map does, the eigenvalues would always be readable at a glance. Whether that rewriting is possible, and what it costs, is the next rung of this ladder.

The matrix satisfies its own equation #

Here is the fact that makes the characteristic polynomial feel less like an accounting device and more like a description.

Take the polynomial $\lambda^2 - p\lambda + q$ that the matrix produced, and substitute the matrix itself for $\lambda$, reading the constant term as $q$ times the identity. The result is the zero matrix, every time. For $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$, with $p = 4$ and $q = 3$:

$$A^2 - 4A + 3I = \begin{pmatrix} 5 & 4 \\ 4 & 5 \end{pmatrix} - \begin{pmatrix} 8 & 4 \\ 4 & 8 \end{pmatrix} + \begin{pmatrix} 3 & 0 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}.$$

This is the Cayley–Hamilton theorem, and its two-by-two case can be verified by multiplying out the general matrix, which takes four lines and no ideas. Every entry cancels.

The temptation is to prove it by substituting $A$ into $\det(A - \lambda I)$ directly and getting $\det(A - A) = \det(0) = 0$. That argument is worthless: $\det(A - \lambda I)$ is a number for each number $\lambda$, and putting a matrix where a number was is not a substitution into anything. The conclusion is right and the reasoning is a coincidence of notation, which is a good example of the kind of proof worth being suspicious of — it has the shape of an argument without any of the content.

What the theorem buys is arithmetic. It says $A^2 = 4A - 3I$, so every power of $A$ from the second upwards is a combination of $A$ and $I$ — the whole infinite sequence of powers lives in a two-dimensional space. Computing $A^{100}$ becomes a matter of reducing $\lambda^{100}$ modulo the characteristic polynomial, and the inverse comes out for free: dividing $A^2 - 4A + 3I = 0$ by $A$ gives $A^{-1} = (4I - A)/3$, an inverse obtained without a single division of entries.

What it costs in larger dimensions #

For an $n \times n$ matrix the same argument gives a polynomial of degree $n$, whose coefficients are the trace, the determinant and $n - 2$ intermediate quantities. The fundamental theorem of algebra then guarantees $n$ roots in the complex numbers, counted with multiplicity, so the eigenvalues always exist somewhere even when they are not real.

The trouble is that the polynomial is a terrible way to find them. Its coefficients are enormous alternating sums of products of matrix entries, so tiny changes in the matrix move them a great deal, and finding roots of a high-degree polynomial is numerically delicate in its own right. Every practical method for computing eigenvalues avoids forming the characteristic polynomial altogether, and one of them does nothing but apply the map repeatedly.

There is also a limit of principle. A general polynomial of degree five or more has no formula in radicals for its roots, and every polynomial is the characteristic polynomial of some matrix — the companion matrix, whose entries are the coefficients. So there is no formula for the eigenvalues of a general $5 \times 5$ matrix either. Eigenvalues are found by iteration because they cannot be found any other way.

What the picture cannot show #

The curve on the page is a real function of a real variable, and it stops at the axis. When the roots are complex the picture goes quiet exactly where the interesting thing is: it shows a parabola floating above the axis and says nothing here, when what is true is that the two roots have moved off the line into the plane. A drawing that showed them would be a drawing of a complex function of a complex variable, which needs four dimensions and is why that subject gets its own pictures.

Nor can the curve show the difference between a doubling and a shear. Both give $(\lambda - k)^2$, and the polynomial is the same object in the two cases. Everything that distinguishes them lives in the shifted matrix, which the curve has already summarised into a single number.

And a curve drawn from 241 samples is a curve drawn from 241 samples. A root that two nearby samples straddle is visible; a pair of roots closer together than the sample spacing is a curve that dips towards the axis and appears not to reach it, which is indistinguishable on the page from no root at all. Every root marked here is placed from the closed-form solution and then checked against the sampled curve, rather than found by watching for a sign change — because near a repeated root the sign never changes, and a search that looks for one finds nothing precisely where the answer is most delicate.

The ladder from here #

Rungs above: rewriting the map in the basis of its own eigenvectors, which turns it into two independent stretches. What symmetry does to the eigen-directions, and why a symmetric matrix always has real eigenvalues and perpendicular ones. The frames a map has when it has no invariant direction at all. The power method, which finds the largest eigenvalue by doing nothing but applying the map. Jordan form, which is the nearest thing to a diagonal that a defective matrix admits. And the Markov chains whose long-run behaviour is the eigenvector of the eigenvalue 1.

The move worth keeping #

The step that does all the work here is worth naming, because it recurs everywhere.

A question about a vector — is there an arrow this map leaves alone? — was turned into a question about a number, by noticing that the existence of such an arrow is equivalent to a map being non-invertible, and that non-invertibility is measured by a single quantity. The unknown arrow was eliminated rather than solved for.

The same move underlies finding a shared root of two polynomials without finding it, where a determinant again reports the existence of a solution nobody has computed. Both are instances of one habit: when an object is hard to produce, look for a number that vanishes exactly when it exists.