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

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?

(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]$$.

• Do you have a good reference for this? I thought the book I'm using was a pretty standard source, but these Hilbert space arguments seem to be of a whole other flavour. Mar 22, 2019 at 0:11
• I only saw the accepted solution, and remembered immediately the structure. (The square roots "must come" from making an orthogonal basis orthonormal, i had it in the feeling, said it to myself, so where is the Hilbert space...?!) I only remembered a situation with professor Ion Cuculescu (probabilistic setting) long time ago, and because the operator algebras were next door, and i had to write an operator algebraic work coordinated by Serban Stratila... Now, years after, a random search gave for instance ime.usp.br/~tassio/TMP/… Mar 22, 2019 at 1:27

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$$.

• This is less straight-forward than I expected. Is it a commonly known result? I'm reading "Markov Chains and Mixing Times" by Levin and Peres and they just state this fact in chapter 12 as if it's obvious... Mar 21, 2019 at 17:23
• Yes, perhaps not in this form. Another way to state reversibility is through $P$ being symmetric WRT to inner product $(v,u) = \sum_{i=1}^n \pi(i) v(i) u(i)$ (check). Mar 21, 2019 at 17:27

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$$.

• If a non-stochastic $P$ satisfy the detailed balance equations for some positive $\pi$, then this proof that $P$ is diagonal still holds, right? I asked this as a separate question. Thanks Mar 16, 2023 at 15:07
• @GFrazao "then this proof that 𝑃 is diagonal still holds" -- my proof does no such thing. Please re-read it. Mar 16, 2023 at 17:22
• Yeah, I meant that $P$ is diagonalizable... You never use the fact that $P$ is stochastic, or that $\pi$ is the eigenvector with unit eigenvalue. Isn't the proof general for any matrix $P$ and positive vector $\pi$ satisfying the detailed balance equations? Mar 16, 2023 at 19:51