How to compute A to the power 25

Question

How to compute A to the power 25 if A is given? In my case A=\begin{bmatrix} 1 &1 &0 \\ -1 & 1 & 2\\ 2 &1 & -1 \end{bmatrix} I know that the minimal polynomial of A is $x^{3}-x^{2}-2x$ In book hint is find minimal polynomial and then use division algorithms. This prosses is lengthy. after dividing $x^{25}$ by $x^{3}-x^{2}-2x$ then remainder is $5505025x^{2}+5505024x$ is this write?

Answer 1

Try $A^2=A\cdot A$, $A^4 = A^2\cdot A^2$, $A^8 = A^4*A^4$, $A^{16}=A^8\cdot A^8$, $A^{24} = A^8\cdot A^{16}$, and $A^{25}=A^{24}\cdot A$. Generally, the Horner scheme is used. The number multiplications of matrices is $O(\log_2 n)$.

Answer 2

HINT

Note that

$$x^{3}-x^{2}-2x=x(x^2-x-2)=x(x+1)(x-2)$$

therefore, since we have three distinct eigenvalues, the matrix can be diagonalized

$$A=P^{-1}DP \implies A^2=P^{-1}DPP^{-1}DP=P^{-1}D^2P \implies \ldots$$

Answer 3

Hint:

$$A^3=A^2+2A$$

$$A^6=(A^2+2A)^2=A^4+4A^3+4A^2=A^3+2A^2+4A^2+8A+4A^2=11A^2+10A$$

$$A^{12}=(11A^2+10A)^2=\cdots$$

With a little more effort, you will obtain $A^{25}$ as a linear combination of $A^2$ and$A$, which is not great deal to compute.

[Computation not checked.]

Answer 4

(Divided into sections following OP's edit.)

If you don't know the minimal polynomial

Use the binary expansion of $25$ and repeated squaring.

$$ 25_{10} = 11001_2 \text{.} $$ So, \begin{align*} A^{2} &= A \cdot A \text{,} \\ A^{4} &= A^2 \cdot A^2 \text{,} \\ A^{8} &= A^4 \cdot A^4 \text{,} \\ A^{16} &= A^8 \cdot A^8 \text{, and} \\ A^{25} &= A^{16} A^8 A \text{.} \end{align*}

In this case, you perform four squarings and then two more matrix multiplications.

If you do know the minimal polynomial

You know that a matrix "is a root" of its minimal polynomial, $A^3 = A^2 + 2A$, so you can perform the exponentiation in a way to leverage this fact to reduce the degrees of terms repeatedly. This is frequently more work than the above, but sometimes, it can give you an answer surprisingly quickly. Here, it's more work \begin{align*} A^{25} &= (A^3)^8 \cdot A \\ &= (((A^2 + 2A)^2)^2)^2 \cdot A \\ &= ((A^4 + 4A^3 + 4A^2)^2)^2 \cdot A \\ &= ((A(A^2 + 2A) + 4(A^2+2A) + 4A^2)^2)^2 \cdot A \\ &= (((A^2 + 2A) + 2A^2 + 4A^2 + 8A + 4A^2)^2)^2 \cdot A \\ &= ((11A^2 + 10A)^2)^2 \cdot A \\ &= \dots \end{align*}