22

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.

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

Rodrigo de Azevedo
  • 20,693
  • 5
  • 43
  • 100
  • 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? –  May 05 '12 at 02:04
  • 3
    Spoiler: [On $p$'th roots of stochastic matrices](http://www.maths.manchester.ac.uk/~higham/papers/hili11.pdf) – Emre May 05 '12 at 02: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 05 '12 at 02:39
  • @Marvis Yes, this or any other simple proof. –  May 05 '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. –  May 05 '12 at 13:36
  • @GerryMyerson This is what I was unable to prove. –  May 05 '12 at 13:36

2 Answers2

21

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.

0

The question by the OP omits one detail that might be misleading: If $\Theta_n$ denotes the subset of the complex plane that contains all eigenvalues of every $n$-by-$n$ stochastic matrix, then $\Theta_n \subseteq \Theta_{n+1}, \forall n \in \mathbb{N}$ because, if $A$ is an $n$-by-$n$ stochastic matrix, then $$ \begin{bmatrix} A & 0 \\ 0 & 1 \end{bmatrix}$$ is an $(n+1)$-by-$(n+1)$ stochastic matrix.

It is also known and easy to show that $\Theta_2 = [-1,1]$ given that the eigenvalues of the two-by-two circulant matrix $$\frac{1}{2}\begin{bmatrix} \lambda + \mu & \lambda - \mu \\ \lambda - \mu & \lambda + \mu \end{bmatrix}$$ are $\lambda$ and $\mu$.

If $\omega_n := \exp(2\pi i /n)$, then $\Theta_3 = \text{conv}(1,\omega_2)\cup \text{conv}(1,\omega_3,\omega_3^2)$.

Pietro Paparella
  • 3,322
  • 1
  • 17
  • 28