# 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
– Set
Commented May 26, 2015 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! Commented May 26, 2015 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.
– Set
Commented May 26, 2015 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! Commented May 26, 2015 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.
– Set
Commented May 26, 2015 at 5:02

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
Commented May 26, 2015 at 17:23
• Very nice approach! +1. Commented May 26, 2015 at 21:20
• you are reinventing cayley-hamilton theorem!
– abel
Commented May 27, 2015 at 2:55

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.

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! Commented May 26, 2015 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
Commented May 26, 2015 at 17:32
• @Ian, $q(x)$ is the quotient polynomial produced by the polynomial division algorithm.
– abel
Commented May 26, 2015 at 17:34
• ......+1 Because used simple method...
– k1.M
Commented May 26, 2015 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
Commented May 26, 2015 at 17:38
• This method is very helpful, because working with this is better and simpler than diagonalizing...
– k1.M
Commented May 26, 2015 at 17:41

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