| Title:
|
Bounds on the subdominant eigenvalue involving group inverses with applications to graphs (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:
|
1-20 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $A$ be an $n\times n$ symmetric, irreducible, and nonnegative matrix whose eigenvalues are $\lambda _1 > \lambda _2 \ge \ldots \ge \lambda _n$. In this paper we derive several lower and upper bounds, in particular on $\lambda _2$ and $\lambda _n$, but also, indirectly, on $\mu = \max _{2\le i \le n} |\lambda _i|$. The bounds are in terms of the diagonal entries of the group generalized inverse, $Q^{\#}$, of the singular and irreducible M-matrix $Q=\lambda _1 I-A$. Our starting point is a spectral resolution for $Q^{\#}$. We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected graphs, where now $Q$ becomes $L$, the Laplacian of the graph. In case the graph is a tree we find a graph-theoretic interpretation for the entries of $L^{\#}$ and we also sharpen an upper bound on the algebraic connectivity of a tree, which is due to Fiedler and which involves only the diagonal entries of $L$, by exploiting the diagonal entries of $L^{\#}$. (English) |
| MSC:
|
05C40 |
| MSC:
|
05C50 |
| MSC:
|
15A09 |
| MSC:
|
15A18 |
| MSC:
|
15A42 |
| MSC:
|
15A48 |
| idZBL:
|
Zbl 0931.15012 |
| idMR:
|
MR1614056 |
| . |
| Date available:
|
2009-09-24T10:10:27Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127394 |
| . |
| Reference:
|
[1] A. Ben-Israel and T. N. Greville: Generalized Inverses: Theory and Applications.Academic Press, New-York, 1973. |
| Reference:
|
[2] A. Berman and R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences.Academic Press, New-York, 1979. MR 0544666 |
| Reference:
|
[3] S. L. Campbell and C. D. Meyer, Jr.: Generalized Inverses of Linear Transformations.Dover Publications, New York, 1991. MR 1105324 |
| Reference:
|
[4] M. Fiedler: Algebraic connectivity of graphs.Czechoslovak Math. J. 23 (1973), 298–305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[5] 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:
|
[6] C. D. Meyer, Jr.: The role of the group generalized inverse in the theory of finite Markov chains.SIAM Rev. 17 (1975), 443–464. Zbl 0313.60044, MR 0383538, 10.1137/1017044 |
| Reference:
|
[7] C. D. Meyer: The condition of a finite Markov chain and perturbations bounds for the limiting probabilities.SIAM J. Alg. Disc. Meth. 1 (1980), 273–283. MR 0586154, 10.1137/0601031 |
| Reference:
|
[8] C. D. Meyer: Sensitivity of the stationary distribution of a Markov chain.SIAM J. Matrix Anal. Appl. 15 (1994), 715–728. Zbl 0809.65143, MR 1282690, 10.1137/S0895479892228900 |
| Reference:
|
[9] C. D. Meyer, Jr. and G. W. Stewart: Derivatives and perturbations of eigenvectors.SIAM J. Numer. Anal. 25 (1988), 679–691. MR 0942213, 10.1137/0725041 |
| Reference:
|
[10] R. Merris: Laplacian matrices and graphs: a survey.Lin. Alg. Appl. 197, 198 (1994), 143–176. MR 1275613, 10.1016/0024-3795(94)90486-3 |
| Reference:
|
[11] B. Mohar: Eigenvalues, diameter, and mean distance in graphs.Graphs Combin. 7 (1991), 53–64. Zbl 0771.05063, MR 1105467, 10.1007/BF01789463 |
| Reference:
|
[12] M. Neumann and R. J. Plemmons: Convergent nonnegative matrices and iterative methods for consistent linear systems.Numer. Math. 31 (1978), 265–279. MR 0514597, 10.1007/BF01397879 |
| Reference:
|
[13] D. L. Powers: Graph partitioning by eigenvectors.Lin. Alg. Appl. 101 (1988), 121–133. Zbl 0666.05056, MR 0941300, 10.1016/0024-3795(88)90147-4 |
| Reference:
|
[14] E. Seneta: Non-negative Matrices and Markov Chains. Second Edition.Springer Verlag, New-York, 1981. MR 2209438 |
| Reference:
|
[15] R. S. Varga: Matrix Iterative Analysis.Prentice-Hall, Englewood Cliffs, NJ, 1962. MR 0158502 |
| Reference:
|
[16] J. H. Wilkinson: The Algebraic Eigenvalue Problem.Oxford Univ. Press, London, 1965. Zbl 0258.65037, MR 0184422 |
| . |
