Diagonalisation and dynamics

Take the matrix from the last section, $A=\left(\begin{array}{cc}2& 1\\ 0& 1\end{array}\right)$, and apply it to the vector $(0,1)$ again and again. The results form a small table.

!Applying $\left(\begin{array}{cc}2& 1\\ 0& 1\end{array}\right)$ to $(0,1)$ again and again puts the state at $(2^t-1,1)$. The points run along $y=1$ toward the eigenvector $(1,0)$: the component along $(1,-1)$ stays put while the other doubles at every step. The upper panel enlarges the first four steps. Status: re-simulated.

The second coordinate never moves. The first one doubles and adds one at each step, so after $t$ steps it equals $2^t-1$. The table answers a question about a process that runs forever, and it answers it with one short formula. !Two matrices, two outcomes for the eigenbasis. On the left, two independent eigendirections span the plane, so the start $s$ splits into $2v_1-v_2$ and each coefficient evolves alone. On the right, the shear $\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$ supplies one eigendirection, and no split into two independent pieces exists. Status: schematic.

This is what happens when you apply the same matrix many times. The matrix is a rule, the vector is a state, and each application is one step of a dynamical system. The long-run behaviour is the thing you want to predict. Eigenvectors make that prediction cheap, because a vector in an eigendirection is multiplied by its eigenvalue and never mixed with anything else.

Suppose the eigenvectors of $A$ form a basis. A basis is a set of vectors that builds every vector in the space in exactly one way, so the recipe is unique. When the basis is made of eigenvectors it is called the eigenbasis. Write the starting vector in that basis,

where $c_1$ and $c_2$ are the coefficients: the amounts of each eigenvector the start contains.

Then each application multiplies the two coefficients by their own eigenvalues, so

That formula is the whole of diagonalisation in two dimensions. In matrix form it reads $A=PD{P}^{-1}$, where the columns of $P$ are the eigenvectors and $D$ holds the eigenvalues on its diagonal. The inverse $P^{-1}$ is the matrix that undoes $P$, so that $P^{-1}P=I$. The formula follows because $P$ turns coefficients into vectors, $D$ multiplies each coefficient by its eigenvalue, and $P^{-1}$ turns the result back into coefficients. Raising $A$ to a power then means raising the two diagonal numbers to that power, which is how Axler computes a high power of a matrix [S:24:181].

The formula also says what the matrix cannot do. It cannot mix the two eigendirections, because each is carried to itself. All the mixing happens once, when the start is written in the eigenbasis. After that the two coefficients evolve alone, and the state is their sum.

The eigenbasis exists exactly when the eigenvectors are numerous enough to span the space [S:24:179]. To span the space means that every vector in it is a combination of the eigenvectors, with none left out. When they span it, the matrix becomes diagonal in that basis, and the dynamics separates into independent one-dimensional pieces.

Worked example. For the matrix above, the eigenvectors are $(1,0)$ with eigenvalue $2$ and $(1,-1)$ with eigenvalue $1$. The starting vector is their difference:

After $t$ steps the first term is $2^t(1,0)$ and the second is $1^t(1,-1)$, so

At $t=5$ this gives $(31,1)$, which matches the table. The eigenvalue $2$ controls the growth, and the eigenvalue $1$ contributes a constant that never dies.

When one eigenvalue is larger in modulus than the other, its term dominates. The two terms point along different eigenvectors, so they are compared through their coefficients, not their lengths. The coefficient $c_2{\lambda }_2^t$ divided by $c_1{\lambda }_1^t$ is $(c_2/c_1)({\lambda }_2/{\lambda }_1{)}^t$, whose modulus shrinks by the factor $|{\lambda }_2/{\lambda }_1|$ at every step. Here that factor is $1/2$, so after ten steps the second term is $1/1024$ of the first, about one part in a thousand.

That ratio is the reason a repeated matrix has a dominant direction. If $|{\lambda }_1|>|{\lambda }_2|\ge \cdots$ and the start has a nonzero coefficient on $v_1$, the direction of the state settles on the line of $v_1$, because every other coefficient shrinks relative to the first. A positive ${\lambda }_1$ makes the arrow tend to $v_1$ itself; a negative ${\lambda }_1$ makes it alternate between the two ends of that line.

The dominant eigenvalue is the one with the largest absolute value, and it sets the long-run growth rate. It need not be the largest signed eigenvalue: for $\mathrm{diag}(-5,1)$ the dominant eigenvalue is $-5$, and the state alternates while growing by a factor of $5$ per step.

Two eigenvalues of equal modulus behave differently from one large and one small, and equal modulus is not the same as equal value. If ${\lambda }_2=-{\lambda }_1$, the two coefficients keep the same size forever, so the state alternates between two mixtures instead of settling. If ${\lambda }_1={\lambda }_2=\lambda$ and the matrix is diagonalisable, then $A=\lambda I$ and every direction is an eigenvector, so no direction is distinguished.

If a negative eigenvalue has the smaller modulus, its term alternates in sign while shrinking relative to the first [S:27:112]. If it has the larger modulus, it dominates instead, and the state alternates along its eigenvector while growing. A complex pair, which a real matrix can have, makes the state rotate instead of settling on a line [S:24:150].

The idea fails when there is no eigenbasis. The shear $\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$ has the repeated eigenvalue $2$ but only one independent eigenvector, so it is not diagonalisable [S:27:114]. It is called defective for that reason [S:27:117]. Its powers still grow like $2^t$, but with an extra factor of $t$: writing $A=2I+S$ with $S^2=0$ gives $A^t=2^{t}I+t{2}^{t-1}S$, so the clean two-term formula does not apply.

A real rotation fails differently: it has no real eigenvector at all, so over the reals it cannot be diagonalised either [S:24:149]. The general repair is the Jordan form, a change of basis that makes the matrix as close to diagonal as possible, with ones on the diagonal above it where directions are missing [S:24:338]. That construction is a later chapter's business.

There is a second cost. The formula describes the limit, not the route. If two eigenvectors point in nearly the same direction, the change of basis is nearly singular, so the coefficients $c=P^{-1}v$ can be huge even when $v$ is small. The two terms then cancel for many steps before the dominant one wins. Eigenvalues alone do not warn you about that, but the size of $P^{-1}$ does.

The formal statement. Let $A$ be an $n\times n$ matrix over $\mathbb{R}$ or $\mathbb{C}$. The matrix is diagonalisable when $A=PD{P}^{-1}$ for an invertible $P$ and a diagonal $D$. Equivalently, the eigenvectors of $A$ form a basis of the space. Equivalently, the eigenspaces of the distinct eigenvalues fill it: the space is the direct sum $\mathrm{null}(A-{\lambda }_{1}I)\oplus \cdots \oplus \mathrm{null}(A-{\lambda }_{m}I)$ [S:24:179]. Then $P$ holds the eigenvectors as columns and $D$ holds their eigenvalues on the diagonal.

The derivation. Suppose $A=PD{P}^{-1}$. Induction on $t$ gives $A^t=P{D}^t{P}^{-1}$, because every inner pair $P^{-1}P$ cancels. For a vector $v=Pc$, where $c$ holds the coefficients, $A^{t}v=P{D}^{t}c$. In the eigenbasis that reads $c_1{\lambda }_1^t{v}_1+\cdots +c_m{\lambda }_m^t{v}_m$. The mixing happens once, in the change of coordinates, and never again. The converse is the step I omit. If the eigenvectors span the space, the matrix of the operator in that basis is diagonal, so $A=PD{P}^{-1}$. That step is the definition of the matrix of an operator in a basis [S:24:181].

The edge case. The shear $A=\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$ has the repeated eigenvalue $2$ and one eigendirection, so it has no eigenbasis [S:27:114]. Its powers do not follow the two-term formula. Write $A=2I+S$ with $S=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$. Then $S^2=0$, and the binomial expansion stops after two terms: $A^t=2^{t}I+t{2}^{t-1}S$. The factor $t$ is the signature of the missing eigenvector. Growth by ${\lambda }^t$ alone would be wrong by a polynomial factor, and no choice of basis removes it. The Jordan form is the general repair [S:28:134].

What the core hid. The core wrote "the eigenvectors form a basis" as a condition and then treated it as typical. It is typical for symmetric matrices and for matrices with distinct eigenvalues [S:27:117], but not for all matrices. The core's table and its two-by-two example both happen to be diagonalisable, so a reader could finish 9.2 believing that every matrix has an eigenbasis. The formal statement shows that this is an extra hypothesis, and 9.4 shows which matrices satisfy it automatically.

Where the analogy breaks. "Each application multiplies each coefficient by its own eigenvalue" describes the diagonalisable case only. With a defective matrix the coefficients do not stay independent, because one direction feeds the next. A near-defective matrix sits between the two cases. The eigenbasis exists, but $P$ is nearly singular, so the coefficients $c=P^{-1}v$ can be huge even when $v$ is small. The two terms then cancel for many steps before the larger eigenvalue wins. The eigenvalues are unchanged in that regime. The size of $P^{-1}$ is what changes, which is why an eigenvalue table alone does not predict the transient.

Original sources. The condition for an eigenbasis is Theorem 5.55 in Axler, which lists four equivalent statements [S:24:179]. Diagonalisation as a tool for high powers is in Axler's diagonalisation section and in the PageRank example in MML [S:24:181][S:27:120]. The dynamics of a stochastic matrix carry the names of Perron, 1907, and Frobenius, 1908 [S:66:547]. The statement you need is that an irreducible nonnegative matrix has a unique largest real eigenvalue, and its eigenvector can be chosen with strictly positive entries [S:55:20].

An open question. For a Markov chain, the gap between the eigenvalue $1$ and the second-largest magnitude controls how many steps the distribution needs to come close to its limit. The field has not settled how to predict that gap for the graphs that appear in practice, because the gap depends on global structure rather than on local degree counts. Evidence that would settle a given case: a bound computed from the graph, checked against the measured iteration count on the same graph, and then tested on graphs the bound was not fitted to.

A frontier result. PageRank is the fixed vector of a stochastic matrix, and it is found by iterating the matrix from a starting vector [S:27:120]. The same computation is the power method of 9.3. At web scale iteration replaces elimination. Gaussian elimination is cubic, the transition matrix is sparse, and the iteration uses about ten nonzeros per column [S:57:200].

What to read next. Read Axler's diagonalisation section for the four conditions [S:24:179]. Read Solomon's subsection on special properties for the Jordan form as the repair [S:28:134]. Read the Monte Carlo chapter of Goodfellow for the Markov-chain reading of repeated multiplication [S:66:547]. Then read the PageRank chapter of Mining of Massive Datasets for the engineering constraints [S:57:200]. A slow gap is not an error in the computation. It is a property of the graph, and it sets the price of the answer.