Computing Matrix Powers by Diagonalization

Why Diagonalization Helps

For a discrete-time Markov chain, the $n$-step transition matrix is $P^n$, where $P$ is the one-step transition matrix. Repeated multiplication is reliable for small $n$, but it becomes inefficient when the desired number of steps is large or symbolic. Diagonalization replaces repeated matrix products with powers of scalar eigenvalues, provided the matrix has a full basis of eigenvectors.

Throughout, let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite state space $S$. Its transition matrix is $P=(p_{ij})$, with $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$. The rows of $P$ sum to $1$, and $p_{ij}^{(n)}=(P^n)_{ij}$ is the probability of moving from $i$ to $j$ in $n$ steps. The identity matrix $P^0=I$ represents zero steps.

Definition: An $m\times m$ matrix $P$ is diagonalizable if there is an invertible matrix $V$ and a diagonal matrix $D$ such that $P=VDV^{-1}$. The columns of $V$ are a basis of eigenvectors of $P$, and the corresponding eigenvalues appear in the same order along the diagonal of $D$. Diagonalization may be over the real or complex numbers; when $P$ is real but the eigenvalues are complex, the resulting $P^n$ is still real.

The Power Identity

Proposition: If $D=\operatorname{diag}(\lambda_1,\ldots,\lambda_m)$, then for every integer $n\ge0$, $D^n=\operatorname{diag}(\lambda_1^n,\ldots,\lambda_m^n)$, with $D^0=I$.

Proof. For $n=0$, both sides are $I$, with each diagonal entry interpreted as $1$, including when an eigenvalue is zero. Suppose the identity holds for some $n\ge0$. Multiplication of diagonal matrices multiplies corresponding diagonal entries and leaves all off-diagonal entries zero. Therefore $D^{n+1}=D^nD=\operatorname{diag}(\lambda_1^n\lambda_1,\ldots,\lambda_m^n\lambda_m)=\operatorname{diag}(\lambda_1^{n+1},\ldots,\lambda_m^{n+1})$. Induction proves the result for every $n\ge0$. $\square$

Theorem (Powers by diagonalization): If $P=VDV^{-1}$ with $V$ invertible and $D$ diagonal, then for every integer $n\ge0$, $$ P^n=VD^nV^{-1}. $$

Proof. For $n=0$, the right side is $VIV^{-1}=I=P^0$. Suppose $P^n=VD^nV^{-1}$ for some $n\ge0$. Using $V^{-1}V=I$, we obtain $$ P^{n+1}=P^nP=(VD^nV^{-1})(VDV^{-1})=VD^n(V^{-1}V)DV^{-1}=VD^{n+1}V^{-1}. $$ The induction begins at $n=0$, so the identity holds for all nonnegative integer powers. The cancellation of $V^{-1}V$ is essential; without it the product is not the power of $P$. $\square$

The practical sequence is to find a basis of eigenvectors, place them as the columns of $V$, put their eigenvalues in matching order on the diagonal of $D$, and compute $VD^nV^{-1}$. The matrix $V$ must be invertible. An eigenvalue may be repeated; what matters for this method is that enough linearly independent eigenvectors exist to form a basis. The earlier material on testing diagonalizability addresses that question.

Worked Calculations

Worked Example: A Two-State Chain

On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, consider a discrete-time Markov chain with state space $S=\{1,2\}$ and transition matrix $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ Each row sums to $\tfrac34+\tfrac14=1$, so the matrix is stochastic.

The vector $v_1=(1,1)^{\mathsf T}$ is an eigenvector with eigenvalue $1$, since $Pv_1=(1,1)^{\mathsf T}$. The vector $v_2=(1,-1)^{\mathsf T}$ is an eigenvector with eigenvalue $\tfrac12$, since $$ Pv_2=\begin{bmatrix}\tfrac34-\tfrac14\\[2pt]\tfrac14-\tfrac34\end{bmatrix} =\begin{bmatrix}\tfrac12\\[2pt]-\tfrac12\end{bmatrix} =\tfrac12v_2. $$ Thus $$ V=\begin{bmatrix}1&1\\1&-1\end{bmatrix},\qquad D=\begin{bmatrix}1&0\\0&\tfrac12\end{bmatrix},\qquad V^{-1}=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac12&-\tfrac12\end{bmatrix}. $$ Indeed, multiplying $V$ by the displayed inverse gives $I$.

For $n\ge0$, the theorem gives $$ P^n=\begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}1&0\\0&(\tfrac12)^n\end{bmatrix} \begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac12&-\tfrac12\end{bmatrix} = \begin{bmatrix} \tfrac{1+(\tfrac12)^n}{2}&\tfrac{1-(\tfrac12)^n}{2}\\[2pt] \tfrac{1-(\tfrac12)^n}{2}&\tfrac{1+(\tfrac12)^n}{2} \end{bmatrix}. $$ For example, at $n=3$, $(\tfrac12)^3=\tfrac18$, so the diagonal entries are $(1+\tfrac18)/2=\tfrac9{16}$, and the off-diagonal entries are $(1-\tfrac18)/2=\tfrac7{16}$. The result is $\begin{bmatrix}\tfrac9{16}&\tfrac7{16}\\[2pt]\tfrac7{16}&\tfrac9{16}\end{bmatrix}$.

Check by multiplication. First, $P^2$ has first-row entries $(\tfrac34)(\tfrac34)+(\tfrac14)(\tfrac14)=\tfrac{10}{16}=\tfrac58$ and $(\tfrac34)(\tfrac14)+(\tfrac14)(\tfrac34)=\tfrac6{16}=\tfrac38$. By symmetry its second row is $(\tfrac38,\tfrac58)$. Multiplying this $P^2$ by $P$, the first-row entries are $(\tfrac58)(\tfrac34)+(\tfrac38)(\tfrac14)=\tfrac{18}{32}=\tfrac9{16}$ and $(\tfrac58)(\tfrac14)+(\tfrac38)(\tfrac34)=\tfrac{14}{32}=\tfrac7{16}$. The second row gives $(\tfrac7{16},\tfrac9{16})$. Both rows of the result sum to $\tfrac9{16}+\tfrac7{16}=1$, as required.

Worked Example: A Three-State Chain

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on $S=\{1,2,3\}$, on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with $$ P=\begin{bmatrix}\tfrac12&\tfrac13&\tfrac16\\[2pt]\tfrac13&\tfrac12&\tfrac16\\[2pt]\tfrac16&\tfrac16&\tfrac23\end{bmatrix}. $$ The first row sums to $\tfrac12+\tfrac13+\tfrac16=1$, the second to $\tfrac13+\tfrac12+\tfrac16=1$, and the third to $\tfrac16+\tfrac16+\tfrac23=1$.

Consider the three column vectors $u=(1,1,1)^{\mathsf T}$, $a=(1,-1,0)^{\mathsf T}$, and $b=(1,1,-2)^{\mathsf T}$. Direct multiplication gives $Pu=u$, $Pa=\tfrac16a$, and $Pb=\tfrac12b$. For the last two, the products are $$ Pa=\begin{bmatrix}\tfrac16\\[2pt]-\tfrac16\\[2pt]0\end{bmatrix},\qquad Pb=\begin{bmatrix}\tfrac12\\[2pt]\tfrac12\\[2pt]-1\end{bmatrix}. $$ Set $V=[u\ a\ b]$. The vectors are independent: subtracting its first row from each of its other rows reduces the determinant calculation to $\det\begin{bmatrix}-2&0\\-1&-3\end{bmatrix}=6\ne0$. Hence $$ V=\begin{bmatrix}1&1&1\\1&-1&1\\1&0&-2\end{bmatrix},\qquad D=\begin{bmatrix}1&0&0\\0&\tfrac16&0\\0&0&\tfrac12\end{bmatrix},\qquad V^{-1}=\begin{bmatrix}\tfrac13&\tfrac13&\tfrac13\\[2pt]\tfrac12&-\tfrac12&0\\[2pt]\tfrac16&\tfrac16&-\tfrac13\end{bmatrix}. $$ The inverse follows, for example, by multiplying its rows by the columns $u,a,b$: the resulting row-column products are $1,0,0$ for the first row; $0,1,0$ for the second; and $0,0,1$ for the third. Thus $P=VDV^{-1}$.

Multiplying the diagonal powers by the corresponding columns and rows gives, for every $n\ge0$, $$ P^n=\frac13\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix} +\frac{(\tfrac16)^n}{2}\begin{bmatrix}1&-1&0\\-1&1&0\\0&0&0\end{bmatrix} +\frac{(\tfrac12)^n}{6}\begin{bmatrix}1&1&-2\\1&1&-2\\-2&-2&4\end{bmatrix}. $$ At $n=2$, the coefficients of the last two displayed matrices are $\tfrac1{72}$ and $\tfrac1{24}$. Entry by entry, the first row is $\tfrac13+\tfrac1{72}+\tfrac1{24}=\tfrac7{18}$, $\tfrac13-\tfrac1{72}+\tfrac1{24}=\tfrac{13}{36}$, and $\tfrac13-\tfrac2{24}=\tfrac14$. The second row is $\tfrac{13}{36},\tfrac7{18},\tfrac14$, from the same three coefficients with the signs shown in the formula. The third row is $\tfrac13-\tfrac2{24}=\tfrac14,\tfrac14,\tfrac13+\tfrac4{24}=\tfrac12$. Therefore $$ P^2=\begin{bmatrix}\tfrac7{18}&\tfrac{13}{36}&\tfrac14\\[2pt]\tfrac{13}{36}&\tfrac7{18}&\tfrac14\\[2pt]\tfrac14&\tfrac14&\tfrac12\end{bmatrix}. $$ The first row sums to $\tfrac{14}{36}+\tfrac{13}{36}+\tfrac9{36}=1$; the second has the same sum; the third sums to $\tfrac14+\tfrac14+\tfrac12=1$.

Check at one step. Substituting $n=1$ in the formula gives entry $(1,1)$ equal to $\tfrac13+\tfrac1{12}+\tfrac1{12}=\tfrac12$, entry $(1,2)$ equal to $\tfrac13-\tfrac1{12}+\tfrac1{12}=\tfrac13$, and entry $(1,3)$ equal to $\tfrac13-\tfrac16=\tfrac16$. The formula is symmetric in states $1$ and $2$, and its third row is $(\tfrac16,\tfrac16,\tfrac23)$; it reproduces the stated $P$.

Worked Example: A Chain with a Negative Eigenvalue

On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $(X_n)_{n\ge0}$ be a chain on $S=\{1,2\}$ with $$ P=\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Each row sums to $1$. The eigenvectors $u=(1,1)^{\mathsf T}$ and $v=(1,-1)^{\mathsf T}$ have eigenvalues $1$ and $-1$, respectively. Taking $V=[u\ v]$ gives $V^{-1}=\tfrac12\begin{bmatrix}1&1\\1&-1\end{bmatrix}$, so $$ P^n=\frac12\begin{bmatrix}1&1\\1&1\end{bmatrix} +\frac{(-1)^n}{2}\begin{bmatrix}1&-1\\-1&1\end{bmatrix}. $$ For $n=4$, $(-1)^4=1$, and the result is $\begin{bmatrix}1&0\\0&1\end{bmatrix}$. For $n=5$, $(-1)^5=-1$, and the result is $\begin{bmatrix}0&1\\1&0\end{bmatrix}$. Each row in either result sums to $1$, and these are exactly the alternating moves of the chain. The sign of an eigenvalue matters: replacing $(-1)^n$ by $1$ would give the wrong answer at odd $n$.

A Common Matrix-Order Mistake

Diagonalization does not mean that one may omit the inverse or place matrices in an arbitrary order. In the two-state example above, use $V=\begin{bmatrix}1&1\\1&-1\end{bmatrix}$ and $D^2=\operatorname{diag}(1,\tfrac14)$. A wrong calculation that omits $V^{-1}$ gives $$ VD^2V= \begin{bmatrix}1&\tfrac14\\1&-\tfrac14\end{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix} = \begin{bmatrix}\tfrac54&\tfrac34\\[2pt]\tfrac34&\tfrac54\end{bmatrix}. $$ Its rows sum to $2$, so it cannot be a transition matrix. The correct expression includes the inverse: $$ VD^2V^{-1}= \begin{bmatrix}\tfrac58&\tfrac38\\[2pt]\tfrac38&\tfrac58\end{bmatrix}. $$ The corrected entries also agree with the direct product $P^2$ calculated earlier. The error is not a small numerical discrepancy: omitting $V^{-1}$ destroys the change back from eigenvector coordinates to the original state coordinates.

Diagonalization is useful because it gives a compact expression for all step counts, not just one chosen $n$. In practice, first verify stochasticity of the given matrix, then verify the eigenvector equations and that the eigenvectors form a basis, and finally check at least one power by direct multiplication or substitution. These checks catch mismatched eigenvalue order, inverse errors, and arithmetic mistakes. Diagonalization is not available for every matrix; if there is no eigenvector basis, this particular method does not apply, even though the powers $P^n$ are still well-defined.

Check Your Understanding

Use the power identity and show enough intermediate work to verify each result.

For $P=\begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac13&\tfrac23\end{bmatrix}$, check the row sums and find its eigenvalues and eigenvectors.
In the two-state worked example, calculate $P^4$ from the diagonalization formula. Check that each row sums to $1$.
Why must the eigenvectors be arranged in $V$ in the same order as their eigenvalues are arranged in $D$?
For the three-state example, use the displayed formula to calculate the $(1,3)$ entry of $P^3$.
For the swapping chain, explain why the sign of $(-1)^n$ distinguishes even-step from odd-step transitions.

Computing Matrix Powers by Diagonalization

What You'll Learn