Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Summary:
In a recent paper the authors proposed a lower bound on $1 - \lambda _i$, where $\lambda _i$, $ \lambda _i \ne 1$, is an eigenvalue of a transition matrix $T$ of an ergodic Markov chain. The bound, which involved the group inverse of $I - T$, was derived from a more general bound, due to Bauer, Deutsch, and Stoer, on the eigenvalues of a stochastic matrix other than its constant row sum. Here we adapt the bound to give a lower bound on the algebraic connectivity of an undirected graph, but principally consider the case of equality in the bound when the graph is a weighted tree. It is shown that the bound is sharp only for certain Type I trees. Our proof involves characterizing the case of equality in an upper estimate for certain inner products due to A. Paz.
References:
[1] F.L. Bauer, Eckart Deutsch, and J. Stoer: Abschätzungen für die Eigenwerte positive linearer Operatoren. Lin. Alg. Appl. 2 (1969), 275–301. DOI 10.1016/0024-3795(69)90031-7 | MR 0245587
[2] A. Ben-Israel and T.N. Greville: Generalized Inverses: Theory and Applications. Academic Press, New-York, 1973.
[3] A. Berman and R.J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. SIAM Publications, Philadelphia, 1994. MR 1298430
[4] S.L. Campbell and C.D. Meyer, Jr.: Generalized Inverses of Linear Transformations. Dover Publications, New York, 1991. MR 1105324
[5] Eckart Deutsch and C. Zenger: Inclusion domains for eigenvalues of stochastic matrices. Numer. Math. 18 (1971), 182–192. DOI 10.1007/BF01436327 | MR 0301908
[6] M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305. MR 0318007 | Zbl 0265.05119
[7] M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory. Czechoslovak Math. J. 25 (1975), 619–633. MR 0387321
[8] S.J. Kirkland, M. Neumann, and B. Shader: Bounds on the subdominant eigenvalue involving group inverses with applications to graphs. Czechoslovak Math. J. 48(123) (1998), 1–20. DOI 10.1023/A:1022455208972 | MR 1614056
[9] S.J. Kirkland, M. Neumann, and B. Shader: Distances in weighted trees via group inverses of Laplacian matrices. SIAM J. Matrix Anal. Appl (to appear). MR 1471996
[10] S.J. Kirkland, M. Neumann, and B. Shader: Characteristic vertices of weighted trees via Perron values. Lin. Multilin. Alg. 40 (1996), 311–325. DOI 10.1080/03081089608818448 | MR 1384650
[11] S.J. Kirkland, M. Neumann, and B. Shader: Applications of Paz’s inequality to perturbation bounds ffor Markov chains. Lin. Alg. Appl (to appear).
[12] R. Merris: Characteristic vertices of trees. Lin. Multilin. Alg., 22 (1987), 115–131. DOI 10.1080/03081088708817827 | MR 0936566 | Zbl 0636.05021
[13] A. Paz: Introduction to Probabilistic Automata. Academic Press, New-York, 1971. MR 0289222 | Zbl 0234.94055
[14] E. Seneta: Non-negative Matrices and Markov Chains. Second Edition. Springer Verlag, New-York, 1981, pp. . MR 2209438
Search
Partner of
