Why Diagonalize a Generator?
For a finite-state continuous-time Markov chain, the transition matrix at time \(t\) is \(P(t)=e^{tQ}\), where \(Q\) is the generator. The matrix exponential can be calculated from its power series, but directly multiplying matrices for that series is often inefficient. If \(Q\) is diagonalizable, a change of basis reduces the calculation to exponentiating its eigenvalues, one scalar at a time.
Throughout, let \((X_t)_{t\ge0}\) be a continuous-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its generator is \(Q=(q_{ij})\), with \(q_{ij}\ge0\) for \(i\ne j\) and \(\sum_j q_{ij}=0\) for every state \(i\). Transition matrices are row-stochastic: \(P(t)=(p_{ij}(t))\), where \(p_{ij}(t)=\mathbb{P}(X_t=j\mid X_0=i)\), and distributions are row vectors, so \(\mu(t)=\mu(0)P(t)\). The earlier matrix-exponential result gives \(P(t)=e^{tQ}\), the unique solution to the finite-state Kolmogorov equations with \(P(0)=I\).
The Exponential After a Change of Basis
Proof. By the definition of the matrix exponential, \(e^{tQ}=\sum_{n=0}^{\infty}t^nQ^n/n!\). From \(Q=V\Lambda V^{-1}\), multiplication and cancellation of each adjacent \(V^{-1}V\) give \(Q^n=V\Lambda^nV^{-1}\) for every integer \(n\ge0\), including \(n=0\), when both sides are \(I\). Substituting these powers into the series and factoring out the fixed matrices \(V\) and \(V^{-1}\) gives $$ e^{tQ}=V\left(\sum_{n=0}^{\infty}\frac{t^n\Lambda^n}{n!}\right)V^{-1} =Ve^{t\Lambda}V^{-1}. $$ The series converges entrywise, since the matrix is finite. A diagonal matrix has powers obtained by raising each diagonal entry to that power, so its exponential has diagonal entries \(e^{t\lambda_i}\). For a generator, the earlier matrix-exponential solution identifies \(e^{tQ}\) as the transition matrix. \(\square\)
The theorem reduces the matrix calculation to three steps: find eigenvalues, find a basis of eigenvectors, and multiply \(V e^{t\Lambda}V^{-1}\). When all eigenvalues are distinct, eigenvectors for them are linearly independent, so they provide such a basis.
Proof. Let \(v_1,\ldots,v_r\) be nonzero eigenvectors with distinct eigenvalues \(\lambda_1,\ldots,\lambda_r\). Suppose \(\sum_{j=1}^r c_jv_j=0\). Fix an index \(k\), and apply the matrix \(\prod_{j\ne k}(Q-\lambda_j I)\) to this equation. For each term \(v_\ell\) with \(\ell\ne k\), the product includes \(Q-\lambda_\ell I\), which sends \(v_\ell\) to zero. The remaining term is $$ c_k\left(\prod_{j\ne k}(\lambda_k-\lambda_j)\right)v_k=0. $$ Every factor \(\lambda_k-\lambda_j\) is nonzero, and \(v_k\ne0\), so \(c_k=0\). This holds for every \(k\), proving linear independence. \(\square\)
A repeated eigenvalue does not by itself rule out diagonalization; what matters is whether there are enough linearly independent eigenvectors. The calculation below assumes an eigenvector basis has been found. Repeated-eigenvalue cases that require a different form are a separate matter.
Worked Calculations
Worked Example: Two Transient States Draining to an Absorbing State
Consider \(S=\{1,2,3\}\), with state 1 moving to state 3 at rate 1, state 2 moving to state 3 at rate 2, and state 3 absorbing. The generator, in the state order \(1,2,3\), is $$ Q=\begin{bmatrix}-1&0&1\\0&-2&2\\0&0&0\end{bmatrix}. $$ Each row sums to zero, and every off-diagonal entry is nonnegative, so this is a valid generator.
The eigenvalues are \(0,-1,-2\). Corresponding eigenvectors, in that order, are \(v_0=(1,1,1)^{\mathsf T}\), \(v_{-1}=(1,0,0)^{\mathsf T}\), and \(v_{-2}=(0,1,0)^{\mathsf T}\): direct multiplication gives \(Qv_0=0\), \(Qv_{-1}=-v_{-1}\), and \(Qv_{-2}=-2v_{-2}\). Thus $$ V=\begin{bmatrix}1&1&0\\1&0&1\\1&0&0\end{bmatrix}, \qquad V^{-1}=\begin{bmatrix}0&0&1\\1&0&-1\\0&1&-1\end{bmatrix}. $$ For example, \(V^{-1}x=(x_3,x_1-x_3,x_2-x_3)^{\mathsf T}\), which verifies the stated inverse. Put \(a=e^{-t}\) and \(b=e^{-2t}\). Then $$ e^{tQ} = \begin{bmatrix}1&1&0\\1&0&1\\1&0&0\end{bmatrix} \begin{bmatrix}1&0&0\\0&a&0\\0&0&b\end{bmatrix} \begin{bmatrix}0&0&1\\1&0&-1\\0&1&-1\end{bmatrix} = \begin{bmatrix}a&0&1-a\\0&b&1-b\\0&0&1\end{bmatrix}. $$ To check the result, each row sums to 1. For \(t\ge0\), \(0<a\le1\) and \(0<b\le1\), so every entry is nonnegative. At \(t=0\), \(a=b=1\) and the matrix is \(I\). Differentiating its entries at \(t=0\) gives \(\begin{bmatrix}-1&0&1\\0&-2&2\\0&0&0\end{bmatrix}=Q\), another check against the generator.
Worked Example: A Two-State Chain with Unequal Rates
Let \(S=\{1,2\}\), with rate 2 from state 1 to state 2 and rate 1 from state 2 to state 1. The generator is $$ Q=\begin{bmatrix}-2&2\\1&-1\end{bmatrix}. $$ Both row sums are \(-2+2=0\) and \(1-1=0\); the off-diagonal rates are nonnegative.
The eigenvalues are \(0\) and \(-3\). Eigenvectors are \((1,1)^{\mathsf T}\) and \((2,-1)^{\mathsf T}\), respectively, since multiplying by \(Q\) gives \((0,0)^{\mathsf T}\) and \((-6,3)^{\mathsf T}=-3(2,-1)^{\mathsf T}\). Therefore $$ V=\begin{bmatrix}1&2\\1&-1\end{bmatrix}, \qquad V^{-1}=\begin{bmatrix}\tfrac13&\tfrac23\\\tfrac13&-\tfrac13\end{bmatrix}. $$ Their product is \(I\): the first row of \(V\) times the first column of \(V^{-1}\) is \(\tfrac13+\tfrac23=1\); the first row times the second column is \(\tfrac23-\tfrac23=0\); the second row times the first column is \(\tfrac13-\tfrac13=0\); and the second row times the second column is \(\tfrac23+\tfrac13=1\). Write \(c=e^{-3t}\). Multiplying the three factors gives $$ P(t)= \begin{bmatrix}1&2\\1&-1\end{bmatrix} \begin{bmatrix}1&0\\0&c\end{bmatrix} \begin{bmatrix}\tfrac13&\tfrac23\\\tfrac13&-\tfrac13\end{bmatrix} = \begin{bmatrix} \tfrac{1+2c}{3}&\tfrac{2-2c}{3}\\ \tfrac{1-c}{3}&\tfrac{2+c}{3} \end{bmatrix}. $$ The first row sums to \((1+2c+2-2c)/3=1\), and the second sums to \((1-c+2+c)/3=1\). For \(t\ge0\), \(0<c\le1\), so all four entries are nonnegative. At \(t=0\), \(c=1\), giving \(P(0)=I\). The derivative at zero is $$ \begin{bmatrix}-2&2\\1&-1\end{bmatrix}=Q, $$ because \(c'(0)=-3\). Thus the computed matrix has the required initial value and generator.
If the initial distribution is \(\mu(0)=(1,0)\), then \(\mu(t)=\mu(0)P(t)=((1+2c)/3,(2-2c)/3)\). Its entries sum to 1, as required for a probability distribution.
Worked Example: A Three-State Generator with Three Distinct Eigenvalues
Consider the generator $$ Q=\begin{bmatrix}-4&1&3\\0&-2&2\\0&0&0\end{bmatrix}. $$ Its row sums are \(-4+1+3=0\), \(-2+2=0\), and \(0\), and its off-diagonal entries are nonnegative. Its eigenvalues, visible from the diagonal of this triangular matrix, are \(-4,-2,0\). Corresponding eigenvectors are \((1,0,0)^{\mathsf T}\), \((1,2,0)^{\mathsf T}\), and \((1,1,1)^{\mathsf T}\). Indeed, multiplication by \(Q\) gives respectively \((-4,0,0)^{\mathsf T}\), \((-2,-4,0)^{\mathsf T}=-2(1,2,0)^{\mathsf T}\), and \((0,0,0)^{\mathsf T}\).
Use this order for the columns of \(V\): $$ V=\begin{bmatrix}1&1&1\\0&2&1\\0&0&1\end{bmatrix}, \qquad V^{-1}=\begin{bmatrix}1&-\tfrac12&-\tfrac12\\0&\tfrac12&-\tfrac12\\0&0&1\end{bmatrix}. $$ To verify the inverse, the first row of \(V\) multiplied by the columns of \(V^{-1}\) gives \(1,0,0\); the second row gives \(0,1,0\); and the third row gives \(0,0,1\). Set \(a=e^{-4t}\) and \(b=e^{-2t}\). Then $$ e^{tQ} = V\begin{bmatrix}a&0&0\\0&b&0\\0&0&1\end{bmatrix}V^{-1} = \begin{bmatrix} a&\tfrac{b-a}{2}&1-\tfrac{a+b}{2}\\ 0&b&1-b\\ 0&0&1 \end{bmatrix}. $$ The first row sums to \(a+(b-a)/2+1-(a+b)/2=1\), and the other row sums are \(b+1-b=1\) and \(1\). Since \(0<a\le1\), \(0<b\le1\), and \(a\le b\) for \(t\ge0\), the first-row second entry is nonnegative; its third entry is also nonnegative because \((a+b)/2\le1\). The remaining entries are nonnegative as well. At \(t=0\), \(a=b=1\), giving the identity. Differentiating at zero yields first row \((-4,1,3)\), second row \((0,-2,2)\), and third row \((0,0,0)\), exactly \(Q\).
Checks, Limits, and a Common Mistake
Diagonalization is a computational method, not a replacement for probability checks. For a proposed transition matrix, verify \(P(0)=I\), the row sums, and nonnegativity for \(t\ge0\). The derivative at zero should equal \(Q\). These checks are useful because an algebraic mistake in \(V^{-1}\) or in the order of multiplication can produce a matrix that looks plausible but is not the desired transition matrix.
Common mistake: multiplying a row distribution on the left. The convention here is \(\mu(t)=\mu(0)P(t)\), not \(P(t)\mu(0)\). In the two-state example, take \(t=(\log 2)/3\), so \(c=e^{-3t}=1/2\). Substitution in the displayed formula gives $$ P(t)=\begin{bmatrix}\tfrac23&\tfrac13\\\tfrac16&\tfrac56\end{bmatrix}. $$ Starting in state 1 means \(\mu(0)=(1,0)\). The correct multiplication gives \(\mu(0)P(t)=(\tfrac23,\tfrac13)\), whose entries sum to 1. The incorrect multiplication gives \(P(t)\begin{bmatrix}1\\0\end{bmatrix}=(\tfrac23,\tfrac16)^{\mathsf T}\), whose entries sum to \(\tfrac23+\tfrac16=\tfrac56\), not 1. The error is both a mismatch of row and column conventions and a failure to produce a probability distribution.
When the eigenvalues are distinct, the lemma guarantees independent eigenvectors. With repeated eigenvalues, a generator may still have a full eigenvector basis, but the diagonalization calculation cannot be used unless that basis exists. Also, diagonalizing a matrix that is not a valid generator does not make its exponential a transition matrix: the generator conditions must be checked separately.
Check Your Understanding
Use the row-vector convention and verify each proposed calculation by substitution.
- For a diagonalizable matrix \(Q=V\Lambda V^{-1}\), explain why \(Q^n=V\Lambda^nV^{-1}\) also holds when \(n=0\).
- For the two-state example, what are the transition probabilities from state 2 at time \(t\), in terms of \(c=e^{-3t}\)?
- In the three-state example with eigenvalues \(-4,-2,0\), why is the entry \((e^{-2t}-e^{-4t})/2\) nonnegative for \(t\ge0\)?
- What three checks at \(t=0\) or near \(t=0\) help verify a computed matrix exponential for a generator?
- Why does a repeated eigenvalue alone not establish that a matrix is non-diagonalizable?