The Nonnegative Inverse Eigenvalue Problem

Given a multiset of $n$ complex numbers $\sigma = \{\lambda_1, \lambda_2, \dots, \lambda_n\}$, does there exist an entrywise nonnegative matrix $A \ge 0$ of order $n$ whose spectrum equals $\sigma$?

Despite over a century of study since the roots of Perron-Frobenius theory, a general constructive characterization for arbitrary dimension $n \ge 5$ remains one of the premier unsolved problems in combinatorial matrix theory.

Several foundational variants isolate specific algebraic and topological structures:

• SNIEP (Symmetric): Requires $A = A^T$, restricting all eigenvalues to $\mathbb{R}$.
• RNIEP (Real): Requires $A \ge 0$ with real spectrum (not necessarily symmetric).
• Stochastic NIEP: Requires row sums equal to $1$, constraining spectral radius $\rho(A) = 1$.
• Nonzero Spectrum Problem: Realization by an $N \times N$ matrix with $N \ge n$, padding with $N - n$ zero eigenvalues.

Any realizable spectrum $\sigma$ must satisfy universal invariants:

While necessary, these trace conditions alone are not sufficient for dimensions $n \ge 5$.

Perron-Frobenius Spectral Theory

O. Perron · G. Frobenius

Established that any nonnegative matrix $A \ge 0$ has a real, maximal eigenvalue $\rho(A) \ge |\lambda|$ with an associated nonnegative eigenvector. For irreducible matrices, $\rho(A)$ is algebraically simple, strictly positive, and any peripheral eigenvalues on the circle $|z| = \rho(A)$ are distributed with exact cyclic root-of-unity symmetry.

Suleĭmanova's Theorem

H. Suleĭmanova

Proved the earliest major sufficiency result for real spectra: if $\sigma$ contains a single positive eigenvalue $\lambda_0 > 0$ and all other $\lambda_i \le 0$, then $\sigma$ is realizable by a nonnegative matrix if and only if the trace condition $\sum_i \lambda_i \ge 0$ holds. This became the foundation for companion matrix constructions and perturbed realizations.

Karpelevič's Boundary Characterization

F. I. Karpelevič

Completely determined the compact region $\mathcal{K}_n \subset \mathbb{C}$ of all possible eigenvalues of $n \times n$ stochastic matrices. The boundary consists of curvilinear arcs connecting roots of unity corresponding to Farey fractions $p/q \le 1$ with $q \le n$. In 1997, T. Ito reformulated these boundary curves as explicit minimal algebraic polynomial equations.

Loewy-London Inequalities & Order 3 Resolution

R. Loewy · D. London

Introduced higher trace inequalities $s_k^m \le n^{m-1} s_{km}$, ruling out infinite candidate spectra that satisfy ordinary trace positivity. They posed the fundamental problem of characterizing the cone $\mathcal{P}_n$ of polynomials preserving nonnegative matrices, completely solving the NIEP for $n = 3$ and trace-zero $n = 4$.

Complete Solution for Dimension 3

C. R. Johnson

Provided a constructive proof completely solving the general NIEP for $n = 3$ with arbitrary trace. Proved that for $n = 3$, a spectrum is realizable if and only if it satisfies reality, the Perron-Frobenius condition, nonnegativity of trace, and the second-order Loewy-London trace inequality.

Boyle-Handelman Spectral Realization Theorem

M. Boyle · D. Handelman

Resolved the nonzero spectrum problem via shift equivalence in topological Markov chains. Proved that a candidate nonzero spectrum is the nonzero spectrum of some nonnegative matrix of possibly larger size $N \ge n$ if and only if it satisfies the Perron condition and $\operatorname{tr}(A^k) \ge 0$ with strict positivity for some power.

Full Resolution of Dimension 4

H. Meehan · T. J. Laffey

Conclusively resolved the general NIEP for $n = 4$ including positive trace cases. Demonstrated that for order 4, the known Loewy-London inequalities, trace nonnegativity, and Perron conditions constitute necessary and sufficient conditions, constructing companion matrix factorizations for all boundary cases.