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$, and the first two traces are nonnegative: $s_1 \ge 0$, $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$$
Loewy-London Inequalities (1978)
Raphael Loewy and David London 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$.
Johnson-Loewy-London (JLL) Inequalities
In 1996, Johnson, Laffey, and Loewy established the strengthened bound: $$n^{m-1} s_{km} \ge s_k^m + \frac{n^{m-1} - 1}{n - 1} (\rho^k - \lambda_j^k)^m$$
4. The Insufficiency of Trace Conditions ($n \ge 5$)
For low dimensions $n \le 3$, trace nonnegativity ($s_1 \ge 0, s_2 \ge 0$) together with the Loewy-London condition is completely necessary and sufficient. It was once hoped that a finite family of trace and moment inequalities might suffice for all $n$.
The Laffey-Meehan Counterexample (1999)
Thomas J. Laffey and Eleanor Meehan discovered that for $n = 5$, there exist spectra that satisfy all trace inequalities, Loewy-London conditions, and Johnson-Loewy-London inequalities, yet cannot be realized by any $5 \times 5$ nonnegative matrix! A celebrated family is:
This foundational counterexample proved that the boundary of the realizable domain $\mathcal{E}_n$ is not cut out purely by trace polynomials, but involves subtle semi-algebraic geometric constraints on the eigenvector configurations.
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, the NIEP becomes completely solvable under strict Perron dominance and positive power traces!
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. 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, non-orthogonal frames, and the Laffey-Loewy separation $\{4, 2, 2, -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.