1. Department of Mathematics, Zhejiang University of Technology, Zhejiang 310023, China;
2. State Key Lab of CAD & CG, Zhejiang University, Zhejiang 310027, China;
3. Department of Mathematics, Zhejiang University of Science & Technology, Zhejiang 310023, China;
4. College of Information Technology, Zhejiang Chinese Medical University, Zhejiang 310053, China

Abstract It is well-known that the eigenvalues of stochastic matrices lie in the unit circle and at least one of them has the value one. Let {1, r_{2}, · · · , r_{N}} be the eigenvalues of stochastic matrix X of size N × N. We will present in this paper a simple necessary and sufficient condition for X such that |r_{j}| < 1, j = 2, · · ·,N. Moreover, such condition can be very quickly examined by using some search algorithms from graph theory.

Abstract：
It is well-known that the eigenvalues of stochastic matrices lie in the unit circle and at least one of them has the value one. Let {1, r_{2}, · · · , r_{N}} be the eigenvalues of stochastic matrix X of size N × N. We will present in this paper a simple necessary and sufficient condition for X such that |r_{j}| < 1, j = 2, · · ·,N. Moreover, such condition can be very quickly examined by using some search algorithms from graph theory.

Supported by grants from Science & Technology Pillar Program of Zhejiang Province (No. 2008C21084, No. 2009C31120, No. 2009C34006), Key Industrial Projects of Major Science & Technology Projects of Zhejiang Province (No. 2009C11023) and Foundation of Zhejiang Educational Committee (No. Y200804427).

Cite this article:

.Estimates for Eigenvalues of Stochastic Matrices[J] Acta Mathematicae Applicatae Sinica, English Serie, 2011,V27(3): 503-508