The liberation set in the inverse eigenvalue problem of a graph

Lin, Jephian C.-H. (author), Oblak, Polona (author), Šmigoc, Helena (author)

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.

• Language: English
• Keywords: symmetric matrix, inverse eigenvalue problem, strong spectral property, Matrix Liberation Lemma, zero forcing
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science ; FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2023
• Number of pages: Str. 1-28
• Numbering: Vol. 675
• PID: 20.500.12556/RUL-147499
• UDC: 512
• ISSN on article: 0024-3795
• DOI: 10.1016/j.laa.2023.06.009
• COBISS.SI-ID: 157762051
• Publication date in RUL: 06.07.2023

LIN, Jephian C.-H., OBLAK, Polona and ŠMIGOC, Helena, 2023, The liberation set in the inverse eigenvalue problem of a graph. Linear algebra and its applications [online]. 2023. Vol. 675, p. 1–28. [Accessed 11 April 2025]. DOI 10.1016/j.laa.2023.06.009. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=147499

Record is a part of a journal

• Title: Linear algebra and its applications
• Shortened title: Linear algebra appl.
• Publisher: Elsevier
• ISSN: 0024-3795
• COBISS.SI-ID: 1119247

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

• Language: Slovenian
• Keywords: simetrična matrika, inverzni problem lastnih vrednosti, krepka spektralna lastnost, ničelna prisila