If $P$ is the transition matrix of a reversible Markov chain, why are its eigenvalues real?

Question

If the MC is reversible, then $\pi(x)P(x,y) = \pi(y)P(y,x)$ for some distribution $\pi$ and for all states $x,y$. I see that if $\pi$ is the uniform distribution, then $P$ is symmetric and thus has real eigenvalues. But what if $P$ is not symmetric?

Answer 1

You're pretty close. Here's what's missing.

We will assume further that $P$ is irreducible so that up to a multiplicative constant: $\pi$ is unique and strictly positive.

Let $D= \mbox{diag} (\sqrt{\pi(1)},\dots, \sqrt{\pi(n)})$. Let $Q = D P D^{-1}$. Observe that

$$ Q_{i,j} = (D P D^{-1})_{i,j} = \sqrt{\pi(i)} p_{i,j} \frac{1}{\sqrt{\pi(j)}}.$$

By assuming

$$(*)\quad \pi(i) p_{i,j} = \pi(j) p_{j,i},$$ we have

\begin{align*} Q_{j,i} &\overset{\mbox{def}}{=} \sqrt{\pi(j)} p_{j,i} \frac{1}{\sqrt{\pi(i)}} \\ & =\frac{1}{\sqrt{\pi(j)}} \pi (j) p_{j,i} \frac{1}{\sqrt{\pi(i)}}\\ & \overset{(*)}{=} \frac{1}{\sqrt{\pi(j)}} \pi(i) p_{i,j} \frac{1}{\sqrt{\pi(i)}} \\ & = \sqrt{\pi(i)} p_{i,j} \frac{1}{\sqrt{\pi(j)}}\\ & = Q_{i,j}. \end{align*}

Therefore $Q$ is symmetric. As a result, all its eigenvalues are real and it is diagonalizable. Since $P$ and $Q$ are similar, the same holds for $P$.

Answer 2

(Typed after the answer of Fnacool was already accepted, only a complement that may make the same argument "human" / structural.)

The usual argument considers the Hilbert spacce $H=L^2(\pi)$, and the operator $P$ (well, same letter, sorry) on $H$ given by $$ (Pf)(x)=\sum_{y\in\Omega}P(x,y)f(y)\ . $$ It is selfadjoint, $$ \begin{aligned} \langle Pf, g\rangle &= \sum_{x}\pi(x)\; (Pf)(x)\;\bar g(x)\\ &= \sum_{x,y}\pi(x)\; P(x,y)\;f(y)\;\bar g(x)\\ &= \sum_{x,y}\pi(y)\; P(y,x)\;f(y)\;\bar g(x)\\ &= \sum_{x,y}\pi(y) \;f(y)\;\overline{P(y,x)\; g(x)}\\ &= \sum_{y}\pi(y)\; f(y)\;\overline {Pg(y)}\\ &= \langle f, Pg\rangle \end{aligned} $$ so the operator $P$ is selfadjoint (and a contraction). Its eigenvalues are thus real and contained in $[-1,1]$.

Answer 3

This thread has aged, but it is less than a year old. This is a simple and extremely important result, so I'll give a very simple, motivated proof.

In particular for simplicity, I assume the chain has one communicating class. I assume this (time homogenous) markov chain has finitely many states since we're discussing eigenvalues; the underlying chain is thus positive recurrent. Let diagonal matrix $D := diag(\mathbf \pi)$ where $\pi$ is the steady state distribution.

Such a chain is reversible iff it satisfies detailed balance equations
$\pi(x)P(x,y) = \pi(y)P(y,x)$

Now calculate $P(x,y)$ two different ways.

First way
$P(x,y) = \mathbf e_x^T P\mathbf e_y $
(with standard basis vector $\mathbf e_k$)

Second way
$P(x,y)= \frac{\pi(y)}{\pi(x)}P(y,x) = \frac{\pi(y)}{\pi(x)}\cdot \mathbf e_y^T P \mathbf e_x = \frac{\pi(y)}{\pi(x)}\cdot \mathbf e_x^T P^T \mathbf e_y = \mathbf e_x^T \big(\frac{\pi(y)}{\pi(x)} P^T\big) \mathbf e_y = \mathbf e_x^T \big(D^{-1}P^T D\big)\mathbf e_y $
where we make use of the fact that transposing a scalar gives the same scalar. As a gut check
$\big(D^{-1}P^T D\big)\mathbf 1 = D^{-1}P^T\mathbf \pi = D^{-1}\mathbf \pi =\mathbf 1 $
so this is a stochastic matrix

Putting this together gives
$ \mathbf e_x^T P\mathbf e_y = P(x,y) = \mathbf e_x^T \big(D^{-1}P^T D\big)\mathbf e_y $
for arbitrary natural numbers $x$ and $y$ so we know $P = \big(D^{-1}P^T D\big) $

effecting a similarity transform with $D^\frac{1}{2}$ gives
$D^\frac{1}{2} PD^\frac{-1}{2} = \big(D^\frac{-1}{2}P^T D^\frac{1}{2}\big) $

this matrix is symmetric, because
$\big(D^\frac{1}{2} PD^\frac{-1}{2}\big) = \big(D^\frac{-1}{2}P^T D^\frac{1}{2}\big) = \big(D^\frac{-T}{2}P^T D^\frac{T}{2}\big) = \big(D^\frac{1}{2}P D^\frac{-1}{2}\big)^T$

and of course this matrix is similar to $P$, so in particular

$P $
$= D^\frac{-1}{2}\big(D^\frac{1}{2} PD^\frac{-1}{2}\big)D^\frac{1}{2} $
$= D^\frac{-1}{2}\big(U \Lambda U^T \big)D^\frac{1}{2} $
$=\big(D^\frac{-1}{2}U\big) \Lambda \big(U^{-1} D^\frac{1}{2}\big) $
$=\big(D^\frac{-1}{2}U\big) \Lambda \big(D^\frac{-1}{2}U\big)^{-1} $
$= S \Lambda S^{-1}$

for some orthogonal matrix $U$. Thus $P$ has real spectrum, is always diagonalizable and while not generally symmetric itself, we can easily estimate/bound say the Frobenius norm (or any Schatten p norm) of $S$ and $S^{-1}$ if we have estimates on the steady state distribution $\mathbf \pi$.