Induction when multiplication has an order

By UK A Level Further Mathematics · independent study · myAudience

Image: illustration, not a documentary photograph. Exact relationships follow the algebra; rendered diagram positions are illustrative. · Original generated project artwork; no source textbook or exam-board figures reused.

Induction when multiplication has an order

A matrix acts on a column vector by combining row entries with coordinates. For M=[[1,2],[0,1]], the vector (x,y) becomes (x+2y,y). This preliminary action should be understood before a matrix-power proof: M² means performing this same map twice, not squaring each entry separately. The vertical coordinate stays fixed, while each application adds another 2y horizontally. This suggests an upper-right entry 2n after n applications, but the suggestion still needs a proof.

Matrix multiplication has dimensions and order. In a product AB applied to a column vector v, B acts first and then A. Even when square matrices have the same dimensions, AB need not equal BA. Powers of one matrix are a special case because associativity permits M^(k+1)=M^kM. This identity is not permission to commute unrelated matrices. Writing down the intended product before expanding its entries avoids a common source of transformation errors.

The identity matrix leaves every vector unchanged. We can define M^0=I and then check whether a proposed formula extends to zero, but that definition must be stated. A theorem initially specified for n≥1 can use n=1 as its base. For a matrix equality, every corresponding entry must agree. A diagram of one vector may expose an incorrect matrix but cannot establish equality of transformations on all vectors without a general argument.

The shear provides a useful geometric check. A horizontal shear fixes every point on the x-axis and preserves each horizontal line as a set; other points move along that line. Its determinant is 1, so the area of a parallelogram is preserved even though individual lengths and angles can change. “Area preserved” does not mean the shape is unchanged. The closed form predicts displacement 2ny, allowing a physical grid diagram to be checked against the algebra.

A more demanding upper-triangular example combines growth with accumulated mixing. For N=[[2,1],[0,2]], the diagonal entries become 2^n, while the off-diagonal entry is n2^(n−1), not 1 or 2^n. Each new product adds one contribution from the first diagonal and one from the previous off-diagonal. The n factor records accumulated contributions. This is a direct induction proof; eigenvalues and diagonalisation are not needed and are not silently claimed as covered.

For M=[[1,2],[0,1]], prove M^n=[[1,2n],[0,1]] for integers n≥1 and describe what repeated application does to (x,y). At n=1 the formula gives M itself. Suppose it holds at an arbitrary k≥1. Multiplying the assumed matrix on the right by M gives first row (1,2+2k) and second row (0,1), because the upper-right entry is 1·2+(2k)·1. Therefore M^(k+1)=[[1,2(k+1)],[0,1]], proving the successor statement. Together with the base this establishes the formula for all positive integers. If we also define M^0=I, the same displayed formula holds at zero, but that is an explicitly checked extension, not a silent change to the proof domain. A column vector (x,y) is sent to (x+2ny,y). The vertical coordinate stays fixed while the horizontal displacement grows in proportion to both the iteration number and y. This is a shear, not an enlargement: its determinant is 1, and area is preserved. It is not legitimate to raise each matrix entry independently to the nth power; doing so would predict upper-right 2^n, contradicted already at n=3. Matrix multiplication combines rows and columns. Nor does the worked identity imply arbitrary matrices commute. We have used a power of the same matrix, whereas composition of different transformations can depend on order. The algebraic proof and vector interpretation agree, but the drawn shear is a bounded illustration rather than evidence for all integers.

For N=[[2,1],[0,2]], prove N^n=[[2^n,n·2^(n−1)],[0,2^n]] for n≥1. Explain a tempting but incorrect entrywise-power rule. The n=1 matrix is correct. Under the k hypothesis, the upper-right entry of N^kN is 2^k+2k·2^(k−1)=(k+1)2^k; both diagonal entries become 2^(k+1). The lower-left remains 0. This proves the next case. Entrywise powers would leave the upper-right 1 instead of n2^(n−1), so they are not matrix powers.

For the shear diagrams, follow a point at height 1: each application changes x by 2 while leaving y unchanged. A point on y=0 does not move. The grid illustrates particular inputs and repeated steps; the entrywise induction supplies the arbitrary-integer conclusion. An invariant horizontal line is not generally a line of fixed points. To distinguish them, test (0,1), which moves to (2,1), and (3,0), which remains (3,0). Neither area preservation nor a fixed axis makes the entire transformation the identity.

Worked example: For M=[[1,2],[0,1]], prove M^n=[[1,2n],[0,1]] for integers n≥1 and describe what repeated application does to (x,y).

Check M¹=[[1,2],[0,1]].

Assume M^k=[[1,2k],[0,1]].

Multiply M^kM: upper-right=2+2k=2(k+1), with diagonal 1 and lower-left 0.

Apply the result to (x,y): (x+2ny,y).

Answer: M^n=[[1,2n],[0,1]] for n≥1; its action is (x,y)→(x+2ny,y).

Check your understanding: For N=[[2,1],[0,2]], prove N^n=[[2^n,n·2^(n−1)],[0,2^n]] for n≥1. Explain a tempting but incorrect entrywise-power rule.

Answer: The n=1 matrix is correct. Under the k hypothesis, the upper-right entry of N^kN is 2^k+2k·2^(k−1)=(k+1)2^k; both diagonal entries become 2^(k+1). The lower-left remains 0. This proves the next case. Entrywise powers would leave the upper-right 1 instead of n2^(n−1), so they are not matrix powers.

Why: Credit exact equivalent derivations with the stated hypotheses, complete candidates and justified restrictions; a correct final value alone does not establish the full reasoning.