The change in multiplicity of an eigenvalue due to adding or removing edges
type: Item
instance of: scholarly article
title: The change in multiplicity of an eigenvalue due to adding or removing edges
zbMATH Open document ID: 1403.15007
author: Charles R. Johnson
author: Carlos M. Saiago
author: Kenji Toyonaga
published in: Linear Algebra and its Applications
publication date: 2018-11-29T00:00:00Z
review text: Let \(G\) be a simple, undirected graph on \(n\) vertices and denote by \( \mathcal{H}(G)\) the set of all \(n\times n\) Hermitian matrices, the graph of whose off-diagonal entries is \(G\) (no restriction is placed on the diagonal entries). For \(A\in \mathcal{H}(G)\), let \(m_{A}(\lambda )\) and \(\sigma (A)\) denote the multiplicity of an eigenvalue \(\lambda \) of \(A\) and the spectrum of \(A,\) respectively. When a vertex \(u\) is removed from \(G\), the remaining graph is denoted by \(G(u)\) and \(A(u)\in \mathcal{H}(G(u))\) denotes the \( (n-1)\times (n-1)\) submatrix of \(A\in \) \(\mathcal{H}(G)\) resulting from deletion of the row and the column corresponding to \(u\). It is known (see [\textit{R. A. Horn} and \textit{C. R. Johnson}, Matrix analysis. 2nd ed. Cambridge: Cambridge University Press (2013; Zbl 1267.15001)]) that for \(A\in \) \(\mathcal{H}(G)\), \(A(u)\in \mathcal{ H}(G(u))\), and \(\lambda \in \sigma (A)\), the multiplicity of \(\lambda \) may change at most \(1\) when the vertex \(u\) is deleted. A vertex \(u\) of a graph \( G \) is called ``Parter'' (respectively, ``neutral'', ``downer'') in \(G\) for an eigenvalue \(\lambda \) of \(A\in \) \(\mathcal{H}(G),\) relative to matrix \(A\), if \[ m_{A(u)}(\lambda )=m_{A}(\lambda )+1 \] (respectively, \(m_{A(u)}(\lambda )=m_{A}(\lambda ),\text{ }m_{A(u)}(\lambda )=m_{A}(\lambda )-1)\). These numbers define the status of the vertex \(u\) for the eigenvalue \(\lambda \) relative to \(A\). Given a graph \(G\) and \(A\in \mathcal{H}(G)\), the authors first investigate in Section 2 the change of multiplicity of an eigenvalue \(\lambda \) of \(A\) when edges are inserted into \(G\). One of the results of Subsection 2.1 follows: Let \(A\in \mathcal{H}(G)\) and let \(v\) be a Parter vertex in \(G\) for \(\lambda \in \sigma (A)\). When edges are inserted between \(v\) and other vertices, let the resulting graph be \(\widehat{G}\), and let \(\widehat{A}\in \mathcal{H}( \widehat{G})\) be the same as \(A\) …
reviewed by: Janko Marovt
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15B57
Mathematics Subject Classification ID: 13H15
zbMATH DE Number: 6986507
zbMATH Keywords: graph
zbMATH Keywords: edge
zbMATH Keywords: cut-edge
zbMATH Keywords: Hermitian matrix
zbMATH Keywords: eigenvalue
zbMATH Keywords: multiplicity
MaRDI profile type: Publication
full work available at URL: j.laa.2018.09.017
OpenAlex ID: W2889606945
cites work: Q4902474
cites work: Ordered multiplicity lists for eigenvalues of symmetric matrices whose graph is a linear tree
cites work: The structure of matrices with a maximum multiplicity eigenvalue
cites work: The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
cites work: On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph
cites work: The Parter--Wiener Theorem: Refinement and Generalization
cites work: On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree
cites work: The change in multiplicity of an eigenvalue of a Hermitian matrix associated with the removal of an edge from its graph
cites work: Hermitian Matrices, Eigenvalue Multiplicities, and Eigenvector Components
cites work: On the Eigenvalues and Eigenvectors of a Class of Matrices
cites work: The classification of edges and the change in multiplicity of an eigenvalue of a real symmetric matrix resulting from the change in an edge value
cites work: Spectral multiplicity and splitting results for a class of qualitative matrices
Wikidata QID: Q129208484
DOI: 10.1016/J.LAA.2018.09.017
Recommended article: The change in multiplicity of an eigenvalue of a Hermitian matrix associated with the removal of an edge from its graph
Recommended article: The classification of edges and the change in multiplicity of an eigenvalue of a real symmetric matrix resulting from the change in an edge value
Recommended article: Classification of edges in a general graph associated with the change in multiplicity of an eigenvalue
Recommended article: The change in multiplicity of an eigenvalue of a real symmetric matrix resulting from the changes in edge values around a classified vertex in a tree
Recommended article: The effect on eigenvalues of connected graphs by adding edges
Recommended article: The multiplicities of eigenvalues of a graph
Recommended article: The change in eigenvalue multiplicity associated with perturbation of a diagonal entry
Recommended article: On the multiplicity of the eigenvalues of a graph
Recommended article: The effect of removing a 2-downer edge or a cut 2-downer edge triangle for an eigenvalue
Recommended article: Graph reduction techniques and the multiplicity of the Laplacian eigenvalues
description: scientific article; zbMATH DE number 6986507