Isospectral graph reductions and improved estimates of matrices' spectra

被引:12
作者
Bunimovich, L. A. [2 ,3 ]
Webb, B. Z. [1 ]
机构
[1] Brigham Young Univ, Dept Math, Provo, UT 84602 USA
[2] Georgia Inst Technol, ABC Math Program, Atlanta, GA 30332 USA
[3] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
基金
美国国家科学基金会;
关键词
Isospectral graph reduction; Eigenvalue approximation; Gershgorin discs; Dynamical networks; NETWORKS;
D O I
10.1016/j.laa.2012.04.031
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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. Published by Elsevier Inc.
引用
收藏
页码:1429 / 1457
页数:29
相关论文
共 20 条
[1]   Dynamical networks: interplay of topology, interactions and local dynamics [J].
Afraimovich, Valentin S. ;
Bunimovich, Leonid A. .
NONLINEARITY, 2007, 20 (07) :1761-1771
[2]  
[Anonymous], 1931, B LACADEMIE SCI LURS
[3]  
[Anonymous], 1982, Linear and Multilinear Algebra
[4]  
[Anonymous], 2004, GERSHGORIN HIS CIRCL
[5]   Long range action in networks of chaotic elements [J].
Blank, M ;
Bunimovich, L .
NONLINEARITY, 2006, 19 (02) :329-344
[6]   LIMITS FOR THE CHARACTERISTIC ROOTS OF A MATRIX .2. [J].
BRAUER, A .
DUKE MATHEMATICAL JOURNAL, 1947, 14 (01) :21-26
[7]  
Brualdi R.A., 1991, Encyclopedia of Mathematics and Its Applications, V39
[8]   Isospectral graph transformations, spectral equivalence, and global stability of dynamical networks [J].
Bunimovich, L. A. ;
Webb, B. Z. .
NONLINEARITY, 2012, 25 (01) :211-254
[9]  
Chung F., 1992, Spectral Graph Theory
[10]  
Chung F., 2006, COMPLEX GRAPH NETWOR