7
$\begingroup$

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!

$\endgroup$
7
  • 3
    $\begingroup$ try an eigen-decomposition $\endgroup$
    – Set
    Commented May 26, 2015 at 4:51
  • $\begingroup$ 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! $\endgroup$ Commented May 26, 2015 at 4:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – Set
    Commented May 26, 2015 at 4:57
  • $\begingroup$ 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! $\endgroup$ Commented May 26, 2015 at 5:01
  • 3
    $\begingroup$ 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. $\endgroup$
    – Set
    Commented May 26, 2015 at 5:02

5 Answers 5

15
$\begingroup$

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}

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

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.

$\endgroup$
7
$\begingroup$

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.

Click here for a reference on performing diagonalization.

$\endgroup$
1
  • $\begingroup$ Glad I could help! $\endgroup$
    – Kaj Hansen
    Commented May 26, 2015 at 5:07
5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ What's $q(x)$? You also have several typos. $\endgroup$
    – Ian
    Commented May 26, 2015 at 17:32
  • $\begingroup$ @Ian, $q(x)$ is the quotient polynomial produced by the polynomial division algorithm. $\endgroup$
    – abel
    Commented May 26, 2015 at 17:34
  • $\begingroup$ ......+1 Because used simple method... $\endgroup$
    – k1.M
    Commented May 26, 2015 at 17:36
  • $\begingroup$ @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. $\endgroup$
    – abel
    Commented May 26, 2015 at 17:38
  • $\begingroup$ This method is very helpful, because working with this is better and simpler than diagonalizing... $\endgroup$
    – k1.M
    Commented May 26, 2015 at 17:41
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .