Suleĭmanova Spectra & Realization Theorems

In the vast landscape of the Nonnegative Inverse Eigenvalue Problem, the most famous and completely understood family of spectra consists of real multisets possessing exactly one positive eigenvalue (the Perron root), with all other eigenvalues being non-positive (zero or negative).

Why is this condition so remarkable? For general candidate spectra, ensuring nonnegativity requires satisfying infinitely many non-linear power-sum inequalities ($s_k = \operatorname{Tr}(A^k) \ge 0$), Newton-Girard relations, and Johnson-Loewy-London constraints. However, when all secondary eigenvalues are non-positive:

• Even powers ($k = 2m$): Every term $\lambda_i^{2m} \ge 0$, so the power sum $s_{2m} = \sum_{i=0}^{n-1} \lambda_i^{2m} > 0$ is trivially and automatically positive.
• Odd powers ($k = 2m+1$): Because $\lambda_0 \ge |\lambda_j|$ for all $j$, we have $\lambda_0^{2m+1} \ge \sum_{j=1}^{n-1} |\lambda_j|^{2m+1}$ whenever $\lambda_0 \ge \sum_{j=1}^{n-1} |\lambda_j|$. Hence all odd power sums $s_{2m+1} \ge 0$ are automatically satisfied!

Thus, every higher-order trace obstruction vanishes. The linear condition $\operatorname{Tr}(A) = s_1 \ge 0$ is the sole necessary obstacle.

In 1949, H. R. Suleĭmanova published a note in Doklady Akademii Nauk SSSR stating that the condition $\sum_{i=0}^{n-1} \lambda_i \ge 0$ is not only necessary, but also sufficient for the existence of an entrywise nonnegative matrix realizing $\sigma$. However, her published paper lacked complete proofs for several inductive steps.

In 1953, the British mathematician Hazel Perfect provided the first completely rigorous, constructive proof in the Duke Mathematical Journal. Perfect's approach was based on companion matrices:

Perfect's construction proved that every Suleĭmanova spectrum belongs to the realizable set $\mathcal{RNIEP}$. However, the resulting matrix $A$ was generally asymmetric.

For more than two decades, it remained an open question whether a Suleĭmanova spectrum could always be realized by a symmetric nonnegative matrix ($A = A^T \ge 0$).

In 1974, the legendary Czech mathematician Miroslav Fiedler resolved this question definitively in Linear Algebra and its Applications, proving one of the landmark theorems of combinatorial matrix theory.

Fiedler's inductive construction builds a sequence of symmetric matrices $A_1, A_2, \dots, A_n = A$ where at step $k$:

By carefully selecting the coupling vector $\mathbf{v}_k \ge 0$ and the diagonal entry $\alpha_k \ge 0$, Fiedler showed that the eigenvalues of $A_k$ interlace precisely with those of $A_{k-1}$, placing $\lambda_k \le 0$ into the spectrum without perturbing previous eigenvalues.

Fiedler's theorem established that there is no symmetry gap for Suleĭmanova spectra:

In 1983, George W. Soules discovered a magnificent geometric perspective: rather than constructing a custom matrix for each individual spectrum, one can find a single fixed orthogonal matrix $R \in \mathrm{O}(n)$ that diagonalizes all Suleĭmanova matrices simultaneously.

In 1998, Ludwig Elsner, Reinhard Nabben, and Michael Neumann published a complete constructive characterization of all Soules bases via binary tree sign patterns. They proved that:

The cone of Suleĭmanova spectra forms an extremal simplicial cone within the trace polytope of symmetric nonnegative matrices. Every Soules matrix acts as a universal geometric embedding of this cone into the positive semidefinite affine cone of matrices.

Since Suleĭmanova's theorem is an exact necessary and sufficient condition, mathematicians have pushed to extend its philosophy to broader spectral configurations:

Our research hub includes the Spectra Realizer, an in-browser computational engine capable of instantly synthesizing both asymmetric companion realizations and symmetric Fiedler/Soules nonnegative matrices for any candidate Suleĭmanova spectrum.