The Nonnegative Inverse Eigenvalue Problem
The overarching challenge in matrix theory: finding necessary and sufficient conditions for a multiset of complex numbers to be the spectrum of an entrywise nonnegative matrix.
1. Formal Definition & Mathematical Setup
The Nonnegative Inverse Eigenvalue Problem (NIEP) is one of the classic, enduring open challenges in combinatorial matrix theory, algebra, and spectral geometry. Posed implicitly in the early twentieth century following the foundational theorems of Oskar Perron and Georg Frobenius, the problem asks:
The Nonnegative Inverse Eigenvalue Problem (NIEP)
Given a multiset $\sigma = \{\lambda_1, \lambda_2, \dots, \lambda_n\}$ of $n$ complex numbers, determine whether there exists an $n \times n$ entrywise nonnegative matrix $A = (a_{ij}) \in \mathcal{M}_n(\mathbb{R})$, with $a_{ij} \ge 0$ for all $i, j$, such that the spectrum of $A$ is precisely $\sigma$:
$$\sigma(A) = \{\lambda \in \mathbb{C} : \det(\lambda I - A) = 0\} = \sigma$$If such a matrix $A$ exists, we say that $\sigma$ is realizable, and $A$ is a realizing matrix for $\sigma$.
The multiset $\sigma$ must be closed under complex conjugation ($\sigma = \bar{\sigma}$), because the characteristic polynomial $p(\lambda) = \det(\lambda I - A)$ of a real matrix has real coefficients.
2. Solvability Progress by Matrix Dimension
The mathematical difficulty of characterizing realizable spectra escalates dramatically with matrix dimension $n$. The boundary between completely solved and open currently lies at dimension $n = 5$:
| Dimension | Status | Resolved By | Characterization & Conditions |
|---|---|---|---|
| $n = 1$ | Solved | Classical | $\sigma = \{\lambda_1\}$ is realizable $\iff \lambda_1 \ge 0$. |
| $n = 2$ | Solved | Classical | $\lambda_1 \ge 0$, $\lambda_1 \ge |\lambda_2|$, and $\lambda_1 + \lambda_2 \ge 0$ with $\lambda_2 \in \mathbb{R}$ or $\lambda_2 = \bar{\lambda}_1$. |
| $n = 3$ | Solved | Loewy & London (1978) | $\sigma = \bar{\sigma}$, $\rho = \max |\lambda_i| \in \sigma$, $s_1 \ge 0$, and the Loewy–London inequality $s_1^2 \le 3s_2$ (which implies $s_2 \ge 0$). |
| $n = 4$ | Solved | Meehan (1998), Torre-Mayo et al. (2007) | Completely classified into cases depending on whether eigenvalues are all real or contain complex pairs; $\operatorname{RNIEP}(4) = \operatorname{SNIEP}(4)$. |
| $n = 5$ | Open | Laffey, Meehan, Loewy (1996–1999) | Trace conditions fail to be sufficient! Symmetric and general problems diverge: $\operatorname{SNIEP}(5) \subsetneq \operatorname{RNIEP}(5)$. |
| $n \ge 6$ | Open | Active Research | General semi-algebraic complexity; Tarski-Seidenberg quantifier elimination is computationally intractable. |
3. Necessary Invariants & Trace Inequalities
Every realizable multiset $\sigma$ must satisfy a hierarchy of necessary algebraic and spectral constraints:
Perron-Frobenius Dominance
The spectral radius $\rho = \max_{1 \le i \le n} |\lambda_i|$ must itself belong to the spectrum $\sigma$. Furthermore, the multiplicity of any peripheral eigenvalue $\lambda$ with $|\lambda| = \rho$ cannot exceed the multiplicity of $\rho$.
Power Trace Nonnegativity
Since $A \ge 0$, every matrix power $A^k \ge 0$ for all integers $k \ge 1$. Consequently, the spectral moments (power sums) must all be nonnegative: $$s_k = \operatorname{Tr}(A^k) = \sum_{i=1}^n \lambda_i^k \ge 0 \quad \forall k \ge 1$$
JLL Inequalities (1978 / 1979)
Raphael Loewy & David London (1978) and Charles R. Johnson (1979/1981) proved that for all integers $k, m \ge 1$: $$n^{m-1} s_{km} \ge s_k^m$$ In particular, for $k=1, m=2$: $s_1^2 \le n s_2$.
Holtz's $M$-Matrix Newton Inequalities (2005)
Olga Holtz proved that the shifted $M$-matrix $\rho I - A$ satisfies Newton's log-concavity inequalities on $c_k = \binom{n}{k}^{-1} e_k(\rho - \lambda_1, \dots, \rho - \lambda_n)$: $$c_k^2 \ge c_{k-1} c_{k+1} \ge 0 \quad (1 \le k \le n - 1)$$
4. The Insufficiency of Trace Conditions ($n \ge 5$)
For low dimensions $n \le 3$, conjugate symmetry, Perron dominance, $s_1 \ge 0$, and the Loewy–London inequality $s_1^2 \le 3s_2$ are necessary and sufficient. It was once hoped that trace and JLL moment inequalities might suffice in higher dimensions as well.
The Laffey–Meehan Counterexample (1999)
Thomas J. Laffey and Eleanor Meehan demonstrated that at $n = 5$, a list can satisfy all power-sum nonnegativity conditions $s_k \ge 0$ and all JLL inequalities $s_k^m \le 5^{m-1} s_{km}$, yet fail to be realizable by any $5 \times 5$ nonnegative matrix:
In this range (including $t = 0$), $4s_4 < s_2^2$, violating Laffey & Meehan's trace-zero $5 \times 5$ inequality $4s_4 \ge s_2^2$ (whereas for $\sqrt{16\sqrt{6}-39} \le t < 1$, $\sigma(t)$ enters $\operatorname{RNIEP}(5) \setminus \operatorname{SNIEP}(5)$, and only reaches $\operatorname{SNIEP}(5)$ at $t \ge 1$).
5. Core Subproblems & Structural Branches
To dissect the complexity of the NIEP, the research community has partitioned the field into fundamental subproblems:
Symmetric NIEP (SNIEP)
Restricts $A = A^T \ge 0$. Requires orthogonal eigenspaces and leads to convex trace polyhedra and Soules bases.
Real NIEP (RNIEP)
Considers real spectra $\sigma \subset \mathbb{R}$ realized by general nonnegative matrices. Unlocks non-orthogonal frames that strictly enlarge the realizable set beyond SNIEP for $n \ge 5$.
Karpelevič Region $\mathcal{K}_n$
Determines all individual complex eigenvalues of stochastic matrices with $\rho(A) = 1$, solved completely by Karpelevič (1951) via Farey boundary arcs.
Suleĭmanova Spectra
The celebrated class with a single positive eigenvalue $\lambda_0 > 0 \ge \lambda_1 \ge \dots \ge \lambda_{n-1}$, where trace nonnegativity is completely sufficient for both general and symmetric realizations.
6. Asymptotic Solvability & Perron Similarities
Two modern frameworks have revolutionized our perspective on the problem:
The Boyle-Handelman Theorem (1991)
In symbolic dynamics, Boyle and Handelman proved that if one allows the matrix dimension $N \ge n$ to increase by adjoining auxiliary zero eigenvalues, primitive nonnegative realizability is completely characterized by conjugation closure, strict Perron dominance, and $s_m \ge 0$ with $s_m > 0 \Rightarrow s_{km} > 0$ ($\forall k \ge 1$).
Perron Similarities
Invertible similarity matrices $S$ whose first column forms a positive Perron eigenvector. Perron similarities generalize orthogonal Soules bases and provide the explicit non-orthogonal coordinate frames that realize spectra across RNIEP and NIEP.
7. Primary Literature & Citations
Foundational papers from the NIEP Comprehensive Bibliography8. See Also & Related Theory Pages
Theoretical Overview
High-level foundational survey covering Perron-Frobenius theory, historical milestones, and semi-algebraic cones.
Symmetric NIEP (SNIEP)
Orthogonal eigenspaces, Fiedler matrices, Soules bases, and trace polytope geometry.
Real NIEP (RNIEP)
The study of real spectra, Jordan blocks, and order-5 separation from SNIEP such as $\{7, 5, -4, -4, -4\}$.
Karpelevič Region
Kolmogorov's problem, stochastic eigenvalue boundaries, Farey vertices, and Ito's algebraic polynomials.
Suleĭmanova Spectra
Spectra with a single positive eigenvalue, trace sufficiency, and Fiedler's symmetric realization theorem.
Boyle-Handelman Theorem
Symbolic dynamics, shifts of finite type, and nonnegative realization with auxiliary zero eigenvalues.
Perron Similarities
Non-orthogonal similarity transformations preserving nonnegative matrix cones and Perron eigenvectors.