The Nonnegative Inverse Eigenvalue Problem
An open-source, interactive collection of computational tools and geometric visualizations designed to explore, understand, and advance research on matrix spectra and nonnegativity.
Interactive Visualizations & Solvers
Select a tool to begin interactive spectral analysis
Karpelevič Region Viewer
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$).
Trace Polytope Gallery
Explore interactive 2D polygons and 3D polyhedra capturing necessary and sufficient trace polytope conditions for the Symmetric (SNIEP) and Real (RNIEP) inverse eigenvalue problems for dimensions n = 4, 5, and 6. Filter by matrix class, dimension, and vertex signature.
Numerical Spectra Realizer
Given a target spectrum, determine whether it can be realized by a Nonnegative, Stochastic, Symmetric, or Stochastic Symmetric matrix. Configure numerical tolerances, run Orsi alternating projection solvers with real Schur factorizations, and inspect the realizing or best-approximation matrix.
Academic Profile & Research
Curated academic website of Benjamin J. Clark, Ph.D. in Mathematics (WSU) and Software Engineer at Google. Browse research papers on matrix-preserving polynomials, conference presentations, student lecture notes, and curriculum vitae.
About the Nonnegative Inverse Eigenvalue Problem
A comprehensive overview of spectral nonnegativity, major theoretical breakthroughs, and foundational literature.
📐 Core Formulation & Subproblems
The mathematical framework governing entrywise nonnegative realizations and their subclasses.
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 combinatorial matrix theory.
Subproblems & Variants
Several foundational variants isolate specific algebraic, geometric, and topological structures:
Symmetric NIEP
Requires $A = A^T$. Restricts all eigenvalues to $\mathbb{R}$ with real orthogonal eigenvectors.
Real NIEP
Requires $A \ge 0$ with $\sigma \subset \mathbb{R}$ (not necessarily symmetric; strictly broader than SNIEP for $n \ge 5$).
Stochastic 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 spectrum with positive Perron root and positive traces can be realized by a nonnegative matrix of some higher order $N \ge n$. However, determining a constructive, sharp upper bound on the required embedding dimension $N_{\min}(\sigma)$ remains an elusive open problem.
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
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
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
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
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
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
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
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.
📚 Key Literature & Citations
Foundational and modern research papers shaping the spectral theory of nonnegative matrices.
Zur Theorie der Matrices
Mathematische Annalen, Vol. 64, pp. 248–263
Über Matrizen aus nicht negativen Elementen
Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften, pp. 456–477
Stochastic matrices with real characteristic values
Doklady Akademii Nauk SSSR, Vol. 66, pp. 343–345
On the characteristic roots of matrices with non-negative elements
Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, Vol. 15, No. 4, pp. 361–383
A note on the nonnegative inverse eigenvalue problem
Linear and Multilinear Algebra, Vol. 6, No. 1, pp. 83–90
Row stochastic matrices similar to doubly stochastic matrices
Linear and Multilinear Algebra, Vol. 10, No. 2, pp. 113–130
The spectra of nonnegative matrices via symbolic dynamics
Annals of Mathematics, Vol. 133, No. 2, pp. 249–316
A new characterization of the Karpelevič region for stochastic matrices
Linear Algebra and its Applications, Vol. 255, pp. 321–346
A result on the symmetric nonnegative inverse eigenvalue problem
Linear Algebra and its Applications, Vol. 302–303, pp. 295–313
Nonnegative realization of spectra having negative real parts
Linear Algebra and its Applications, Vol. 420, No. 2–3, pp. 672–689
Perron spectroids and the boundary of the Karpelevič region
Linear Algebra and its Applications, Vol. 507, pp. 215–229