1.7 - Proof by induction for matrix powers

1.7 - Proof by induction for matrix powers

A few matrix powers can reveal a pattern, but a proof must establish that every entry continues correctly. In this part of 1.7, you will check the appropriate first power, use matrix multiplication in an induction step, and turn patterns in small powers into proved formulae.

The first matrix power

Can a proposed formula agree with a matrix at power 11 and still fail at power 22? For U=(1401)\mathbf U=\begin{pmatrix}1&4\\0&1\end{pmatrix}, raising the top-right entry to a power would suggest 4n4^n. It gives 44 at n=1n=1, but U2\mathbf U^2 has top-right entry 88, not 1616.

A matrix identity means equality of every corresponding entry. A base case therefore compares the whole proposed matrix with the actual first matrix power, not just one entry that happens to agree.

The zero power

For a square matrix A\mathbf A, define A0=I\mathbf A^0=\mathbf I, the identity matrix of the same size. This definition applies even when A\mathbf A is singular. A formula claimed for integers n≥0n\geq0 must be defined at 00 and give I\mathbf I there.

If the stated domain is n≥1n\geq1, checking n=1n=1 is enough for the base. You do not need to extend the claim to zero. If the claim includes zero, start there or establish that case separately.

Worked example 1: checking every entry

Question. For U=(1401)\mathbf U=\begin{pmatrix}1&4\\0&1\end{pmatrix}, consider the proposed formula

Un=(14n01)(n≥0).\mathbf U^n=\begin{pmatrix}1&4n\\0&1\end{pmatrix} \qquad(n\geq0).

Check the base case at 00, and verify the formula at 11.

Plan. Substitute each index into the proposed matrix and compare with I\mathbf I and U\mathbf U, respectively.

(14(0)01)=(1001)=U0(14(1)01)=(1401)=U.\begin{aligned} \begin{pmatrix}1&4(0)\\0&1\end{pmatrix} &=\begin{pmatrix}1&0\\0&1\end{pmatrix}=\mathbf U^0\\ \begin{pmatrix}1&4(1)\\0&1\end{pmatrix} &=\begin{pmatrix}1&4\\0&1\end{pmatrix}=\mathbf U. \end{aligned}

All four entries agree in each case.

Answer. The base at 00 is valid, and the formula also agrees at 11. An induction step is still needed to establish all powers.

Check. Multiplying U\mathbf U by itself directly gives (1801)\begin{pmatrix}1&8\\0&1\end{pmatrix}, agreeing at the additional index 22.

Change only the two equal diagonal entries from 11 to 22, keeping the top-right entry 44. Diagonal powers now grow, so the proposed top-right entry also needs an exponential factor.

Worked example 2: a base with exponential entries

Question. For A=(2402)\mathbf A=\begin{pmatrix}2&4\\0&2\end{pmatrix}, check the proposed formula

An=(2nn2n+102n)\mathbf A^n=\begin{pmatrix}2^n&n2^{n+1}\\0&2^n\end{pmatrix}

at n=0n=0 and n=1n=1.

Plan. Evaluate the powers and the coefficient nn separately; the top-right entry must vanish at zero.

At n=0n=0, the proposed matrix is

(10⋅201)=I=A0.\begin{pmatrix}1&0\cdot2\\0&1\end{pmatrix}=\mathbf I=\mathbf A^0.

At n=1n=1, it is

(21⋅2202)=(2402)=A.\begin{pmatrix}2&1\cdot2^2\\0&2\end{pmatrix} =\begin{pmatrix}2&4\\0&2\end{pmatrix}=\mathbf A.

Answer. The proposed formula has the correct zero and first powers; the next part will establish its continuing step.

Check. Independently, A2=(41604)\mathbf A^2=\begin{pmatrix}4&16\\0&4\end{pmatrix} by row-column multiplication. The proposed top-right entry at n=2n=2 is 2⋅23=162\cdot2^3=16, agreeing with the row-column calculation.

The coincidence 42=164^2=16 in that last calculation does not rescue the entrywise rule: at zero it would give a top-right entry 11, and at three it would give 6464 instead of the proposed 4848.

Watch out

Checking n=1n=1 is a base case, not an induction step. A formula can fit its first value and still fail later. Prove that multiplying by one more copy produces the next proposed matrix.

Check the first values of a fresh proposal and identify what remains to be proved.

Multiplying by one more matrix

For powers of one square matrix, the next-case link is Ak+1=AkA\mathbf A^{k+1}=\mathbf A^k\mathbf A.

The hypothesis replaces Ak\mathbf A^k by its proposed expression. You then perform a genuine row-column multiplication and simplify every entry into the proposed form at k+1k+1. We will multiply on the right consistently; multiplying on the left would also be valid for powers of this same matrix, but it does not permit rearranging unrelated matrices.

You already know

Matrix multiplication is associative, so the product of k+1k+1 copies can be grouped as AkA\mathbf A^k\mathbf A. It is generally not commutative: preserve the factor order when substituting a matrix expression.

The upper-right entry often carries the important calculation in a triangular matrix. Still show that the other three entries are correct.

Worked example 3: establishing the exponential pattern

Question. Prove by induction that, for A=(2402)\mathbf A=\begin{pmatrix}2&4\\0&2\end{pmatrix},

An=(2nn2n+102n)\mathbf A^n=\begin{pmatrix}2^n&n2^{n+1}\\0&2^n\end{pmatrix}

for every integer n≥0n\geq0.

Plan. Start at zero, substitute the hypothesised matrix, and multiply it on the right by A\mathbf A.

At n=0n=0, the right side is I=A0\mathbf I=\mathbf A^0. Assume the formula holds for an arbitrary integer k≥0k\geq0. Then

Ak+1=(2kk2k+102k)(2402)=(2k+14⋅2k+2k2k+102k+1)=(2k+1(k+1)2k+202k+1).\begin{aligned} \mathbf A^{k+1} &=\begin{pmatrix}2^k&k2^{k+1}\\0&2^k\end{pmatrix} \begin{pmatrix}2&4\\0&2\end{pmatrix}\\ &=\begin{pmatrix} 2^{k+1}&4\cdot2^k+2k2^{k+1}\\ 0&2^{k+1} \end{pmatrix}\\ &=\begin{pmatrix} 2^{k+1}&(k+1)2^{k+2}\\ 0&2^{k+1} \end{pmatrix}. \end{aligned}

For the top-right entry, both terms contain 2k+22^{k+2}, leaving the factor 1+k1+k. The final matrix is the proposed formula at k+1k+1.

Answer. The formula holds for every integer n≥0n\geq0, by induction.

Check. Direct squaring gives A2=(41604)\mathbf A^2=\begin{pmatrix}4&16\\0&4\end{pmatrix}. Squaring this block gives A4=(16128016)\mathbf A^4=\begin{pmatrix}16&128\\0&16\end{pmatrix}, agreeing with the formula at 44 using a different grouping of factors.

Change only the sign of the top-right entry in the original matrix. The top-right entries of all powers change sign, while the induction structure remains intact.

Worked example 4: retaining a negative sign

Question. For B=(2−402)\mathbf B=\begin{pmatrix}2&-4\\0&2\end{pmatrix}, prove that

Bn=(2n−n2n+102n)\mathbf B^n=\begin{pmatrix}2^n&-n2^{n+1}\\0&2^n\end{pmatrix}

for every integer n≥0n\geq0.

Plan. Keep both negative contributions in the top-right row-column product.

The proposed matrix at n=0n=0 is I=B0\mathbf I=\mathbf B^0. Assume the formula for an arbitrary integer k≥0k\geq0. Therefore

Bk+1=(2k−k2k+102k)(2−402)=(2k+1−4⋅2k−2k2k+102k+1)=(2k+1−(k+1)2k+202k+1).\begin{aligned} \mathbf B^{k+1} &=\begin{pmatrix}2^k&-k2^{k+1}\\0&2^k\end{pmatrix} \begin{pmatrix}2&-4\\0&2\end{pmatrix}\\ &=\begin{pmatrix} 2^{k+1}&-4\cdot2^k-2k2^{k+1}\\ 0&2^{k+1} \end{pmatrix}\\ &=\begin{pmatrix} 2^{k+1}&-(k+1)2^{k+2}\\ 0&2^{k+1} \end{pmatrix}. \end{aligned}

This is exactly the next proposed matrix.

Answer. The base case and the next-case calculation prove the formula for every integer n≥0n\geq0, by induction.

Check. Direct multiplication gives B2=(4−1604)\mathbf B^2=\begin{pmatrix}4&-16\\0&4\end{pmatrix}. Squaring it gives B4=(16−128016)\mathbf B^4=\begin{pmatrix}16&-128\\0&16\end{pmatrix}, confirming both the sign and the size predicted at n=4n=4.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account