Matrix Powers by Induction

Powers of a matrix

For a square matrix A, $A^2$A² means A × A, $A^3$A³ means $A^2\times A$A² × A, and in general $A^n$Aⁿ is n copies of A multiplied together. Only a square matrix has powers, because A × A needs A to have as many columns as rows.

Take A = (1 1; 0 1). Row by column, $A^2$A² has top row 1 × 1 + 1 × 0 = 1 and 1 × 1 + 1 × 1 = 2, and bottom row 0 and 1, so $A^2$A² is the matrix (1 2; 0 1). Then $A^3=A^2\times A$A³ = A² × A has top row 1 and 1 × 1 + 2 × 1 = 3, so $A^3$A³ is (1 3; 0 1).

One more: $A^4=A^3\times A$A⁴ = A³ × A has top right entry 1 × 1 + 3 × 1 = 4, so $A^4$A⁴ is (1 4; 0 1). Each time, only the top right entry moves, and it goes up by 1.

Row 1 of $A^3$A³ meets column 2 of A: 1 × 1 + 3 × 1 = 4, the top right entry of $A^4$A⁴.

A pattern is not a proof

The powers suggest the formula that $A^n$Aⁿ is the matrix (1 n; 0 1). Checking more cases makes it more believable, but no number of checked cases covers every n: there is always a next power that has not been checked.

Proof by induction covers them all with two parts, exactly as it does for a formula for a sum. The base case shows the formula is true for n = 1. The inductive step shows that if it is true for some n = k, it must be true for n = k + 1.

The base case

At n = 1 the formula gives (1 1; 0 1), with a 1 in the top right corner. That is A itself, and $A^1=A$A¹ = A, so the formula is true for n = 1.

The inductive step

Assume the formula is true for n = k, so that $A^k$Aᵏ is the matrix (1 k; 0 1). The next power is one more factor of A: $A^{k+1}=A^k\times A$Aᵏ⁺¹ = Aᵏ × A.

Multiply row by column. The top left entry is 1 × 1 + k × 0 = 1. The top right entry is 1 × 1 + k × 1 = k + 1. The bottom left entry is 0 × 1 + 1 × 0 = 0, and the bottom right entry is 0 × 1 + 1 × 1 = 1.

So $A^{k+1}$Aᵏ⁺¹ is the matrix (1 k+1; 0 1), which is exactly what the formula gives for n = k + 1.

Row 1 of $A^k$Aᵏ meets column 2 of A: 1 × 1 + k × 1 = k + 1, the corner the formula predicts for the next power.

The conclusion

The formula is true for n = 1. Whenever it is true for n = k, it is true for n = k + 1. So it is true for n = 2, and therefore for n = 3, and so on without end: $A^n$Aⁿ is (1 n; 0 1) for every positive whole number n.

A written proof ends with that sentence, naming both parts. The step alone proves nothing, since it only passes truth from one power to the next, and the base case alone covers only n = 1.

The factor of A can go on either side

$A^{k+1}$Aᵏ⁺¹ is also $A\times A^k$A × Aᵏ, because every product of copies of A is the same whatever the bracketing. Worked that way, the top right entry is 1 × k + 1 × 1 = k + 1 again. Either side gives the proof; what matters is that exactly one more factor of A is multiplied in.

A second matrix

Take M = (2 1; 0 1). Then $M^2$M² is (4 3; 0 1), since its top row is 2 × 2 + 1 × 0 = 4 and 2 × 1 + 1 × 1 = 3, and $M^3=M^2\times M$M³ = M² × M is (8 7; 0 1), since its top row is 4 × 2 = 8 and 4 × 1 + 3 × 1 = 7. The top left entry doubles each time, and the top right entry is always 1 less than it. The guess is that $M^n$Mⁿ has top row $2^n$2ⁿ and $2^n-1$2ⁿ − 1, and bottom row 0 and 1.

Base case: at n = 1 the formula gives (2 1; 0 1), which is M.

Inductive step: assume that $M^k$Mᵏ has top row $2^k$2ᵏ and $2^k-1$2ᵏ − 1, and bottom row 0 and 1. Then $M^{k+1}=M^k\times M$Mᵏ⁺¹ = Mᵏ × M has top left entry $2^k\times 2+\left(2^k-1\right)\times 0=2^{k+1}$2ᵏ × 2 + (2ᵏ − 1) × 0 = 2ᵏ⁺¹ and top right entry $2^k\times 1+\left(2^k-1\right)\times 1=2\times 2^k-1=2^{k+1}-1$2ᵏ × 1 + (2ᵏ − 1) × 1 = 2 × 2ᵏ − 1 = 2ᵏ⁺¹ − 1, and its bottom row is 0, 1. That is the formula for n = k + 1, so it holds for every positive whole number n.

Row 1 of $M^k$Mᵏ meets column 2 of M: $2^k\times 1+\left(2^k-1\right)\times 1=2^{k+1}-1$2ᵏ × 1 + (2ᵏ − 1) × 1 = 2ᵏ⁺¹ − 1, the top right entry of $M^{k+1}$Mᵏ⁺¹.

What the formula is for

Once proved, a formula gives any power without multiplying out all the ones before it. $A^{10}$A¹⁰ is (1 10; 0 1), and $M^{10}$M¹⁰ has top row $2^{10}=1024$2¹⁰ = 1024 and $2^{10}-1=1023$2¹⁰ − 1 = 1023, so it is (1024 1023; 0 1), with no products worked at all.

The usual mistakes

Stopping after checking A, $A^2$A² and $A^3$A³. The pattern is easy to see in three cases, but seeing it is not proving it; only the inductive step covers every later power.

Finding $A^{k+1}$Aᵏ⁺¹ as $A^k\times A^k$Aᵏ × Aᵏ. That is $A^{2k}$A²ᵏ, and it doubles the corner to 2k; the next power has exactly one more factor of A.

Squaring A entry by entry. Every entry of (1 1; 0 1) is 0 or 1, so squaring the entries gives back A, but $A^2$A² is (1 2; 0 1).

Doubling every entry for $A^2$A². 2A = (2 2; 0 2) is a scalar multiple; $A^2$A² is a product.

Trees, year after year

In the application below, one year in a park is multiplication by M = (1 5; 0 1) acting on a column of trees and gardeners. The powers $M^2$M² and $M^3$M³ suggest that $M^n$Mⁿ is (1 5n; 0 1), which is proved by induction and then used for ten years at once.