Bounds on the subdominant eigenvalue involving group inverse with applications to graphs
- 1 March 1998
- journal article
- Published by Institute of Mathematics, Czech Academy of Sciences in Czechoslovak Mathematical Journal
- Vol. 48 (1) , 1-20
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 = λ1I − 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#.
Keywords
This publication has 10 references indexed in Scilit:
- Sensitivity of the Stationary Distribution of a Markov ChainSIAM Journal on Matrix Analysis and Applications, 1994
- Laplacian matrices of graphs: a surveyLinear Algebra and its Applications, 1994
- Eigenvalues, diameter, and mean distance in graphsGraphs and Combinatorics, 1991
- Derivatives and Perturbations of EigenvectorsSIAM Journal on Numerical Analysis, 1988
- Graph partitioning by EigenvectorsLinear Algebra and its Applications, 1988
- Non-negative Matrices and Markov Chains1981
- The Condition of a Finite Markov Chain and Perturbation Bounds for the Limiting ProbabilitiesSIAM Journal on Algebraic Discrete Methods, 1980
- Convergent nonnegative matrices and iterative methods for consistent linear systemsNumerische Mathematik, 1978
- The Role of the Group Generalized Inverse in the Theory of Finite Markov ChainsSIAM Review, 1975
- On the determination of χl,η+−0 AND η000 from bubble chamber measurementsCzechoslovak Journal of Physics, 1975