Helena Šmigoc

The inverse eigenvalue problem of a graph $G$ is the problem of characterizing all lists of eigenvalues of real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of $G$. The strong spectral property is a powerful tool in this problem, which identifies matrices whose entries can be perturbed while controlling the pattern and preserving the eigenvalues. The Matrix Liberation Lemma introduced by Barrett et al.~in 2020 advances the notion to a more general setting. In this paper we revisit the Matrix Liberation Lemma and prove an equivalent statement, that reduces some of the technical difficulties in applying the result. We test our method on matrices of the form $M=A \oplus B$ and show how this new approach supplements the results that can be obtained from the strong spectral property only. While extending this notion to the direct sums of graphs, we discover a surprising connection with the zero forcing game on Cartesian products of graphs. Throughout the paper we apply our results to resolve a selection of open cases for the inverse eigenvalue problem of a graph on six vertices.

If $G$ is a graph and $\mathbf{m}$ is an ordered multiplicity list which is realizable by at least one symmetric matrix with graph $G$, what can we say about the eigenvalues of all such realizing matrices for $\mathbf{m}$? It has sometimes been tempting to expect, especially in the case that $G$ is a tree, that any spacing of the multiple eigenvalues should be realizable. In 2004, however, F. Barioli and S. Fallat produced the first counterexample: a tree on 16 vertices and an ordered multiplicity list for which every realizing set of eigenvalues obeys a nontrivial linear constraint. We extend this by giving an infinite family of trees and ordered multiplicity lists whose sets of realizing eigenvalues are very highly constrained, with at most 5 degrees of freedom, regardless of the size of the tree in this family. In particular, we give the first examples of multiplicity lists for a tree which impose nontrivial nonlinear eigenvalue constraints and produce an ordered multiplicity list which is achieved by a unique set of eigenvalues, up to shifting and scaling.