A characterization of sets realizable by compensation in the SNIEP

Abstract

The symmetric nonnegative inverse eigenvalue problem (SNIEP) is the problem of characterizing all possible spectra of entry-wise nonnegative symmetric matrices of given dimension. A list of real numbers is said to be symmetrically realizable if it is the spectrum of some nonnegative symmetric matrix. One of the most general sufficient conditions for realizability is the so-called C-realizability, which amounts to some kind of compensation between the positive and negative entries of the list of real numbers whose realizability one is trying to decide. A combinatorial characterization of C-realizable lists with zero trace was given in [11]. In this paper we make use of a recursive method for constructing simmetrically realizable lists due to Ellard and Šmigoc [3] to extend this combinatorial characterization of C-realizability to general lists with nonnegative trace. One consequence of this characterization is that the set of nonnegative C-realizable lists is a union of polyhedral cones whose faces are described by equations involving only linear combinations with coefficients 1 and −1 of the entries in the list. Another remarkable consequence is the monotonicity of C-realizability, i.e., the operation of increasing any positive entry of a C-realizable list preserves C-realizability.