×

Lower bounds for the first eigenvalue of certain M-matrices associated with graphs. (English) Zbl 0784.15010

The author gives Cheeger type lower bounds [cf. J. Cheeger [Probl. Anal. Symp. in Honor of Salomon Bochner, Princeton Univ. 1969, 195-199 (1970; Zbl 0212.449)] for the smallest eigenvalue of the Laplacian of corresponding undirected connected multigraphs in terms of the expansion coefficients and norm estimates. Upper bounds for the convergence rate of certain nonnegative irreducible symmetric matrices and irreducible diagonally symmetrizable stochastic matrices are also obtained.

MSC:

15A42 Inequalities involving eigenvalues and eigenvectors
65F10 Iterative numerical methods for linear systems
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

Citations:

Zbl 0212.449
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., eigenvalues and expanders, (Combinatorica, 6 (1986)), 83-96 · Zbl 0661.05053
[2] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, (Gunning, R. C., Problems in Analysis (1970), Princeton U.P), 195-199 · Zbl 0212.44903
[3] Dodziuk, J., Difference equation, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc., 284, 787-794 (1984) · Zbl 0512.39001
[4] S. Friedland, Estimates of the spectral radius of graphs, Linear Multilin. Algebra; S. Friedland, Estimates of the spectral radius of graphs, Linear Multilin. Algebra
[5] Golub, G. H.; Van Loan, C. F., Matrix Computations (1989), Johns Hopkins U.P · Zbl 0733.65016
[6] A. Lubotzky, Discrete groups, expanding graphs and invariant measures, to appear.; A. Lubotzky, Discrete groups, expanding graphs and invariant measures, to appear. · Zbl 1183.22001
[7] Sinclair, A.; Jerrum, M., Approximate counting, uniform generation and rapidly mixing Markov chains (1987), Preprint
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.