$A^{n}$ matrix problem without using $A=PDP^{-1}$ Eigendecomposition

Question

i have the following problem

Find $A^n$ for the following matrix

\begin{equation} A=\begin{pmatrix} 0 & 0 & 1\\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \end{equation}

I have tried the following, calculating for $n=1,2,3,4,5,6$

\begin{equation} A^1=\begin{pmatrix} 0 & 0 & 1\\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \qquad \qquad A^2=\begin{pmatrix} 1 & 1 & 1\\ 1 & 2 & 2 \\ 1 & 2 & 3 \end{pmatrix} \qquad \qquad A^3=\begin{pmatrix} 1 & 2 & 3\\ 2 & 4 & 5 \\ 3 & 5 & 6 \end{pmatrix} \\ A^4=\begin{pmatrix} 3 & 5 & 6\\ 5 & 9 & 11 \\ 6 & 11 & 14 \end{pmatrix} \qquad \qquad A^5=\begin{pmatrix} 6 & 11 & 14\\ 11 & 20 & 25 \\ 14 & 25 & 31 \end{pmatrix} \qquad \qquad A^6=\begin{pmatrix} 14 & 25 & 31\\ 25 & 45 & 56 \\ 31 & 56 & 70 \end{pmatrix} \end{equation}

That gives the following terms

\begin{equation} A_{11} = 0,1,1,3,6,14,...\\ A_{12} = 0,1,2,5,11,25,...\\ A_{22} = 1,2,4,9,20,45,... \end{equation}

But i can't figure out the succesion in terms of n.

Answer 1

With $\{e_1, e_2, e_3\}$ as your base, check what happens when you operate on them $$Ae_1 = e_3 \implies A^ne_1 = A^{n-1}e_3$$ $$Ae_2 = e_2+e_3 \implies A^ne_2 = A^{n-1}(e_2+e_3) = A^{n-1}e_3 + A^{n-1}e_2$$ $$Ae_3 = e_1+e_2+e_3\implies A^ne_3 = A^{n-1}(e_1+e_2+e_3) = $$ $$ = A^{n-1}e_1+A^{n-1}e_2+A^{n-1}e_3 = 2A^{n-2}e_3+A^{n-2}e_2 +A^{n-1}e_3$$ This implies a recursive expression for each of your columns, maybe it can be tweaked a bit further.

Answer 2

The following solution is using the eigenvalues in an implicit way.

$$A^3=2A^2+A-I_3$$

Which can be found by inspection or by calculating the characteristic polynomial.

Then, by long division $$X^n=Q(X)(X^3-2X^2-X+1)+aX^2+bX+c$$ You can find $a,b,c$ by setting $X=\lambda_{1,2,3}$ the solutions to $X^3-2X^2-X+1$ in the above equation.

Then, setting $x=A$ in the equation we get: $$A^n=aA^2+bA+C$$

Note The above implies that all entries of $A^n$ are of the form $c_1\lambda_1^n+c_2 \lambda_2^n+c_3 \lambda_3^n$ (which is consistent with diagonalisation). Since the roots $\lambda_{1,2,3}$ of the equation $$x^3-2x^2-x+1$$ are ugly, the formula is almost impossible to guess.