# Identify a formula for each entry of the matrix $\small \begin{pmatrix} 1 & 3 \\ 2 & 6 \end{pmatrix}^n$

Identify a formula for each entry of the matrix $\begin{pmatrix} 1 & 3 \\ 2 & 6 \end{pmatrix}^n$.

It's easy to find a solution by just looking at the first few results: \begin{pmatrix} 7^{n-1} & 3\cdot 7^{n-1} \\ 2\cdot 7^{n-1} & 6\cdot 7^{n-1} \end{pmatrix}

But how would I do it if it wasn't so obvious?

-
Diagonalize.${}$ –  Chris Eagle Feb 14 '13 at 11:30
with Cayley-Hamilton theorem –  Mercy Feb 14 '13 at 11:30
If $M = A^{-1}DA$ then $M^n = A^{-1}D^nA$. If $D$ is diagonal, $D^n$ can be easily calculated. –  Alfonso Fernandez Feb 14 '13 at 11:32
Diagonalization is the "standard" way to solve this kind of problems. In your particular case, however, your matrix is equal to $uv^T$, where $u^T=(1,2)$ and $v^T=(1,3)$. Therefore $(uv^T)^n=u(v^Tu)(v^Tu)v^T\cdots u(v^Tu)v^T=(v^Tu)^{n-1}uv^T$. –  user1551 Feb 14 '13 at 11:41
Or you can use inducion. For $n=1$ it is clearly true. Now suppose it is true for some natural $n$. And prove that it is true for $n+1$. –  Tomas Feb 14 '13 at 11:43

Fleshing out a little what the comments hint you:

$$\det(tI-A)=\begin{vmatrix}t-1&-3\\-2&t-6\end{vmatrix}=t(t-7)\Longrightarrow$$

the matrix's eigenvalues are $\,0\,,\,7\,$ , and eigenvectors for these values can be found as follows:

$$(1)\,\,\lambda=0:\;\;\;\;\begin{cases}\;\,-x-3y=0\\{}\\-2x-6y=0\end{cases}\;\;\Longrightarrow x=-3y\Longrightarrow\,\,\text{for example}\,\,\binom{3}{\!\!-1}$$

$$(1)\,\,\lambda=t:\;\;\;\;\begin{cases}\;6x-3y=0\\{}\\-2x+y=0\end{cases}\;\;\Longrightarrow y=2y\Longrightarrow\,\,\text{for example}\,\,\binom{1}{2}$$

Form now the matrix

$$P:=\begin{pmatrix}3&1\\\!\!\!-1&2\end{pmatrix}\Longrightarrow P^{-1}=\begin{pmatrix}\frac{2}{7}&\!\!\!-\frac{1}{7}\\{}\\\frac{1}{7}&\;\frac{3}{7}\end{pmatrix}$$

so that

$$P^{-1}AP=\begin{pmatrix}0&0\\0&7\end{pmatrix}=:D$$

And now it is a piece of cake:

$$A^n=\left(PDP^{-1}\right)^n=PD^nP^{-1}\;\;,\;\;\text{and}\;\;\;D^n=\begin{pmatrix}0&0\\0&7^n\end{pmatrix}\ldots$$

-
Nice formula for $D^n$ + –  Babak S. Feb 15 '13 at 9:07

Diagonalization works generally, but it's overkill here. Simpler, note that the 2nd row is twice the 1st, which must stay true for $\rm\,A^n\,$ too since $\rm\, vA = (2,-1)A = 0\,$ $\Rightarrow$ $\rm\,vA^n = (vA)A^{n-1}\! = 0.\:$ So

$$\rm \left[\begin{array}{rr}\rm a_{n+1}\!\!\!\! &\rm b_{n+1}\\ \rm 2a_{n+1}\!\!\!\! &\rm 2b_{n+1}\end{array}\!\right] = \left[\begin{array}{cc}1 \!\!&\rm 3\\ 2\!\! &\rm 6\end{array}\!\right] \left[\begin{array}{rr}\rm a_{n}\!\!\!\! &\rm b_{n}\\ \rm 2a_{n}\!\!\!\! &\rm 2b_{n}\end{array}\right]\Rightarrow \begin{array}{ll} \rm a_{n+1}\! = 7 a_n\!= 7^n a_0\! = 7^n\\ \rm b_{n+1}\! = 7 b_n\! = 7^n b_0\! = 3\!\cdot\! 7^n\end{array} \!\Rightarrow A^{\!n+1} \! = \left[\begin{array}{rr}\rm 7^n\!\!\! &\rm 3\!\cdot\! 7^n\\ \rm 2\!\cdot\! 7^n\!\!\!&\rm 6\!\cdot\! 7^n\end{array}\right]$$

-

$$A^2-Tr(A)\cdot A +\det{A}\cdot I_{2}=O_{2}.$$

$$\det{A}=6-6=0.$$

$$A^{2}=Tr(A) \cdot A=7 \cdot A.$$

$$A^{2}=7A.$$ $$A^{3}=7A^{2}=7^{2}A.$$ $$\vdots$$ $$A^{n}=7^{n-1}\cdot A$$

for me, this proof is more simple.

-

I expand the Mercy's idea with Cayley-Hamilton theorem because I like it.

Let $p(\lambda) = \text{det}(A-\lambda I)$ characteristic polynomial of A. Than you can write $\lambda^n = p(\lambda)g(\lambda) + q(\lambda)$, where $\deg(q)<\deg(p)$. By Cayley-Hamilton theorem you get $A^n = q(A)$. So you need only calculate $A^1,..,A^{m-1}$ where $m$ is dimension of matrix.

-