Learn / Library / Linear algebra

Repeated multiplication

Linear algebraHard

Raise the matrix $A = [1120]$ to the power $8$ , by repeated squaring or any other method. What number stands in the top left corner of $A^{8}$ ?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Find the eigenvalues; every entry of a power of $A$ is then a fixed combination of their powers.

Solution

The characteristic polynomial is $λ^{2} - λ - 2 = (λ - 2) (λ + 1)$ , so the eigenvalues are $2$ and $- 1$ .
So the top left entry of $A^{n}$ has the form $c_{1} \times 2^{n} + c_{2} \times (- 1)^{n}$ for fixed numbers $c_{1}$ and $c_{2}$ .
Since $A^{2} = [3122]$ , that entry is $1$ at $n = 1$ and $3$ at $n = 2$ , so $2 c_{1} - c_{2} = 1$ and $4 c_{1} + c_{2} = 3$ , giving $c_{1} = \frac{2}{3}$ and $c_{2} = \frac{1}{3}$ .
For $n = 8$ the entry is $\frac{2}{3} \times 256 + \frac{1}{3} \times 1 = \frac{513}{3} = 171$ .

Answer: $171$