pith. sign in

arxiv: 2604.21552 · v1 · submitted 2026-04-23 · 🧮 math.CO · math.SP

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

Pith reviewed 2026-05-09 21:41 UTC · model grok-4.3

classification 🧮 math.CO math.SP
keywords non-symmetric strong spectral propertynSSPdirected graphszero-nonzero patternstridiagonal patternscombinatorial methodsspectral properties of matrices
0
0 comments X

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.

The paper links zero-nonzero matrix patterns to directed graphs and develops a combinatorial test for when those graphs require or allow the non-symmetric strong spectral property without examining individual matrices. It introduces a method that identifies requiring patterns by examining loop assignments on double paths. Applying the method yields a negative answer to an open question on irreducible tridiagonal patterns and confirms that certain digraph families achieve the conjectured minimum of 2n-1 arcs while still requiring the property.

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

Figures reproduced from arXiv: 2604.21552 by Polona Oblak, Sara Koljan\v{c}i\'c.

Figure 1
Figure 1. 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 ≥ 3, Pn,{1,n} allows the nSSP but does not require it (see Theorem 5.7). This example motivates us to propose the following alternative refinement to [1, Problem 6.5], which we will investigate in Section 5: Problem 1.6. For every positive integer n clas… view at source ↗
Figure 2
Figure 2. Figure 2: An example of a weakly but not strongly connected digraph G that allows but does not require the nSSP, and G′ that does not allow the nSSP. Example 2.6. Theorem 2.4(C) provides a family of strongly connected digraphs with possible double arcs that do not require the nSSP. For example, for m = 4, a family of supergraphs of a directed cycle is shown of [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example of a family of supergraphs of a directed cycle that does not require the nSSP; the black arcs have to be in a graph, but the blue arcs are optional. Proof. (A) Let A = (aij ) ∈ M(G) and without loss of generality assume a11 ̸= 0. Let X = (xij ) defined by X := a11I −A⊤ ∈ R n×n . Note the x11 = 0 and xii = a11 ̸= 0 for i ≥ 2. Since there are no double arcs in G, it follows that A ◦ X = O, and mat… view at source ↗
Figure 4
Figure 4. Figure 4: All graphs on four vertices satisfying (A)-(C). Using a Wolfram Mathematica code we verified that Problem 1.8 has a positive answer for n = 5 as well, and so all connected directed graphs on at most n ≤ 5 vertices and at most 2n − 2 arcs do not require the nSSP. These results together with the Example 1.7 motivate the following two questions. Problem 2.9. Is the minimum number of arcs in a strongly connect… view at source ↗
Figure 5
Figure 5. Figure 5: Sequence of G ⊂ G1 ⊂ G2 ⊂ G3 = K◦ 3 which shows that G requires the nSSP. Note that N + G [i] ∩ N + G [3]c = ∅ and N − G [3] ∩ N − G [i] c = {1} for i ∈ [2], and so by Lemma 3.1(B), it follows that X ∈ M(Gc 1 ), where G1 = G+{(1, 1),(1, 2)}. Equivalently, x11 = x12 = 0. Similarly N + G [1] ∩ N + G1 [2]c = {3} and N − G [2] ∩ N − G1 [1]c = ∅, therefore X ∈ M(Gc 2 ), where G2 = G1 + {(2, 3)} by the same Lemm… view at source ↗
Figure 6
Figure 6. Figure 6: Supergraphs G1 and G2 of the lollipop digraph G = L5,6,[8] from the proof of Corollary 4.2. In black, the double lollipop digraph L5,6,[8] shown, and all undirected edges represent double arcs. and N − G [p+ 3−i]∩N − Gi [j] c = {p+ 2−i} for all j > p+ 1. By Lemma 3.1 and Remark 3.2 it follows that xp+2−i,j = xj,p+2−i = 0, and so X ∈ M(Gc i+1). Now, inductively we have X ∈ M(Gc p+2). Since Gp+2 = K◦ n , it … view at source ↗
Figure 7
Figure 7. Figure 7: Five examples of digraphs from [5] on at most four vertices, all requiring the nSSP. We start with a technical lemma that shows that the commuting condition [A, X ⊤] = O on some tridiagonal matrices A force many entries in matrix X of the complementary pattern to be zero. Lemma 5.2. Let m, n ∈ N with m < n, and let G := Pn,L, [m] ⊆ L and m + 1 ∈ L/ . If A ∈ M(G), X = (xij ) ∈ M(Gc ) and [A, X⊤] = 0, then x… view at source ↗
Figure 8
Figure 8. Figure 8: Sequence P5,{1,2,4} ⊂ G1 ⊂ G2 ⊂ . . . ⊂ G8 = K◦ 5 which shows that P5,{1,2,4} requires the nSSP. Every undirected edge represents a double arc and Gℓ+1 = Gℓ+{{j, k}}, where the double arc {j, k} is coloured green. [2] 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… view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

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)
  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)
  1. [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.
  2. [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

1 responses · 0 unresolved

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
  1. 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

0 steps flagged

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

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available, so the ledger is necessarily incomplete. The work appears to rest on standard definitions of zero-nonzero patterns, directed graphs, and the nSSP itself without introducing new free parameters or invented entities.

axioms (2)
  • domain assumption Standard correspondence between zero-nonzero matrix patterns and directed graphs.
    Used throughout to translate matrix questions into graph questions.
  • domain assumption Existence of matrix realizations for given patterns.
    Implicit when claiming that a pattern requires or allows the nSSP.

pith-pipeline@v0.9.0 · 5428 in / 1352 out tokens · 27550 ms · 2026-05-09T21:41:01.282413+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [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...

  2. [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

  3. [3]

    Berliner, M

    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

  4. [4]

    Breen, C

    J. Breen, C. Brouwer, M. Catral, M. Cavers, P. van den Driessche, and K. N. Vander Meulen. Minimum number of distinct eigenvalues allowed by a sign pattern.Linear Algebra Appl., 654:311– 338, 2022

  5. [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

  6. [6]

    Cavers and K.N

    M. Cavers and K.N. Vander Meulen. Nonzero matrix patterns that require distinct eigenvalues. Linear Algebra and its Applications, 742:66–76, 2026

  7. [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. [8]

    Chu and Gene H

    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

  9. [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

  10. [10]

    Shader, and Kevin N

    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

  11. [11]

    Curtis and Bryan L

    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

  12. [12]

    On an inverse tridiagonal eigenvalue problem and its application to synchronization of network motion.arXiv preprint arXiv:2408.01066, 2024

    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. [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

  14. [14]

    Fallat, H

    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}  ...

  15. [15]

    Lin, and Bryan L

    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

  16. [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

  17. [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...