ELA, Volume 12, pp. 25-41, January 2005, abstract.

Girth and Subdominant Eigenvalues for Stochastic 
Matrices

S. Kirkland

The set S(g,n) of all stochastic matrices of order 
n whose directed graph has girth g is considered. 
For any g and n, a lower bound is provided on the 
modulus of a subdominant eigenvalue of such a matrix 
in terms of g and n, and for the cases g=1,2,3 the 
minimum possible modulus of a subdominant eigenvalue 
for a matrix in S(g,n) is computed. A class of examples 
for the case g=4 is investigated, and it is shown 
that if g > 2n/3 and n is at least 27, then for every 
matrix in S(g,n), the modulus of the subdominant 
eigenvalue is at least (1/5)^{1/(2 lfloor n/3 rfloor)}.