Real Nonnegative Inverse Eigenvalue Problem

The Real Nonnegative Inverse Eigenvalue Problem (RNIEP) asks: given a multiset of $n$ real numbers $\sigma = \{\lambda_1, \lambda_2, \dots, \lambda_n\} \subset \mathbb{R}$, does there exist an entrywise nonnegative matrix $A \ge 0$ (not necessarily symmetric) whose spectrum equals $\sigma$?

Unlike the Symmetric NIEP (SNIEP), where $A = Q \Lambda Q^T$ is always orthogonally diagonalizable, a general real nonnegative realization need not even be diagonalizable—as shown already at order two by $\bigl(\begin{smallmatrix}1 & 1 \\ 0 & 1\end{smallmatrix}\bigr)$. In general, $A$ admits a Jordan decomposition over $\mathbb{C}$ (or real Jordan form):

Both non-orthogonal eigenbases and nontrivial Jordan blocks enlarge the feasible spectral region: an orthogonal matrix $Q \in O(n)$ possesses only $n(n-1)/2$ angular parameters, whereas a general similarity $X \in \mathrm{GL}(n, \mathbb{R})$ has $n^2$ entries, allowing eigenspaces and generalized eigenspaces to tilt relative to the nonnegative orthant.

For real spectra $\sigma \subset \mathbb{R}$, all even power sums $s_{2k} = \sum \lambda_i^{2k} \ge 0$ hold automatically, while odd trace bounds $s_{2k-1} \ge 0$ and the Johnson–Loewy–London (JLL) inequalities $s_k^m \le n^{m-1} s_{km}$ (such as $s_1^2 \le n s_2$ and $s_1^3 \le n^2 s_3$) impose nontrivial constraints on negative eigenvalues.

A major historic milestone in combinatorial matrix theory was establishing whether symmetry is a restrictive requirement for real spectra. For dimensions $n \le 4$, symmetry is non-restrictive:

In 1996, Charles R. Johnson, Thomas J. Laffey, and Raphael Loewy proved that the symmetric and real problems are genuinely different (first constructed at $n = 6$), and subsequent work by Eleanor Meehan (1998), Laffey & Meehan (1999), and Hartwig & Loewy established strict containment for every order $n \ge 5$: