Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

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

share|cite|improve this question
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
Spoiler: On $p$'th roots of stochastic matrices – 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
up vote 15 down vote accepted

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.

share|cite|improve this answer
"...which is non-negative for any non-negative..." mmm some hint? – leonbloy May 9 '12 at 20:27
@leonbloy I've added more information on this problem. – Byron Schmuland May 9 '12 at 21:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.