Define \begin{equation} 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}. \end{equation}

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$?

  • 2
    $\begingroup$ Use Cayley-Hamilton to write $A^n=aI+bA+cA^2$ and then use the eigenvalues to find the coefficients. $\endgroup$ – amd May 25 at 17:18
  • 2
    $\begingroup$ 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. $\endgroup$ – amd May 25 at 17:19
  • 3
    $\begingroup$ @amd Because people can upvote or downvote freely. $\endgroup$ – DonAntonio May 25 at 17:27
  • 3
    $\begingroup$ @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. $\endgroup$ – Maximilian Janisch May 25 at 17:37
  • $\begingroup$ Yes, I hadn’t noticed that you had answered your own question. I withdraw that part of my comment. $\endgroup$ – 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}$$


$$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 !).

  • 2
    $\begingroup$ That is very nice indeed! $\endgroup$ – Maximilian Janisch May 25 at 22:21
  • 3
    $\begingroup$ I have been able to find such a decomposition guided by the fact that $A$ is a stochastic matrix. $\endgroup$ – Jean Marie May 25 at 22:23
  • $\begingroup$ Thanks for your appreciation. $\endgroup$ – Jean Marie May 25 at 22:43
  • $\begingroup$ I definitely learned something from your answer (I accidentally deleted my previous comment) $\endgroup$ – Maximilian Janisch May 25 at 22:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Jean Marie May 25 at 22:48

Note that your matrix $A$ has the generalized eigenvectors

\begin{equation}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}.\end{equation}

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

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

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{equation} \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}. \end{equation}

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, \begin{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}.\end{equation}

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

And by some calculations, we find that \begin{equation} 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}. \end{equation}

  • $\begingroup$ 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 ... $\endgroup$ – Jean Marie May 25 at 17:39
  • 1
    $\begingroup$ @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 $\endgroup$ – Maximilian Janisch May 25 at 17:41
  • $\begingroup$ Thanks for your answer... I think you have understood it as humor. $\endgroup$ – Jean Marie May 25 at 17:45
  • 2
    $\begingroup$ 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. $\endgroup$ – amd May 26 at 0:02
  • $\begingroup$ @amd great idea $\endgroup$ – Maximilian Janisch May 26 at 7:30

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.