1

So i had to solve a problem for which i had to find $A^n$

Where A= $$ \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 2 & 1 \\ \end{bmatrix} $$

So what i did was find $A^2$= $$ \begin{bmatrix} 1 & 0 & 0 \\ 4 & 0 & 0 \\ 12 & 4 & 1 \\ \end{bmatrix} $$

Then $A^3$= $$ \begin{bmatrix} 1 & 0 & 0 \\ 6 & 1 & 0 \\ 24 & 6 & 1 \\ \end{bmatrix} $$

so then i noticed the pattern and proved it by induction.

$A^n$= $$ \begin{bmatrix} 1 & 0 & 0 \\ 2n & 1 & 0 \\ 2n(n+1) & 2n & 1 \\ \end{bmatrix} $$

Now this is a really troublesome method to solve these kind of questions. First of all it's not easy to notice the pattern . Then you could have to always guessed wrong ,so you have also verify with induction.

So i want to know is there a better to solve this question. Does that method work here only or is it possible to find $A^n$ for any A(a method which always work).I would be happy to know what you keep in mind or tricks you use while solving these kind of problems. Links are also welcomed.

And again thankyou all for your help.

aryan bansal
  • 1,923
  • 1
    If you are lucky, the best way for calculating $A^n$ is diagonalization.

    However, it seems that you are not lucky always. If matrix $A$ is not diagonalizable, Generally you can use Jordan Canonical form for calculating $A^n$. But normally it is not easy as diagonalization. So I think your induction argument is efficient enough. //Wiki link: https://en.wikipedia.org/wiki/Jordan_normal_form

     – Needmoremath Feb 07 '20 at 12:20
  • what's diagonalization? – aryan bansal Feb 07 '20 at 12:45
  • 1
    let us think matrix $A$ can be represented by $P \begin{pmatrix} a& 0\ 0 & b \end{pmatrix} P^{-1}$. Then you can easily see $A^n = P \begin{pmatrix} a^n& 0\ 0 & b^n \end{pmatrix} P^{-1}$. For more, see // https://en.wikipedia.org/wiki/Diagonalizable_matrix#Diagonalization . You may want 'Application to matrix functions' part. – Needmoremath Feb 07 '20 at 13:23

2 Answers2

3

Let $J=\pmatrix{0&0&0\\ 2&0&0\\ 0&2&0}$. Then $J^3=0$ and $$ A=I+J+J^2=1+J+J^2+J^3+\cdots=(I-J)^{-1}. $$ Thus \begin{aligned} A^n&=(I-J)^{-n}=\left[(I-J)^n\right]^{-1}\\ &=\left(I-nJ+\binom{n}{2}J^2+\binom{n}{3}J^3+\cdots\right)^{-1}\\ &=\left(I-nJ+\binom{n}{2}J^2\right)^{-1}\\ &=I+nJ+\left(n^2-\binom{n}{2}\right)J^2\\ &=\pmatrix{1&0&0\\ 2n&1&0\\ 2n(n+1)&2n&1}. \end{aligned}

user1551
  • 139,064
1

By the Cayley-Hamilton theorem, any $n \times n$ matrix $A$ satisfies its characteristic polynomial $P(x) = \det(x I - A)$. Let $P(x) = x^n + \sum_{j=0}^{n-1} c_j x^j$. Then we have the linear recurrence $$A^k = - \sum_{j=0}^{n-1} c_j A^{k-n+j}$$ The solutions to this recurrence will be of the form $$ A^k = \sum_i \lambda_i^k Q_i(k)$$ where $\lambda_i$ are the eigenvalues of $A$ and $Q_i$ is a matrix whose entries are polynomials of degree at most one less than the multiplicity of $\lambda_i$ as a root of $P$. Thus in your case the only eigenvalue is $1$, with multiplicity $3$, so the entries are polynomials of degree $\le 2$.

Robert Israel
  • 448,999