Example 23: Powers of the rotation matrix, by induction

Basics you need

Solution

1. State the statement $P(n)$

   For each natural number $n$⁠, let $P(n)$ be the statement

   $$P(n):\quad A^n = \begin{bmatrix} \cos n\theta & \sin n\theta \\ -\sin n\theta & \cos n\theta \end{bmatrix}.$$

   We must prove $P(n)$ is true for every $n \in \N$⁠, for the given (arbitrary) $\theta$⁠.

   Induction needs one statement for each $n$⁠, written so we can plug in $n = 1$ or $n = k$ or $n = k+1$⁠. Writing $P(n)$ out exactly also fixes what "the result for $k+1$" means: the same matrix with $(k+1)\theta$ in every entry.
   Principle of mathematical induction (Class XI). Basics: compound angles and induction

2. Base case: $P(1)$ is true

   With $n = 1$⁠, the right side of $P(1)$ has $1\cdot\theta = \theta$ in every entry:

   $$\begin{bmatrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{bmatrix},$$

   which is exactly $A$⁠. Since $A^1 = A$⁠, $P(1)$ is true.

   The base case is the first domino. It is easy here, but it must be stated: without it, the inductive step alone proves nothing.

3. Inductive hypothesis: assume $P(k)$

   Let $k$ be any natural number for which $P(k)$ is true, that is,

   $$A^k = \begin{bmatrix} \cos k\theta & \sin k\theta \\ -\sin k\theta & \cos k\theta \end{bmatrix}.$$

   We now show that $P(k+1)$ must then be true.

   We do not claim $P(k)$ is true; we only ask "if it were, would $P(k+1)$ follow?" Showing this for an arbitrary $k$ covers every link of the chain $P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \dots$ at once.

4. Write $A^{k+1}$ as a product and check the orders

   $A^{k+1} = A \cdot A^k$ (Basic 4). Both $A$ and $A^k$ are $2\times2$⁠: the columns of $A$ (2) match the rows of $A^k$ (2), so the product is defined and is $2\times2$⁠. Using the hypothesis from Step 3,

   $$A^{k+1} = \begin{bmatrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} \cos k\theta & \sin k\theta \\ -\sin k\theta & \cos k\theta \end{bmatrix}.$$
   This is where the hypothesis is used: it lets us replace $A^k$ by an explicit matrix that we can multiply. Splitting off one factor of $A$ links the $k$-th power to the $(k+1)$-th power.
   Associative law, Section 3.4.6: $(XY)Z = X(YZ)$⁠, which is why $A \cdot A^k$ and $A^k\cdot A$ are both $A^{k+1}$⁠. Lesson: properties of the operations

5. Multiply, one entry at a time

   Each entry is (row of $A$⁠) times (column of $A^k$⁠):

   $$\begin{aligned} c_{11} &= \cos\theta\cos k\theta + \sin\theta(-\sin k\theta)\\ &= \cos\theta\cos k\theta - \sin\theta\sin k\theta,\\[4pt] c_{12} &= \cos\theta\sin k\theta + \sin\theta\cos k\theta,\\[4pt] c_{21} &= (-\sin\theta)\cos k\theta + \cos\theta(-\sin k\theta)\\ &= -(\sin\theta\cos k\theta + \cos\theta\sin k\theta),\\[4pt] c_{22} &= (-\sin\theta)\sin k\theta + \cos\theta\cos k\theta\\ &= \cos\theta\cos k\theta - \sin\theta\sin k\theta. \end{aligned}$$
   Row 1 of $A$ is $\cos\theta, \sin\theta$ and row 2 is $-\sin\theta, \cos\theta$⁠; column 1 of $A^k$ is $\cos k\theta, -\sin k\theta$ and column 2 is $\sin k\theta, \cos k\theta$⁠. In $c_{21}$ both terms are negative, so we take out a minus sign; in $c_{22}$ we just reorder the two terms. These rearrangements are chosen to make each entry match a compound angle formula exactly.
   Matrix multiplication, Section 3.4.5. Basics: pair up, multiply, add

6. Recognise the compound angle formulas

   Put $x = \theta$ and $y = k\theta$ in Basic 2:

   $$\begin{aligned} c_{11} &= \cos(\theta + k\theta) = \cos(k+1)\theta,\\ c_{12} &= \sin(\theta + k\theta) = \sin(k+1)\theta,\\ c_{21} &= -\sin(\theta + k\theta) = -\sin(k+1)\theta,\\ c_{22} &= \cos(\theta + k\theta) = \cos(k+1)\theta. \end{aligned}$$

   For $c_{12}$⁠, note that $\cos\theta\sin k\theta + \sin\theta\cos k\theta$ is $\sin\theta\cos k\theta + \cos\theta\sin k\theta$ with the two terms swapped, which is $\sin(\theta + k\theta)$⁠. Also $\theta + k\theta = (k+1)\theta$⁠. So

   $$A^{k+1} = \begin{bmatrix} \cos(k+1)\theta & \sin(k+1)\theta \\ -\sin(k+1)\theta & \cos(k+1)\theta \end{bmatrix},$$

   which is exactly $P(k+1)$⁠.

   The compound angle formulas hold for all real angles, so no restriction on $\theta$ or $k$ is needed. This is the moment the idea of the problem becomes visible: multiplying by $A$ turned the angle $k\theta$ into $k\theta + \theta$⁠.
   Compound angle formulas (Class XI, Chapter 3). Basics: compound angles and induction

7. Conclude by induction

   $P(1)$ is true (Step 2), and for every $k \in \N$⁠, $P(k)$ true implies $P(k+1)$ true (Steps 3 to 6). By the principle of mathematical induction, $P(n)$ is true for every natural number $n$⁠:

   $$A^n = \begin{bmatrix} \cos n\theta & \sin n\theta \\ -\sin n\theta & \cos n\theta \end{bmatrix}, \quad n \in \N.$$
   Both conditions of induction have been checked, so the chain of implications reaches every natural number. The picture shows the same fact geometrically: $A$ is a rotation through $\theta$ (clockwise, because of where the minus sign sits), and doing it $n$ times is a rotation through $n\theta$⁠.

Every fact used, and where it comes from