Optimizing Gershgorin for symmetric matrices

Research output: Contribution to journalArticlepeer-review

Abstract

The Gershgorin Circle Theorem is a well-known and efficient method for bounding the eigenvalues of a matrix in terms of its entries. If A is a symmetric matrix, by writing A=B+x1, where 1 is the matrix with unit entries, we consider the problem of choosing x to give the optimal Gershgorin bound on the eigenvalues of B, which then leads to one-sided bounds on the eigenvalues of A. We show that this x can be found by an efficient linear program (whose solution can in may cases be written in closed form), and we show that for large classes of matrices, this shifting method beats all existing piecewise linear or quadratic bounds on the eigenvalues. We also apply this shifting paradigm to some nonlinear estimators and show that under certain symmetries this also gives rise to a tractable linear program. As an application, we give a novel bound on the lowest eigenvalue of a adjacency matrix in terms of the “top two” or “bottom two” degrees of the corresponding graph, and study the efficacy of this method in obtaining sharp eigenvalue estimates for certain classes of matrices.

Original languageEnglish (US)
Pages (from-to)360-383
Number of pages24
JournalLinear Algebra and Its Applications
Volume577
DOIs
StatePublished - Sep 15 2019
Externally publishedYes

Keywords

  • Adjacency matrix
  • Eigenvalue bounds
  • Gershgorin circle theorem
  • Linear program

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Optimizing Gershgorin for symmetric matrices'. Together they form a unique fingerprint.

Cite this