| Title:
|
On a bound on algebraic connectivity: the case of equality (English) |
| Author:
|
Kirkland, Stephen J. |
| Author:
|
Neumann, Michael |
| Author:
|
Shader, Bryan L. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
48 |
| Issue:
|
1 |
| Year:
|
1998 |
| Pages:
|
65-76 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| MSC:
|
05C40 |
| MSC:
|
05C50 |
| MSC:
|
15A09 |
| MSC:
|
15A42 |
| MSC:
|
15A45 |
| MSC:
|
15A51 |
| MSC:
|
60J10 |
| idZBL:
|
Zbl 0931.15013 |
| idMR:
|
MR1614076 |
| . |
| Date available:
|
2009-09-24T10:11:06Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127399 |
| . |
| Reference:
|
[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. MR 0245587, 10.1016/0024-3795(69)90031-7 |
| Reference:
|
[2] A. Ben-Israel and T.N. Greville: Generalized Inverses: Theory and Applications.Academic Press, New-York, 1973. |
| Reference:
|
[3] A. Berman and R.J. Plemmons: Nonnegative Matrices in the Mathematical Sciences.SIAM Publications, Philadelphia, 1994. MR 1298430 |
| Reference:
|
[4] S.L. Campbell and C.D. Meyer, Jr.: Generalized Inverses of Linear Transformations.Dover Publications, New York, 1991. MR 1105324 |
| Reference:
|
[5] Eckart Deutsch and C. Zenger: Inclusion domains for eigenvalues of stochastic matrices.Numer. Math. 18 (1971), 182–192. MR 0301908, 10.1007/BF01436327 |
| Reference:
|
[6] M. Fiedler: Algebraic connectivity of graphs.Czechoslovak Math. J. 23 (1973), 298–305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[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 |
| Reference:
|
[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. MR 1614056, 10.1023/A:1022455208972 |
| Reference:
|
[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 |
| Reference:
|
[10] S.J. Kirkland, M. Neumann, and B. Shader: Characteristic vertices of weighted trees via Perron values.Lin. Multilin. Alg. 40 (1996), 311–325. MR 1384650, 10.1080/03081089608818448 |
| Reference:
|
[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). |
| Reference:
|
[12] R. Merris: Characteristic vertices of trees.Lin. Multilin. Alg., 22 (1987), 115–131. Zbl 0636.05021, MR 0936566, 10.1080/03081088708817827 |
| Reference:
|
[13] A. Paz: Introduction to Probabilistic Automata.Academic Press, New-York, 1971. Zbl 0234.94055, MR 0289222 |
| Reference:
|
[14] E. Seneta: Non-negative Matrices and Markov Chains. Second Edition.Springer Verlag, New-York, 1981, pp. . MR 2209438 |
| . |
