Previous |  Up |  Next


eigenvalue; irreducible nonnegative matrix; averaged minimal cut
We present a lower and an upper bound for the second smallest eigenvalue of Laplacian matrices in terms of the averaged minimal cut of weighted graphs. This is used to obtain an upper bound for the real parts of the non-maximal eigenvalues of irreducible nonnegative matrices. The result can be applied to Markov chains.
[1] A. Berman and R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. Academic Press, New York-San Francisco-London, 1979; SIAM, Philadelphia, 1994. MR 1298430
[2] M. Fiedler: An estimate for the non-stochastic eigenvalues of doubly stochastic matrices. Linear Algebra Appl. 214 (1995), 133–143. MR 1311633
[3] D. J. Hartfiel and C. D. Meyer: On the structure of stochastic matrices with a subordinant eigenvalue near  1. Linear Algebra Appl. 272 (1998), 193–203. MR 1489387
[4] A. W. Marshall and I. Olkin: Inequalities: Theory of Majorization and Applications. Academic Press, New York, 1979. MR 0552278
[5] R. Merris: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197–198 (1994), 143–176. MR 1275613 | Zbl 0802.05053
[6] R. Merris: A survey of graph laplacians. Linear and Multilinear Algebra 39 (1995), 19–31. MR 1374468 | Zbl 0832.05081
[7] B. Mohar: Laplace eigenvalues of graphs—a survey. Discrete Math. 109 (1992), 171–183. DOI 10.1016/0012-365X(92)90288-Q | MR 1192380 | Zbl 0783.05073
[8] H. Schneider: Note on the fundamental theorem on irreducible nonnegative matrices. Proc. Edinburgh Math. Soc. 12 (1960/1961), 107–112.
Partner of
EuDML logo