Spectra of stochastic matrices with a Toeplitz interior
math.PR, math.RA
Submitted: 2026-10-30
Updated: 2026-11-15
Comments: 41 pages, 4 figures, 16 references
License: http://creativecommons.org/licenses/by/4.0/
The gist: For stochastic matrices of order n, the Karpelevič region is the set of all possible eigenvalues.
Abstract
For stochastic matrices of order n, the Karpelevič region is the set of all possible eigenvalues. We study matrices whose first and last m rows are arbitrary probability vectors, while the remaining middle rows come from one probability vector by successive cyclic shifts to the right, moving the last entry to the first position each time. As m increases, their eigenvalue regions expand from the polygon spanned by the n th roots of unity. For n at least3, they first equal the full Karpelevič region at m= (n-1)/4. Reproducing all n eigenvalues, counted with multiplicity, of every stochastic matrix of the same order requires m= n/2. Thus, in even order n at least4, retaining two consecutive rows with the Toeplitz pattern can exclude eigenvalue lists even when every possible eigenvalue occurs individually. The boundary of the Karpelevič region consists of arcs joining roots of unity. We determine the least m for which every point of each arc occurs as an eigenvalue in our family. For arcs whose nonreal points first become possible eigenvalues at order n at least4, and for m at least1 below this minimum, no point on the arc other than its endpoints occurs in the family. At the minimum, every point on the arc becomes attainable. At the smallest order n at least4 at which a nonreal point on a boundary arc away from its endpoints can occur as an eigenvalue, that point determines the characteristic polynomial of every stochastic matrix of order n having it as an eigenvalue. Further results describe the smaller regions and the angles at which their boundaries approach roots of unity.
Sources
- The Type III realisation conjecture of Kirkland and migoc
- Stochastic realisers of non-degenerate full-degree Type II reduced Ito polynomials
- A proof of the Karpelevi theorem via invariant polygons
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves