Graphs that allow all the eigenvalue multiplicities to be even

DOI10.1016/J.LAA.2014.04.017MaRDI QIDQ2451699zbMATH OpenOpenAlexFDO

Authors Polona Oblak, Helena Šmigoc

Publication date 4 June 2014

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

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

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)

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.

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

Cites work

• Graphs whose minimal rank is two
• Inertia sets for graphs on six or fewer vertices
• Minimum number of distinct eigenvalues of graphs
• 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
• The inertia set of the join of graphs
• The inverse eigenvalue problem for nonnegative matrices
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• The minimum rank of symmetric matrices described by a graph: a survey
• Unordered multiplicity lists of a class of binary trees
• Unordered multiplicity lists of wide double paths

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 maximum of the minimal multiplicity of eigenvalues of symmetric matrices whose pattern is constrained by a graph
• The inverse eigenvalue and inertia problems for minimum rank two graphs
• Corrigendum to: ``Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
• 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)