The Nonnegative Inverse Eigenvalue Problem
Nonsensically Nonnegative is an open-source research and visualization hub dedicated to the Nonnegative Inverse Eigenvalue Problem (NIEP) and its structured variants. This site is a place for short blog-style posts and interactive tools exploring past and current research on the topic.
Currently maintained by Benjamin J. Clark, new solvers, polyhedral datasets, and articles are added continuously. Please visit About & Contributing if you spot an issue, have a spectrum to test, or want to collaborate.
Highlighted posts and interactive tools
Visualize the exact region $\mathcal{K}_n$ of all complex numbers that can arise as eigenvalues of an $n \times n$ stochastic matrix. Features live Farey sequence root calculation, Ito boundary polynomial solver, point containment testing, and dynamic power orbit visualization ($z^1, z^2, \dots, z^k$).
A complete nine-stop visual monograph reconstructing and updating F. I. Karpelevič’s 1951 characterization of the stochastic eigenvalue region $\mathcal{K}_n$, from invariant polygons and the chip game to cyclic polygons, Farey arcs, and boundary induction.
Explore 125 interactive 2D polygons and 3D polyhedra visualizing order-5 ($n = 5$) trace polytope cross-sections and realizability regions for the Symmetric (SNIEP) and Real (RNIEP) inverse eigenvalue problems. Filter by matrix class, dimension, and vertex signature.
Interactive exploration of selected $5 \times 5$ group character tables and reducible adjoined blocks as ideal Perron similarities, collectively covering 99.97% of the constructively realizable 2D $(1,a,a,b,b)$ plane and mapping the unsolved 3D $(1,a,a,b,c)$ frontier.
Given a target spectrum, check necessary spectral conditions and search numerically (or via exact analytical constructors) for a realizing Nonnegative, Stochastic, Symmetric, or Symmetric Stochastic matrix using Orsi alternating projections with real Schur factorizations.
About the Nonnegative Inverse Eigenvalue Problem
The mathematical framework governing entrywise nonnegative realizations, structured subproblems, and universal spectral invariants.
The NIEP Formulation
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 spectral matrix theory.
Subproblems & Variants
Several foundational variants isolate specific algebraic, geometric, and topological structures:
Symmetric NIEP (SNIEP)
Requires $A = A^T$. Restricts all eigenvalues to $\mathbb{R}$ with real orthogonal eigenvectors.
Real NIEP (RNIEP)
Requires $A \ge 0$ with $\sigma \subset \mathbb{R}^n$ (not necessarily symmetric; strictly broader than SNIEP for $n \ge 5$).
Stochastic NIEP (S-NIEP)
Requires row sums equal to $1$, normalizing spectral radius $\rho(A) = 1$ and connecting directly to Karpelevič regions.
Spectral Padding
Realization by an $N \times N$ matrix with $N \ge n$, padding with $N - n$ auxiliary zero eigenvalues.
Necessary Conditions
Any realizable spectrum $\sigma = \{\lambda_1, \dots, \lambda_n\}$ must satisfy universal spectral and trace invariants:
Conjugate Symmetry
Spectrum must be closed under complex conjugation because $A \in \mathbb{R}^{n \times n}$.
Perron Root Dominance
The spectral radius must be an eigenvalue of $A$ (Perron–Frobenius theorem).
Power Sum Traces
Since $A \ge 0$, all powers $A^k \ge 0$, so their diagonal entries and traces must be nonnegative.
Loewy–London Inequalities
Higher-order moments derived from entrywise Cauchy–Schwarz and Hölder inequalities.
Comprehensive Problem Background & Mathematical Theory
Explore the century-long history, complete dimension-by-dimension characterizations ($n=1$ to $n \ge 5$), Loewy–London polynomial cones, and modern semi-algebraic geometry advances.
Open Problems & Active Conjectures
Crucial unanswered questions, structural conjectures, and geometric frontiers shaping modern research in spectral nonnegativity.
General NIEP Solvability for $n \ge 5$
While completely solved for $n \le 4$, dimensions $n \ge 5$ remain open. Because moment trace conditions are known to be insufficient, identifying an explicit, minimal system of polynomial inequalities or geometric criteria that completely characterizes realizability is one of the premier challenges in combinatorial matrix theory.
Minimal Nonzero Spectrum Padding
By the Boyle–Handelman theorem (1991), any conjugation-closed nonzero spectrum with a strictly dominant positive Perron root ($\lambda_1 > |\lambda_j|$) and $s_m \ge 0$ with $s_m > 0 \Rightarrow s_{km} > 0$ ($\forall k \ge 1$) is the nonzero spectrum of a primitive nonnegative matrix of some higher order $N \ge n$. Determining sharp general upper bounds on the minimal embedding dimension $N_{\min}(\sigma)$ remains open.
Geometry of Preserving Cones $\mathcal{P}_n$
The cone $\mathcal{P}_n$ of polynomials preserving nonnegative matrices provides infinite families of necessary trace invariants. While recently proven to be non-polyhedral for degree $d \ge 2n$ with arbitrarily negative coefficients, characterizing its extreme rays, boundary equations, and spherical measure remains active research.
The RNIEP vs. SNIEP Boundary Gap
In 1996, Johnson, Laffey, and Loewy proved that $\operatorname{SNIEP}(n) \subsetneq \operatorname{RNIEP}(n)$ for all $n \ge 5$. Realizing spectra non-symmetrically unlocks non-orthogonal eigenvectors that accommodate real spectra where symmetric matrices fail. Exactly delineating the geometric gap and boundary between these two semi-algebraic sets remains unresolved.
Landmark Results & Milestones
Chronological developments establishing the boundaries, characterizations, and solvability of the NIEP.
Perron–Frobenius Spectral Theory
Mathematische Annalen, 64(2): 248–263 · Sitzungsber. Preuss. Akad. Wiss. Berlin: 456–477
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
Doklady Akademii Nauk SSSR, 66(3): 343–345
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
Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 15(4): 361–383
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, H. Ito reformulated these boundary curves as explicit minimal algebraic polynomial equations.
Loewy–London Inequalities & Order 3 Resolution
Linear and Multilinear Algebra, 6(1): 83–90
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$.
General JLL Power-Sum Inequalities
Linear and Multilinear Algebra, 10(2): 113–130
Independently established and generalized the Johnson–Loewy–London (JLL) inequalities $s_k^m \le n^{m-1} s_{km}$ for all nonnegative matrices and integers $k, m \ge 1$, providing fundamental necessary conditions on higher spectral moments across all matrix orders.
Boyle–Handelman Spectral Realization Theorem
Annals of Mathematics, 133(2): 249–316
Resolved the nonzero spectrum problem for primitive real nonnegative matrices via symbolic dynamics: a conjugation-closed nonzero list $\sigma$ is the nonzero spectrum of a primitive $A \in \mathcal{M}_N(\mathbb{R}_{\ge 0})$ for some $N \ge |\sigma|$ if and only if it has a strictly dominant positive Perron eigenvalue $\lambda_1 > |\lambda_j|$ and satisfies $s_m \ge 0$ together with $s_m > 0 \Rightarrow s_{km} > 0$ for all $k \ge 1$.
Full Resolution of Dimension 4
Linear Algebra and its Applications, 426(2–3): 729–773
Completed the solution of the general complex NIEP for $n = 4$ (following Loewy & London's 1978 solution of the real $n = 4$ and trace-zero $n = 4$ cases), characterizing the exact nonlinear coefficient inequalities beyond JLL bounds needed when a $4 \times 4$ spectrum contains a nonreal conjugate pair.
Comprehensive NIEP Bibliography & Citation Archive
Search and filter foundational and modern research papers across Perron–Frobenius theory, Karpelevič regions, SNIEP, RNIEP, and preserving polynomial cones, with direct links and one-click BibTeX export.