5

Compute $A^{100 }$ where $A = \begin{bmatrix} 1 &2 \\ 3& 4 \end{bmatrix}$.

I can calculate $A^{100}$ using a calculator, but my question is that is there any short formula/method or is their any trick to find the $A^{100}$?

jasmine
  • 14,457
  • 2
    Hint: Diagonalization (you have unique eigenvalues) and similar approaches are methods. See: https://en.wikipedia.org/wiki/Diagonalizable_matrix#Diagonalization. – Moo Jul 25 '18 at 01:09
  • 1
    To elaborate, supposing that $A$ can be diagonalized in the form $A=SDS^{-1}$ where $D$ is a diagonal matrix, one would have $A^n = (SDS^{-1})^n$ which by expanding and induction you would see simplifies dramatically to be $A^n = SD^n S^{-1}$, remembering also that the power of a diagonal matrix is extremely easy to compute. – JMoravitz Jul 25 '18 at 01:12
  • 3
    No. don't use diagonalization. That is a bad advice. You waste time computing eigenvalues, eigenvectors, operations that potentially take you out of the ring of coefficients. The ideal (no pun intended) solution for this problem is the following: Compute the characteristic polynomial $p(x)$, which will have degree only $2$. By Hamilton-Cayley $p(A)=0$. Divide $x^{100}=p(x)q(x)+ax+b$. Then $A^{100}=p(A)q(A)+aA+b=aA+b$. –  Jul 25 '18 at 01:17
  • Does it have to be the matrix you've written down? It isn't the best example to start with in attempting to understand this process. You may want to consider something simpler, like $$\begin{pmatrix}1&2\2&1\end{pmatrix}$$, which has a nice diagonal form. – Chickenmancer Jul 25 '18 at 01:20
  • @nextpuzzle Great idea, but you don't really want to divide, do you? $q$ has degree $98.$ Wouldn't it be better to compute $x^{100}$ modulo $p$ by repeated squaring? – saulspatz Jul 25 '18 at 01:31
  • 2
    To complete my comment above. Since $x^{100}=p(x)q(x)+ax+b$ and we only need $a,b$, then we can evaluate at the roots $r1,r2=\frac{5\pm\sqrt{33}}{2}$ of $p(x)$. We get $r_1^{100}=ar_1+b$ and $r_2^{100}=ar_2+b$. From where $a=\frac{r_1^{100}-r_2^{100}}{r_1-r_2}$ and $b=\frac{r_1r_2^{100}-r_2r_1^{100}}{r_1-r_2}$. Therefore, $A^{100}=\frac{r_1^{100}-r_2^{100}}{r_1-r_2}A+\frac{r_1r_2^{100}-r_2r_1^{100}}{r_1-r_2}$. –  Jul 25 '18 at 01:34
  • @saulspatz You don't need $q$. You only need $a$ and $b$. –  Jul 25 '18 at 01:34
  • @nextpuzzle Yes, that was my point. Your comment says to divide $x^{100}$ by $p$ and I don't think you really mean that. – saulspatz Jul 25 '18 at 01:36
  • See OEIS sequence A100638. – Robert Israel Jul 25 '18 at 02:02
  • Are you trying for an approximate (floating-point) result, or exact integers? For the exact integers, the eigenvalue-based methods may not be so convenient, as the eigenvalues are irrational. Repeated squaring may be better. – Robert Israel Jul 25 '18 at 02:10
  • @nextpuzzle You should write up answers as answers instead of comments. – amd Jul 25 '18 at 02:21

5 Answers5

3

The conventional answer is going to be to diagonalize the matrix into $A=P\Lambda P^{-1}$ and then compute $P\Lambda^{100}P^{-1}$, but once you have the eigenvalues $\lambda_1$ and $\lambda_2$ there are ways to do this without computing an eigenbasis:

  • Decompose $A$ into $\lambda_1P_1+\lambda_2P_2$, where $P_1$ and $P_2$ are projections onto the corresponding eigenspaces with $P_1P_2=P_2P_1=0$. There’s a fairly simply formula for these projections in terms of $A$ and the two eigenvalues. If you expand $A^{100}$ using the binomial theorem, you’ll find that all but two terms vanish.
  • Use the Cayley-Hamilton theorem to write $A^{100}=aI+bA$ for some undetermined coefficients $a$ and $b$. This equation is also satisfied by the eigenvalues, which gives you the system of linear equations $a+b\lambda_i=\lambda_i^{100}$ for $a$ and $b$.

The above assumes that $A$ has distinct real eigenvalues. If they’re not, you will have to modify the above methods a bit.

amd
  • 53,693
3

There is no need for diagonalizations.

The eigenvalues of $$A = \begin{bmatrix} 1 &2 \\ 3& 4 \end{bmatrix}$$ are $$\frac {5\pm\sqrt {33}}{2}$$

Cayley-Hamilton Theorem indicates that $$A^{100}=\alpha A + \beta I.$$

We can find the coefficients $\alpha$ and $\beta $ by equations

$$ \alpha \lambda _1 +\beta = \lambda _1^{100}\\ \alpha \lambda _2 +\beta = \lambda _2^{100}$$ Where $\lambda _1$ and $\lambda _2$ are eighenvalues of $A.$

Mohammad Riazi-Kermani
  • 68,728
2

You could use diagonalization.

Let $A$ be a matrix then if you diagonalize $A$ then you get $A=PBP^{-1}$ with $B$ as a diagonal matrix and $P^{-1}$ an invertible matrix. If you try for $A^2$, then it is equal to $A^2=PB^2P^{-1}$. Similarly for $A^n=PB^nP^{-1}$

$A^{100}=PB^{100}P^{-1}$

Key Flex
  • 9,475
  • 7
  • 17
  • 34
2

You can first diagonalize the matrix as follows: $$A=P^{-1}DP,$$ where $P$ is an orthogonal matrix. The matrix $P$ is the matrix of eigenvectors $\{v_1,v_2\}$ that correspond to eigenvalues $\{\lambda_1,\lambda_2\}$ of $A$. Here, $$D=\mathrm{diag}\{\lambda_1,\lambda_2 \}$$

After diagonalizing, you can calculate $A^{100}$ as follows: $$A^{100} = (P^{-1}DP)^{100}=P^{-1}D^{100}P = P^{-1}\mathrm{diag}\{\lambda_1^{100},\lambda_2^{100}\}P. $$

Math Lover
  • 15,153
gph
  • 21
  • what is value of P ?? as i can not able find the value of P – jasmine Jul 25 '18 at 14:01
  • @stupid http://wwwf.imperial.ac.uk/metric/metric_public/matrices/eigenvalues_and_eigenvectors/eigenvalues2.html – gph Jul 26 '18 at 01:16
  • @stupid this is an very clear tutorial about how to compute the eigenvalues and eigenvectors of a matrix. after you have found the eigenvectors ${v_1,v_2,..}$,you will have to change them to orthonormal basis${u_1,u_2,...}$, that is they are orthogonal to each other, and each of them have length one. This procedure can be done by "gram-schmidt orthogonalization", you can find many tutorials such as http://www.math.usm.edu/lambers/mat415/lecture3.pdf. Then $P^{-1}=P'=[u_1,u_2,...]$ It is solved. P is orthogonal matrix. – gph Jul 26 '18 at 01:29
1

Hint: the characteristic function of the matrix is $$\lambda^2=5\lambda+2$$so according to Caylay-Hamilton theorem we have $$A^2=5A+2$$

Mostafa Ayaz
  • 31,924