Core Formulation & Mathematical Background

1. Core Formulation & Mathematical Setup

The precise mathematical statement of spectral nonnegativity and polynomial realization.

The Nonnegative Inverse Eigenvalue Problem (NIEP) is one of the classic, long-standing open problems in combinatorial matrix theory and linear algebra. Posed implicitly in the early twentieth century alongside the genesis of Perron-Frobenius theory and formalized extensively in the 1930s–1940s, the problem asks which multisets of complex numbers can arise as the spectrum of an entrywise nonnegative matrix.

Definition: The NIEP

Problem Statement

Let $\sigma = \{\lambda_1, \lambda_2, \dots, \lambda_n\}$ be a multiset of $n$ complex numbers. The NIEP asks: does there exist an $n \times n$ matrix $A = (a_{ij}) \in \mathbb{R}^{n \times n}$ satisfying:

$$\begin{aligned} a_{ij} &\ge 0 \quad \text{for all } 1 \le i, j \le n \\[4pt] \det(\lambda I - A) &= \prod_{i=1}^n (\lambda - \lambda_i) \end{aligned}$$

When such an $A$ exists, the multiset $\sigma$ is said to be realizable, and the matrix $A$ is a nonnegative realization of $\sigma$.

A notable generalization is the Nonzero Spectrum NIEP (often termed spectral padding). Here, rather than demanding an exact matrix of order $n$, one asks whether $\sigma$ can be realized as the set of nonzero eigenvalues of an $N \times N$ nonnegative matrix $B \ge 0$ of order $N \ge n$, with $N - n$ additional zero eigenvalues:

$$\sigma(B) = \sigma \cup \{\underbrace{0, 0, \dots, 0}_{N - n \text{ zeros}}\}$$

While spectral padding frequently simplifies realization constructions (e.g. via borderings and companion matrices), the exact-dimension problem where $N = n$ is significantly more constrained and mathematically rigid.

2. Perron-Frobenius Foundations

Universal geometric and spectral structures governing nonnegative linear operators.

Any study of spectral nonnegativity begins with the celebrated theorems of Oskar Perron (1907) for strictly positive matrices and their profound generalization to nonnegative matrices by Georg Frobenius (1912).

Theorem: Perron-Frobenius Spectral Invariants

Classical Milestone

Let $A \ge 0$ be an $n \times n$ nonnegative matrix. Then:

Perron Root: The spectral radius $\rho(A) = \max_{\lambda \in \sigma(A)} |\lambda|$ is itself an eigenvalue of $A$. That is, $\rho(A) \in \sigma(A)$.
Nonnegative Eigenvector: There exists a nonzero vector $v \ge 0$ such that $Av = \rho(A)v$.
Irreducibility & Primitivity: If $A$ is irreducible (its associated directed graph is strongly connected), then $\rho(A) > 0$ is an algebraically simple eigenvalue with a strictly positive eigenvector $v > 0$.
Cyclic Peripheral Spectrum: If $A$ is irreducible with $h$ peripheral eigenvalues on the circle $|z| = \rho(A)$, then these eigenvalues are exactly the $h$ equally spaced roots of unity scaled by $\rho(A)$:
$$\lambda_k = \rho(A) \exp\left(\frac{2\pi i k}{h}\right), \quad k = 0, 1, \dots, h-1$$

Frobenius's cyclic structure implies that peripheral eigenvalues cannot be arbitrary points on the boundary circle $|z| = \rho(A)$; they must possess strict rotational symmetry. This fundamental constraint was later extended to its geometric culmination by Karpelevič.

3. Necessary Conditions & Trace Inequalities

Algebraic invariants and moments that every realizable spectrum must obey.

Because entrywise nonnegative matrices $A \ge 0$ have real entries, their characteristic polynomials $p_A(\lambda) \in \mathbb{R}[\lambda]$ have real coefficients. Furthermore, because matrix multiplication preserves entrywise nonnegativity ($A^k \ge 0$ for all $k \in \mathbb{N}$), every power of $A$ has nonnegative diagonal entries, and therefore nonnegative trace.

Universal Necessary Conditions

Spectral Invariants

1

Reality Symmetry

$$\sigma = \bar{\sigma}$$

Non-real eigenvalues must occur in conjugate pairs with equal multiplicities.

2

Perron Dominance

$$\rho = \max_{i} |\lambda_i| \in \sigma$$

The maximum absolute value in $\sigma$ must be a member of $\sigma$.

3

Trace Nonnegativity

$$s_k = \sum_{i=1}^n \lambda_i^k \ge 0 \quad (\forall k \ge 1)$$

All power sum traces $s_k = \operatorname{tr}(A^k) = \sum a_{ii}^{(k)} \ge 0$.

4

Loewy-London Inequalities

$$s_k^m \le n^{m-1} s_{km} \quad (\forall k, m \ge 1)$$

Moments derived from applying Hölder's inequality to the matrix diagonals.

In 1978/1979, Raphael Loewy and David London established condition (4) using entrywise Cauchy-Schwarz and Hölder inequalities. A notable special case is $k=1, m=2$:

$$s_1^2 \le n s_2 \iff \left(\sum_{i=1}^n \lambda_i\right)^2 \le n \sum_{i=1}^n \lambda_i^2$$

In 1996, Charles R. Johnson, Thomas J. Laffey, and Raphael Loewy refined these conditions into the Johnson-Loewy-London (JLL) inequalities:

$$n^{m-1} s_{km} \ge s_k^m + \frac{n^{m-1} - 1}{n - 1} (\rho^k - \lambda_j^k)^m$$

The Insufficiency of Trace Conditions ($n \ge 5$)

Non-Sufficiency Frontier

While trace nonnegativity and Loewy-London conditions completely solve the problem for $n \le 3$ (and with additional refinements for $n = 4$), Laffey and Meehan showed that for $n = 5$, there exist spectra satisfying all Loewy-London, JLL, and trace inequalities that cannot be realized by any $5 \times 5$ nonnegative matrix! A celebrated example is:

$$\sigma = \{3+t, 3-t, -2, -2, -2\} \quad \text{for specific intervals } t \in (0, 1)$$

This failure of trace sufficiency at $n = 5$ demonstrates that realization requires deeper geometric and algebraic compatibility beyond moment power sums.

4. Subproblems & The Real vs. Symmetric Divide

Distinguishing Symmetric, Real, and Stochastic realization classes.

To isolate specific algebraic and structural difficulties, researchers study several prominent subproblems:

Core NIEP

The NIEP →

Dimensional solvability ($n=1$ to $n \ge 5$), necessary moments, trace non-sufficiency, and semi-algebraic complexity.

SNIEP

Symmetric NIEP →

Requires $A = A^T$. Since symmetric real matrices are orthogonally diagonalizable, every eigenvalue is guaranteed to be real ($\sigma \subset \mathbb{R}$).

RNIEP

Real NIEP →

Requires $A \ge 0$ with $\sigma \subset \mathbb{R}$, but does not enforce symmetry. Eigenvectors need not be orthogonal.

Karpelevič

Karpelevič Region $\mathcal{K}_n$ →

The exact set of all individual complex numbers $z \in \mathbb{C}$ that can belong to the spectrum of some $n \times n$ stochastic matrix.

Suleimanova

Suleĭmanova Spectra →

Real spectra with exactly one positive eigenvalue $\lambda_0 > 0 \ge \lambda_1 \dots$, where the trace condition $s_1 \ge 0$ is necessary and sufficient.

Dynamics

Boyle-Handelman Theorem →

Symbolic dynamics, shifts of finite type, and nonnegative realization when auxiliary zero eigenvalues are permitted.

Similarities

Perron Similarities →

Non-orthogonal similarity transformations that preserve nonnegative cone geometry and resolve the RNIEP vs SNIEP gap.

The Divide: RNIEP $\neq$ SNIEP for $n \ge 5$

Johnson-Laffey-Loewy (1996)

For decades, it was conjectured that if a real spectrum $\sigma \subset \mathbb{R}$ is realizable by some nonnegative matrix, it might always be realizable by a symmetric nonnegative matrix. In dimensions $n \le 4$, this holds true:

$$\operatorname{RNIEP}(n) = \operatorname{SNIEP}(n) \quad \text{for } n \le 4$$

However, in 1996, Charles Johnson, Thomas Laffey, and Raphael Loewy proved the surprising result that this equivalence breaks down at order 5:

$$\operatorname{SNIEP}(n) \subsetneq \operatorname{RNIEP}(n) \quad \text{for all } n \ge 5$$

Specifically, the spectrum $\sigma = \{4, 2, 2, -4, -4\}$ is realizable by a $5 \times 5$ nonnegative matrix, but cannot be realized by any symmetric $5 \times 5$ nonnegative matrix! Non-symmetric realizations possess extra degrees of freedom via non-orthogonal eigenvector geometries that can accommodate spectra where symmetric matrices fail.

5. Solvability by Dimension ($n = 1$ to $n \ge 5$)

The chronological progression of complete mathematical characterizations.

The difficulty of the NIEP escalates dramatically with dimension $n$. Below is the current state of knowledge across matrix dimensions:

n = 1, 2 Solved

Elementary Realization

For $n=1$, $\lambda_1 \ge 0$. For $n=2$, $\sigma = \{\lambda_1, \lambda_2\}$ is realizable if and only if $\lambda_1 \ge 0$ (Perron root) and $\lambda_1 + \lambda_2 \ge 0$ with $\lambda_1, \lambda_2 \in \mathbb{R}$ or $\lambda_2 = \bar{\lambda}_1$.

n = 3 Solved (1978)

Loewy & London Theorem

A multiset $\sigma = \{\lambda_1, \lambda_2, \lambda_3\}$ is realizable if and only if $\sigma = \bar{\sigma}$, $\rho = \max |\lambda_i| \in \sigma$, and the first two traces are nonnegative: $s_1 \ge 0$ and $s_2 \ge 0$.

n = 4 Solved (2007)

Meehan & Torre-Mayo et al.

Real spectra solved by Meehan (1998); general complex spectra completely characterized by Torre-Mayo et al. (2007) through a system of trace and coefficient polynomial inequalities.

n ≥ 5 Open Frontier

General Dimensions

No closed constructive or semi-analytic characterization is known. Trace inequalities are insufficient, and algebraic boundary polynomials grow exponentially in degree.

6. Modern Frontiers: Real Algebraic Geometry & Preserving Cones

Novel mathematical perspectives connecting polynomial preservation, real algebraic sets, and polytope geometry.

Recent research into the NIEP has shifted toward modern geometric and algebraic paradigms that transcend traditional matrix perturbational methods.

Semi-Algebraic Solvability of the NIEP

Clark (arXiv:2407.14472, 2024)

In 2024, Benjamin J. Clark applied foundational tools from real algebraic geometry to establish the structural solvability of the inverse eigenvalue problem:

$$\sigma \text{ is realizable} \iff (\sigma = \bar{\sigma}) \;\wedge\; \Phi(\lambda_1, \dots, \lambda_n) \ge 0$$

where $\Phi$ is a finite Boolean combination (unions and intersections) of polynomial inequalities in the spectrum entries. By reformulating the realization problem as the projection of the semialgebraic set of nonnegative matrices $(A \ge 0, \det(\lambda I - A) = p(\lambda))$ via the Tarski-Seidenberg theorem, it is proven that the NIEP, SNIEP, and RNIEP are semi-algebraic sets and are therefore solvable by finitely many polynomial inequalities.

Cones of Nonnegativity-Preserving Polynomials

Loewy-London Question & Clark (2022, 2024)

In their seminal work, Loewy and London (1978/79) introduced the cone $\mathcal{P}_n$ of all polynomials $p(x)$ that preserve matrix nonnegativity:

$$\mathcal{P}_n = \{p \in \mathbb{R}[x] : p(A) \ge 0 \text{ for all } A \in \mathbb{R}^{n \times n}_{\ge 0}\}$$

While polynomials with nonnegative coefficients clearly belong to $\mathcal{P}_n$, it is known that $\mathcal{P}_n$ contains polynomials with negative coefficients (e.g., $x^4 - x^2 + 1$ under specific scaling). Recent breakthroughs show:

Non-Polyhedral Cones: For fixed degree $d \ge 2n$, the cone $\mathcal{P}_n$ is non-polyhedral.
Arbitrarily Negative Coefficients: A polynomial preserving $n \times n$ nonnegative matrices can have its largest term, in absolute value, be arbitrarily negative while remaining coefficients are $1$.
Spectral Filter: If $p \in \mathcal{P}_n$ and $\sigma$ is realizable by $A \ge 0$, then $p(\sigma) = \{p(\lambda_1), \dots, p(\lambda_n)\}$ must be realizable by $p(A) \ge 0$, creating infinite families of necessary trace tests.

7. Interactive Computational Tools on This Hub

Explore spectral nonnegativity through interactive WebGL tools and solvers.

This research hub provides open-source, high-performance visual computing tools to investigate each mathematical facet of the problem:

🎯

Karpelevič Region Viewer

Visualize the exact region $\mathcal{K}_n$ of eigenvalues of stochastic matrices up to order $n=16$. Features dynamic Farey arcs, Ito polynomial solvers, containment tests, and power-up orbit trails.

Launch Karpelevič Viewer →

📊

Trace Polytope Gallery

Explore interactive 2D and 3D WebGL projections of trace polytopes for SNIEP and RNIEP across dimensions $n = 4, 5, 6$. Filter by matrix class, dimension, and polytope vertex signatures.

Open Polytope Gallery →

🧮

Spectra Realizer

Input arbitrary candidate multisets $\sigma \subset \mathbb{C}$, test necessary conditions (Perron, reality, trace nonnegativity, Loewy-London), and solve for nonnegative matrix realizations.

Open Spectra Realizer →

8. Foundational Literature & Citations

Pioneering publications that established the theoretical core of the NIEP.

Foundation 1907

Zur Theorie der Matrices

O. Perron

Mathematische Annalen, 64(2), 248–263

Foundation 1912

Über Matrizen aus nicht negativen Elementen

G. Frobenius

Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften, 456–477

Geometry 1951

On the characteristic roots of matrices with non-negative elements

F. I. Karpelevič

Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 15(4), 361–383

Milestone 1978

A note on the nonnegative inverse eigenvalue problem

R. Loewy · D. London

Linear and Multilinear Algebra, 6(1), 83–90

Milestone 1996

The real dimension of the nonnegative inverse eigenvalue problem

C. R. Johnson · T. J. Laffey · R. Loewy

Linear Algebra and its Applications, 241–243, 625–635

Real Algebraic Geometry 2024

The NIEP is solvable by reality and finitely many polynomial inequalities

B. J. Clark

arXiv:2407.14472 [math.RA]