On bounds of extremal eigenvalues of irreducible and m-reducible matrices

Abstract

For a complex matrix A, the well-known Lévy-Desplanques theorem states that A is nonsingular if |Aii|>∑ j≠i|Aij| for all i. The equivalent Gershgorin theorem on the localization of eigenvalues implies that the eigenvalues λ of A must satisfy |λ|≥mini(|Aii|-∑j≠i|A ij|). Taussky extended this by showing that A is nonsingular if A is irreducible and |Aii|≥∑j≠i|Aij| with the inequality strict for at least one i. A goal of this paper is to give lower bounds on |λ| for this case as well. We give bounds which depend on the diameter and the algebraic connectivity of the graph of A. We also study bounds for reducible matrices by introducing the notion of m-reducibility. In particular, we give bounds for reducible matrices which depend on the algebraic connectivity of the strongly connected components of the graph and the number of edges between them. These bounds are also applicable to bound the subdominant eigenvalues of reducible stochastic matrices and Laplacian matrices of directed graphs. © 2005 Elsevier Inc. All rights reserved.