# Identify a formula for each entry of the matrix $\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?

-

1
Diagonalize.${}$ – Chris Eagle Feb 14 at 11:30

1
with Cayley-Hamilton theorem – Mercy Feb 14 at 11:30

6
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 at 11:32

1
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 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 at 11:43
show 1 more comment

## 4 Answers

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 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 14, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8875111937522888, "perplexity_flag": "middle"}