Practice Maths

← Back to Proof by Mathematical Induction (Extension)›Specialist Maths

Induction for Matrices and Complex Numbers

Key Terms

Mathematical induction
A proof technique: verify P(1) as base case, then prove P(k) ⇒ P(k+1) as the inductive step.
De Moivre’s theorem
(cos θ + i sin θ)n = cos(nθ) + i sin(nθ) for all positive integers n; proved by induction.
cis notation
cis θ = cos θ + i sin θ; De Moivre’s theorem: (cis θ)n = cis(nθ).
Matrix power induction
Inductive step: Ak+1 = Ak × A; substitute the inductive hypothesis for Ak, then multiply and simplify.
Compound angle formulas
Used in De Moivre’s proof: cos(kθ + θ) = cos kθ cos θ − sin kθ sin θ and the analogous sin formula.
Conclusion statement
Always end with: “By the principle of mathematical induction, the result holds for all positive integers n.”

Key Results — Matrix Powers and De Moivre’s Theorem

De Moivre’s Theorem (positive integers): For all integers n ≥ 1,

(&cos;θ + i sinθ)n = cos(nθ) + i sin(nθ)

This is proved by mathematical induction using the compound angle formulas:

• cos(A+B) = cosA cosB − sinA sinB

• sin(A+B) = sinA cosB + cosA sinB

Matrix Power Induction Template:

• Base case: Compute A1 directly and verify it matches the conjectured formula with n = 1.

• Inductive hypothesis: Assume Ak equals the formula with n = k.

• Inductive step: Compute Ak+1 = Ak × A (or A × Ak), substitute the inductive hypothesis, and simplify to show it equals the formula with n = k+1.

Useful notation: cis(θ) = cosθ + i sinθ, so De Moivre’s theorem reads (cisθ)n = cis(nθ).

Worked Example 1 — Matrix Power: [[1,1],[0,1]]n = [[1,n],[0,1]]

Base case n = 1: [[1,1],[0,1]]1 = [[1,1],[0,1]] and [[1,1],[0,1]] with n=1 gives [[1,1],[0,1]]. ✓

Inductive hypothesis: Assume [[1,1],[0,1]]k = [[1,k],[0,1]] for some k ≥ 1.

Inductive step: [[1,1],[0,1]]k+1 = [[1,1],[0,1]]k × [[1,1],[0,1]]

= [[1,k],[0,1]] × [[1,1],[0,1]]     [by inductive hypothesis]

Entry (1,1): 1(1) + k(0) = 1    Entry (1,2): 1(1) + k(1) = k+1

Entry (2,1): 0(1) + 1(0) = 0    Entry (2,2): 0(1) + 1(1) = 1

= [[1, k+1],[0, 1]] = [[1, k+1],[0, 1]]. ✓

Conclusion: By mathematical induction, [[1,1],[0,1]]n = [[1,n],[0,1]] for all n ≥ 1.

Worked Example 2 — De Moivre’s Theorem

Base case n = 1: (cosθ + i sinθ)1 = cosθ + i sinθ = cos(1·θ) + i sin(1·θ). ✓

Inductive hypothesis: Assume (cosθ + i sinθ)k = cos(kθ) + i sin(kθ).

Inductive step: (cosθ + i sinθ)k+1 = (cosθ + i sinθ)k × (cosθ + i sinθ)

= [cos(kθ) + i sin(kθ)](cosθ + i sinθ)     [by IH]

= cos(kθ)cosθ − sin(kθ)sinθ + i[sin(kθ)cosθ + cos(kθ)sinθ]

= cos(kθ + θ) + i sin(kθ + θ)     [compound angle formulas]

= cos((k+1)θ) + i sin((k+1)θ). ✓

Conclusion: By mathematical induction, De Moivre’s theorem holds for all positive integers n.

Hot Tip: When proving matrix power results, always multiply Ak × A (not A × Ak) to maintain consistency — these give the same answer only when matrix multiplication is commutative, which it generally is not. For these special structured matrices, both orders work, but right-multiplying by A is the standard convention in induction proofs.

Why Induction Extends to Matrices

Mathematical induction applies to any statement about positive integers — and matrix power formulas are precisely such statements. The claim “An equals [some matrix formula]” is a statement P(n) for each positive integer n. Since the base case P(1) is trivially verified by direct computation, and the inductive step Ak+1 = Ak × A lets us substitute the inductive hypothesis, the logical structure is identical to induction for sums or divisibility.

What makes matrix induction manageable is that matrix multiplication distributes over addition and is associative. These properties mean the algebraic manipulation in the inductive step is well-defined and straightforward, even though matrices do not commute. The key tool is simply computing a matrix product entry by entry: take each row of the left matrix dotted with each column of the right matrix.

Diagonal Matrices: A Particularly Clean Case

For a diagonal matrix D = [[a,0],[0,b]], the power formula Dn = [[an,0],[0,bn]] is especially elegant. The inductive step reduces to: Dk+1 = Dk × D = [[ak,0],[0,bk]] × [[a,0],[0,b]] = [[ak+1,0],[0,bk+1]]. No cross-terms appear because the off-diagonal entries are zero, making the algebra trivial. This pattern reflects the fact that diagonal matrices represent independent scaling in each coordinate direction.

Shear Matrices: Where the Structure is Richer

The matrix A = [[1,1],[0,1]] is called a shear matrix: it leaves the x-axis fixed and shifts points horizontally in proportion to their y-coordinate. Its powers An = [[1,n],[0,1]] show that applying n shears accumulates: the off-diagonal entry simply counts the number of shear operations applied. This is a beautiful example of how algebraic structure (the induction proof) and geometric meaning (accumulated shearing) align perfectly.

The matrix [[1,0],[1,1]] is the transpose of the shear above, and its powers are [[1,0],[n,1]]. These lower-triangular shear matrices arise naturally in Gaussian elimination.

De Moivre’s Theorem: Connecting Induction to Complex Analysis

De Moivre’s theorem (cosθ + i sinθ)n = cos(nθ) + i sin(nθ) is one of the most remarkable results in all of mathematics. It says that raising a complex number to a power is equivalent, in polar form, to simply multiplying its argument by n. The modulus raises to the nth power while the argument scales linearly.

The inductive proof is elegant because the compound angle formulas — themselves provable from first principles — are exactly what is needed at the inductive step. There is no circularity: the compound angle formulas are proved geometrically, and De Moivre’s theorem is proved by induction using them.

Why is this theorem remarkable? Because it allows us to compute arbitrarily high powers of complex numbers instantly (no repeated multiplication required), to find all n-th roots of any complex number, to derive multiple-angle formulas for trigonometric functions (as in Q10), and to connect complex analysis to Fourier analysis and signal processing. It is one of those results that seems almost too good to be true — and yet the induction proof establishes it rigorously for all positive integers.

Applications of De Moivre’s Theorem

Setting n = 2 gives: (cosθ + i sinθ)2 = cos(2θ) + i sin(2θ). Expanding the left side directly: cos²θ − sin²θ + 2i sinθ cosθ. Comparing real and imaginary parts immediately yields the double angle formulas cos(2θ) = cos²θ − sin²θ and sin(2θ) = 2sinθcosθ. This approach generalises to any n, giving formulas for cos(nθ) and sin(nθ) in terms of powers of cosθ and sinθ — a far more systematic derivation than the geometric approach.

For n = 3: (cosθ + i sinθ)3 = cos(3θ) + i sin(3θ). Expanding directly using the binomial theorem and i2 = −1, i3 = −i gives cos(3θ) = 4cos³θ − 3cosθ and sin(3θ) = 3sinθ − 4sin³θ. See Q10 for this derivation.

Exam Tip: In a matrix induction proof, write the inductive hypothesis explicitly as a matrix equation. Then write Ak+1 = Ak × A, substitute the matrix from the inductive hypothesis, and compute the product entry by entry. Never skip the entry-by-entry computation — it is the core of the proof and must be shown in full.
Exam Tip: When using De Moivre’s theorem in a calculation, always convert to polar form first: find the modulus r and argument θ. Then (r cisθ)n = rn cis(nθ). Convert back to Cartesian form if required by reading off cos(nθ) and sin(nθ) exactly.

Mastery Practice

See Answers ➔
  1. Fluency

    Q1 — Base Case Verification

    Verify the base case n = 1 for the matrix power formula: [[1,2],[0,1]]n = [[1,2n],[0,1]].

  2. Fluency

    Q2 — Computing Matrix Powers

    Compute [[1,1],[0,1]]² and [[1,1],[0,1]]³ directly, and verify that each result matches the pattern [[1,n],[0,1]].

  3. Fluency

    Q3 — Applying De Moivre’s Theorem

    Using De Moivre’s theorem, evaluate (cos30° + i sin30°)4 exactly. Express your answer in Cartesian form.

  4. Fluency

    Q4 — Applying De Moivre’s Theorem

    Using De Moivre’s theorem, evaluate (cos(π/6) + i sin(π/6))6. Express your answer in Cartesian form.

  5. Understanding

    Q5 — Proving a Matrix Power Formula

    Prove by mathematical induction that for all positive integers n:

    [[1,1],[0,1]]n = [[1,n],[0,1]].

  6. Understanding

    Q6 — Diagonal Matrix Powers

    Prove by mathematical induction that for all positive integers n:

    [[2,0],[0,3]]n = [[2n,0],[0,3n]].

  7. Understanding

    Q7 — Proving De Moivre’s Theorem

    Prove De Moivre’s theorem by mathematical induction: for all positive integers n,

    (cosθ + i sinθ)n = cos(nθ) + i sin(nθ).

  8. Understanding

    Q8 — Applying De Moivre’s Theorem

    Use De Moivre’s theorem to find the exact value of (1 + i)8. Express your answer in Cartesian form.

  9. Problem Solving

    Q9 — Lower Triangular Matrix Power

    Prove by induction that for all positive integers n:

    [[1,0],[1,1]]n = [[1,0],[n,1]].

    Hence state the value of [[1,0],[1,1]]100.

  10. Problem Solving

    Q10 — Triple Angle Formulas via De Moivre’s Theorem

    Use De Moivre’s theorem with n = 3 to express cos(3θ) in terms of cosθ, and sin(3θ) in terms of sinθ. Hence show that cos(3θ) = 4cos³θ − 3cosθ.