An Exact Three-State Diagonalization Workshop

A Three-State Chain for Exact Diagonalization

Diagonalization is especially useful when the question asks for transition probabilities after many steps. Instead of multiplying the transition matrix repeatedly, we express it in an eigenvector basis, raise its diagonal form to the desired power, and transform back. This workshop carries out the calculation for one chain from the stochasticity check through to exact entries of \(P^n\).

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be a discrete-time Markov chain with state space \(S=\{1,2,3\}\) and transition matrix \(P=(p_{ij})\). Its filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The entry \(p_{ij}^{(n)}\) of \(P^n\) is the probability of being in state \(j\) after \(n\) steps when the chain starts in state \(i\). Distributions are row vectors, so an initial distribution \(\mu_0\) evolves by \(\mu_n=\mu_0P^n\).

Consider the matrix

Before calculating powers, check the rows: \(\tfrac12+\tfrac12+0=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(0+\tfrac12+\tfrac12=1\). Every entry is nonnegative, so \(P\) is row-stochastic and is a valid transition matrix.

Proof. Linear independence of the \(m\) columns makes \(V\) invertible. The eigenvector equations, placed side by side, say \(PV=VD\). Multiplying on the right by \(V^{-1}\) gives \(P=VDV^{-1}\). For \(n\ge1\), multiplying this identity by itself \(n\) times and using \(V^{-1}V=I\) gives \(P^n=VD^nV^{-1}\). For \(n=0\), both sides equal the identity matrix, since \(P^0=I\) and \(D^0=I\). \(\square\)

Find the Eigenvectors and Assemble the Diagonalization

For the eigenvalue \(1\), the column vector \(v_1=(1,1,1)^{\mathsf T}\) works: multiplying by \(P\) gives \((1,1,1)^{\mathsf T}\). This reflects the fact that the rows sum to one. For a second eigenvector, direct multiplication gives \(P(1,0,-1)^{\mathsf T}=(\tfrac12,0,-\tfrac12)^{\mathsf T}\), so \(v_2=(1,0,-1)^{\mathsf T}\) has eigenvalue \(\tfrac12\). Finally, \(P(1,-1,1)^{\mathsf T}=(0,0,0)^{\mathsf T}\), so \(v_3=(1,-1,1)^{\mathsf T}\) has eigenvalue \(0\).

Use these vectors as the columns of \(V\). The eigenvectors are linearly independent, as can be checked using the inverse displayed below; thus they provide a full eigenvector basis.

For example, the first row of \(V^{-1}\) multiplied by the first column of \(V\) gives \(\tfrac14+\tfrac12+\tfrac14=1\), while its products with the second and third columns give \(\tfrac14-\tfrac14=0\) and \(\tfrac14-\tfrac12+\tfrac14=0\). The other rows give the other rows of the identity by the same direct multiplication. The eigenvector equations therefore give \(PV=VD\), and the inverse yields \(P=VDV^{-1}\).

An Exact Formula for the Powers

For \(n\ge1\), the diagonal power is \(D^n=\operatorname{diag}(1,2^{-n},0)\). The zero eigenvalue contributes zero at every positive power. Multiplying \(VD^nV^{-1}\) gives the formula below. The case \(n=0\) is different: \(D^0=I\), including a \(1\) in the position corresponding to the zero eigenvalue.

Proof. The three eigenvectors above are linearly independent because \(V^{-1}V=I\). The proposition therefore gives \(P^n=VD^nV^{-1}\). For \(n\ge1\), \(D^n=\operatorname{diag}(1,2^{-n},0)\). Multiplication gives the contribution from the eigenvalue \(1\) as a matrix whose every row is \((\tfrac14,\tfrac12,\tfrac14)\), and the contribution from the eigenvalue \(\tfrac12\) as \(2^{-n}\) times \(\begin{bmatrix}\tfrac12&0&-\tfrac12\\0&0&0\\-\tfrac12&0&\tfrac12\end{bmatrix}\). The eigenvalue \(0\) contributes nothing for \(n\ge1\). Adding the two displayed contributions gives the stated entries, since \(2^{-n}\tfrac12=2^{-(n+1)}\). \(\square\)

The expression also passes basic probability checks. Each row sums to \(1\): the first and third have cancelling terms \(+2^{-(n+1)}\) and \(-2^{-(n+1)}\), while the middle row sums to \(\tfrac14+\tfrac12+\tfrac14=1\). For nonnegativity, \(n\ge1\) implies \(2^{-(n+1)}\le\tfrac14\), so even the smallest entries, \(\tfrac14-2^{-(n+1)}\), are nonnegative.

Propagate an Initial Distribution

Once the matrix power is known, the distribution after \(n\) steps follows by multiplying the initial row vector by \(P^n\). This uses the row-vector convention: the \(j\)th entry of \(\mu_0P^n\) is \(\sum_i\mu_0(i)p_{ij}^{(n)}\), the total probability of reaching \(j\) from all possible starting states.

Common Pitfall: Forgetting the Zero-Eigenvalue Term at Time Zero

The formula for \(P^n\) above is stated only for \(n\ge1\). Substituting \(n=0\) into it would give the matrix with every row \((\tfrac14+\tfrac12,\tfrac12,\tfrac14-\tfrac12)=(\tfrac34,\tfrac12,-\tfrac14)\). This is not \(P^0=I\): it even has a negative entry. The error is treating the zero-eigenvalue contribution as zero at \(n=0\). In fact, \(D^0=I\), so \(0^0\) need not be evaluated as a scalar; the whole diagonal matrix at exponent zero is the identity. The correct calculation is \(P^0=VD^0V^{-1}=VIV^{-1}=I\).

Diagonalization gives exact powers efficiently, but the result should still be checked: confirm the original matrix is stochastic, use the correct row-vector convention for distributions, keep track of whether the exponent is zero or positive, and verify that the calculated probability rows sum to one.