Abstract
Let A be an n × n symmetric, irreducible, and nonnegative matrix whose eigenvalues are λ1〉λ2≥ ... ≥λn. In this paper we derive several lower and upper bounds, in particular on λ2 and λ n , but also, indirectly, on \(\mu = \mathop {\max }\limits_{2 \leqslant i \leqslant 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 = λ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 #.
Similar content being viewed by others
References
A. Ben-Israel and T. N. Greville: Generalized Inverses: Theory and Applications. Academic Press, New-York, 1973.
A. Berman and R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. Academic Press, New-York, 1979.
S. L. Campbell and C. D. Meyer, Jr.: Generalized Inverses of Linear Transformations. Dover Publications, New York, 1991.
M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305.
M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory. Czechoslovak Math. J. 25 (1975), 619–633.
C. D. Meyer, Jr.: The role of the group generalized inverse in the theory of finite Markov chains. SIAM Rev. 17 (1975), 443–464.
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.
C. D. Meyer: Sensitivity of the stationary distribution of a Markov chain. SIAM J. Matrix Anal. Appl. 15 (1994), 715–728.
C. D. Meyer, Jr. and G. W. Stewart: Derivatives and perturbations of eigenvectors. SIAM J. Numer. Anal. 25 (1988), 679–691.
R. Merris: Laplacian matrices and graphs: a survey. Lin. Alg. Appl. 197, 198 (1994), 143–176.
B. Mohar: Eigenvalues, diameter, and mean distance in graphs. Graphs Combin. 7 (1991), 53–64.
M. Neumann and R. J. Plemmons: Convergent nonnegative matrices and iterative methods for consistent linear systems. Numer. Math. 31 (1978), 265–279.
D. L. Powers: Graph partitioning by eigenvectors. Lin. Alg. Appl. 101 (1988), 121–133.
E. Seneta: Non-negative Matrices and Markov Chains. Second Edition. Springer Verlag, New-York, 1981.
R. S. Varga: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962.
J. H. Wilkinson: The Algebraic Eigenvalue Problem. Oxford Univ. Press, London, 1965.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kirkland, S.J., Neumann, M. & Shader, B.L. Bounds on the subdominant eigenvalue involving group inverse with applications to graphs. Czechoslovak Mathematical Journal 48, 1–20 (1998). https://doi.org/10.1023/A:1022455208972
Issue Date:
DOI: https://doi.org/10.1023/A:1022455208972