← 2015 Paper 1

UPSC 2015 Maths Optional Paper 1 Q2a — Step-by-Step Solution

12 marks · Section A

Algebra of matrices · Linear Algebra · asked 5× in 13 yrs · Read the full method →

Question

If matrix $A=\begin{bmatrix}1 & 0 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\end{bmatrix}$, then find $A^{30}$.

Technique

Direct iteration to spot a parity pattern; induction to confirm; optional Jordan-form cross-check.

Solution

Strategy. The matrix has a block structure: row 1 is $(1,0,0)$, and the lower-right $2\times 2$ block $B=\begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}$ is the swap permutation. Compute $A^2$, observe a stable pattern, find a formula.

Step 1 — Compute $A^2$

$A^2=A\cdot A$. Row 1: $(1,0,0)A=(1,0,0)$. Row 2: $(1,0,1)A=(1,0,0)+(0,1,0)=(1,1,0)$. Row 3: $(0,1,0)A=(1,0,1)$.

Step 2 — Compute $A^3$

$A^3=A^2\cdot A$. Row 1: $(1,0,0)$. Row 2: $(1,1,0)A=(1,0,0)+(1,0,1)=(2,0,1)$. Row 3: $(1,0,1)A=(1,0,0)+(0,1,0)=(1,1,0)$.

Step 3 — Compute $A^4$

Row 1: $(1,0,0)$. Row 2: $(2,0,1)A=2(1,0,0)+(0,1,0)=(2,1,0)$. Row 3: $(1,1,0)A=(1,0,0)+(0,0,1)+0=(1,0,1)$.

Hmm let me recompute row 3 of $A^4$: $(1,1,0)A$ means $1\cdot R_1(A)+1\cdot R_2(A)+0\cdot R_3(A)=(1,0,0)+(1,0,1)+(0,0,0)=(2,0,1)$.

And row 2 of $A^4$: $(2,0,1)A=2(1,0,0)+0+1(0,1,0)=(2,1,0)$.

Step 4 — Spot the pattern

Compare:

• $A^1$: row 2 = $(1,0,1)$, row 3 = $(0,1,0)$.
• $A^2$: row 2 = $(1,1,0)$, row 3 = $(1,0,1)$.
• $A^3$: row 2 = $(2,0,1)$, row 3 = $(1,1,0)$.
• $A^4$: row 2 = $(2,1,0)$, row 3 = $(2,0,1)$.
• $A^5$: row 2 should be $(3,0,1)$, row 3 = $(2,1,0)$.

The pattern by parity:

• For $n$ even, $A^n=\begin{pmatrix}1 & 0 & 0\\ n/2 & 1 & 0\\ n/2 & 0 & 1\end{pmatrix}$.
• For $n$ odd, $A^n=\begin{pmatrix}1 & 0 & 0\\ (n+1)/2 & 0 & 1\\ (n-1)/2 & 1 & 0\end{pmatrix}$.

Check $A^2$: $n/2=1$, matrix $\begin{pmatrix}1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 0 & 1\end{pmatrix}$ ✓. Check $A^4$: $n/2=2$, matrix $\begin{pmatrix}1 & 0 & 0\\ 2 & 1 & 0\\ 2 & 0 & 1\end{pmatrix}$ ✓.

Check $A^3$: $(n+1)/2=2$, $(n-1)/2=1$, matrix $\begin{pmatrix}1 & 0 & 0\\ 2 & 0 & 1\\ 1 & 1 & 0\end{pmatrix}$ ✓.

Step 5 — Prove the even-case formula by induction (sketch)

For $n=2k$ assume $A^{2k}=\begin{pmatrix}1 & 0 & 0\\ k & 1 & 0\\ k & 0 & 1\end{pmatrix}$. Then $A^{2k+2}=A^{2k}\cdot A^2$:

Row 2 of product: $(k,1,0)\cdot A^2=k(1,0,0)+(1,1,0)+0=(k+1,1,0)$. ✓ Row 3 of product: $(k,0,1)\cdot A^2=k(1,0,0)+0+(1,0,1)=(k+1,0,1)$. ✓

Hence by induction the even-case formula holds.

Step 6 — Apply $n=30$

$n=30=2\cdot 15$, so $n/2=15$:

Answer