# Find $3a+b+3c+4d$ if $\left(\begin{smallmatrix}-4&-15\\2&7\end{smallmatrix}\right)^{100}=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)$.

Let $$\begin{pmatrix} -4 & -15 \\ 2 & 7 \end{pmatrix}^{100} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$.
Find $$3a + b + 3c + 4d$$.
I've gotten this answer for the matrix to the 100th power (via calculator), but it's HUGE. I need a simpler method to find it. Can I get some tips please?

Let $A=\begin{pmatrix}-4&-15\\2&7\end{pmatrix}$. By Cayley-Hamilton theorem, we get $A^2-3A+2I=O$. Thus $A^n$ can be represented as the sum of $A$ and $I$; that is, there are $a_n$ and $b_n$ such that $A^n = a_n A + b_n I$. Then \begin{align} A^{n+1}&=a_n A^2+b_n A\\ &=a_n(3A-2I)+b_n A\\ &=(3a_n +b_n)A-2a_n I. \end{align} We get $$\begin{cases} a_{n+1}=3a_n+b_n\\ b_{n+1} = -2a_n. \end{cases}$$ Now we can construct the linear recurrence relation of second order for $a_n$: $$a_{n+2}=3a_{n+1}-2a_n.$$ Thus, $a_n = c_1 2^n + c_2$ for some $c_1,c_2$. Since $a_1=1$ and $a_2=3$, $a_n = 2^n -1$, and $b_n = -2^n+2$. Also, \begin{align} A^{100}&= a_{100}A+b_{100}I\\ &=\begin{pmatrix} -4a_{100}+b_{100} & -15a_{100}\\ 2a_{100} & 7a_{100} + b_{100} \end{pmatrix}. \end{align} Therefore, \begin{align} 3a+b+3c+4d&=3(-4a_{100}+b_{100})-15a_{100}+3\cdot 2a_{100} +4(7a_{100}+b_{100})\\ &=7a_{100}+7b_{100}\\ &=7(2^{100}-1)+7(-2^{100}+2)\\ &=7. \end{align}

Hint: If $A$ is that matrix, then $A^2=3A-2I$ and so $A^n = (2^n-1)A-(2^n-2)I$.

Then you can compute $3a + b + 3c + 4d$ directly for $A^n$.

Or you can set $$\varphi\begin{pmatrix} a & b \\ c & d \end{pmatrix}=3a + b + 3c + 4d$$ and notice that $\varphi(A)=\varphi(I)=7$ and so $\varphi(A^n) = (2^n-1)\varphi(A)-(2^n-2)\varphi(I)=7$.

Let us denote $$A^n=\begin{pmatrix}a_n&b_n\\c_n&d_n\end{pmatrix}$$.

We have $$\operatorname{Tr}(A)=3$$, $$\det(A)=2$$ so the characteristic polynomial is $$\chi_A(t)=t^2-3t+2=(t-1)(t-2)$$; and we have the eigenvalues $$\lambda_1=1$$ a $$\lambda_2=2$$.

We can see that $$(2,5)A=(2,5)$$ and $$A\begin{pmatrix}3\\-1\end{pmatrix}=A\begin{pmatrix}3\\-1\end{pmatrix}$$. (These are simply the left and right eigenvectors corresponding to the eigenvalue $$\lambda_1=1$$.)

By induction we can get that $$(2,5)A^n=(2,5)$$ and $$A^n\begin{pmatrix}3\\-1\end{pmatrix}=\begin{pmatrix}3\\-1\end{pmatrix}$$ (for each integer $$n$$ such that $$n\ge0$$). By rewriting these equalities using $$a_n,\ldots,d_n$$ we get several expressions which are constant (independent of $$n$$): \begin{align*} 2a_n+5c_n&=2\\ 2b_n+5d_n&=5\\ 3a_n-b_n&=3\\ 3c_n-d_n&=-1 \end{align*} By adding the last three we get: \begin{align*} (3a_n-b_n)+(2b_n+5d_n)+(3c_n-d_n)&=3+5-1\\ 3a_n+b_n+3c_n+4d_n&=7 \end{align*}