Eigenvalues of stochastic matrices

eigenvalues-eigenvectorsreference-requestroots-of-unitystochastic-matrices

A stochastic matrix is a real $n\times n$ square matrix with nonnegative coefficients such that every row sums to $1$. It is well known that

  • $1$ is an eigenvalue every stochastic matrix,
  • the complex spectrum of a stochastic matrix is included in the unit disk,
  • if $\lambda$ is a modulus $1$ eigenvalue, then $\lambda$ has to be a root of unity of order $\leq n$.

I seem to remember something to the effect that the spectrum of a stochastic $n\times n$ matrix was a subset of the convex hull of all roots of unity of order $\leq n$. Is this correct? And if so, what is the proof / where can I read the proof?

Note the graph in this question suggests a more precise result, maybe along the lines that ''the spectrum of an $n\times n$ stochastic matrix is included in the union of the convex hulls of $k$-th roots of unity, where $1\leq k\leq n$'' or so…

EDIT the paper On $p$th roots of stochastic matrices (Nicholas J. Higham,Lijing Lin linked in a comment to that question asserts that the claim from the note is false for $n>3$. Is there a simple proof for the first statement?

Best Answer

The question of the possible eigenvalues of stochastic matrices is a question that have been solved by F. Karpelevic in 1951. The result is the one cited as Theorem 5.1 in the paper on the pth root of stochastics matrices you are cited. However the original paper is written in russian and very hard to find.

You may find useful this paper about the realizing matrices of the boundary of the set of possible eigenvalues : A matricial view of the Karpelevič Theorem

Another option is to look at Joanne Swift's master thesis (McGill university): Location of characteristic roots of stochastic matrices that translate a previous work by Dmitriev and Dynkin on this question.

Related Question