Matrix Powers by Diagonalization

Aⁿ = P Dⁿ P⁻¹, and a power becomes cheap.

Squaring P D P⁻¹

The matrix A = (4 −1; 2 1) diagonalizes as A = P D P⁻¹, with P = (1 1; 1 2) holding the eigenvectors (1, 1) and (1, 2) as its columns, D = (3 0; 0 2) holding the eigenvalues, and the inverse of P equal to the matrix (2 −1; −1 1).

Square it. A² = (P D P⁻¹)(P D P⁻¹). Matrix multiplication is associative, so the six factors may be grouped in any way that keeps their order: A² = P D (P⁻¹ P) D P⁻¹. The inner pair P⁻¹ P is the identity I, and multiplying by I changes nothing, so A² = P D D P⁻¹ = P D² P⁻¹.

Every power

Multiply once more by A to get the cube: A³ = (P D² P⁻¹)(P D P⁻¹) = P D² (P⁻¹ P) D P⁻¹ = P D³ P⁻¹. Each extra factor of A brings one more D into the middle and one more P⁻¹ P, which collapses to I.

With n factors of A there are n − 1 inner pairs, and every one of them is I. What is left is one P at the front, n copies of D in the middle and one P⁻¹ at the back: Aⁿ = P Dⁿ P⁻¹, for every whole number n.

Powers of a diagonal matrix

Square D = (3 0; 0 2) by multiplying rows into columns. The top left entry is 3 × 3 + 0 × 0 = 9, the bottom right is 0 × 0 + 2 × 2 = 4, and each off-diagonal entry is a sum of two products that each contain a 0, such as 3 × 0 + 0 × 2 = 0. So D squared is the matrix (9 0; 0 4): still diagonal, with each entry squared.

Every further factor of D does the same, so each entry on the diagonal is raised to the power on its own. D⁵ has 3⁵ = 243 and 2⁵ = 32 on its diagonal and zeros elsewhere.

D3002D⁵2430032→

Raising D to the fifth power raises each diagonal entry to the fifth power, 3⁵ = 243 and 2⁵ = 32, and the zeros stay zero.

A⁵ in two products

Now A⁵ = P D⁵ P⁻¹. Work from the left. Multiplying P on the right by a diagonal matrix scales its columns: the first column (1, 1) by 243 and the second column (1, 2) by 32. So P D⁵ is the matrix (243 32; 243 64).

Multiply that by the inverse of P, the matrix (2 −1; −1 1). Row 1 gives 243 × 2 + 32 × (−1) = 486 − 32 = 454 and 243 × (−1) + 32 × 1 = −211. Row 2 gives 243 × 2 + 64 × (−1) = 486 − 64 = 422 and 243 × (−1) + 64 × 1 = −179.

So A⁵ is the matrix (454 −211; 422 −179). The work was two powers of numbers and two matrix products, and it would be the same amount of work for A²⁰ or A¹⁰⁰.

P D⁵2433224364P⁻¹2−1−11A⁵454−211422−179×=

The columns of P scaled by 243 and 32, then multiplied by the inverse of P, give A to the fifth power.

Check it the long way

Multiplying A by itself step by step gives the same matrices. A² is (14 −5; 10 −1), and through the diagonal it is P D² P⁻¹: P D² is (9 4; 9 8), and multiplying by the inverse of P gives the entries 18 − 4 = 14, −9 + 4 = −5, 18 − 8 = 10 and −9 + 8 = −1, which is (14 −5; 10 −1) again.

Carrying on, A³ is (46 −19; 38 −11), A⁴ is (146 −65; 130 −49), and A⁵ is (454 −211; 422 −179), the same matrix as before. The long way took four matrix products, and every further power costs one more.

Every entry of Aⁿ

Keep n as a letter. Dⁿ has 3ⁿ and 2ⁿ on its diagonal, so P Dⁿ scales the first column of P by 3ⁿ and the second by 2ⁿ: its columns are (3ⁿ, 3ⁿ) and (2ⁿ, 2 × 2ⁿ). Multiplying by the inverse of P gives every entry of Aⁿ at once. The top row of Aⁿ is 2 × 3ⁿ − 2ⁿ and 2ⁿ − 3ⁿ, and the bottom row is 2 × 3ⁿ − 2ⁿ⁺¹ and 2ⁿ⁺¹ − 3ⁿ.

Check it at n = 1: 6 − 2 = 4, 2 − 3 = −1, 6 − 4 = 2 and 4 − 3 = 1, which is A. At n = 5: 486 − 32 = 454, 32 − 243 = −211, 486 − 64 = 422 and 64 − 243 = −179, which is A⁵.

The larger eigenvalue takes over

The first column of Aⁿ is what A does, n times over, to the column (1, 0). Write (1, 0) in eigenvector steps: (1, 0) = 2(1, 1) − (1, 2). Each application of A multiplies the first part by 3 and the second by 2, so after n steps the column is 2 × 3ⁿ (1, 1) − 2ⁿ (1, 2), which is the first column of the formula.

Divide by 3ⁿ to compare the two parts: 2(1, 1) − (2/3)ⁿ (1, 2). The factor (2/3)ⁿ shrinks toward 0, so the column points closer and closer along (1, 1), the eigenvector of the larger eigenvalue. This is how a population model behaves: Mⁿ times the starting counts gives the counts n years later, and in the long run the counts settle into the proportions of the eigenvector with the largest eigenvalue.

xy(2, 2)

The first column of Aⁿ divided by 3ⁿ, for n = 0, 1, 2, 3 and 4: (1, 0), then (4/3, 2/3), (14/9, 10/9), (46/27, 38/27) and (146/81, 130/81). Each point lies on the line y = 2x − 2, which runs in the direction (1, 2), and the gap to (2, 2) shrinks by a factor of 2/3 at every step.

The usual mistakes

Writing Aⁿ = Pⁿ Dⁿ (P⁻¹)ⁿ. Matrices do not commute, so the factors of (P D P⁻¹)ⁿ cannot be gathered up by kind. Only the inner pairs cancel, which leaves one P and one P⁻¹.

Raising the entries of A itself. A⁵ is not the matrix of fifth powers (1024 −1; 32 1); only a diagonal matrix can be raised entry by entry.

Multiplying the diagonal entries by the power instead of raising them. D⁵ has 243 and 32 on its diagonal, not 15 and 10.

Forgetting P and P⁻¹ at the end. D⁵ is A⁵ written in eigenvector coordinates; it becomes A⁵ only after the two outer products.

Losing the sign of a negative eigenvalue. (−1)¹⁰ = 1 and (−1)¹¹ = −1, so an even power and an odd power give different matrices.

Rabbits, voles and owls

In the applications below, a breeding matrix is diagonalized and only the diagonal matrix is raised to the tenth power, to count the young and adult rabbit pairs ten months ahead. Then the starting numbers of voles and owls are written as a mix of two eigenvectors, each part is multiplied by its own eigenvalue once for each year, and the larger eigenvalue gives the long-run number of voles for each owl.

Worked example: Rabbits Breeding Month by Month, Counted Ten Months Ahead by Diagonalization

Question A breeder models young pairs y and adult pairs a of rabbits month by month. Each month every adult pair produces 2 young pairs, each young pair grows up into an adult pair, and the adult pairs live on. So next month's counts are Mya, where M = 0211. The breeder starts with one adult pair. (a) Write M = PDP−1, with D a diagonal matrix. (b) Use M10 = PD10P−1 to find the numbers of young and adult pairs after 10 months.

  1. 1.det(M − λ I) = −λ(1 − λ) − 2 × 1 = λ2 − λ − 2 = (λ − 2)(λ + 1), so the eigenvalues are 2 and −1.

    det(M − λI) = −λ(1 − λ) − 2 × 1= (λ − 2)(λ + 1): λ = 2 or −1
    det(M − λI) = −λ(1 − λ) − 2 × 1= (λ − 2)(λ + 1): λ = 2 or −1
    det(M − λ I) = λ2 − λ − 2 = (λ − 2)(λ + 1): the eigenvalues are 2 and −1.

  2. 2.For λ = 2, the first row of (M − 2I)v = 0 reads −2y + 2a = 0, so y = a and v1 = 11. For λ = −1 it reads y + 2a = 0, so v2 = 2−1. Check: M2−1 = −21 = −1 × 2−1.

    λ = 2:11λ = −1:2−1M ×2−1=−21
    λ = 2:11λ = −1:2−1M ×2−1=−21
    The eigenvectors are 11 for 2 and 2−1 for −1.

  3. 3.(a) P = 121−1 and D = 200−1. det P = 1 × (−1) − 2 × 1 = −3, so P−1 = −13−1−2−11 = 13121−1, and M = PDP−1.

    P =121−1D =200−1P−1= 1/3 ×121−1
    P =121−1D =200−1P−1= 1/3 ×121−1
    (a) M = PDP−1 with P = 121−1, D = 200−1 and P−1 = 13121−1.

  4. 4.D10 = 21000(−1)10 = 1024001. Work from the right: P−101 = 132−1, and then D10 gives 132048−1.

    D10=2^{10}00(−1)^{10}=1024001P−101= 1/3 ×2−1
    D10=2^{10}00(−1)^{10}=1024001P−101= 1/3 ×2−1
    Only D is raised to the power: D10 = 1024001. From the right, P−101 = 132−1.

  5. 5.Finally P gives 132048 − 22048 + 1 = 1320462049 = 682683.

    D10× 1/3 ×2−1= 1/3 ×2048−1P × 1/3 ×2048−1=682683
    D10× 1/3 ×2−1= 1/3 ×2048−1P × 1/3 ×2048−1=682683
    D10 gives 132048−1, and P gives 1320462049 = 682683.

  6. 6.(b) After 10 months there are 682 young pairs and 683 adult pairs, 1365 pairs in all. Check by stepping month by month: 21, 23, 65, 1011, …, 342341, 682683.

    after 10 months:682683682 young pairs, 683 adult pairspairs month by month: 1, 3, 5, 11, 21, …, 1365
    after 10 months:682683682 young pairs, 683 adult pairspairs month by month: 1, 3, 5, 11, 21, …, 1365
    (b) After 10 months there are 682 young pairs and 683 adult pairs, the same as stepping the model month by month.

Answer: (a) P = 121−1, D = 200−1 and P−1 = 13121−1; (b) 682 young pairs and 683 adult pairs after 10 months

Common mistakes

  • Writing M10 = P10D10(P−1)10. Only the diagonal matrix is raised to the power: each P−1 meets the P of the next factor and they cancel, which leaves one P at the front and one P−1 at the back.
  • Taking (−1)10 as −1. An even power of −1 is 1; with −1 the counts come out as 1320502047, which is not a whole number of pairs.

More eigenvalues and eigenvectors problems, worked step by step →

Worked example: Voles and Barn Owls on a Farm, Predicted Four Years Ahead and in the Long Run

Question An ecologist models the field voles and barn owls on a farm. If one spring there are x hundred voles and y tens of owls, the next spring there are Mxy, where M = 4−211: the voles breed fast but the owls eat them, and the owls do better when there are more voles. This spring there are 600 voles and 20 owls. (a) Find the eigenvalues and eigenvectors of M, and write the starting counts as a combination of the eigenvectors. (b) Find the numbers of voles and owls in four years' time, and the number of voles for each owl in the long run.

  1. 1.det(M − λ I) = (4 − λ)(1 − λ) − (−2) × 1 = λ2 − 5λ + 6 = (λ − 3)(λ − 2), so the eigenvalues are 3 and 2.

    yearvoles per owl1234102030det(M − λI) = (4 − λ)(1 − λ) + 2= (λ − 3)(λ − 2): λ = 3 or 2
    yearvoles per owl1234102030det(M − λI) = (4 − λ)(1 − λ) + 2= (λ − 3)(λ − 2): λ = 3 or 2
    det(M − λ I) = λ2 − 5λ + 6 = (λ − 3)(λ − 2): the eigenvalues are 3 and 2.

  2. 2.For λ = 3 the first row gives x − 2y = 0, so v1 = 21. For λ = 2 it gives 2x − 2y = 0, so v2 = 11. Check: M21 = 8 − 22 + 1 = 63 = 321.

    yearvoles per owl1234102030λ = 3:21λ = 2:11
    yearvoles per owl1234102030λ = 3:21λ = 2:11
    The eigenvectors are 21 for 3 and 11 for 2.

  3. 3.(a) Solve 62 = p21 + q11: 2p + q = 6 and p + q = 2, so p = 4 and q = −2. The starting counts are 421 − 211.

    yearvoles per owl12341020303062= 4 ×21− 2 ×11
    yearvoles per owl12341020303062= 4 ×21− 2 ×11
    (a) 62 = 421 − 211: this spring there are 30 voles for each owl.

  4. 4.Each year multiplies the first part by 3 and the second by 2, so after n years the counts are 4 × 3n21 − 2 × 2n11. For n = 4 this is 32421 − 3211 = 616292.

    yearvoles per owl12341020303021.14 × 34×21− 2 × 24×11=616292
    yearvoles per owl12341020303021.14 × 34×21− 2 × 24×11=616292
    After four years, 4 × 3421 − 2 × 2411 = 616292: about 21.1 voles for each owl.

  5. 5.(b) In four years there are 616 hundred voles, which is 61,600, and 292 tens of owls, which is 2920. As n grows, 3n outweighs 2n, so the counts approach the direction 21: 2 hundred voles for each ten owls, which is 20 voles for each owl.

    yearvoles per owl1234102030203021.161,600 voles and 2920 owlslong run: (2, 1), 20 voles for each owl
    yearvoles per owl1234102030203021.161,600 voles and 2920 owlslong run: (2, 1), 20 voles for each owl
    (b) There are 61,600 voles and 2920 owls. As 3n outweighs 2n, the counts approach (2, 1): 20 voles for each owl.

  6. 6.Check year by year: M62 = 208, then 6428, 20092 and 616292, and the voles for each owl run 30, 25, 22.9, 21.7, 21.1, approaching 20.

    yearvoles per owl1234102030203021.1(20, 8), (64, 28), (200, 92), (616, 292)30, 25, 22.9, 21.7, 21.1 voles per owl
    yearvoles per owl1234102030203021.1(20, 8), (64, 28), (200, 92), (616, 292)30, 25, 22.9, 21.7, 21.1 voles per owl
    Year by year the voles for each owl run 30, 25, 22.9, 21.7, 21.1, approaching the dashed 20.

Answer: (a) λ = 3 with eigenvector 21 and λ = 2 with eigenvector 11, and 62 = 421 − 211; (b) 616 hundred voles, which is 61,600, and 292 tens of owls, which is 2920, after four years, and 20 voles for each owl in the long run

Common mistakes

  • Multiplying the starting counts by 34 = 81, as if every part grew by the larger eigenvalue, which gives 486 hundred voles. The part along 11 grows by only 2 each year and is subtracted, so the answer is 616 hundred.
  • Reading the long-run ratio as 2 voles for each owl straight from the eigenvector 21. The voles are counted in hundreds and the owls in tens, so 2 hundred voles to 1 ten owls is 20 voles for each owl.

More eigenvalues and eigenvectors problems, worked step by step →

Practice Matrix Powers by Diagonalization in the app