CP 1.1 - Induction for powers of matrices

CP 1.1 - Induction for powers of matrices

A formula for a matrix power can replace thousands of multiplications with one substitution. You will prove such formulae by induction, using the whole assumed matrix in one further row-by-column product, then use the proved result to calculate or determine a power.

What a matrix-power formula claims

What is A2027\mathbf{A}^{2027}, where

A=(21−10)\mathbf{A}=\begin{pmatrix}2&1\\-1&0\end{pmatrix}

without doing 20262026 successive matrix multiplications? The first few powers have a surprising pattern:

A2=(32−2−1)A3=(43−3−2)\mathbf{A}^2=\begin{pmatrix}3&2\\-2&-1\end{pmatrix} \qquad \mathbf{A}^3=\begin{pmatrix}4&3\\-3&-2\end{pmatrix}

Although we keep multiplying, the entries appear to change only by addition. The proposed formula is

An=(n+1n−n1−n)\mathbf{A}^n=\begin{pmatrix}n+1&n\\-n&1-n\end{pmatrix}

If it holds, even a million multiplications leave entries with magnitudes no larger than 1 000 0011\,000\,001. You will prove this steady growth, rather than relying on the first few powers.

You already know

For a square matrix, positive integer powers mean repeated matrix products. Use row-by-column multiplication and keep the factor order. Equal matrices have equal corresponding entries. From the induction lesson, one checked case and a proved implication from kk to k+1k+1 establish every case in the stated range.

A claimed formula predicts every entry simultaneously. Assuming it at n=kn=k gives you the entire matrix Ak\mathbf{A}^k, which can be multiplied by one more copy of A\mathbf{A}. The task is to show that the resulting entries match the same claimed formula with k+1k+1 substituted for nn.

The next matrix power

For a square matrix M\mathbf{M} and a positive integer kk:

Mk+1=MkM=MMk\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}=\mathbf{M}\mathbf{M}^k

The equality of these two orders holds because both consist of k+1k+1 copies of the same matrix. It does not mean arbitrary matrices commute.

Not in the formula booklet: learn it.

If the claim is Mn=F(n)\mathbf{M}^n=\mathbf{F}(n), where F(n)\mathbf{F}(n) is a matrix expression, the inductive calculation is

Mk+1=MkM=F(k)M\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}=\mathbf{F}(k)\mathbf{M}

You then multiply and show that the last expression is F(k+1)\mathbf{F}(k+1). Substituting k+1k+1 into the proposed formula at the start would assume the very case you need to prove.

Key idea

Assume the full formula at kk, then multiply by the original matrix. A correct entry pattern is a conjecture until the base case and this next-case calculation are proved.

The same logic that proved sums now applies to all the entries of a matrix at once. Explain that connection without performing a long product.

Powers whose entries grow linearly

In some matrices, positive and negative products cancel most of the growth: one multiplication simply increases each changing entry by a fixed amount.

The opening matrix is an example. Your inductive multiplication must demonstrate those cancellations for an arbitrary kk. Checking a single entry is insufficient, because the claimed equality concerns the whole matrix.

Worked example 1: proving the opening pattern

Question. For A=(21−10)\mathbf{A}=\begin{pmatrix}2&1\\-1&0\end{pmatrix}, prove by induction that

An=(n+1n−n1−n)\mathbf{A}^n=\begin{pmatrix}n+1&n\\-n&1-n\end{pmatrix}

for all positive integers nn.

Plan. Substitute n=1n=1, assume the displayed matrix at kk and multiply it on the right by A\mathbf{A}.

At n=1n=1, the proposed right side is

(1+11−11−1)=(21−10)=A1\begin{pmatrix}1+1&1\\-1&1-1\end{pmatrix} =\begin{pmatrix}2&1\\-1&0\end{pmatrix} =\mathbf{A}^1

so the result is true for n=1n=1.

Assume Ak=(k+1k−k1−k)\mathbf{A}^k=\begin{pmatrix}k+1&k\\-k&1-k\end{pmatrix} for an arbitrary positive integer kk. Then

Ak+1=AkAone more factor=(k+1k−k1−k)(21−10)use the assumption=(2(k+1)−kk+1−2k−(1−k)−k)row by column=(k+2k+1−(k+1)1−(k+1))collect each entry\begin{aligned} \mathbf{A}^{k+1} &=\mathbf{A}^k\mathbf{A} &&\text{one more factor}\\ &=\begin{pmatrix}k+1&k\\-k&1-k\end{pmatrix} \begin{pmatrix}2&1\\-1&0\end{pmatrix} &&\text{use the assumption}\\ &=\begin{pmatrix}2(k+1)-k&k+1\\-2k-(1-k)&-k\end{pmatrix} &&\text{row by column}\\ &=\begin{pmatrix}k+2&k+1\\-(k+1)&1-(k+1)\end{pmatrix} &&\text{collect each entry} \end{aligned}

This is the proposed formula with n=k+1n=k+1.

Why this step? Multiplying the assumed matrix by A\mathbf{A} uses a case you may assume to derive a case you may not assume. The row-column calculation proves that all four entries advance together.

Answer. If true for n=kn=k, the formula is true for n=k+1n=k+1. It is true for n=1n=1, so it is true for all positive integers nn, by induction.

Check. At n=2n=2, direct multiplication gives (4−12−2−1)=(32−2−1)\begin{pmatrix}4-1&2\\-2&-1\end{pmatrix}=\begin{pmatrix}3&2\\-2&-1\end{pmatrix}, agreeing with the formula.

Worked example 2 changes one feature: the increments away from the identity matrix are doubled. Each changing entry will now advance by 22, while the proof still uses one ordinary matrix multiplication.

Worked example 2: doubling the increments

Question. For B=(32−2−1)\mathbf{B}=\begin{pmatrix}3&2\\-2&-1\end{pmatrix}, prove by induction that

Bn=(2n+12n−2n1−2n)\mathbf{B}^n=\begin{pmatrix}2n+1&2n\\-2n&1-2n\end{pmatrix}

for every positive integer nn. Hence find B5\mathbf{B}^5.

Plan. Check the first case, multiply the assumed kk-case matrix by B\mathbf{B}, then substitute n=5n=5 only after completing the proof.

At n=1n=1,

(2(1)+12(1)−2(1)1−2(1))=(32−2−1)=B1\begin{pmatrix}2(1)+1&2(1)\\-2(1)&1-2(1)\end{pmatrix} =\begin{pmatrix}3&2\\-2&-1\end{pmatrix} =\mathbf{B}^1

so the base case is true.

Assume Bk=(2k+12k−2k1−2k)\mathbf{B}^k=\begin{pmatrix}2k+1&2k\\-2k&1-2k\end{pmatrix} for an arbitrary positive integer kk. Then

Bk+1=(2k+12k−2k1−2k)(32−2−1)use BkB=(3(2k+1)−4k2(2k+1)−2k−6k−2(1−2k)−4k−(1−2k))row by column=(2k+32k+2−2k−2−2k−1)simplify=(2(k+1)+12(k+1)−2(k+1)1−2(k+1))the required next form\begin{aligned} \mathbf{B}^{k+1} &=\begin{pmatrix}2k+1&2k\\-2k&1-2k\end{pmatrix} \begin{pmatrix}3&2\\-2&-1\end{pmatrix} &&\text{use }\mathbf{B}^k\mathbf{B}\\ &=\begin{pmatrix} 3(2k+1)-4k&2(2k+1)-2k\\ -6k-2(1-2k)&-4k-(1-2k) \end{pmatrix} &&\text{row by column}\\ &=\begin{pmatrix}2k+3&2k+2\\-2k-2&-2k-1\end{pmatrix} &&\text{simplify}\\ &=\begin{pmatrix}2(k+1)+1&2(k+1)\\-2(k+1)&1-2(k+1)\end{pmatrix} &&\text{the required next form} \end{aligned}

Why this step? The unsimplified product shows how the negative entries cancel. Skipping straight to the printed next form would hide the step the proof is meant to establish.

Answer. Truth for n=kn=k implies truth for n=k+1n=k+1. The formula is true for n=1n=1, so it holds for all positive integers nn, by induction. Hence

B5=(1110−10−9)\mathbf{B}^5=\begin{pmatrix}11&10\\-10&-9\end{pmatrix}

Check. At n=2n=2, direct multiplication gives B2=(54−4−3)\mathbf{B}^2=\begin{pmatrix}5&4\\-4&-3\end{pmatrix}, agreeing with the proved formula.

These matrix-power formulae are not in the formula booklet: derive them when asked. They explain the opening surprise: multiplication can produce linear entry growth because the products cancel in a particular pattern.

Watch out

Wrong: square the entries of A\mathbf{A} to get (4110)\begin{pmatrix}4&1\\1&0\end{pmatrix}. A matrix power is a repeated matrix product. Right: A2=(32−2−1)\mathbf{A}^2=\begin{pmatrix}3&2\\-2&-1\end{pmatrix}, using row-by-column sums.

The base-case mark in a matrix induction needs actual substitution into the proposed right side. The words “true for n=1n=1” alone do not demonstrate the equality.

Exam tip

Display the assumed matrix, the product with the original matrix, an unsimplified row-column result and the simplified next form. End with the implication, the checked base and the full integer domain. Pearson rewards the calculation and its logical conclusion separately.

The next matrix increases the same increments to 33. Its four entries must all reach their k+1k+1 forms.

Powers with exponential entries

Other matrices have entries involving powers such as 3n3^n; the proof still advances by multiplying the assumed matrix once, then using ordinary index laws inside its entries.

An upper-triangular matrix, with zero below its main diagonal, makes the multiplication particularly easy to follow. The upper-right entry collects two products, while the lower-left entry stays zero. Keep the non-zero upper-right calculation visible rather than treating the whole matrix as a list of separate powers.

Worked example 3: an upper-right entry involving a power

Question. Given T=(1203)\mathbf{T}=\begin{pmatrix}1&2\\0&3\end{pmatrix}, prove by induction that

Tn=(13n−103n)\mathbf{T}^n=\begin{pmatrix}1&3^n-1\\0&3^n\end{pmatrix}

for all positive integers nn.

Plan. Check n=1n=1, multiply the assumed matrix by T\mathbf{T} and simplify the upper-right entry to 3k+1−13^{k+1}-1.

At n=1n=1,

(131−1031)=(1203)=T1\begin{pmatrix}1&3^1-1\\0&3^1\end{pmatrix} =\begin{pmatrix}1&2\\0&3\end{pmatrix} =\mathbf{T}^1

so the result is true for n=1n=1.

Assume Tk=(13k−103k)\mathbf{T}^k=\begin{pmatrix}1&3^k-1\\0&3^k\end{pmatrix} for an arbitrary positive integer kk. Then

Tk+1=(13k−103k)(1203)use TkT=(12+3(3k−1)03×3k)row by column=(13×3k−103k+1)expand and collect=(13k+1−103k+1)the required next form\begin{aligned} \mathbf{T}^{k+1} &=\begin{pmatrix}1&3^k-1\\0&3^k\end{pmatrix}\begin{pmatrix}1&2\\0&3\end{pmatrix} &&\text{use }\mathbf{T}^k\mathbf{T}\\ &=\begin{pmatrix}1&2+3(3^k-1)\\0&3\times3^k\end{pmatrix} &&\text{row by column}\\ &=\begin{pmatrix}1&3\times3^k-1\\0&3^{k+1}\end{pmatrix} &&\text{expand and collect}\\ &=\begin{pmatrix}1&3^{k+1}-1\\0&3^{k+1}\end{pmatrix} &&\text{the required next form} \end{aligned}

Why this step? The top-right entry is 2+3(3k−1)2+3(3^k-1), because matrix multiplication adds two row-column products. Its constants combine to −1-1, exactly as the next case requires.

Answer. If true for n=kn=k, the formula is true for n=k+1n=k+1. It is true for n=1n=1, so it holds for all positive integers nn, by induction.

Check. Direct multiplication gives T2=(1809)\mathbf{T}^2=\begin{pmatrix}1&8\\0&9\end{pmatrix}, and 32−1=83^2-1=8.

Worked example 4 changes only the lower-right entry, from 33 to 44. The upper-right formula now needs a factor of 2/32/3; do not discard it during the multiplication.

Worked example 4: retaining a fractional coefficient

Question. For U=(1204)\mathbf{U}=\begin{pmatrix}1&2\\0&4\end{pmatrix}, prove by induction that

Un=(123(4n−1)04n)\mathbf{U}^n=\begin{pmatrix}1&\frac23(4^n-1)\\0&4^n\end{pmatrix}

for every positive integer nn. Hence determine the positive integer nn for which the upper-right entry of Un\mathbf{U}^n is 4242.

Plan. Verify the first case, keep the factor 2/32/3 through the next-case product, then solve the equation for the required entry.

At n=1n=1,

(123(41−1)041)=(1204)=U1\begin{pmatrix}1&\frac23(4^1-1)\\0&4^1\end{pmatrix} =\begin{pmatrix}1&2\\0&4\end{pmatrix} =\mathbf{U}^1

so the base case is true.

Assume Uk=(123(4k−1)04k)\mathbf{U}^k=\begin{pmatrix}1&\frac23(4^k-1)\\0&4^k\end{pmatrix} for an arbitrary positive integer kk. Then

Uk+1=(123(4k−1)04k)(1204)use UkU=(12+83(4k−1)04×4k)row by column\begin{aligned} \mathbf{U}^{k+1} &=\begin{pmatrix}1&\frac23(4^k-1)\\0&4^k\end{pmatrix}\begin{pmatrix}1&2\\0&4\end{pmatrix} &&\text{use }\mathbf{U}^k\mathbf{U}\\ &=\begin{pmatrix}1&2+\frac83(4^k-1)\\0&4\times4^k\end{pmatrix} &&\text{row by column} \end{aligned}

For the changing upper-right entry,

2+83(4k−1)=23[3+4(4k−1)]take out 23=23(4k+1−1)collect and use index laws\begin{aligned} 2+\frac83(4^k-1) &=\frac23\bigl[3+4(4^k-1)\bigr] &&\text{take out }\frac23\\ &=\frac23(4^{k+1}-1) &&\text{collect and use index laws} \end{aligned}

Hence

Uk+1=(123(4k+1−1)04k+1)\mathbf{U}^{k+1}=\begin{pmatrix}1&\frac23(4^{k+1}-1)\\0&4^{k+1}\end{pmatrix}

Why this step? Factoring 2/32/3 makes the constant term 3−4=−13-4=-1, so the whole entry becomes the required next-case expression.

Answer. Truth for n=kn=k implies truth for n=k+1n=k+1. The formula is true for n=1n=1, so it holds for every positive integer nn, by induction. For the specified entry,

23(4n−1)=42⟹4n=64=43⟹n=3\frac23(4^n-1)=42 \quad\Longrightarrow\quad 4^n=64=4^3 \quad\Longrightarrow\quad n=3

Check. U2=(110016)\mathbf{U}^2=\begin{pmatrix}1&10\\0&16\end{pmatrix}, so one more product gives upper-right entry 2+4(10)=422+4(10)=42, as required.

Neither exponential matrix-power formula is in the formula booklet: derive it when asked. The formula can then be used directly in a “Hence” part, even though the proof itself required full working.

Watch out

Wrong: 2+83(4k−1)=83(4k+1)2+\frac83(4^k-1)=\frac83(4^k+1). The separate 22 is not 8/38/3. Right: first write the expression as 23[3+4(4k−1)]\frac23[3+4(4^k-1)], then simplify to 23(4k+1−1)\frac23(4^{k+1}-1).

The opening power now needs only a substitution into Worked example 1:

A2027=(20282027−2027−2026)\mathbf{A}^{2027}=\begin{pmatrix}2028&2027\\-2027&-2026\end{pmatrix}

That small matrix contains the result of 20272027 repeated factors. Its linear pattern was useful because we proved it, entry by entry, for every positive integer.

The following matrix changes the upper-right entry of Worked example 4 from 22 to 33. That removes the fractional coefficient from the proposed power formula.

Quick Recap

  • Substitute the starting index into the proposed matrix to verify the base case.
  • Assume the whole formula for one arbitrary kk, then use Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}.
  • Show enough row-by-column working to establish every entry of the next form.
  • Conclude with the implication, the checked base and the full domain; only then use the proved formula for a requested power.

The opening power is A2027=(20282027−2027−2026)\mathbf{A}^{2027}=\begin{pmatrix}2028&2027\\-2027&-2026\end{pmatrix}, obtained from a proved pattern rather than thousands of separate products.