Combinatorial aspects of the nonsymmetric strong spectral property for graphs

Koljančić, Sara (author), Oblak, Polona (author)

In this paper, we investigate the nonsymmetric 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 recognize several patterns that require the nSSP. It is shown that loop assignments in double paths play a critical role in establishing this property. In particular, we characterize all possible loop assignments for double paths on at most five vertices that require, allow or do not allow the nSSP, and 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.

• Language: English
• Keywords: nonsymmetric strong spectral property, nSSP, sign pattern matrices, digraphs, inverse eigenvalue problem
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: Str. 755-779
• Numbering: Vol. 42
• PID: 20.500.12556/RUL-190888
• UDC: 512.643:519.17
• ISSN on article: 1537-9582
• DOI: 10.13001/ela.2026.10523
• COBISS.SI-ID: 304180483
• Publication date in RUL: 06.11.2026

Record is a part of a journal

• Title: The electronic journal of linear algebra
• Shortened title: Electron. j. linear algebra
• Publisher: International Linear Algebra Society
• ISSN: 1537-9582
• COBISS.SI-ID: 16372313

Licences

• License: UND, Copyright Undetermined
• Link: http://rightsstatements.org/vocab/UND/1.0/
• Description: This Rights Statement should be used for Items for which the copyright status is unknown and for which the organization that has made the Item available has undertaken an (unsuccessful) effort to determine the copyright status of the underlying Work. Typically, this Rights Statement is used when the organization is missing key facts essential to making an accurate copyright status determination.

Secondary language

• Language: Slovenian
• Keywords: nesimetrična krepka spektralna lastnost, nSSP, predznačeni vzorci matrik, usmerjeni grafi, inverzni problem lastnih vrednosti