On a bound on algebraic connectivity: the case of equality

Stephen J. Kirkland; Neumann, Michael; Bryan L. Shader

Czechoslovak Mathematical Journal (1998)

  • Volume: 48, Issue: 1, page 65-76
  • ISSN: 0011-4642

Abstract

top
In a recent paper the authors proposed a lower bound on 1 - λ i , where λ i , λ 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.

How to cite

top

Kirkland, Stephen J., Neumann, Michael, and Shader, Bryan L.. "On a bound on algebraic connectivity: the case of equality." Czechoslovak Mathematical Journal 48.1 (1998): 65-76. <http://eudml.org/doc/30402>.

@article{Kirkland1998,
abstract = {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.},
author = {Kirkland, Stephen J., Neumann, Michael, Shader, Bryan L.},
journal = {Czechoslovak Mathematical Journal},
keywords = {eigenvalues; algebraic connectivity; undirected graphs; lower bound; transition matrix; ergodic Markov chain; group inverse; stochastic matrix},
language = {eng},
number = {1},
pages = {65-76},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On a bound on algebraic connectivity: the case of equality},
url = {http://eudml.org/doc/30402},
volume = {48},
year = {1998},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 48
IS - 1
SP - 65
EP - 76
AB - 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.
LA - eng
KW - eigenvalues; algebraic connectivity; undirected graphs; lower bound; transition matrix; ergodic Markov chain; group inverse; stochastic matrix
UR - http://eudml.org/doc/30402
ER -

References

top
  1. 10.1016/0024-3795(69)90031-7, Lin. Alg. Appl. 2 (1969), 275–301. (1969) MR0245587DOI10.1016/0024-3795(69)90031-7
  2. Generalized Inverses: Theory and Applications, Academic Press, New-York, 1973. (1973) 
  3. Nonnegative Matrices in the Mathematical Sciences, SIAM Publications, Philadelphia, 1994. (1994) MR1298430
  4. Generalized Inverses of Linear Transformations, Dover Publications, New York, 1991. (1991) MR1105324
  5. 10.1007/BF01436327, Numer. Math. 18 (1971), 182–192. (1971) MR0301908DOI10.1007/BF01436327
  6. Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973), 298–305. (1973) Zbl0265.05119MR0318007
  7. A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975), 619–633. (1975) MR0387321
  8. 10.1023/A:1022455208972, Czechoslovak Math. J. 48(123) (1998), 1–20. (1998) MR1614056DOI10.1023/A:1022455208972
  9. Distances in weighted trees via group inverses of Laplacian matrices, SIAM J. Matrix Anal. Appl (to appear). (to appear) MR1471996
  10. 10.1080/03081089608818448, Lin. Multilin. Alg. 40 (1996), 311–325. (1996) MR1384650DOI10.1080/03081089608818448
  11. Applications of Paz’s inequality to perturbation bounds ffor Markov chains, Lin. Alg. Appl (to appear). (to appear) 
  12. 10.1080/03081088708817827, Lin. Multilin. Alg., 22 (1987), 115–131. (1987) Zbl0636.05021MR0936566DOI10.1080/03081088708817827
  13. Introduction to Probabilistic Automata, Academic Press, New-York, 1971. (1971) Zbl0234.94055MR0289222
  14. Non-negative Matrices and Markov Chains. Second Edition, Springer Verlag, New-York, 1981, pp. . (1981) MR2209438

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.