Left Eigenvector of a Stochastic Matrix
- 1
Abstract
We determine the left eigenvector of a stochastic matrix <i>M</i> associated to the eigenvalue 1 in the commutative and the noncommutative cases. In the commutative case, we see that the eigenvector associated to the eigenvalue 0 is (<i>N</i><sub>1</sub>,<i>N<sub>n</sub></i>) , where <i>N</i><sub>i</sub> is the <i>i</i>–<i>th</i> iprincipal minor of <i>N</i>=<i>M</i>–<i>I<sub>n</sub></i> , where <i>I<sub>n</sub></i> is the identity matrix of dimension <i>n</i>. In the noncommutative case, this eigenvector is (<i>P</i><sub>1</sub><sup>-1</sup>,<i>P</i><sub><i>n</i></sub><sup>-1</sup>) , where <i>P<sub>i</sub></i> is the sum in Q《α<sub><i>ij</i></sub>》 of the corresponding labels of nonempty paths starting from <i>i</i> and not passing through <i>i</i> in the complete directed graph associated to <i>M</i> .
- S. Lavall′ee, D. Perrin, C. Reutenauer and V. Retakh. “Codes and Noncommutative Stochastic Matrices,” To appear, 2008.
- A. Broder. “Generating random spanning trees. Proc 30th IEEE Symp,” Proceedings of the 30th IEEE Symposium on Foundation of Computer Science, Boston, 1989, pp. 442-447.
- V. Anantharam and P. Tsoucas. “A Proof of the Markov Chain Tree Theorem,” Statistic and Probability Letters, Vol. 8, No. 2, 1989, pp. 189-192.
- D.-J. Aldous. “The randow Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees,” SIAM Journal on Discrete Mathe-matics, Vol. 3, No. 4, 1990, pp. 450-465.
- J. Berstel and C. Reutenauer. “Les s′eries rationnelles et leurs langages,” Mas-son, Paris, 1984.
- J. Berstel and C. Reutenauer, “Rational Series and Their Languages,” 2008. http://www-igm.univ-mlv.fr/~berstel/LivreSeries/Livre-Series08janvier2008.pdf.
- A. Amitsur, “Rational Identities and Applications to Algebra and Geometry,” Journal of Alge-bra, Vol. 3, 1966, pp. 304-359.
- G.M. Bergman, “Skew Field of Noncommutative Rational Functions, after Amitsur.” S′eminaire Schu¨tzen- berger-Lentin-Nivat, Vol. 16, 1970.
- P. Malcolmson, “A Prime Matrix Ideal Yields a Skew Field,” Journal of the London Mathematical Society, Vol. 18, 1978, pp. 221-233.
- P. M. Cohn, “Free Rings and Their Relations,” Academic Press, Salt Lake City, 1971.
- P. M. Cohn, “Skew Fields: Theory of General Di-vision Rings,” Encyclopedia of Mathematics and Its Applica-tions,” Cambridge University Press, Cambridge, 1995.
- M. Fliess, “Sur le Plongement de l’alg`ebre des S′eries Rationelles non Commutatives dans un Corps Gauche,” Proceedings of the National Academy of Sciences, Paris, 1970.