How to determine $A^n$ based on the division of its characteristic polynomial?

Question

Let $$\begin{bmatrix} 2 &1 & 1 & -1\\ 0& 1& -1& 1\\ -1 & -1& 1& 0\\ -1& -1& -1& 2 \end{bmatrix} $$

I found its eigenvalues to be $1$ and $2$.

Its characteristic polynomial is $(\lambda - 1)^2(\lambda -2)^2$.

Its minimal polynomial is $(\lambda - 1)(\lambda -2)$.

Now I am asked to calculate the remainder of the Euclidian division of $(X-1)(X-2)$ by $X^n$ where $n \geq 1, n \in \mathbb{N}$. Here, I already struggle to do it.

Calculating the quotien of the division, I find $X^{\frac{2}{n}}-3X^{\frac{1}{n}}$ with a remainder of $2$, but this can't even be a quotient because a polynomial can't have non-natural powers.

How do I do this?

Answer 1

You're meant to divide $X^n$ by $(X-1)(X-2)$, not $(X-1)(X-2)$ by $X^n$.

Then, the remainder has degree at most $1$ and so $$ X^n = (X-1)(X-2)q(X) + aX+b $$ Now evaluate at $X=1$ and $X=2$ and solve the linear system $$ 1^n = a+b, \quad 2^n = 2a+b $$ to find $a,b$. This gives $$ A^n = aA + bI = (2^n-1)A+(2-2^n)I $$ because $(A-I)(A-2I)=0$.

Answer 2

A simple variant:

The remainder in the division of $P(X)$ by $(X-a)(X-b)$ $\;(a\ne b)$ is the determinant $$\frac1{a-b}\begin{vmatrix}P(a)&P(b)\\X-a&X-b\end{vmatrix}.$$ In the present case you obtain $$X^n\equiv 2^n(X-1)-(X-2)=(2^n-1)X+2-2^n\mod (X-1)(X-2).$$ Applying this congruence to $A$ yields $$A^n=(2^n-1)A+(2-2^n)I.$$