Combinatorial aspects of the nonsymmetric strong spectral property for graphs

Abstract

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.