The same map in a better basis

A matrix is not a map. It is a map plus a choice of grid to measure against, and the four numbers in it depend on both. Reading a matrix as a deformation of the grid makes that concrete: the columns are where the two grid arrows land, so changing which arrows count as the grid changes every entry while the deformation stays exactly where it was.

That freedom is worth spending. A map has directions it leaves alone; if those directions are used as the grid, the map cannot shear anything, because shearing is what happens to arrows that get turned, and along an invariant direction nothing is turned.

What the middle panel is claiming #

Write $P$ for the matrix whose columns are the two eigenvectors. As a map, $P$ takes the ordinary grid arrows to the eigenvectors, so it translates from eigen-coordinates into ordinary coordinates. Its inverse goes the other way.

Then

$$A = P D P^{-1}, \qquad D = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix},$$

which is read right to left as a sentence: put the arrow into eigen-coordinates, stretch each coordinate by its own eigenvalue, put it back.

Checking the sentence is a two-line computation. Applying $PDP^{-1}$ to the first eigenvector, $P^{-1}$ sends it to $(1, 0)$; $D$ sends that to $(\lambda_1, 0)$; $P$ sends that to $\lambda_1$ times the first eigenvector. That is what $A$ does to it, by definition of an eigenvector. The same for the second, and since the two eigenvectors span the plane and everything in sight is linear, the two maps agree everywhere.

The figure does not take that on trust. It multiplies $P$, $D$ and $P^{-1}$ out and compares all four entries against the matrix it started from, to eight decimal places.

Two matrices that are the same map #

Matrices $A$ and $D$ related by $A = PDP^{-1}$ are called similar, and the relation is exactly these describe one map against two different grids. Similar matrices therefore agree about everything that is a property of the map rather than of the description: the same eigenvalues, the same determinant, the same trace, the same characteristic polynomial.

That last agreement is worth checking against the arithmetic, because it is easy to say and not obvious. The determinant of a product is the product of the determinants, so

$$\det(PDP^{-1}) = \det(P)\det(D)\det(P)^{-1} = \det(D),$$

the outer factors cancelling because they are numbers and numbers commute. The trace needs a different fact, that $\operatorname{tr}(MN) = \operatorname{tr}(NM)$ for any two square matrices — both sides are the same sum of products of entries, rearranged — and then $\operatorname{tr}(PDP^{-1}) = \operatorname{tr}(DP^{-1}P) = \operatorname{tr}(D)$.

So the trace and determinant of a matrix are not features of its entries. They are features of the map, and the entries are what one grid happened to make of it. That is the reason they turned out to be the whole of the characteristic polynomial: the polynomial is a question about the map, so its coefficients had to be quantities the grid cannot move.

Why anybody would want this #

The payoff is powers. Applying a map many times is what a great many questions come down to, and the diagonal form makes it almost free:

$$A^n = (PDP^{-1})(PDP^{-1}) \cdots (PDP^{-1}) = P D^n P^{-1},$$

since every interior $P^{-1}P$ collapses to the identity. Raising a diagonal matrix to a power means raising its two entries to that power, so the cost of $A^{100}$ is two exponentials and two matrix multiplications rather than ninety-nine.

More important than the cost is what the form makes visible. In eigen-coordinates the two components of a point evolve independently, one multiplied by $\lambda_1^n$ and the other by $\lambda_2^n$, and nothing mixes them. Whichever eigenvalue is larger in size wins the race, so after enough steps the point is very nearly along that eigenvector whatever it started as.

A worked case that is not a matrix problem #

The Fibonacci numbers are the standing example, and they are an example because the recurrence $F_{n+1} = F_n + F_{n-1}$ is a linear map applied over and over. Keeping the last two terms as a pair, one step is

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix},$$

so the $n$-th Fibonacci number is an entry of the $n$-th power of that matrix. Its trace is 1 and its determinant is $-1$, so the eigenvalues are the two numbers adding to 1 and multiplying to $-1$: $\varphi = (1 + \sqrt5)/2$ and $1 - \varphi = -1/\varphi$. Those are the golden ratio and its conjugate, arriving from a recurrence with no rectangle anywhere near it.

Diagonalising and reading off the top entry gives Binet’s formula,

$$F_n = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt5},$$

a closed form for a sequence defined by a rule. And the second eigenvalue has size about $0.618$, so its power shrinks: for $n$ past a handful, $F_n$ is $\varphi^n/\sqrt5$ rounded to the nearest whole number. The ratio of consecutive Fibonacci numbers tending to $\varphi$ is the power method running, on a two-by-two matrix, in a setting nobody would have called linear algebra.

That is not merely a consequence of diagonalisation; it is a way of finding the eigenvector without ever forming the characteristic polynomial. Apply the map, rescale, repeat. The method is called the power method and it is what the picture above is doing.

Two identities that fall out of the bookkeeping #

The same matrix pays for more than a closed form, and the extra facts come from the two quantities the change of grid cannot touch.

Take the determinant first. Writing $M$ for the Fibonacci matrix, its $n$-th power is

$$M^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix},$$

which is checked by induction in one line: multiplying by $M$ once more adds each pair of neighbours, which is the recurrence. The determinant of a product is the product of the determinants, so $\det(M^n) = (\det M)^n = (-1)^n$. Reading the left side off the entries,

$$F_{n+1}F_{n-1} - F_n^2 = (-1)^n.$$

That is Cassini’s identity, and it says the Fibonacci numbers miss being a geometric progression by exactly one, in alternating directions, for ever. At $n = 5$ the matrix is $\begin{pmatrix} 8 & 5 \\ 5 & 3\end{pmatrix}$ and the arithmetic is $8 \times 3 - 5^2 = -1$. Nothing about that identity mentions eigenvalues; it was obtained by asking what the map does to areas, and then asking the same question of the map applied $n$ times.

The trace gives the second identity, and it is stranger. The trace of $M^n$ is the sum of the eigenvalues of $M^n$, which are the $n$-th powers of the eigenvalues of $M$, so

$$\varphi^n + (1 - \varphi)^n = F_{n+1} + F_{n-1}.$$

The right-hand side is a whole number by construction. The left-hand side is a sum of two irrational powers, neither of which is anywhere near a whole number: at $n = 5$ they are about $11.090$ and $-0.090$, and they add to $8 + 3 = 11$. The irrational parts cancel exactly, at every $n$, because the two eigenvalues are conjugate roots of one quadratic with whole-number coefficients and the trace is a symmetric function of them. Those sums are the Lucas numbers, and they satisfy the same recurrence from a different pair of starting values.

Both identities are instances of one habit worth naming. The trace and the determinant survive a change of grid, so any quantity they compute can be read in whichever grid is convenient — in eigen-coordinates, where it is a statement about $\varphi^n$, or in ordinary coordinates, where it is a statement about whole numbers. An identity is what one invariant looks like from two directions.

How fast, and the case where it is hopeless #

The rate is readable from the same decomposition. A starting arrow is $c_1$ times the first eigenvector plus $c_2$ times the second; after $n$ steps it is $c_1\lambda_1^n$ and $c_2\lambda_2^n$, and dividing through by the first, the contamination is proportional to $(\lambda_2/\lambda_1)^n$. So the angle to the answer falls geometrically, by a factor of $|\lambda_2/\lambda_1|$ per step.

The figure measures that factor off the iteration rather than quoting it: it takes the ratio of successive angles at the end of the run and requires it to match the ratio of the eigenvalues to four decimal places. Two computations, one from the geometry of the drawing and one from the algebra, and the assertion is that they agree.

The dependence is brutal and it is the reason a whole industry of better methods exists. A ratio of $1/3$ gains about half a decimal place a step; a ratio of $0.99$ gains a decimal place every two hundred and thirty. The same arithmetic governs how fast a contraction settles onto its fixed point, and for the same reason: both are errors multiplied by a constant, and a constant just under 1 is a slow constant.

What the change of basis costs #

Nothing here is free, and it is worth being plain about where the work went.

Building $P$ requires the eigenvectors, which requires the eigenvalues, which for a large matrix is the expensive part — so diagonalising in order to compute one power is a poor trade. It pays when many powers are wanted, when the answer wanted is the behaviour as $n$ grows rather than a particular term, or when the eigen-decomposition is available for some other reason.

There is a subtler cost. Inverting $P$ is well behaved only when its columns are far from parallel. Two eigenvectors that nearly coincide make $P$ nearly singular, $P^{-1}$ enormous, and the decomposition numerically useless even though it exists — the quantity measuring this is called the condition number of the eigenvector matrix, and it is unbounded as a matrix approaches a defective one. So “diagonalisable” is not a property that can be checked by computation and then relied on. It is a yes-or-no answer to a question whose honest answer is a number. The number can be made concrete in one example. The map $\begin{pmatrix} 1 & 1 \\ 0 & 1 + \delta\end{pmatrix}$ has eigenvalues 1 and $1 + \delta$, so for any non-zero $\delta$ it is diagonalisable and the theory is satisfied. Its eigenvectors are $(1, 0)$ and $(1, \delta)$, which close to within an angle of about $\delta$ as $\delta$ shrinks, and the entries of $P^{-1}$ grow like $1/\delta$. At $\delta = 10^{-6}$ the diagonal form exists, is exact, and multiplies any rounding error in the data by roughly a million. The shear sits at $\delta = 0$, where the construction fails outright — and everything the failure does to the arithmetic, it has already started doing on the way in.

Perpendicular eigenvectors escape all of this, because a matrix with orthonormal columns has its transpose for an inverse and is as well conditioned as anything can be. Which matrices have them is the next rung, and the answer is short.

The maps this cannot be done to #

Not every map has enough invariant directions to build a grid from. The construction needs $P$ to be invertible, which needs two eigenvectors that are not parallel — and a defective matrix has only one.

It is worth being precise about what has failed. The eigenvalue is perfectly good — 1, twice — and there is a perfectly good invariant line. What is missing is a second line, and without it the plane cannot be split into two pieces the map treats separately. The shear mixes the two coordinates and no change of grid unmixes them, because the mixing is not an artefact of the grid.

The failure is not an accident of small examples. Over the real numbers it can also happen for the duller reason that the eigenvalues are complex, as they are for any rotation — although that case is repaired by allowing complex entries, after which the rotation is diagonal, with $e^{i\theta}$ and $e^{-i\theta}$ down the diagonal. The shear is not repaired by anything. It is defective over every field.

The consequence for powers is visible without any theory. The $n$-th power of the shear is the shear by $n$: the off-diagonal entry grows linearly while the eigenvalue stays at 1. A diagonalisable map with eigenvalue 1 twice over would be the identity, whose powers do nothing at all. So the defective case is not a technicality about existence — it produces behaviour, growth like $n$ rather than like $\lambda^n$, that no diagonal form can express.

What is available instead is the Jordan form, which puts the matrix as close to diagonal as it can get: eigenvalues down the diagonal and a scattering of 1s just above it, one for each missing eigenvector. The shear is already in that form. Jordan form is the right general answer and it is numerically hopeless — an arbitrarily small change to a defective matrix generally makes it diagonalisable, so which Jordan form a computed matrix has is not a question its digits can answer.

The same trick, one dimension down #

It is worth seeing what diagonalisation looks like when there is nothing to diagonalise, because that is where the idea is clearest.

A one-by-one matrix is a number, and applying it $n$ times multiplies by $\lambda^n$. Everything in this essay is a restatement of that fact for two coordinates at once, and the whole content of the diagonal form is the plane can be split into two independent copies of the one-dimensional case. Once that split exists, no reasoning about matrices is needed at all: whatever is true of repeated multiplication by a number is true, twice over, of the map.

That is why the same construction settles questions that look unrelated to each other. Whether iterating a map sends everything to the origin depends on whether both $|\lambda|$ are below 1. Whether a system of two linked differential equations grows or decays depends on the signs of the two eigenvalues. Whether a random process forgets its start depends on the size of the second eigenvalue. Three questions, one answer each, and in every case the work was done by turning a coupled problem into two uncoupled ones.

The move has a name in almost every field it turns up in and one description: find the parts the operation does not mix, and treat them separately.

Where the idea goes #

The habit generalises well past matrices. Differentiation is a linear operation on functions, and the functions it leaves alone up to a factor are the exponentials, since differentiating $e^{kx}$ multiplies it by $k$. So writing a function as a sum of exponentials is diagonalising the derivative — and writing it as a sum of sines and cosines diagonalises the second derivative, which is why heat diffusion decomposes into independent decays that never interact.

In a Markov chain the map is a matrix of transition probabilities and the dominant eigenvalue is exactly 1, with the long-run distribution as its eigenvector. The power method there is not an algorithm somebody chose; it is the chain running, and the ratio $|\lambda_2/\lambda_1|$ that governs the convergence is how quickly the process forgets where it began.

What the picture cannot show #

The three panels are drawn at one moment of one map, and the honest limitation is that the middle one is a picture of a description. Nothing physical happens when coordinates change; the arrow is where it was. The grid in the middle panel is skewed on the page precisely because it is being drawn against the ordinary grid, which is the thing it was supposed to replace — there is no way to show a coordinate system from inside itself.

The right-hand panel has the reverse problem. It reports the fifth power as four numbers because the fifth power of a map cannot be drawn as a deformation without either shrinking the picture to nothing or running off the page. Powers grow, and a page does not.

The ladder from here #

Rungs above: what forces the two directions to be perpendicular, which is a condition on the matrix and not a piece of luck. The frames every map has, including the ones with no invariant direction. Complex eigenvalues read as rotation and scaling together. Jordan form drawn rather than described. The condition number, which measures how much a change in the matrix moves its eigenvalues. And the algorithms that find eigenvalues in practice, all of which are refinements of applying the map and looking at what happens.