Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix

Charles R. Johnson; Carlos Manuel Saiago

doi:10.13001/1081-3810.1070

Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix

Charles R. Johnson, Carlos Manuel Saiago

Research output: Contribution to journal › Article › peer-review

17 Citations (Scopus)

5 Downloads (Pure)

Abstract

The maximum multiplicity among eigenvalues of matrices with a given graph cannot generally be expressed in terms of the degrees of the vertices (even when the graph is a tree). Given are best possible lower and upper bounds, and characterization of the cases of equality in these bounds. A by-product is a sequential algorithm to calculate the exact maximum multiplicity by simple counting.

Original language	English
Pages (from-to)	27-31
Number of pages	5
Journal	Electronic Journal Of Linear Algebra
Volume	9
Issue number	3
DOIs	https://doi.org/10.13001/1081-3810.1070
Publication status	Published - Mar 2002

Keywords

Eigenvalues
Multiplicity
Symmetric matrix
Tree
Vertex degrees

Access to Document

10.13001/1081-3810.1070Licence: CC BY

vol9_pp27-31.pdfFinal published version, 113 KBLicence: CC BY

Cite this

@article{66ebb83b52e044f2ad933101aed85faf,

title = "Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix",

abstract = "The maximum multiplicity among eigenvalues of matrices with a given graph cannot generally be expressed in terms of the degrees of the vertices (even when the graph is a tree). Given are best possible lower and upper bounds, and characterization of the cases of equality in these bounds. A by-product is a sequential algorithm to calculate the exact maximum multiplicity by simple counting.",

keywords = "Eigenvalues, Multiplicity, Symmetric matrix, Tree, Vertex degrees",

author = "Johnson, {Charles R.} and Saiago, {Carlos Manuel}",

note = "Research supported in part by Funda{\c c}{\~a}o para a Ci{\^e}ncia e a Tecnologia, Portugal, through the research grant SFRH/BD/899/2000. Part of the research was done while visiting the College of William and Mary.",

year = "2002",

month = mar,

doi = "10.13001/1081-3810.1070",

language = "English",

volume = "9",

pages = "27--31",

journal = "Electronic Journal Of Linear Algebra",

issn = "1081-3810",

publisher = "International Linear Algebra Society",

number = "3",

}

TY - JOUR

T1 - Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix

AU - Johnson, Charles R.

AU - Saiago, Carlos Manuel

N1 - Research supported in part by Fundação para a Ciência e a Tecnologia, Portugal, through the research grant SFRH/BD/899/2000. Part of the research was done while visiting the College of William and Mary.

PY - 2002/3

Y1 - 2002/3

N2 - The maximum multiplicity among eigenvalues of matrices with a given graph cannot generally be expressed in terms of the degrees of the vertices (even when the graph is a tree). Given are best possible lower and upper bounds, and characterization of the cases of equality in these bounds. A by-product is a sequential algorithm to calculate the exact maximum multiplicity by simple counting.

AB - The maximum multiplicity among eigenvalues of matrices with a given graph cannot generally be expressed in terms of the degrees of the vertices (even when the graph is a tree). Given are best possible lower and upper bounds, and characterization of the cases of equality in these bounds. A by-product is a sequential algorithm to calculate the exact maximum multiplicity by simple counting.

KW - Eigenvalues

KW - Multiplicity

KW - Symmetric matrix

KW - Tree

KW - Vertex degrees

U2 - 10.13001/1081-3810.1070

DO - 10.13001/1081-3810.1070

M3 - Article

VL - 9

SP - 27

EP - 31

JO - Electronic Journal Of Linear Algebra

JF - Electronic Journal Of Linear Algebra

SN - 1081-3810

IS - 3

ER -

Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix

Abstract

Keywords

Access to Document

Fingerprint

Cite this