Matrix Exponentiation in Olympiad Problem [duplicate]

I am dealing with the test of the OBM (Brasilian Math Olympiad), University level, 2016, phase 2.

As I've said at this topic (question 1), this other (question 2) and this (question 3, yet open), I hope someone can help me to discuss this test. Thanks for any help.

The question 4 says:

Let $A=\begin{pmatrix}4&-\sqrt5\\ 2\sqrt5&-3\end{pmatrix}$.

Find all the pairs of numbers $(n,m)\in\mathbb{N}\times \mathbb{Z}$ with $|m|\leq n$ such that $A^n-(n^2+m)A$ has all the coordinates integers.

I'm trying solving this and I'd like a lot to have clues.

I'm doing some "simulations" and have an ideia about $a_{n21}$ (entry $21$ of the matrix $A^n$). It seems $x_n\sqrt{5}$ where $x_n=2$ to $n=1,2$ and $x_{n+2}=x_{n+1}+2x_n$. Maybe we can use something about recurrence. I'm trying.

Thank you.

This is a pure computation.

$A$ has characteristic polynomial $\chi_A(t)=t^2-t-2$, so has eigenvalues $2,-1$. By Cayley-Hamilton, $\chi_A(A)=0$ and so $$ A^{n+2}=A^{n+1}+2A^n. $$ Hence the diagonals are integers for all $n\in\mathbb{N}$. Also, we have an explicit formula for $A^n$:

$$A^n=\frac13\begin{pmatrix}(-2)(-1)^n+5\times 2^n & -(2^n-(-1)^n)\sqrt{5}\\2(2^n-(-1)^n)\sqrt{5} & 5(-1)^n-2^{n+1}\end{pmatrix}.$$ This is easily obtained from fitting the coefficients for $A^0=I$ and $A^1=A$.

The upshot is that we want

$$m=\frac{2^n-(-1)^n}3-n^2$$

for which there are only finitely many solution $\lvert m\rvert\leq n$:

since $2^n$ eventually dominates in the RHS.

It is easy enough to estimate when to stop looking:

if $2^n>6n^2$ then $2^n>3(n^2+n)$ so $m>n$. So we only need to compute up to $n\leq 7$.

The result is:

\begin{array}{c|c|c}n & m & \text{Solution?}\\\hline0 & 0 & \text{Yes}\\1 & 0 & \text{Yes}\\2 & -3 & \text{No}\\3 & -6 & \text{No}\\4 & -11 & \text{No}\\5 & -14 & \text{No}\\6 & -15 & \text{No}\\7 & -6 & \text{Yes}\end{array}

The examiner seems to have a sense of humour: Note that the only nontrivial solution gives $A^n-(n^2+m)A=42I$, so maybe this is motivated by the "Answer to the Ultimate Question of Life, the Universe, and Everything" in Hitchhiker's Guide to the Galaxy?

Observation: in the answer above, note that $A = S\Lambda S^{-1}$ (this implies $A^n = S\Lambda^n S^{-1}$), since A is diagonalizable matrix. Now, since the eigenvalues are $\lambda_1 = -1$ and $\lambda_2 = 2$ (note that we decided to choose this order), we have that:

$$\Lambda=\begin{pmatrix}\lambda_1&0\\ 0&\lambda_2\end{pmatrix}$$

Now observe that it can be proven that:

$$\Lambda^n=\begin{pmatrix}\lambda_1^n&0\\ 0&\lambda_2^n\end{pmatrix}$$

So it follows:

$$\Lambda=\begin{pmatrix}(-1)^n&0\\ 0&2^n\end{pmatrix}$$

$S$ is given by the matrix the "composition" of the eigenvectors, corresponding respectively to $\lambda_1$ and $\lambda_2$. Supose $v_1$ and $v_2$, they are given by the column vectors:

$$v_1 = (1, \sqrt 5 ) $$ and $$v_2 = (\sqrt 5, 1) $$

So, we have that:

$$S=\begin{pmatrix}1&\sqrt5\\ \sqrt5&1\end{pmatrix}$$

And the inverse can be found easily.