Graphs that allow all the eigenvalue multiplicities to be even

DOI10.1016/J.LAA.2014.04.017zbMATH Open1288.05165arXiv1401.1940OpenAlexW2963519751MaRDI QIDQ2451699FDOQ2451699

Authors: Polona Oblak, Helena Šmigoc 

Publication date: 4 June 2014

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

Abstract: Let $G$ be an undirected graph on $n$ vertices and let $S(G)$ be the set of all $nimesn$ real symmetric matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of $G$. The inverse eigenvalue problem for a graph $G$ is a problem of determining all possible lists that can occur as the lists of eigenvalues of matrices in $S(G).$ This question is, in general, hard to answer and several variations were studied, most notably the minimum rank problem. In this paper we introduce the problem of determining for which graphs $G$ there exists a matrix in $S(G)$ whose characteristic polynomial is a square, i.e. the multiplicities of all its eigenvalues are even. We solve this question for several families of graphs.

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

Recommendations

• The inverse eigenvalue problem of a graph: multiplicities and minors
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• The inverse eigenvalue and inertia problems for minimum rank two graphs
• On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices
• Ordered multiplicity inverse eigenvalue problem for graphs on six vertices

zbMATH Keywords

grapheigenvaluesymmetric matrixmaximum multiplicity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Hermitian, skew-Hermitian, and related matrices (15B57)

Cites Work

• The inverse eigenvalue problem for nonnegative matrices
• Minimum number of distinct eigenvalues of graphs
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• The minimum rank of symmetric matrices described by a graph: a survey
• On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree
• The implicit construction of multiplicity lists for classes of trees and verification of some conjectures
• Inertia sets for graphs on six or fewer vertices
• Unordered multiplicity lists of a class of binary trees
• Graphs whose minimal rank is two
• Unordered multiplicity lists of wide double paths
• The inertia set of the join of graphs

Cited In (12)

• On the inverse eigenvalue problem for block graphs
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Distinct eigenvalues are realizable with generic eigenvectors
• The inverse eigenvalue and inertia problems for minimum rank two graphs
• The maximum of the minimal multiplicity of eigenvalues of symmetric matrices whose pattern is constrained by a graph
• Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
• Corrigendum to: ``Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• The combinatorial inverse eigenvalue problems: complete graphs and small graphs with strict inequality
• The combinatorial inverse eigenvalue problem. II: All cases for small graphs
• Orthogonal symmetric matrices and joins of graphs
• Null vectors, Schur complements, and Parter vertices
• A zero forcing technique for bounding sums of eigenvalue multiplicities

This page was built for publication: Graphs that allow all the eigenvalue multiplicities to be even

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