This paper is a survey about the emerging topic of eigenvalue location in symmetric matrices, that is: given a real symmetric matrix \(A\) and a real interval \(I\), determine the number of eigenvalues of \(A\) lying in \(I\). One way to solve this problem for a given symmetric matrix \(A\) is to compute its eigendecomposition \[ A = Q^{-1}DQ, \] where \(D\) is the diagonal matrix whose entries are the eigenvalues of \(A\). However, for many classes of symmetric matrices one can exploit the underlying graph structure of the matrix \(A\) (obtained from the off-diagonal nonzero entries of \(A\)) and use this graph structure to devise efficient linear time algorithms for the problem of eigenvalue location. The general procedure is as follows: recall that the inertia of a matrix \(A\) is the triple \((n_{+}(A), n_{-}(A), n_{0}(A))\). Sylvester’s law of inertia states that two real symmetric matrices \(A\) and \(B\) have the same inertia if and only if they are congruent, i.e., if there is an invertible matrix \(P\) such that \(A= P^{T}BP\). If, for a real symmetric matrix \(A\) and a real number \(x\), one could efficiently find a diagonal matrix \(D\) that is congruent to \(A+x \mathrm{I}\) (here \(\mathrm{I}\) is the identity matrix), then the inertia of \(A+x\mathrm{I}\) could be readily obtained from the inertia of \(D\), and the eigenvalue location problem can be easily solved.
The first part of the survey (Sections 2 and 3) considers the case of sparse matrices. In Section 2, a linear time algorithm is given which finds a diagonal matrix \(D\) congruent to a real symmetric matrix \(A\) when the underlying graph of \(A\) is a tree (the nonzero entries of \(A\) can be arbitrary). In Section 3, this is extended to matrices whose underlying graph has a tree decomposition of width \(k\).
The second part of the survey (Sections 4 and 5) considers the case of dense graphs. Here, the results are no longer applicable for arbitrary symmetric matrices with the appropriate underlying graph, but are restricted to matrices where each off-diagonal entry is in the set \(\{0, \beta\}\) for some \(\beta \in \mathbb{R}\) (note that this class of matrices includes many matrices well-studied in spectral graph theory, {e.g.}, the adjacency, Laplacian and signless Laplacian matrices of a graph). In Section 4, an efficient algorithm is given for the eigenvalue location of {cographs} (a definition of the family of cographs is that it is the family of graphs which does not contain the path \(P_4\) as an induced subgraph). The important property of cographs exploited here is that there are two vertices \(u\) and \(v\) whose corresponding rows and columns in the adjacency matrix of the graph can differ in at most two positions. In Section 5, algorithms for arbitrary dense graphs are given using a slick clique decomposition of the underlying graph.
The third part of the survey (Sections 6 and 8) focuses on applications of eigenvalue location to problems in spectral graph theory. An application is to limit points of spectral radii of graphs. Among other applications described in the paper are inertial and spectral characterization of cographs and some progress on Brouwer’s conjecture about Laplacian eigenvalues. Eigenvalue location may find further applications in spectral graph theory.