Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
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^{\#}$.
References:
[1] A. Ben-Israel and T. N. Greville: Generalized Inverses: Theory and Applications. Academic Press, New-York, 1973.
[2] A. Berman and R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. Academic Press, New-York, 1979. MR 0544666
[3] S. L. Campbell and C. D. Meyer, Jr.: Generalized Inverses of Linear Transformations. Dover Publications, New York, 1991. MR 1105324
[4] M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305. MR 0318007 | Zbl 0265.05119
[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
[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. DOI 10.1137/1017044 | MR 0383538 | Zbl 0313.60044
[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. DOI 10.1137/0601031 | MR 0586154
[8] C. D. Meyer: Sensitivity of the stationary distribution of a Markov chain. SIAM J. Matrix Anal. Appl. 15 (1994), 715–728. DOI 10.1137/S0895479892228900 | MR 1282690 | Zbl 0809.65143
[9] C. D. Meyer, Jr. and G. W. Stewart: Derivatives and perturbations of eigenvectors. SIAM J. Numer. Anal. 25 (1988), 679–691. DOI 10.1137/0725041 | MR 0942213
[10] R. Merris: Laplacian matrices and graphs: a survey. Lin. Alg. Appl. 197, 198 (1994), 143–176. DOI 10.1016/0024-3795(94)90486-3 | MR 1275613
[11] B. Mohar: Eigenvalues, diameter, and mean distance in graphs. Graphs Combin. 7 (1991), 53–64. DOI 10.1007/BF01789463 | MR 1105467 | Zbl 0771.05063
[12] M. Neumann and R. J. Plemmons: Convergent nonnegative matrices and iterative methods for consistent linear systems. Numer. Math. 31 (1978), 265–279. DOI 10.1007/BF01397879 | MR 0514597
[13] D. L. Powers: Graph partitioning by eigenvectors. Lin. Alg. Appl. 101 (1988), 121–133. DOI 10.1016/0024-3795(88)90147-4 | MR 0941300 | Zbl 0666.05056
[14] E. Seneta: Non-negative Matrices and Markov Chains. Second Edition. Springer Verlag, New-York, 1981. MR 2209438
[15] R. S. Varga: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962. MR 0158502
[16] J. H. Wilkinson: The Algebraic Eigenvalue Problem. Oxford Univ. Press, London, 1965. MR 0184422 | Zbl 0258.65037
Search
Partner of
