Theory Wiki · Subproblem Analysis

Real Nonnegative Inverse Eigenvalue Problem

Investigating real spectra realizable by general nonnegative matrices ($A \ge 0$, $\sigma \subset \mathbb{R}$), non-orthogonal eigenvector geometries, and the symmetry gap.

Subproblem

RNIEP

Matrix Constraint	$A \ge 0$ (arbitrary symmetry)
Spectrum Domain	$\sigma \subset \mathbb{R}$ (all real)
Eigenvectors	General invertible $X \in \mathrm{GL}(n, \mathbb{R})$
Relation to SNIEP	$= \operatorname{SNIEP}$ ($n \le 4$) $\supsetneq \operatorname{SNIEP}$ ($n \ge 5$)
Solvability $n \le 4$	Completely Solved
Solvability $n \ge 5$	Open Frontier
Key Invariants	$s_k \ge 0$, Newton sums, JLL inequalities
Key Milestones	Loewy & London (1978), Johnson-Laffey-Loewy (1996), Clark (2024)

→ Compare with SNIEP → View RNIEP Trace Polytopes → Test Spectrum in Solver

1. Definition & Eigenvector Degrees of Freedom

Relaxing the symmetry constraint provides significant geometric flexibility.

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$?

Definition: The RNIEP

Formal Statement

Find an $n \times n$ matrix $A = (a_{ij}) \in \mathbb{R}^{n \times n}$ such that:

$$\begin{aligned} a_{ij} &\ge 0 \quad (\text{entrywise nonnegativity}) \\ \sigma(A) &= \{\lambda_1, \lambda_2, \dots, \lambda_n\} \subset \mathbb{R} \end{aligned}$$

Unlike the Symmetric NIEP (SNIEP) where $A$ must be orthogonally diagonalizable ($A = Q \Lambda Q^T$), a general real realization $A$ diagonalizes as:

$$A = X \Lambda X^{-1}, \quad X \in \mathrm{GL}(n, \mathbb{R})$$

This difference is profound: an orthogonal matrix $Q \in O(n)$ possesses only $n(n-1)/2$ free angular parameters, whereas a general invertible basis $X \in \mathrm{GL}(n, \mathbb{R})$ provides $n^2$ degrees of freedom. Non-orthogonal eigenvectors can tilt and shear relative to one another, opening up feasible regions in matrix space that are geometrically inaccessible to symmetric matrices.

2. Necessary Invariants for RNIEP

Trace nonnegativity, Newton inequalities, and moment constraints.

Real Spectrum

$$\sigma \subset \mathbb{R}$$

All candidate eigenvalues are required to be real.

Perron Root

$$\lambda_1 = \max_{i} |\lambda_i| \in \sigma$$

Perron-Frobenius theorem guarantees the maximal root is positive.

Power Sum Traces

$$s_k = \sum_{i=1}^n \lambda_i^k \ge 0 \quad (\forall k \ge 1)$$

Because $A \ge 0$, all powers $A^k \ge 0$, so their traces must be nonnegative.

Newton's Inequalities

$$d_k^2 \ge d_{k-1} d_{k+1}$$

Elementary symmetric polynomial averages $d_k = e_k / \binom{n}{k}$ are log-concave.

In addition to Newton's inequalities, any realizable spectrum must obey the Johnson-Loewy-London (JLL) inequalities (1996):

$$n^{m-1} s_{km} \ge s_k^m + \frac{n^{m-1} - 1}{n - 1} (\rho^k - \lambda_j^k)^m \quad (\forall k, m \ge 1)$$

3. The Advantage of Non-Symmetry: $\operatorname{RNIEP} \supsetneq \operatorname{SNIEP}$

Why non-symmetric realizations can achieve what symmetric realizations cannot.

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:

$$\operatorname{RNIEP}(n) = \operatorname{SNIEP}(n) \quad \text{for } n \le 4$$

However, in 1996, Charles Johnson, Thomas Laffey, and Raphael Loewy proved that for every dimension $n \ge 5$, there exist real spectra realizable by nonnegative matrices that cannot be realized by any symmetric nonnegative matrix:

$$\operatorname{SNIEP}(n) \subsetneq \operatorname{RNIEP}(n) \quad \text{for all } n \ge 5$$

The Separation Spectrum

Johnson, Laffey, Loewy (1996)

The canonical separating spectrum is:

$$\sigma = \{4, 2, 2, -4, -4\}$$

An explicit non-symmetric realization $A \ge 0$ is given by the block companion structure:

$$A = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 64 & 0 & 32 & 0 & 0 \end{pmatrix}$$

The characteristic polynomial is $p(\lambda) = \lambda^5 - 32\lambda^3 - 64 = (\lambda - 4)(\lambda - 2)^2(\lambda + 4)^2$. While this non-symmetric companion matrix realizes $\sigma$, Johnson, Laffey, and Loewy proved that no symmetric nonnegative matrix can realize $\sigma$ because the eigenspace corresponding to $-4$ cannot be embedded orthogonally without forcing negative off-diagonal entries.

4. Dimension Solvability & The Laffey-Meehan Frontier

Trace conditions suffice for $n \le 4$, but fail definitively at order 5.

n ≤ 4 Completely Solved

Trace & Coefficient Criteria

Solved by Loewy & London ($n=3$) and Meehan ($n=4$). A real spectrum is realizable if and only if Perron dominance and power sum trace conditions hold.

n = 5 Open Frontier

Trace Insufficiency

Laffey and Meehan constructed spectra such as $\{3+t, 3-t, -2, -2, -2\}$ where all trace conditions and JLL inequalities hold, but no $5 \times 5$ realization exists.

n ≥ 6 Open Frontier

Higher Dimensions

Requires higher-order semi-algebraic polynomial inequalities. Constructive algorithms remain an active field of research.

5. Real Algebraic Geometry & Trace Polytopes

Semi-algebraic solvability and interactive geometric visualizations.

Semi-Algebraic Solvability (Clark, 2024)

Real Algebraic Geometry

In 2024, Benjamin J. Clark demonstrated that the RNIEP forms a semi-algebraic set. By the Tarski-Seidenberg projection theorem, the set of realizable real spectra $\operatorname{RNIEP}(n) \subset \mathbb{R}^n$ can be defined by a finite Boolean combination of polynomial equalities and inequalities:

$$\sigma \in \operatorname{RNIEP}(n) \iff \bigvee_{i=1}^M \bigwedge_{j=1}^{K_i} \big( P_{ij}(\lambda_1, \dots, \lambda_n) \ge 0 \big)$$

This confirms that the RNIEP is solvable by finitely many algebraic conditions, shifting modern research toward identifying minimal defining systems.

Interactive Trace Polytope Gallery

Compare RNIEP vs. SNIEP trace polytopes in real-time 3D WebGL. See how the RNIEP polytope expands beyond the symmetric boundary for dimensions $n = 4, 5, 6$.

Open Polytope Gallery →

Real Nonnegative Inverse Eigenvalue Problem

1. Definition & Eigenvector Degrees of Freedom

Definition: The RNIEP

2. Necessary Invariants for RNIEP

Real Spectrum

Perron Root

Power Sum Traces

Newton's Inequalities

3. The Advantage of Non-Symmetry: $\operatorname{RNIEP} \supsetneq \operatorname{SNIEP}$

The Separation Spectrum

4. Dimension Solvability & The Laffey-Meehan Frontier

Trace & Coefficient Criteria

Trace Insufficiency

Higher Dimensions

5. Real Algebraic Geometry & Trace Polytopes

Semi-Algebraic Solvability (Clark, 2024)

Interactive Trace Polytope Gallery

6. See Also & Related Articles

Symmetric NIEP (SNIEP)

Suleimanova Spectra

Karpelevič Region

NIEP Overview