# Eigenvalues for $3\times 3$ stochastic matrices

This is a plot of the non-real eigenvalues of 10000 randomly generated $3\times3$ stochastic matrices. It's pretty clear that they lie in the convex hull of the three cube roots of unity.

The boundary on the left hand side is easy to explain. If the stochastic matrix $P$ has a non-real eigenvalue $\lambda$, then $\text{trace}(P)=\lambda+\bar\lambda+1=2\text{Re}(\lambda)+1$. On the other hand, the trace of $P$ is also the sum of its diagonal entries, and hence is non-negative real number. Therefore, $\text{Re}(\lambda)\geq -{1\over 2}$.

I hope that there is an easy explanation for the other 2 sides of the triangle, perhaps in terms of some other matrix invariant. So far, I can't think of any. Any ideas?

By the way, it is not hard to show that every point in the triangle can be achieved as the eigenvalue of a stochastic matrix of the form $$P=\begin{bmatrix}1-s-t&s&t\\ t&1-s-t&s\\ s&t&1-s-t \end{bmatrix}$$ for some $s\geq 0, t\geq 0, s+t\leq 1$.

-
So the claim is $1 + \lambda x + \bar{\lambda} x^2 \geq 0$ where $x$ is the cube-root of unity and you want to view it as some matrix invariant? –  user17762 May 5 '12 at 2:04
–  Emre May 5 '12 at 2:08
Can you prove there's a stochastic matrix with $\alpha$ as an eigenvalue if and only if there's one with $e^{2\pi i/3}\alpha$ as an eigenvalue? –  Gerry Myerson May 5 '12 at 2:39
@Marvis Yes, this or any other simple proof. –  Byron Schmuland May 5 '12 at 13:35
@Emre Thanks for the reference. At least I know that the result is true. I would still like a simple proof for the $n=3$ case. –  Byron Schmuland May 5 '12 at 13:36

The invariant that I was looking for is $3(\lambda_1^2+\lambda_2^2+\lambda_3^2)-(\lambda_1+\lambda_2+\lambda_3)^2$, which is non-negative for any non-negative $3\times 3$ matrix $P$. When the eigenvalues are $1$, $\lambda$, and $\bar\lambda$, this means that $$3(1+2\,\text{Re}(\lambda^2))\geq (1+2\,\text{Re}(\lambda))^2,$$ which can be rewritten as $$(1-\text{Re}(\lambda))^2\geq 3\,\text{Im}(\lambda)^2.$$ This gives the other two sides of the triangle in the plot.
Here is a proof of the claim above. Using the positivity of $P$ and the Cauchy-Schwarz inequality, we have \begin{eqnarray*} \lambda_1^2+\lambda_2^2+\lambda_3^2&=&\text{Trace}(P^2)\\ &=&\left(\sum_j p_{1j}p_{j1}\right)+\left(\sum_j p_{2j}p_{j2}\right)+\left(\sum_j p_{3j}p_{j3}\right)\\ &\geq&p_{11}^2+p_{22}^2+p_{33}^2\\ &\geq&{1\over 3}\left(p_{11}+p_{22}+p_{33}\right)^2\\ &=&{1\over 3}\left(\lambda_{1}+\lambda_{2}+\lambda_{3}\right)^2\\ \end{eqnarray*}