# Computing the matrix powers of a non-diagonalizable matrix

Define $$$$A = \begin{pmatrix} \frac{1}{2} &\frac{1}{2} & 0\\ 0& \frac{3}{4} & \frac{1}{4}\\ 0& \frac{1}{4} & \frac{3}{4} \end{pmatrix}.$$$$

Note that the sum of the dimensions of the eigenspaces of $$A$$ is only two. $$A$$ is thus not diagonalizable. How can we compute $$A^n$$?

• Use Cayley-Hamilton to write $A^n=aI+bA+cA^2$ and then use the eigenvalues to find the coefficients. – amd May 25 at 17:18
• Why is this question getting upvotes? It show no effort to solve the problem and aside from a trivial difference in the specific values of the matrix elements is a duplicate of many other previous questions. – amd May 25 at 17:19
• @amd Because people can upvote or downvote freely. – DonAntonio May 25 at 17:27
• @amd it would be great if you linked some of these questions that seem to already have good answers to my question. Also, I don’t show effort to solve the problem because I answered my own question below. – Maximilian Janisch May 25 at 17:37
• Yes, I hadn’t noticed that you had answered your own question. I withdraw that part of my comment. – amd May 25 at 22:27

Here is a different way using a rather classical trick, converting the issue into a binomial expansion. Indeed, we can write :

$$A=\frac12(I+B) \ \text{where} \ B:=\begin{pmatrix}0&1&0 \\0&1/2&1/2\\0&1/2&1/2\end{pmatrix}$$

where matrix $$B$$ has the following particularity

$$B^n=C \ \text{for all} \ n>1 \ \text{where} \ C:=\begin{pmatrix}0&1/2&1/2\\0&1/2&1/2\\0&1/2&1/2\end{pmatrix}$$

Therefore

$$A^n = \dfrac{1}{2^n}\left(I+\binom{n}{1}B+\binom{n}{2}B^2+\binom{n}{3}B^3+\cdots+\binom{n}{n}B^n\right)$$

$$A^n = \dfrac{1}{2^n}\left(I+nB+\binom{n}{2}C+\binom{n}{3}C+\cdots+\binom{n}{n}C\right)\tag{1}$$

As is well known, $$\sum_{k=0}^n \binom{n}{k}=2^n$$, reducing (1) to :

$$A^n = \dfrac{1}{2^n}\left(I+nB+(2^n-n-1)C\right)$$

It suffices now to replace $$B$$ and $$C$$ by their expression

$$A^n = \dfrac{1}{2^n}\left(\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}+n\begin{pmatrix}0&1&0 \\0&1/2&1/2\\0&1/2&1/2\end{pmatrix}+(2^n-n-1)\begin{pmatrix}0&1/2&1/2\\0&1/2&1/2\\0&1/2&1/2\end{pmatrix}\right)$$

to get the result (coinciding with yours !).

• That is very nice indeed! – Maximilian Janisch May 25 at 22:21
• I have been able to find such a decomposition guided by the fact that $A$ is a stochastic matrix. – Jean Marie May 25 at 22:23
• Thanks for your appreciation. – Jean Marie May 25 at 22:43
• I definitely learned something from your answer (I accidentally deleted my previous comment) – Maximilian Janisch May 25 at 22:45
• Something I haven't said is that $(A+B)^n$ can be expanded using the binomial theorem whenever $A$ and $B$ commute. This is the case in this problem, with $A=I$ which commutes with any matrix. – Jean Marie May 25 at 22:48

Note that your matrix $$A$$ has the generalized eigenvectors

$$$$v_1=\begin{pmatrix}1 \\ 0 \\ 0\end{pmatrix}, v_2=\begin{pmatrix}0 \\ 2 \\ -2\end{pmatrix}, v_3=\begin{pmatrix}0\\ 0 \\ 1\end{pmatrix}.$$$$

Thus, by Jordan decomposition, $$A=\big(v_1,v_2,v_3\big)J\big(v_1,v_2,v_3\big)^{-1}$$, where

$$$$J=\begin{pmatrix}\frac12 & 1 & 0\\0 & \frac12 & 0\\0 & 0 & 1\end{pmatrix}.$$$$

The problem of calculating $$A^n$$ is thus reduced to calculating $$J^n$$. Let $$a_{ij}^{(n)}$$ denote the entry of $$J^n$$ in the $$i$$-th row and $$j$$-th column.

The product of an arbitrary $$3\times3$$-matrix with $$J$$ is given by: $$$$\begin{pmatrix} a&b&c\\d&e&f\\g&h&i \end{pmatrix} J = \begin{pmatrix} \frac a2&a+\frac b2&c\\\frac d2&d+\frac e2&f\\\frac g2&g+\frac h2&i \end{pmatrix}.$$$$

We can deduce that, for all $$n\in\Bbb N$$: \begin{align} a_{11}^{(n)}&=a_{22}^{(n)}=\frac1{2^n}, \\a_{21}^{(n)}&=a_{31}^{(n)}=0,\\ a_{13}^{(n)}&=a_{23}^{(n)}=a_{32}^{(n)}=0, \\ a_{33}^{(n)}&=1,\\ a_{12}^{(n+1)}&=a_{11}^{(n)}+\frac{a_{12}^{(n)}}2=\frac1{2^n}+\frac{a_{12}^{(n)}}2. \end{align}

Thus, all $$a_{ij}^{(n)}$$ are explicitly known except for $$a_{12}^{(n)}$$. Note that, by the last equation, $$$$a_{12}^{(n+1)}=2^{-n}+\frac{a_{12}^{(n)}}2 = 2^{-n}+2^{-n}+\frac{a_{12}^{(n-1)}}4 = \dots = (n+1)\cdot2^{-n}.$$$$

Thus, $$$$J^n=\begin{pmatrix}2^{-n}&n\cdot 2^{1-n} & 0\\0 & 2^{-n} & 0\\0 & 0 & 1\end{pmatrix}.$$$$

And by some calculations, we find that $$$$A^n=\big(v_1,v_2,v_3\big)J^n\big(v_1,v_2,v_3\big)^{-1}= \begin{pmatrix} 2^{-n} & n\cdot 2^{-n-1} - 2^{-n-1} + \frac12 & {1-\frac{n+1}{2^n}\over2}\\ 0 & {2^{-n}+1\over2} & {1-2^{-n}\over2} \\ 0 & {1-2^{-n}\over2} & {2^{-n}+1\over2} \end{pmatrix}.$$$$

• I don't understand very well the "your" in the first sentence of this answer "Note that your matrix..." ; in fact, as far I have understood, you are answering your own question ... – Jean Marie May 25 at 17:39
• @JeanMarie indeed I am answering my own question. On the questions on this forum that I saw that were answered by the OP, the OP was always talking about himself in second person; so I decided to do the same. Feel free to edit this if that is actually a wrong decision on my part. PS: Another factor in this is that I first wanted this to be a part of my answer to this question, but I decided to outsource it – Maximilian Janisch May 25 at 17:41
• Thanks for your answer... I think you have understood it as humor. – Jean Marie May 25 at 17:45
• I think that you can simplify this quite a bit by noting that $J=D+N$, where $D$ is diagonal and $N$ is nilpotent of order 2. $D$ and $N$ commute, so expand using the Binomial Theorem: $(D+N)^n=D^n+nND^{n-1}$. Powers of $D$ are themselves diagonal, so the second term should be quite simple to compute. – amd May 26 at 0:02
• @amd great idea – Maximilian Janisch May 26 at 7:30