Geodesic
On a bound on algebraic connectivity: the case of equality
Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 65-76 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C40, 05C50, 15A09, 15A42, 15A45, 15A51, 60J10 
@article{CMJ_1998_48_1_a5,
     author = {Kirkland, Stephen J. and Neumann, Michael and Shader, Bryan L.},
     title = {On a bound on algebraic connectivity: the case of equality},
     journal = {Czechoslovak Mathematical Journal},
     pages = {65--76},
     year = {1998},
     volume = {48},
     number = {1},
     mrnumber = {1614076},
     zbl = {0931.15013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a5/}
}
TY  - JOUR
AU  - Kirkland, Stephen J.
AU  - Neumann, Michael
AU  - Shader, Bryan L.
TI  - On a bound on algebraic connectivity: the case of equality
JO  - Czechoslovak Mathematical Journal
PY  - 1998
SP  - 65
EP  - 76
VL  - 48
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a5/
LA  - en
ID  - CMJ_1998_48_1_a5
ER  - 
%0 Journal Article
%A Kirkland, Stephen J.
%A Neumann, Michael
%A Shader, Bryan L.
%T On a bound on algebraic connectivity: the case of equality
%J Czechoslovak Mathematical Journal
%D 1998
%P 65-76
%V 48
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a5/
%G en
%F CMJ_1998_48_1_a5
Kirkland, Stephen J.; Neumann, Michael; Shader, Bryan L. On a bound on algebraic connectivity: the case of equality. Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 65-76. http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a5/

[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 | MR

[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

[4] S.L. Campbell and C.D. Meyer, Jr.: Generalized Inverses of Linear Transformations. Dover Publications, New York, 1991. | MR

[5] Eckart Deutsch and C. Zenger: Inclusion domains for eigenvalues of stochastic matrices. Numer. Math. 18 (1971), 182–192. | DOI | MR

[6] M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305. | MR | Zbl

[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

[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 | MR

[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

[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 | MR

[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 | MR | Zbl

[13] A. Paz: Introduction to Probabilistic Automata. Academic Press, New-York, 1971. | MR | Zbl

[14] E. Seneta: Non-negative Matrices and Markov Chains. Second Edition. Springer Verlag, New-York, 1981, pp. . | MR