Nonpositive Eigenvalues of Hollow, Symmetric, Nonnegative Matrices

Abstract

Among hollow, symmetric $n$-by-$n$ nonnegative matrices, it is shown that any number $k$, $2\leq k\leq n-1$ of nonpositive eigenvalues is possible. However, as $n$ grows, small numbers of nonpositive eigenvalues become increasingly rare. In particular, if there is only a given finite number of distinct off-diagonal entries, the minimum number of nonpositive eigenvalues (among $n$-by-$n$ hollow, symmetric, nonnegative matrices) grows with $n$, and this remains so if just the ratio of the smallest positive off-diagonal entry to the largest is bounded away from zero. Nonetheless, every $n$-by-$n$ hollow, symmetric, nonnegative matrix with positive off-diagonal entries and with two nonpositive eigenvalues may be embedded in an $(n+1)$-by-$(n+1)$ one as a principal submatrix. This statement does not hold without the requirement of positive off-diagonal entries. Our proof recognizes some special, anti-Morishima structure of Schur complements which may be of independent interest. Relations to the independence number of a graph are also presented.