Testing Whether a Transition Matrix Is Diagonalizable

Why Eigenvalue Multiplicity Is Not Enough

Eigenvalues of a transition matrix can help organize questions about its powers, but an eigenvalue calculation alone does not tell us whether the matrix has a full basis of eigenvectors. That distinction matters: diagonalization requires enough linearly independent eigenvectors to represent every state-space direction. A repeated eigenvalue may have several independent eigenvectors, or it may not.

Consider a discrete-time Markov chain \((X_n)_{n\ge0}\) on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). In the convention used here, \(P\) is row-stochastic: each entry is nonnegative and each row sums to \(1\). To discuss eigenvectors, we apply \(P\) to column vectors \(v\), so the eigenvector equation is \(Pv=\lambda v\). This is compatible with row-vector distributions evolving by \(\mu_{n+1}=\mu_nP\); it simply uses a different vector orientation for a different calculation.

Because transition matrices have real entries, they can be studied over either \(\mathbb{R}\) or \(\mathbb{C}\). Unless specified otherwise, the criterion and examples below concern diagonalizability over \(\mathbb{C}\). Diagonalizability over \(\mathbb{R}\) is a stronger requirement: the eigenvalues and a full eigenvector basis must be real. For a complex eigenvalue, a real matrix cannot have a nonzero real eigenvector with that eigenvalue.

The Multiplicity Test

Proof. Write \(m_\lambda\) for the algebraic multiplicity and \(g_\lambda=\dim E_\lambda\) for the geometric multiplicity. First suppose \(P=VDV^{-1}\). Similar matrices have the same characteristic polynomial, so the diagonal entries of \(D\) list the eigenvalues with their algebraic multiplicities. Also, \(P-\lambda I=V(D-\lambda I)V^{-1}\), so multiplication by \(V^{-1}\) gives a one-to-one correspondence between \(\ker(P-\lambda I)\) and \(\ker(D-\lambda I)\). The latter has one free coordinate for each diagonal entry of \(D\) equal to \(\lambda\). Thus \(g_\lambda=m_\lambda\) for every eigenvalue.

Now suppose \(g_\lambda=m_\lambda\) for every eigenvalue. The characteristic polynomial has degree \(n\), and over \(\mathbb{C}\) it factors into its roots, so \(\sum_\lambda m_\lambda=n\). Choose a basis for each eigenspace. Eigenvectors belonging to distinct eigenvalues are linearly independent across those eigenspaces: to verify this, suppose \(\sum_\lambda v_\lambda=0\), where each \(v_\lambda\in E_\lambda\). Fix one eigenvalue \(\alpha\) and apply the operator \(\prod_{\lambda\ne\alpha}(P-\lambda I)\) to the sum. Every term except the one involving \(v_\alpha\) vanishes, leaving \(\bigl(\prod_{\lambda\ne\alpha}(\alpha-\lambda)\bigr)v_\alpha=0\). The scalar product is nonzero because the eigenvalues in the product differ from \(\alpha\), so \(v_\alpha=0\). This holds for each \(\alpha\), proving the asserted independence. The chosen eigenvector bases therefore contain \(\sum_\lambda g_\lambda=\sum_\lambda m_\lambda=n\) linearly independent vectors. They form a basis of \(\mathbb{C}^n\); in that basis \(P\) is diagonal. This proves diagonalizability and both directions of the criterion. \(\square\)

The equivalent dimension-sum version is useful when solving eigenvector equations directly. The sum of the algebraic multiplicities is already \(n\), so the test asks whether the eigenspaces together supply \(n\) independent directions. Repetition in the characteristic polynomial signals a question to check; it does not answer that question.

A Distinct-Eigenvalue Case and a Reliable Workflow

The test can be applied systematically. First verify that the matrix really describes a chain: every entry must be nonnegative and every row must sum to \(1\). Next compute and factor \(\det(zI-P)\), recording the algebraic multiplicity of each distinct root. Then solve \((P-\lambda I)v=0\) for each eigenvalue and count the dimension of its solution space. Finally compare the two multiplicities for each eigenvalue, or add the eigenspace dimensions and compare the total with the number of states.

Common Pitfalls and Why the Test Matters

Common mistake: treating a repeated root as multiple eigenvectors. In the second worked example, one might see the factor \((z-\tfrac12)^2\) and incorrectly assign two independent eigenvectors to \(\tfrac12\). That would count algebraic multiplicity as if it were geometric multiplicity. The actual calculation gives \((P-\tfrac12I)v=0\), which forces \(x_1=x_2=0\) while leaving only \(x_3\) free. The eigenspace therefore has dimension \(1\), so the matrix is not diagonalizable.

Another potential error is to test row sums but overlook negative entries. A row such as \((-1,2)\) sums to \(1\), but it cannot describe transition probabilities because one entry is negative. The validity check requires both nonnegativity and row sums equal to \(1\).

Diagonalizability is a property of the matrix, not a consequence of being stochastic. The first and second worked examples are both valid transition matrices with a repeated eigenvalue, yet one is diagonalizable and the other is not. The multiplicity test determines which case holds. It also specifies the field: eigenvectors over \(\mathbb{C}\) do not automatically give a real eigenvector basis. The immediate conclusion of a successful test is precisely that a complete eigenvector basis exists over the chosen field; calculations using that basis are a separate step.