Diagonalisation and powers

Applying a matrix a thousand times is a thousand matrix multiplications in general and a single exponentiation along an eigenvector, so a basis of eigenvectors converts the hard problem into the easy one.

The previous two lessons supply everything needed. A change of basis replaces $A$ by $P^{- 1} A P$ , where the columns of $P$ are the new basis vectors. An eigenvector is a direction the transformation merely scales. Putting the two together is this lesson.

The factorisation

Suppose an $n$ by $n$ matrix $A$ has $n$ independent eigenvectors $v_{1}, \dots, v_{n}$ , with eigenvalues $λ_{1}, \dots, λ_{n}$ . Let $P$ be the matrix whose columns are those eigenvectors, and $D$ the diagonal matrix with the eigenvalues down the diagonal in the same order.

Consider $A P$ . Its $j$ th column is $A$ applied to the $j$ th column of $P$ , which is $A v_{j} = λ_{j} v_{j}$ . Now consider $P D$ . Its $j$ th column is $P$ applied to the $j$ th column of $D$ , which is $λ_{j}$ times the $j$ th standard basis vector, so $P$ applied to it is $λ_{j} v_{j}$ . The two agree column by column, so

A P = P D hence A = P D P^{- 1} and D = P^{- 1} A P

where $P$ is invertible precisely because the eigenvectors were assumed independent. A matrix admitting this is called diagonalisable, and $D$ is its description in the eigenvector basis: a list of stretch factors, one per direction.

Take $A = [(4, 1), (- 2, 1)]$ , whose eigenvalues were found to be $2$ and $3$ with eigenvectors $(1, 1)$ and $(2, 1)$ . Then $P = [(1, 1), (2, 1)]$ and $D = [(2, 0), (0, 3)]$ . Since $\det P = (1) (1) - (2) (1) = - 1$ , the inverse is $P^{- 1} = [(- 1, 1), (2, - 1)]$ , and multiplying out $P D P^{- 1}$ returns $[(4, 1), (- 2, 1)]$ exactly.

Example. Diagonalise $B = [(1, 2), (2, 1)]$ .

Its eigenvalues are $3$ and $- 1$ , with eigenvectors $(1, 1)$ and $(1, - 1)$ , from the previous lesson. So $P = [(1, 1), (1, - 1)]$ and $D = [(3, 0), (0, - 1)]$ . Here $\det P = - 1 - 1 = - 2$ , so $P^{- 1} = \frac{1}{2} [(1, 1), (1, - 1)]$ , which happens to be $\frac{1}{2} P$ because the eigenvectors are perpendicular and of equal length. Multiplying $P D P^{- 1}$ reproduces $B$ .

Now you. Diagonalise $C = [(2, 1), (1, 2)]$ , whose eigenvalues are $3$ and $1$ .

Answer

The eigenvectors are $(1, 1)$ for $λ = 3$ and $(- 1, 1)$ for $λ = 1$ , so $P = [(1, 1), (- 1, 1)]$ and $D = [(3, 0), (0, 1)]$ . This is the change of basis performed two lessons ago, now explained: the basis that worked was the eigenvector basis, and there was never anything else it could have been.

Powers become arithmetic

The point of the factorisation is what it does to repeated application. Since

A^{2} = (P D P^{- 1}) (P D P^{- 1}) = P D (P^{- 1} P) D P^{- 1} = P D^{2} P^{- 1}

and the same collapse happens at every stage, $A^{k} = P D^{k} P^{- 1}$ for every $k$ . Raising a diagonal matrix to a power raises each diagonal entry to that power and nothing else, so the entire cost is $n$ exponentiations plus two matrix multiplications, however large $k$ is.

Do it explicitly for $C = [(2, 1), (1, 2)]$ , with $P = [(1, 1), (- 1, 1)]$ , $D = [(3, 0), (0, 1)]$ and $P^{- 1} = \frac{1}{2} [(1, - 1), (1, 1)]$ . Multiplying out gives every entry as a combination of $3^{k}$ and $1^{k}$ :

C^{k} = \frac{1}{2} [(3^{k} + 1, 3^{k} - 1), (3^{k} - 1, 3^{k} + 1)]

At $k = 1$ that is $[(2, 1), (1, 2)]$ , correct. At $k = 3$ it gives $[(14, 13), (13, 14)]$ , and multiplying $C$ by itself three times confirms it. At $k = 5$ it gives $[(122, 121), (121, 122)]$ , which also checks. The general behaviour is now readable: every entry grows like $3^{k} / 2$ , so the matrix is asymptotically $\frac{1}{2} 3^{k}$ times the matrix of all ones, and the dominant eigenvalue dictates everything.

Example. Using the formula above, what is $C^{10}$ ?

$3^{10} = 59049$ , so the diagonal entries are $(59049 + 1) / 2 = 29525$ and the off-diagonal entries are $(59049 - 1) / 2 = 29524$ . Ten matrix multiplications avoided, and the answer is exact.

Now you. What is $C^{4}$ ?

Answer

$3^{4} = 81$ , so $C^{4} = [(41, 40), (40, 41)]$ . Checking against $C^{3} = [(14, 13), (13, 14)]$ : multiplying by $C$ gives first column $14 (2, 1) + 13 (1, 2) = (28 + 13, 14 + 26) = (41, 40)$ , which agrees.

A Markov chain

Here is the machinery on a problem worth solving. Two mobile networks compete. Each month, $10$ per cent of network A's customers leave for B, and $20$ per cent of B's leave for A. Writing the state as the pair of market shares, the update is $x_{k + 1} = M x_{k}$ with

M = [(0.9, 0.1), (0.2, 0.8)]

whose first column says where A's customers go and whose second says where B's go. Each column sums to one, since customers are not created or destroyed, which is what makes this a Markov matrix.

Find the eigenvalues. The trace is $1.7$ and the determinant is $0.72 - 0.02 = 0.70$ , so $λ^{2} - 1.7 λ + 0.7 = 0$ , which factors as $(λ - 1) (λ - 0.7) = 0$ . The eigenvalue $1$ is not a coincidence. Every column of $M - I$ sums to zero, so adding all the rows of $M - I$ together gives a row of zeros, which makes the rows dependent and the matrix singular. Hence $\det (M - I) = 0$ , and $λ = 1$ is an eigenvalue of every Markov matrix.

The eigenvector for $λ = 1$ solves $(M - I) v = 0$ , where $M - I = [(- 0.1, 0.1), (0.2, - 0.2)]$ has rows $(- 0.1, 0.2)$ and $(0.1, - 0.2)$ , so $v_{1} = 2 v_{2}$ and the eigenvector is $(2, 1)$ , or as shares, $(2 / 3, 1 / 3)$ . For $λ = 0.7$ , the matrix $M - 0.7 I = [(0.2, 0.1), (0.2, 0.1)]$ has rows $(0.2, 0.2)$ and $(0.1, 0.1)$ , so $v_{1} = - v_{2}$ and the eigenvector is $(1, - 1)$ .

Now start with everyone on network A, $x_{0} = (1, 0)$ , and write it in the eigenvector basis: $a (2, 1) + b (1, - 1) = (1, 0)$ gives $a = b = 1 / 3$ . Then

x_{k} = \frac{1}{3} (2, 1) + \frac{1}{3} (0.7)^{k} (1, - 1)

because each eigenvector component is multiplied by its own eigenvalue each month. The first term never changes. The second decays by a factor $0.7$ per month, so the shares converge to $(2 / 3, 1 / 3) = (66.7 %, 33.3 %)$ whatever the starting point, and the speed of the approach is set by the second eigenvalue.

Check at $k = 5$ : ${0.7}^{5} = 0.16807$ , so the formula gives $(0.6667 + 0.0560, 0.3333 - 0.0560) = (0.7227, 0.2773)$ . Multiplying by $M$ five times directly gives $(0.9, 0.1)$ , then $(0.83, 0.17)$ , $(0.781, 0.219)$ , $(0.7467, 0.2533)$ and finally $(0.72269, 0.27731)$ . The two agree to every digit shown.

This is the whole method of eigenvalue analysis of a repeated process, and it reads off three things that simulation gives only slowly: the limit, the fact that the limit is independent of the start, and the rate of approach.

Example. For $M^{'} = [(0.8, 0.2), (0.3, 0.7)]$ , find the long-run shares.

Trace $1.5$ , determinant $0.56 - 0.06 = 0.50$ , so $λ^{2} - 1.5 λ + 0.5 = 0$ and the eigenvalues are $1$ and $0.5$ . For $λ = 1$ : $M^{'} - I = [(- 0.2, 0.2), (0.3, - 0.3)]$ , whose first row is $(- 0.2, 0.3)$ , so $0.2 v_{1} = 0.3 v_{2}$ and $v = (3, 2)$ . As shares that is $(0.6, 0.4)$ , and checking, $M^{'} (0.6, 0.4) = 0.6 (0.8, 0.2) + 0.4 (0.3, 0.7) = (0.48 + 0.12, 0.12 + 0.28) = (0.6, 0.4)$ , fixed as it should be. The deviation halves each step, since the second eigenvalue is $0.5$ .

Now you. In the original chain, how many months until the deviation from the steady state falls below one per cent of its initial size?

Answer

The deviation is multiplied by $0.7$ each month, so it needs ${0.7}^{k} < 0.01$ , that is $k > \ln (0.01) / \ln (0.7) = (- 4.605) / (- 0.3567) = 12.9$ . So thirteen months. Note that the answer depends only on the second eigenvalue and not at all on the starting shares.

Fibonacci in closed form

The same trick produces a formula for a sequence defined by a rule. The Fibonacci numbers satisfy $F_{k + 1} = F_{k} + F_{k - 1}$ with $F_{0} = 0$ and $F_{1} = 1$ . Package two consecutive terms as a vector: if $u_{k} = (F_{k + 1}, F_{k})$ then $u_{k + 1} = A u_{k}$ with $A = [(1, 1), (1, 0)]$ , since the new pair is $(F_{k + 1} + F_{k}, F_{k + 1})$ .

The trace is $1$ and the determinant is $- 1$ , so $λ^{2} - λ - 1 = 0$ and the eigenvalues are

λ = \frac{1 \pm \sqrt{5}}{2}

that is $φ = 1.618034$ , the golden ratio, and $ψ = - 0.618034$ . Diagonalising and reading off the second component gives Binet's formula,

F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}

Test it at $n = 10$ : $φ^{10} = 122.9919$ and $ψ^{10} = 0.008131$ , so $F_{10} = 122.9837 / 2.23607 = 55.000$ , which is correct. Since $| ψ | < 1$ its powers vanish, so $F_{n}$ is the nearest whole number to $φ^{n} / \sqrt{5}$ , and consecutive Fibonacci numbers have ratio tending to $φ$ . A formula built entirely out of irrational numbers returns whole numbers every time, which is the two irrational parts cancelling exactly.

When it fails, and one guarantee

Not every matrix is diagonalisable. The shear $[(1, 0), (1, 1)]$ has only one independent eigenvector, so no basis of eigenvectors exists and no $P$ can be built. Since similarity preserves the eigenvalues, and a diagonal matrix similar to it would have to be $I$ , and the only matrix similar to $I$ is $I$ itself, the shear is provably not diagonalisable rather than merely resistant.

One condition is easy to check and covers most cases: if the $n$ eigenvalues are distinct, the matrix is diagonalisable. The reason is that eigenvectors with different eigenvalues are automatically independent. Suppose $v_{1}$ and $v_{2}$ have distinct eigenvalues and $c_{1} v_{1} + c_{2} v_{2} = 0$ . Apply $A$ to get $c_{1} λ_{1} v_{1} + c_{2} λ_{2} v_{2} = 0$ , and subtract $λ_{2}$ times the first relation to get $c_{1} (λ_{1} - λ_{2}) v_{1} = 0$ . Since $λ_{1} \neq λ_{2}$ and $v_{1} \neq 0$ , we get $c_{1} = 0$ , and then $c_{2} = 0$ too. The same argument extended by induction handles $n$ eigenvectors.

Distinct eigenvalues are sufficient and not necessary: the identity has every eigenvalue equal and is already diagonal. The genuine criterion is that each repeated eigenvalue must supply as many independent eigenvectors as its multiplicity in the characteristic polynomial, and a defective matrix is one where it does not.

Honest limits

Diagonalisation over the real numbers fails for rotations, which have no real eigenvectors at all, and over the complex numbers it fails for defective matrices such as the shear. The complete answer is the Jordan form, in which any matrix is similar to a nearly diagonal one with the eigenvalues on the diagonal and some ones just above it, one for each missing eigenvector. It is a theoretical instrument only: the Jordan form is discontinuous in the entries, so any rounding destroys it, and no numerical library computes it.

The factorisation is also useless when $P$ is badly conditioned, meaning the eigenvectors are nearly parallel. Then $P^{- 1}$ has enormous entries, and the near-cancellation that follows swamps the answer. The tell is that a matrix close to a defective one has eigenvectors close to parallel, so being nearly defective is the practical version of being defective.

Finally, this whole method requires the same matrix to be applied repeatedly. A process whose matrix changes at every step gets no benefit, since $A_{2} A_{1}$ has no relation to the eigenvectors of either factor.

One family of matrices escapes every one of these problems. Symmetric matrices always have a full set of eigenvectors, always have real eigenvalues, and their eigenvectors are always perpendicular, which makes $P$ orthogonal and $P^{- 1}$ free. That is the last lesson, together with what such matrices are for.