# To Find $A^{50}$ [duplicate]

$$A=\begin{bmatrix}1 & 0&0\\1 & 0&1\\0&1&0\end{bmatrix}$$
Find $A^{50}$ ?

Now from Cayley–Hamilton theorem, I get $A^3-A^2-A+I=0$ and $A^{50}=(A^4)^{12}A^2$ so I found $A^4$ which is $-2A-I$, then we have $A^{50}=B^{12}A^2$ where $B =A^4$ was calculated, now should I again use Cayley–Hamilton theorem to find $B^{12}$ or is there a better possibility?

• Do you know about diagonalization? Mar 29, 2014 at 18:10
• Would you please illustrate it? Mar 29, 2014 at 18:11
• You can't diagonalize this matrix. The geometric multiplicity is not equal to the algebraic multiplicity. Mar 29, 2014 at 18:12

Let $f(x) = x^3-x^2-x-1 = (x^2-1)(x-1) = (x-1)^2(x+1)$.
Since $f(A) = 0$, we want to find polynomial $q(x), r(x)$ such that $$x^{50} = q(x)f(x) + r(x)\tag{*1}$$ with $\deg r(x) \le \deg f(x) - 1 = 2$. If we can figure out what is $r(x)$, then

$$A^{50} = q(A)f(A) + r(A) = r(A)$$

Write $r(x)$ as $a x^2 + b x + c$. To fix the coefficients, evaluate both side of $(*1)$ at $1$ and $-1$ and the derivative at the double root $1$, we get:

$$\begin{cases} 1 &= a + b + c\\ 1 &= a - b + c\\ 50 &= 2a + b \end{cases} \quad\implies\quad \begin{cases} a &= 25\\ b &= 0\\ c &= 24\\ \end{cases} \quad\implies\quad r(x) = 25 x^2 - 24.$$ As a result,

$$A^{50} = 25 A^2 - 24 I = 25 \begin{pmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 0 & 1 \end{pmatrix} - 24 \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ 25 & 1 & 0\\ 25 & 0 & 1 \end{pmatrix}$$

• from where have you learnt this step:-> we want to find polynomial q(x),r(x) such that $x^{50} = q(x)f(x) + r(x)$.would you tell more regarding this step? plz add some basic explanation to first 2 steps. Mar 29, 2014 at 18:36
• @ketan, Cayley Hamilton theorem tell us we can reduce $A^{50}$ to a quadratic polynomial in $A$. To carry out the reduction, one need to subtract suitable multiple of $f(A)$ from $A^{50}$. If you think carefully, what we need is the properties of polynomials instead of anything that $A$ is an matrix. So we temporarily forget $A$ is a matrix and look at everything from the angle of polynomials. Once we are done, it will automatically works for the matrix $A$. Think of this as a general tactic to solve algebraic problem using correspondence between different types of algebraic structures. Mar 29, 2014 at 18:56
• @ketan That is long division of polynomials.
– OR.
Mar 29, 2014 at 18:57
• $\deg r(x) \le \deg f(x) - 1$ this is still mystery! how come this sir? also can this process be generalised? Mar 29, 2014 at 19:13
• @ketan if you have a $n \times n$ matrix $B$, Cayley Hamilton theorem tell us $B^n$ can be expressed in terms of $I,B,\ldots,B^{n-1}$. This implies for any $B^m$ with $m \ge n$, one can express $B^m$ in terms of $B^{m-n}, B^{m-n+1},\ldots,B^{m-1}$. If one repeat these steps, one find every $B^{m}$ with $m \ge n$ can be expressed in terms of $I,B,\ldots,B^{n-1}$. Translate this to polynomial, the degree of the remainder $r(x)$ is at most $n-1$. In our case of $A$, $n = 3$ and so degree of $r(x)$ is at most $2$. Mar 29, 2014 at 19:22

If you do a few calculations: $$A^2= \begin{bmatrix} 1&0&0\\1&1&0\\1&0&1 \end{bmatrix}$$$$A^4= \begin{bmatrix} 1&0&0\\2&1&0\\2&0&1 \end{bmatrix}$$$$A^6= \begin{bmatrix} 1&0&0\\3&1&0\\3&0&1 \end{bmatrix}$$ ...so then from here you can deduce the answer...

On a more rigorous note: note that $A^2=\begin{bmatrix} 1&0&0\\1&1&0\\1&0&1 \end{bmatrix} =(\begin{bmatrix} 0&0&0\\1&0&0\\1&0&0 \end{bmatrix}+I)$.

Now $\begin{bmatrix} 0&0&0\\1&0&0\\1&0&0 \end{bmatrix}^2 =0$.

So that $(\begin{bmatrix} 0&0&0\\1&0&0\\1&0&0 \end{bmatrix}+I)^{n}=\binom{n}{n-1} \begin{bmatrix} 0&0&0\\1&0&0\\1&0&0 \end{bmatrix}^1I^{n-1}+I^{n}=n\begin{bmatrix} 0&0&0\\1&0&0\\1&0&0 \end{bmatrix}I+I$.

(This last step is just using the binomial theorem combined with the result directly above it. You can write out the full binomial expansion and then just reduce to zero all higher powers of the nilpotent matrix.)

So then $A^{50}=(A^2)^{25}$, so that $n=25$ and the result follows.

• You mean induce. Mar 29, 2014 at 18:31
• nope, I mean deduction...but I guess, you could also use the principle of induction as a proof methodology in this specific case, yes. Mar 29, 2014 at 18:40
• No, you mean induction, as in generalizing from a few cases. I didn't mean mathematical induction. Mar 29, 2014 at 18:42
• ah ok - yes you are right! Mar 29, 2014 at 18:44