# Example of a Markov chain transition matrix that is not diagonalizable?

It is well-known that every detailed-balance Markov chain has a diagonalizable transition matrix. I am looking for an example of a Markov chain whose transition matrix is not diagonalizable. That is:

Give a transition matrix $M$ such that there exists no invertible matrix $U$ with $U^{-1} M U$ a diagonal matrix.

Is there a combinatorial interpretation for the Jordan blocks that I can see directly from the graph?

Edit: I found this example here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-262-discrete-stochastic-processes-spring-2011/video-lectures/lecture-8-markov-eigenvalues-and-eigenvectors/MIT6_262S11_lec08.pdf on page 21.

\begin{array}{ccc}
1/2 & 1/2 & 0\\
0 & 1/2 & 1/2\\
0 & 0 & 1
\end{array}

This particular example has two non-recurrent states, which is not really what I want. So I am modifying my question to ask for an example of a Markov chain for which every state is recurrent.

#### Solutions Collecting From Web of "Example of a Markov chain transition matrix that is not diagonalizable?"

Consider the matrix, $$M={1\over300}\pmatrix{210&40&24\cr15&210&96\cr75&50&180\cr}$$ Note that I adopt the convention that the columns, not the rows, are to add up to $1$. Now $1/2$ is an eigenvalue, since the first row of $$M-{1\over2}I={1\over300}\pmatrix{60&40&24\cr15&60&96\cr75&50&30\cr}$$ is four-fifths of the 3rd row. But also $1$ is an eigenvalue, and the eigenvalues add up to $2$, so $1/2$ is a repeated eigenvalue. Its eigenspace is one-dimensional, since $M-(1/2)I$ has rank $2$, so $M$ is not diagonalizable.

EDIT. I thought I’d have a go at finding an example with smaller numbers. Let $$M={1\over5}\pmatrix{2&2&1\cr1&2&1\cr2&1&3\cr}$$ The eigenvalues are $1$ (since the matrix is column-stochastic), $1/5$ (since the 1st and 3rd columns of $$M-{1\over5}I={1\over5}\pmatrix{1&2&1\cr1&1&1\cr2&1&2\cr}$$ are identical), and $1/5$ again (since the eigenvalues add up to $(2+2+3)/5=7/5$). $M-(1/5)I$ has rank $2$, so the eigenspace of the eigenvalue $1/5$ is 1-dimensional, so $M$ is not diagonalizable.