# Find an expression for $A^n = \left( \begin{array}{cc} 1 & 4 \\ 2 & 3 \end{array} \right)^n$

We want to find an expression for $A^n = \left( \begin{array}{cc} 1 & 4 \\ 2 & 3 \end{array} \right)^n$ for an arbitrary "n".

I have tried writing out a few elements of the sequence as $n \to \infty$:

• $A^2 = \left( \begin{array}{cc} 9 & 16 \\ 8 & 17 \end{array} \right)$
• $A^3 = \left( \begin{array}{cc} 41 & 84 \\ 36 & 51 \end{array} \right)$

However, a pattern doesn't seem to appear.

This is where I want to ask my question: if we put this matrix into reduced-row echelon form, would an expression of the $(reduced matrix)^n$ work as an expression for the original matrix $A$?

i.e. reduced-row matrix $= \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)^n$. Then, we know that any diagonal matrix to the $n^{th}$ is just the diagonal entries to the $n^{th}$ and this would make an expression easy to come up with.

Thank you!

• try an eigen-decomposition – Thoth May 26 '15 at 4:51
• How did you know this would be useful? Just curious how you were able to come up with this answer just by looking at the problem! – David South May 26 '15 at 4:55
• as long as the matrix is non-defective (distinct eigenvalues is enough), then the eigenvalues of $A^n$ are just the eigenvalues of $A$ all raised to the $nth$ power. Raising the eigen-decomposition to the $nth$ power and simplifying shows you why. – Thoth May 26 '15 at 4:57
• Non-defective? What other conditions must a matrix satisfy (other than having distinct eigenvalues) to be non-defective? Thank you for your insight thus far! – David South May 26 '15 at 5:01
• having distinct eigenvalues is actually a stronger condition than non-defectivity. A matrix is non-defective if for each eigenvalue its algebraic multiplicity is equal to its geometric multiplicity. Or conversely, a matrix is defective if it has an eigenvalue whose geometric multiplicity is less than its algebraic multiplicity, which means its eigenvectors don't form a basis for the vector space. – Thoth May 26 '15 at 5:02

Performing row operations is the same as left-multiplication by elementary matrices: http://en.wikipedia.org/wiki/Elementary_matrix

Here is your question in these terms: If $E_1,\cdots,E_n$ is are elementary matrices, can we find a useful relation between $(E_1\cdots E_n A)^n$ and $A^n$? It doesn't look like a good strategy!

However if you manage to diagonalize $A$ by solving its eigenvalue problem, then you will have a matrix $S$ with $SAS^{-1}$ diagonal. The easy relation $(SAS^{-1})^n=SA^nS^{-1}$ should then help you out.

In problems such as these one of the most efficient ways to calculate powers of a matrix is through diference equations. For the matrix of this problem the following is obtained.

Given \begin{align} A = \left( \begin{array}{cc} 1 & 4 \\ 2 & 3 \end{array} \right) \end{align} it is found that \begin{align} A^{2} = \left( \begin{array}{cc} 9 & 16 \\ 8 & 17 \end{array} \right) \hspace{10mm} A^{3} = \left( \begin{array}{cc} 41 & 84 \\ 42 & 83 \end{array} \right). \end{align} The problem asks for the values of $A^{n}$. This is done by letting \begin{align} A^{n} = \left( \begin{array}{cc} a_{n} & b_{n} \\ c_{n} & d_{n} \end{array} \right). \end{align} With this and $A^{n} = A \cdot A^{n-1}$ then \begin{align} \left( \begin{array}{cc} a_{n} & b_{n} \\ c_{n} & d_{n} \end{array} \right) = \left( \begin{array}{cc} 1 & 4 \\ 2 & 3 \end{array} \right) \left( \begin{array}{cc} a_{n-1} & b_{n-1} \\ c_{n-1} & d_{n-1} \end{array} \right). \end{align} From this equation it is quickly determined that \begin{align} a_{n} &= a_{n-1} + 4 c_{n-1} \hspace{12mm} b_{n} = b_{n-1} + 4 d_{n-1} \\ c_{n} &= 2 a_{n-1} + 3 c_{n-1} \hspace{10mm} d_{n} = 2 b_{n-1} + 3 d_{n-1}. \end{align} These equations are reducible to the second order difference equation, $\phi_{n} \in \{ a_{n} , b_{n}, c_{n}, d_{n} \}$, \begin{align} \phi_{n+2} = 4 \phi_{n-1} + 5 \phi_{n} \end{align} which has the solution \begin{align} \phi_{n} = A \, 5^{n} + B \, (-1)^{n}. \end{align} Now returnig to the first few powers of $A$ the conditions \begin{align} a_{1} &= 1, a_{2} = 9, a_{3} = 41 \\ b_{1} &= 4, b_{2} = 16, b_{3} = 84 \\ c_{1} &= 2, c_{2} = 8, c_{3} = 42 \\ d_{1} &= 3, d_{2} = 17, d_{3} = 83 \end{align} are obtained. The second order difference equation equation can be solved for each of the condition sets and is determined that \begin{align} a_{n} &= \frac{1}{3} \left( 5^{n} + 2 (-1)^{n} \right) \hspace{10mm} b_{n} = \frac{2}{3} \left( 5^{n} - (-1)^{n} \right) \\ c_{n} &= \frac{1}{3} \left( 5^{n} - (-1)^{n} \right) \hspace{12mm} d_{n} = \frac{1}{3} \left( 2 \cdot 5^{n} + (-1)^{n} \right). \end{align} Putting this together the $n^{th}$-power of $A$ is given by \begin{align} A^{n} = \frac{1}{3} \left( \begin{array}{cc} 5^{n} + 2 (-1)^{n} & 2(5^{n} - (-1)^{n}) \\ 5^{n} - (-1)^{n} & 2 \cdot 5^{n} + (-1)^{n} \end{array} \right). \end{align}

• In my opinion, you are actually better off in the matrix setting than you are in the difference equation setting; that is, given a hard difference equation, I would inevitably convert it into a matrix iteration, and would almost never convert a matrix iteration to a difference equation. But this is opinion; as you have shown, the two approaches are equivalent. – Ian May 26 '15 at 17:23
• Very nice approach! +1. – Rogelio Molina May 26 '15 at 21:20
• you are reinventing cayley-hamilton theorem! – abel May 27 '15 at 2:55

Hint:

The matrix $\displaystyle A = \begin{pmatrix} 1 & 4 \\ 2 & 3 \end{pmatrix}$ is diagonalizable. That is, it can be written in the form $A = QDQ^{-1}$, where $D$ is a diagonal matrix and $Q$ is invertible. This is useful since $A^n = (QDQ^{-1})^n = QD^nQ^{-1}$, and it is very easy to compute powers of diagonal matrices.

• Glad I could help! – Kaj Hansen May 26 '15 at 5:07

you can also find $A^n$ using cayley-hamilton theorem which says that a matrix satisfies its own characteristic equation. the characteristic polynomial of $A$ is $$det (A-xI) = (x-5)(x+1).$$

by polynomial division algorithm, we can find constants $a$ and $b$ so that $$x^n = q(x)(x-5)(x+1) + ax + b \to a = \frac16\left(5^n - (-1)^n\right), b = \frac16\left(5^n + 5(-1)^n \right)$$

by cayley-hamilton, $$A^n = aA + bI.$$

• What's $q(x)$? You also have several typos. – Ian May 26 '15 at 17:32
• @Ian, $q(x)$ is the quotient polynomial produced by the polynomial division algorithm. – abel May 26 '15 at 17:34
• ......+1 Because used simple method... – k1.M May 26 '15 at 17:36
• @k1.M, thank you. there is no need to find eigenvectors. there is another method called putzers method that too works without ever finding the eigenvectors. – abel May 26 '15 at 17:38
• This method is very helpful, because working with this is better and simpler than diagonalizing... – k1.M May 26 '15 at 17:41

Hint. Try use the Jordan form of $A.$