Combinatorial aspects of the non-symmetric strong spectral property for graphs
Pith reviewed 2026-05-09 21:41 UTC · model grok-4.3
The pith
A combinatorial method using directed graphs shows that some irreducible tridiagonal patterns do not require the non-symmetric strong spectral property.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors show that loop assignments in double paths determine whether a directed graph requires the nSSP, that this criterion gives a negative answer to the question of whether every irreducible tridiagonal pattern requires the nSSP, and that the lower bound of 2n-1 arcs for requiring the nSSP holds for several explicit families of digraphs on n vertices.
What carries the argument
The combinatorial recognition method that decides nSSP requirement by checking loop assignments on double paths in the directed graph associated to a zero-nonzero pattern.
Load-bearing premise
The newly introduced combinatorial method correctly identifies every pattern that requires or allows the nSSP without missing a matrix realization that satisfies the pattern yet violates the property.
What would settle it
A concrete matrix realization of an irreducible tridiagonal pattern whose eigenvalues fail to satisfy the nSSP condition would confirm the negative answer; conversely, proving that every such pattern admits only matrices with the nSSP would refute it.
Figures
read the original 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$ vertices that requires the nSSP, is equal to $2n-1$, and confirm this minimum for several specific digraph families.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper associates directed graphs to zero-nonzero matrix patterns and develops a combinatorial method, centered on loop assignments along double paths, to determine when a pattern requires or allows the non-symmetric strong spectral property (nSSP). It applies the method to resolve an open question by showing that certain irreducible tridiagonal patterns do not require the nSSP, and it confirms that 2n-1 is the minimum number of arcs for several families of digraphs on n vertices that require the nSSP.
Significance. If the combinatorial criteria are both sufficient and necessary, the framework supplies a useful tool for classifying patterns without per-matrix verification, which would be a clear advance in combinatorial matrix theory. The negative answer to the tridiagonal question and the explicit confirmations for concrete families are concrete contributions; the paper also supplies explicit constructions and examples that can be checked independently.
major comments (1)
- [combinatorial method section and tridiagonal application] The negative answer for irreducible tridiagonal patterns and the 2n-1 arc-minimum claims both rest on the new combinatorial method being exhaustive (i.e., that every matrix realizing a flagged pattern must satisfy nSSP). The manuscript does not appear to contain an explicit argument or exhaustive search showing that the loop-assignment conditions on double paths are necessary rather than merely sufficient; a counterexample matrix realizing a pattern classified as requiring nSSP but failing the spectral property would invalidate both results. This is load-bearing for the central claims (see the section defining the combinatorial recognition procedure and its application to tridiagonal patterns).
minor comments (2)
- [preliminaries] Notation for the directed graphs associated to patterns is introduced without a consolidated table of symbols; a small table listing the correspondence between arcs/loops and nonzero entries would improve readability.
- [figures in the method section] Several figures illustrating double-path loop assignments are referenced but their captions do not explicitly state which combinatorial condition each figure demonstrates; adding one sentence per caption would help.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for identifying this important point about the scope of the combinatorial method. We address the concern directly below and will revise the paper to strengthen the presentation of the results.
read point-by-point responses
-
Referee: [combinatorial method section and tridiagonal application] The negative answer for irreducible tridiagonal patterns and the 2n-1 arc-minimum claims both rest on the new combinatorial method being exhaustive (i.e., that every matrix realizing a flagged pattern must satisfy nSSP). The manuscript does not appear to contain an explicit argument or exhaustive search showing that the loop-assignment conditions on double paths are necessary rather than merely sufficient; a counterexample matrix realizing a pattern classified as requiring nSSP but failing the spectral property would invalidate both results. This is load-bearing for the central claims (see the section defining the combinatorial recognition procedure and its application to tridiagonal patterns).
Authors: We agree that the manuscript would benefit from greater clarity on this point. The combinatorial method, based on loop assignments along double paths, is presented as a sufficient condition for a zero-nonzero pattern to require the nSSP. This sufficiency is used to identify families of digraphs that require the nSSP and to confirm the 2n-1 arc minimum for several concrete families where the condition holds. For the negative result on irreducible tridiagonal patterns, the manuscript resolves the open question by exhibiting explicit matrix realizations (with the required zero-nonzero pattern) that fail to satisfy the nSSP; these constructions are independent of the loop-assignment criterion and directly establish that the patterns do not require the property. In the revised version we will (i) add a dedicated paragraph in the combinatorial method section explicitly stating that the loop-assignment conditions are sufficient but not claimed to be necessary, (ii) expand the tridiagonal section to include the explicit counterexample matrices and verify that they lie outside the sufficient condition, and (iii) clarify the minimality arguments by separating the sufficient-condition cases from the direct verifications for smaller arc counts. These changes will make the logical structure fully transparent and remove any ambiguity about exhaustiveness. revision: yes
Circularity Check
New combinatorial method for nSSP is independent of its inputs; no reduction to self-definition or fitted predictions.
full rationale
The paper associates zero-nonzero patterns with directed graphs and introduces explicit combinatorial criteria (loop assignments on double paths and related structures) to determine when a pattern requires the nSSP. These criteria are applied to give a negative answer to an open question on irreducible tridiagonal patterns and to confirm the 2n-1 arc minimum for several digraph families. The derivation relies on standard pattern-digraph associations plus new structural arguments rather than any self-definitional loop, parameter fit renamed as prediction, or load-bearing self-citation chain. The framework is presented as a sufficient test that avoids per-matrix verification, but the central claims remain non-circular because they rest on direct combinatorial reasoning rather than re-expressing the inputs.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Standard correspondence between zero-nonzero matrix patterns and directed graphs.
- domain assumption Existence of matrix realizations for given patterns.
Reference graph
Works this paper leans on
-
[1]
Hall, Hein van der Holst, Zhongshan Li, Aram Mathivanan, Jiamin Pan, Hanfei Xu, and Zheng Yang
Marina Arav, Frank J. Hall, Hein van der Holst, Zhongshan Li, Aram Mathivanan, Jiamin Pan, Hanfei Xu, and Zheng Yang. Advances on similarity via transversal intersection of manifolds.Linear Algebra Appl., 688:1–20, 2024. 22 1 2 3 4 5 G0 =P 5,{1,2,4} (2,1,3) 1 2 3 4 5 G1 (3,1,4) 1 2 3 4 5 G2 (3,5,2) 1 2 3 4 5 G3 (1,5,1) 1 2 3 4 5 G4 (1,4,2) 1 2 3 4 5 G5 (2...
work page 2024
-
[2]
Tracy Hall, Leslie Hogben, Jephian C.-H
Wayne Barrett, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, and Bryan L. Shader. Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph.Electron. J. Combin., 24(2):Paper No. 2.40, 28, 2017
work page 2017
-
[3]
A.H. Berliner, M. Catral, M. Cavers, S. Kim, and P. van den Driessche. Refined inertia sets for structured sign patterns.Linear Algebra and its Applications, 2026
work page 2026
- [4]
-
[5]
Brouwer, Minerva Catral, Michael Cavers, Pauline van den Driessche, and Kevin N
Jane Breen, Carraugh C. Brouwer, Minerva Catral, Michael Cavers, Pauline van den Driessche, and Kevin N. Vander Meulen. The allow sequence of distinct eigenvalues for a sign pattern.Electron. J. Linear Algebra, 40:48–80, 2024
work page 2024
-
[6]
M. Cavers and K.N. Vander Meulen. Nonzero matrix patterns that require distinct eigenvalues. Linear Algebra and its Applications, 742:66–76, 2026
work page 2026
-
[7]
The strong singular value property for matrices.arXiv preprint arXiv:2507.08313, 2025
Caleb Cheung and Bryan Shader. The strong singular value property for matrices.arXiv preprint arXiv:2507.08313, 2025
-
[8]
Moody T. Chu and Gene H. Golub.Inverse eigenvalue problems: theory, algorithms, and appli- cations. Numerical Mathematics and Scientific Computation. Oxford University Press, New York, 2005
work page 2005
-
[9]
On a new graph invariant and a criterion for planarity
Yves Colin de Verdi` ere. On a new graph invariant and a criterion for planarity. InGraph structure theory (Seattle, WA, 1991), volume 147 ofContemp. Math., pages 137–147. Amer. Math. Soc., Providence, RI, 1993
work page 1991
-
[10]
Bryan Curtis, Colin Garnett, Bryan L. Shader, and Kevin N. Vander Meulen. The non-symmetric strong multiplicity property for sign patterns.Electron. J. Linear Algebra, 41:153–165, 2025
work page 2025
-
[11]
Bryan A. Curtis and Bryan L. Shader. Sign patterns of orthogonal matrices and the strong inner product property.Linear Algebra Appl., 592:228–259, 2020
work page 2020
-
[12]
Luca Dieci, Cinzia Elia, and Alessandro Pugliese. On an inverse tridiagonal eigenvalue problem and its application to synchronization of network motion.arXiv preprint arXiv:2408.01066, 2024
-
[13]
On some structured inverse eigenvalue problems.Numer
Robert Erra and Bernard Philippe. On some structured inverse eigenvalue problems.Numer. Algo- rithms, 15(1):15–35, 1997
work page 1997
-
[14]
Shaun M. Fallat, H. Tracy Hall, Jephian C.-H. Lin, and Bryan L. Shader. The bifurcation lemma for strong properties in the inverse eigenvalue problem of a graph.Linear Algebra Appl., 648:70–87, 2022. 23 L A X {1,4} 1 2 0 0 0 1 0 2 0 0 0 4 0 2 0 0 0−1−1 2 0 0 0 1 0 0 0 2 1 1 0 4 0−2 0 2 0 2 0−1 −2 2 0 0 0 −4 0 4 0 2 {2,3} ...
work page 2022
-
[15]
Leslie Hogben, Jephian C.-H. Lin, and Bryan L. Shader.Inverse problems and zero forcing for graphs, volume 270 ofMathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2022
work page 2022
-
[16]
Lin, Polona Oblak, and Helena ˇSmigoc
Jephian C.-H. Lin, Polona Oblak, and Helena ˇSmigoc. The strong spectral property for graphs. Linear Algebra Appl., 598:68–91, 2020
work page 2020
-
[17]
Vander Meulen, and Adam Van Tuyl
Abhilash Saha, Leona Tilis, Kevin N. Vander Meulen, and Adam Van Tuyl. Sign patterns which require or allow the strong multiplicity property.arXiv preprint arXiv:2505.08967, 2025. (S. Koljanˇ ci´ c)F aculty of Natural Sciences and Mathematics, University of Banja Luka, Bosnia and Herzegovina Email address:sara.jevdjenic@pmf.unibl.org (P. Oblak)F aculty of...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.