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$
  • 2
    $\begingroup$ try an eigen-decomposition $\endgroup$ – Thoth May 26 '15 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$ – David South May 26 '15 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$ – Thoth May 26 '15 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$ – David South May 26 '15 at 5:01
  • 2
    $\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$ – Thoth May 26 '15 at 5:02
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$
14
$\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$
  • 1
    $\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 May 26 '15 at 17:23
  • 2
    $\begingroup$ Very nice approach! +1. $\endgroup$ – Rogelio Molina May 26 '15 at 21:20
  • $\begingroup$ you are reinventing cayley-hamilton theorem! $\endgroup$ – abel May 27 '15 at 2:55
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$
  • $\begingroup$ Glad I could help! $\endgroup$ – Kaj Hansen May 26 '15 at 5:07
4
$\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$
  • $\begingroup$ What's $q(x)$? You also have several typos. $\endgroup$ – Ian May 26 '15 at 17:32
  • $\begingroup$ @Ian, $q(x)$ is the quotient polynomial produced by the polynomial division algorithm. $\endgroup$ – abel May 26 '15 at 17:34
  • $\begingroup$ ......+1 Because used simple method... $\endgroup$ – k1.M May 26 '15 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 May 26 '15 at 17:38
  • $\begingroup$ This method is very helpful, because working with this is better and simpler than diagonalizing... $\endgroup$ – k1.M May 26 '15 at 17:41
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.