Markov chain,transition matrix and jordan form

Question

If i have a transition matrix $$P= \begin{bmatrix} \frac12 & \frac14 & \frac14 \\ 0 & \frac12 & \frac12 \\ 0 & 0 & 1 \end{bmatrix}$$

i know that it's not diagonalizable,so if i want to compute $P^n$ i have to use the jordan normal form. My teacher said that we can write $P^n=UD^nU^{-1}$ where $$D^n= \begin{bmatrix} \frac1{2^n} & 2n\frac1{2^n} & 0 \\ 0 & \frac1{2^n} & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ I don't understand how i can compute $D^n$. After that , i know that the element $P^{(n)}_{ij}=\alpha_1\lambda_1+...+\alpha_n\lambda_n$ iff eigenvalues have geometric molteplicity equal to 1, but here for example teacher writes: i.e. $$P^{(n)}_{ij}=\alpha\frac{1}{2^n}+\beta\frac{1}{2^n}2n+\gamma$$ why?

Answer 1

The result is easy to prove by induction once it has been shown to you, so let's focus on how to find these powers on your own. The point of the Jordan Normal Form of a square matrix is clearly revealed by its geometrical interpretation. Each of its blocks, of dimensions $k\times k$, corresponds to a subspace on which the matrix acts as an endomorphism. On each such subspace it is the sum of a homothety $\lambda \mathbb{I}_k$ and a nilpotent transformation $N$. Moreover, it is so arranged that a basis $(e_1, e_2, \ldots, e_k)$ can be found in which $$N:e_{j+1}\to e_j\tag{*}$$ for $j=1, 2, \ldots, k-1$ and $N(e_1)=0$. Because $\lambda\mathbb{I}_k$ commutes with $N$, this makes it easy to find powers of $D = \lambda\mathbb{I}_k + N$, since

1. Repeated application of $(*)$ immediately shows that for $i \ge 1$, $N^i(e_{j+i}) = e_j$ for $j=1, 2, \ldots, k-i$ and $N^i(e_j) = 0$ for $j \le i$ and

2. The Binomial Theorem asserts $$(\lambda \mathbb{I}_k + N)^n = \sum_{i=0}^n \binom{n}{i} \lambda^{n-i} N^i.$$

(1) guarantees that $N^k = N^{k+1} = \cdots = 0$: that's what it means to be nilpotent and it's the reason why this form is so convenient.

In the example $D$ has two blocks of dimensions $2$ and $1$. The $k=1$ block acts trivially. The $k=2$ block has $\lambda=1/2$. Its matrix in the basis $(e_1, e_2)$ therefore is $$D_2 = \pmatrix{\frac{1}{2} & 1 \\ 0 & \frac{1}{2}} = \frac{1}{2}\pmatrix{1 & 0 \\ 0 & 1} + \pmatrix{0 & 1 \\ 0 & 0} = \frac{1}{2}\mathbb{I}_2 + N.$$

Consequently $N^2 = 0$, whence for any positive integral power $n$,

$$D_2^n =\sum_{i=0}^n \binom{n}{i} \left(\frac{1}{2}\right)^{n-i} N^i = \left(\frac{1}{2}\right)^n + \binom{n}{1} \left(\frac{1}{2}\right)^{n-1} N + 0 + 0 + \cdots + 0.$$

In terms of the basis $(e_1, e_2)$ the matrix of $D_2^n$ therefore is

$$D_2^n = \frac{1}{2^n}\pmatrix{1 & 0 \\ 0 & 1} + \binom{n}{1}\frac{1}{2^{n-1}}\pmatrix{0 & 1 \\ 0 & 0} = \pmatrix{\frac{1}{2^n} & 0 \\ 0 & \frac{1}{2^n}} + \pmatrix{0 & n \frac{1}{2^{n-1}} \\ 0 & 0}.$$

That's algebraically equivalent to the formula in the question.