Combinatorial aspects of the non-symmetric strong spectral property for graphs

Sara Koljančić, Polona Oblak · 2026

Read Combinatorial aspects of the non-symmetric strong spectral property for graphs by Sara Koljančić, Polona Oblak (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21552.txt.

Introduction

Sara Koljančić and Polona Oblak study the non-symmetric Strong Spectral Property, linking digraphs with zero-nonzero matrix patterns and asking when they require or allow it, avoiding per-matrix checks. A new combinatorial method spots several patterns requiring the property. Loop assignments in double paths matter, and an open question on irreducible tridiagonal patterns gets a negative answer. They ask whether the minimum arc count in a directed graph on n vertices requiring it equals twice n minus one, confirming it for several families.

Catalog record

CREATORSara Koljančić, Polona Oblak
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71881
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2604.21552

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Combinatorial aspects of the non-symmetric strong spectral property for graphs Thanks: Both authors acknowledge the financial support from the bilateral projects no. BI-BA/24-25-024, BI-BA/26-27-007 and BI-BA/26-27-008 funded by Slovenian Research Agency and Ministry of Civil Affairs, Bosnia and Herzegovina. Polona Oblak has also received funding from Slovenian Research Agency, research core funding no. P1-0222. Sara Koljančić, Polona Oblak Abstract . In this paper, we investigate the non-symmetric Strong Spectral Property (nSSP) from a combinatorial perspective. To zero–nonzero patterns of matrices we associate directed graphs and study when they require or allow the nSSP, providing a framework that avoids verifying the nSSP for individual matrices. A new combinatorial method is introduced and used to recognise several patterns that require the nSSP. It is shown that loop assignments in double paths play a critical role in establishing this property, and we show that an open question regarding irreducible tridiagonal patterns has a negative answer. We also investigate whether the minimum number of arcs in a directed graph on n n vertices that requires the nSSP, is equal to 2 ​ n − 1 2n-1 , and confirm this minimum for several specific digraph families. Keywords: Non-symmetric strong spectral property (nSSP), Sign pattern matrices, Digraphs, Inverse eigenvalue problem. AMS subject classifications: 05C50, 05C38, 15B35, 15A29 1. Introduction The Inverse Eigenvalue Problems (IEP) are central questions in spectral theory, concerned with determining matrices of a specific structure that realise a prescribed set of eigenvalues. The continuing difficulty of these problems has sustained a large and active research community, driven by multidisciplinary applications, [ 8 ] . In the last decade, the Strong Properties of matrices, which rely on the transversal intersection of manifolds and the Implicit Function Theorem, have proven to be a powerful tool for the symmetric inverse eigenvalue problem, and have significantly advanced the solutions for the IEP for graphs, [ 2 , 9 , 15 ] . Recently, their non-symmetric versions were introduced, see e.g. [ 1 , 7 , 10 , 11 , 14 , 17 ] . In this work we investigate the non-symmetric Strong Spectral Property (nSSP) of matrices, firstly introduced in [ 14 ] . Definition 1.1 ( [ 14 ] ) . A matrix A\in\mathbb{R}^{n\times n} has the non-symmetric Strong Spectral Property (nSSP) provided X=O is the only matrix such that A\circ X=[A,X^{\top}]=O. The authors in [ 14 ] developed the non-symmetric Superpattern Lemma, which shows the strength of an existence of a matrix with a desired spectrum and having the nSSP. Lemma 1.2 (Superpattern Lemma, [ 14 ] ) . If an n\times n real matrix A of pattern P has the nSSP, then for every superpattern P^{\prime} of P there exists a matrix A^{\prime} of pattern P^{\prime} with the nSSP, which is similar to A . Existing literature concerning the IEP for non-symmetric matrices has predominantly concentrated on tridiagonal patterns, see e.g., [ 12 , 13 ] . However, Superpattern Lemma together with the Bifurcation Lemma (see [ 14 , Theorem 5.3] ) enable researchers to advance the studies in several subproblems of the IEP , [ 1 , 3 , 4 , 5 , 6 ] . It is difficult to resolve the existence of a matrix with the nSSP and with a desired spectrum. We follow [ 16 ] and give a combinatorial description of non-symmetric patterns for which every matrix has the nSSP. Such pattern proved to be useful in IEP, since we do not have to verify if a matrix A in the Superpattern Lemma has the nSSP. In particular, it says that all spectra achieved by pattern P , in which every matrix has the nSSP, can be also realised in every superpattern of P . In this paper, the zero–nonzero patterns will be presented by directed graphs with loops. For A=(a_{ij})\in{\mathbb{R}}^{n\times n} we denote by {\mathcal{D}}(A) the directed graph G=(V(G),E(G)) , for which V(G)=[n] and a_{ij}\neq 0 if and only if (i,j)\in E(G) . For the fundamental definitions and properties of these digraphs, the reader is referred to Subsection 1.3 . For a directed graph G with n vertices, let {\mathcal{M}}(G) be the set of all n\times n real matrices A with {\mathcal{D}}(A)=G . Definition 1.3 . If every matrix A\in{\mathcal{M}}(G) has the nSSP, then we say that G requires the nSSP , and if there is a matrix A\in{\mathcal{M}}(G) with the nSSP, then G allows the nSSP . A similar notion was introduced in [ 10 ] , where the authors define the nSMP and investigate digraphs and sign patterns that require the nSMP. It was proved in [ 17 ] that a pattern allows the nSMP if and only if it allows distinct eigenvalues. Some additional work on the number of distinct eigenvalues of a pattern has also been carried out in [ 4 , 5 , 10 , 17 ] . Note that any digraph requiring the nSSP necessarily requires the nSMP. Consequently, several results established herein for the nSSP hold in the context of the nSMP as well. In [ 1 ] the authors showed that nSSP is equivalent to Similarity-Transversality Property (STP), which relies on the rank of the Jacobian matrix of the commutator [A,X] . The authors present several zero–nonzero patterns and several sign patterns that require the nSSP. Also, the authors observe that the loop assignment plays a crucial role in a digraph requiring/allowing the nSSP. Lemma 1.4 . Let G be a directed graph. (A) [ 1 , Observation 3.4] If G has no loops, then G does not allow the nSSP. (B) [ 1 , Proposition 5.4] If all vertices of G have loops, then G allows the nSSP. In our work, we examine more closely how the assignment of the loops influences whether a digraph possesses the nSSP. Our work is motivated by two of their open questions. We present them in the next two subsections and give an overview of our work. 1.1. Irreducible tridiagonal patterns In [ 1 , Problem 6.5] , the authors ask whether every irreducible tridiagonal zero–nonzero pattern with at least one nonzero diagonal entry requires the STP. Note that for an irreducible tridiagonal matrix A its directed graph {\mathcal{D}}(A) is a strongly connected directed graph, whose underlying simple graph is a path. We call it a double path, and we label vertices of the double path in its natural labeling as following. Definition 1.5 . A digraph P_{n,{\mathcal{L}}} is called a double path with loop assignment {\mathcal{L}}\subseteq[n] if V(P_{n,{\mathcal{L}}})=[n] and E(P_{n,{\mathcal{L}}})=\{(i,i+1),(i+1,i),(\ell,\ell)\colon i\in[n-1],\ell\in{\mathcal{L}}\}. Note that a matrix A=(a_{ij})\in{\mathcal{M}}(P_{n,{\mathcal{L}}}) has a_{ij}\neq 0 if and only if i=j and i\in{\mathcal{L}} or |i-j|=1 . This means A is an irreducible tridiagonal matrix with nonzero diagonal entries in the position of {\mathcal{L}} . It is straightforward to check that matrices A=\begin{pmatrix}a&b&0\\ c&0&c\\ 0&b&a\end{pmatrix}\quad\text{and }\quad X=\begin{pmatrix}0&0&1\\ 0&1&0\\ 1&0&0\end{pmatrix} satisfy A\circ X=[A,X^{\top}]=O . So, the digraph {\mathcal{D}}(A)=P_{3,\{1,3\}} shown on Figure 1 , does not require the nSSP, and hence the answer to [ 1 , Problem 6.5] is negative. P_{3,\{1,3\}} Figure 1. Example of a directed graph which does not require but allows the nSSP, see also Theorem 5.5 together with Lemma 1.2 . In this paper we show that for any n\geq 3 , P_{n,\{1,n\}} allows the nSSP

Read the complete text