Isospectral graph reductions and improved estimates of matrices' spectra

DOI10.1016/J.LAA.2012.04.031MaRDI QIDQ445806zbMATH OpenOpenAlexFDO

Authors Leonid A. Bunimovich, B. Z. Webb

Publication date 27 August 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.2453

zbMATH Keywords

eigenvalue approximationdynamical networksGershgorin discsisospectral graph reduction

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Via the process of isospectral graph reduction the adjacency matrix of a graph can be reduced to a smaller matrix while its spectrum is preserved up to some known set. It is then possible to estimate the spectrum of the original matrix by considering Gershgorin-type estimates associated with the reduced matrix. The main result of this paper is that eigenvalue estimates associated with Gershgorin, Brauer, Brualdi, and Varga improve as the matrix size is reduced. Moreover, given that such estimates improve with each successive reduction, it is also possible to estimate the eigenvalues of a matrix with increasing accuracy by repeated use of this process.

Recommendations

• Isospectral reduction in infinite graphs
• On Isospectral Graphs.
• Isospectral graphs and the representation-theoretical spectrum
• The isospectral problem in graph theory
• scientific article; zbMATH DE number 3968632
• Characterizing cospectral vertices via isospectral reduction
• Eigenvectors of isospectral graph transformations
• scientific article; zbMATH DE number 3968633
• On the isoperimetric spectrum of graphs and its approximations
• Graph approximations to the Laplacian spectra

Cites work

• scientific article; zbMATH DE number 3002670 (Why is no real title available?)
• scientific article; zbMATH DE number 2120941 (Why is no real title available?)
• Combinatorial matrix theory
• Complex graphs and networks
• Dynamical networks: interplay of topology, interactions and local dynamics
• Isospectral graph transformations, spectral equivalence, and global stability of dynamical networks
• Limits for the characteristic roots of a matrix. II
• Long range action in networks of chaotic elements
• Matrices eigenvalues, and directed graphs
• Matrix Analysis
• Open problems of Paul Erd�s in graph theory
• Synchronization in networks of nonlinear dynamical systems coupled via a directed graph
• The structure and dynamics of networks

Cited in

(11)

• Pseudospectra of isospectrally reduced matrices.
• Isospectral reduction in infinite graphs
• Generalized eigenvectors of isospectral transformations, spectral equivalence and reconstruction of original networks
• Characterizing cospectral vertices via isospectral reduction
• A new Gershgorin-type result for the localisation of the spectrum of matrices
• Isospectral compression and other useful isospectral transformations of dynamical networks
• Stationary measures on infinite graphs
• Eigenvectors of isospectral graph transformations
• On the spectral properties of Feigenbaum graphs
• Isospectral reductions and quantum walks on graphs
• Improved estimates of survival probabilities via isospectral transformations

This page was built for publication: Isospectral graph reductions and improved estimates of matrices' spectra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445806)