This is a plot of the non-real eigenvalues of $10^4$ 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$.
Best Answer
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*}
Reference. R. Loewy and D. London, A note on an inverse problem for non-negative matrices, Linear and Multilinear Algebra, Volume 6, pages 83-90, 1978.