Abstract
In a recent paper the authors proposed a lower bound on 1 − λ i , where Λ i ≠ 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F.L. Bauer, Eckart Deutsch, and J. Stoer: Abschätzungen für die Eigenwerte positive linearer Operatoren. Lin. Alg. Appl. 2 (1969), 275–301.
A. Ben-Israel and T.N. Greville: Generalized Inverses: Theory and Applications. Academic Press, New-York, 1973.
A. Berman and R.J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. SIAM Publications, Philadelphia, 1994.
S.L. Campbell and C.D. Meyer, Jr.: Generalized Inverses of Linear Transformations. Dover Publications, New York, 1991.
Eckart Deutsch and C. Zenger: Inclusion domains for eigenvalues of stochastic matrices. Numer. Math. 18 (1971), 182–192.
M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305.
M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory. Czechoslovak Math. J. 25 (1975), 619–633.
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.
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.
S.J. Kirkland, M. Neumann, and B. Shader: Characteristic vertices of weighted trees via Perron values. Lin. Multilin. Alg. 40 (1996), 311–325.
S.J. Kirkland, M. Neumann, and B. Shader: Applications of Paz's inequality to perturbation bounds ffor Markov chains. Lin. Alg. Appl. To appear.
R. Merris: Characteristic vertices of trees. Lin. Multilin. Alg., 22 (1987), 115–131.
A. Paz: Introduction to Probabilistic Automata. Academic Press, New-York, 1971.
E. Seneta: Non-negative Matrices and Markov Chains. Second Edition. Springer Verlag, New-York, 1981.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kirkland, S.J., Neumann, M. & Shader, B.L. On a bound on algebraic connectivity: the case of equality. Czechoslovak Mathematical Journal 48, 65–76 (1998). https://doi.org/10.1023/A:1022415527627
Issue Date:
DOI: https://doi.org/10.1023/A:1022415527627