Finding a 2x2 Matrix raised to the power of 1000

Let $A= \pmatrix{1&4\\ 3&2}$. Find $A^{1000}$.

Does this problem have to do with eigenvalues or is there another formula that is specific to 2x2 matrices?

-
Eigenvalues should do it. Does a formula exist? Probably, but it would just be the process of diagonalizing, written out in one line. – Eric Stucky Dec 8 '13 at 2:17
Unless there is a pattern specific to the matrix, usually one has to the diagonalize it. – David H Dec 8 '13 at 2:18
Abstract duplicate? of math.stackexchange.com/questions/55285/… – Eric Stucky Dec 8 '13 at 2:23

Check that you get $A=PBP^{-1}$ with $B$ a diagonal matrix with entries $-2$ and $5$, and $P$ an invertible matrix. Then note that $A^2=(PBP^{-1})(PBP^{-1})=PB^2P^{-1}$, and in general you get $$A^n=PB^nP^{-1}$$

The right hand side is easy to deal with since the power of a diagonal matrix is very easy to see :)

-

The well-known strategy is to diagonalize since this matrix is diagonalizable. For a change, here is a slightly different approach which is convenient for small matrices. If you have time, try to perform both methods until the end without computer help. This is fairly equivalent. Although you have two linear systems to solve for eigenvectors, and only one here for the constants $c,d$ below.

We will compute $A^n$.

Let $p_A(X)=X^2-3X-10$ be the characteristic polynomial of the matrix $A$. By Cayley-Hamilton, $p_A(A)=0$. So it suffices to determine the degree $\leq 1$ remainder in the Euclidean divison of $X^{n}$ by $p_A(X)$ to compute $A^{n}$.

For every $n\geq 1$, denote

$$X^n=q_n(X)p_A(X)+a_nX+b_n$$

the Euclidean division of $X^n$ by $p_A(X)$. Since $X^2\equiv 3X+10$ modulo $p_A(X)$, multiplication of the latter by $X$ yields $$\cases{a_{n=1}=3a_n+b_n \\b_{n+1}=10a_n}\iff\cases{a_{n+1}=3a_n+10a_{n-1}\\b_{n+1}=10a_n}$$ Solving for $a_n$ is straightforward given the theory of recurrent linear homogeneous sequences. Given that the roots of the characteristic equation (which is of course $p_A(X)=0$) are $-2$ and $5$, we have $a_n=c (-2)^n+d 5^n$. Considering the initial cases $n=0,1$, we find $c$ and $d$ whence

$$a_n=\frac{5^n-(-2)^{n}}{7}\quad\mbox{whence} \quad b_n=\frac{2\cdot 5^{n}+5(-2)^{n}}{7}$$

Therefore $$A^n=q_n(A)p_A(A)+a_nA+b_nI_2=a_nA+b_nI_2=\pmatrix{a_n+b_n&4a_n\\3a_n& 2a_n+b_n}$$ hence $A^n$ is equal to

$$A^n=\pmatrix{\frac{3\cdot 5^{n}+ (-2)^{n+2}}{7} & \frac{4\cdot 5^{n}- (-2)^{n+2}}{7} \\ \frac{3\cdot 5^{n}-3\cdot (-2)^{n}}{7} & \frac{4\cdot 5^{n}+3\cdot (-2)^{n}}{7}}$$

-

You should diagonalize it, if possible.

This means to find the eigenvalues and eigenvectors.

1. The eigenvalues are roots of the characteristic polynomial of $A$, which is $$\det\pmatrix{1-x&4\\3&2-x}=(1-x)(2-x)-12=x^2-3x-10\,.$$
2. If you find its roots, (which together sum up to $3$ and multiply to $-10$), then find an eigenvector for both ($v_1$ and $v_2$), [e.g. $v_2:=\pmatrix{1\\1}$ will be an eigenvector].
3. Then build the matrix $P$ with columns $(v_1|v_2)$, and calculate its inverse.
4. Finally, $D:=P^{-1}AP$ will be the diagonal containing the eigenvalues, because $$AP=A\,(v_1|v_2)=(\lambda_1 v_1\,|\,\lambda_2 v_2) = P\,\pmatrix{\lambda_1&0\\ 0&\lambda_2}$$

And after all these, you can easily raise $A$ to any power: $$A^{1000}=PD^{1000}P^{-1}\,.$$

-

Perform an eigenvalue decomposition of $A$, we then get $$A = \begin{bmatrix} -4/5 & -1/\sqrt2\\ 3/5 & -1/\sqrt2 \end{bmatrix} \begin{bmatrix} -2 & 0\\ 0 & 5 \end{bmatrix} \begin{bmatrix} -4/5 & -1/\sqrt2\\ 3/5 & -1/\sqrt2 \end{bmatrix}^{-1} =VDV^{-1}$$ where $V = \begin{bmatrix} -4/5 & -1/\sqrt2\\ 3/5 & -1/\sqrt2 \end{bmatrix}$ and $D = \begin{bmatrix} -2 & 0\\ 0 & 5 \end{bmatrix}$.

Hence, $$A^n = \underbrace{\left(VDV^{-1} \right)\left(VDV^{-1} \right)\cdots \left(VDV^{-1} \right)}_{n \text{ times}} = VD^n V^{-1}$$

-
This is a Jordan decomposition, not an eigenvalue decomposition (nor does an eigenvalue decomposition with a diagonal $D$ exist for non-symmetric/non-Hermitian matrix $A$), because $$V^*V = \begin{bmatrix} 1 & (5\sqrt{2})^{-1} \\ (5\sqrt{2})^{-1} & 1 \end{bmatrix} \ne {\rm I}_2.$$ – Vedran Šego Dec 8 '13 at 3:28

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $$A = \pars{\begin{array}{cc}1 & 4 \\ 3 & 2\end{array}} = {3 \over 2} \overbrace{\pars{\begin{array}{cc}1 & 0 \\ 0 & 1\end{array}}}^{\ds{1}} + \overbrace{{7 \over 2}}^{\ds{b_{x}}} \overbrace{\pars{\begin{array}{cc}0 & 1 \\ 1 & 0\end{array}}}^{\ds{\sigma_{x}}} + \overbrace{\half\,\ic}^{\ds{b_{y}}} \overbrace{\pars{\begin{array}{cc}0 & -\ic \\ \ic & 0\end{array}}}^{\ds{\sigma_{y}}} \overbrace{- \half}^{\ds{b_{z}}}\overbrace{\pars{\begin{array}{cc}1 & 0 \\ 1 & -1\end{array}}}^{\ds{\sigma_{z}}} = {3 \over 2} + \vec{b}\cdot\vec{\sigma}$$ where $\braces{\sigma_{\ell}\,,\ \ell = x, y, z}$ are the Pauli matrices. Then, $\expo{At} = \expo{3t/2}\expo{\vec{b}\cdot\vec{\sigma}t}$. However, $\vec{b}\cdot\vec{\sigma}\vec{b}\cdot\vec{\sigma} = \vec{b}\cdot\vec{b} = 49/4$ such that $$\pars{\totald[2]{}{t} - {49 \over 4}}\expo{\vec{b}\cdot\vec{\sigma}t} = 0 \quad\imp\quad \expo{\vec{b}\cdot\vec{\sigma}t} = \mu\expo{7t/2} + \nu\expo{-7t/2}\,,\quad \mu, \nu\ \mbox{are constants},$$ with $1 = \mu + \nu$ and $2\vec{b}\cdot\vec{\sigma}/7 = \mu - \nu$ such that $\mu = 1/2 + \vec{b}\cdot\vec{\sigma}/7$ and $\nu = 1/2 - \vec{b}\cdot\vec{\sigma}/7$: $$\expo{At} = \mu\expo{5t} + \nu\expo{-2t}\,, \quad\sum_{n = 0}^{\infty}{t^{n} \over n!}\,A^{n} = \sum_{n = 0}^{\infty}{t^{n} \over n!}\, \bracks{5^{n}\mu + \pars{-1}^{n}2^{n}\nu}$$ $$\color{#0000ff}{\large% \left\lbrace% \begin{array}{rcl} A^{n} = 5^{n}\mu + \pars{-1}^{n}2^{n}\nu & = & \half\bracks{5^{n} + \pars{-1}^{n}2^{n}} + {1 \over 7}\bracks{5^{n} - \pars{-1}^{n}2^{n}}\vec{b}\cdot\vec{\sigma} \\[3mm] \vec{b}\cdot\vec{\sigma} & = & A - {3 \over 2} = \pars{\begin{array}{cc}-1/2 & 5/2 \\ 3/2 & 1/2\end{array}} = \half\pars{\begin{array}{cc}-1 & 5 \\ 3 & 1\end{array}} \end{array}\right.}$$

-