Nonnegative inverse eigenvalue problem

A table of nonnegative weights can update quantities by adding weighted contributions from their current values. One two-place rule simply swaps the quantities: the new first value is the old second, and vice versa. Equal values stay the same, but a difference between them reverses sign at each step. These patterns have eigenvalues 1 and −1, describing their unchanged size and their sign reversal. The inverse problem asks which complete lists of eigenvalues can come from a table with no negative weights.[3]

A square table of nonnegative weights updates a list of quantities by adding weighted contributions. This is a nonnegative matrix. Which prescribed complete spectrum—a list of all eigenvalues, including repetitions—can arise from such an update? The general problem fixes a size $n$ and allows any real $n$-by-$n$ matrix whose entries are nonnegative, without a symmetry requirement. For $A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, the patterns $(1,1)$ and $(1,-1)$ are multiplied by 1 and −1 respectively. The contrast uses a negative component to describe a difference; actual nonnegative quantities are simply swapped.

In general $Av=\lambda v$ defines an eigenvalue $\lambda$ through a nonzero, possibly complex vector $v$. The requested list contains $n$ values with their algebraic multiplicities, meaning their repetitions as roots of the characteristic polynomial. A real matrix requires conjugate pairs for nonreal values. Moreover, each power of a nonnegative matrix still has nonnegative entries, so its trace—the sum of its diagonal entries—is nonnegative. In particular, the eigenvalue sum cannot be negative: the list $(1,-2)$, whose sum is −1, cannot be the spectrum of a nonnegative two-by-two matrix. Adding extra zero eigenvalues changes the specified dimension and is a different instance.[3]

Some proposed lists can be ruled out and many can be constructed, but there is no complete test covering all sizes. The swap example shows why “nonnegative weights” does not mean “only nonnegative eigenvalues.” Special answers for tables with additional symmetry or other structure leave the general question open.[3] [4]

The survey collects necessary conditions and construction methods without a complete characterization in arbitrary dimension. The Perron-similarity work fixes possible eigenvector coordinates and determines regions of eigenvalues for which changing back to the original coordinates gives nonnegative matrix entries. These constructions address the diagonalizable version. They do not cover every nonnegative matrix: repeated eigenvalues may occur without a full eigenvector basis. The unrestricted nonsymmetric problem remains the target.[3] [4]

Positive contributions at each location can still produce alternating contrasts across locations. The problem asks how far this freedom goes: which combinations of collective growth, decay and oscillation can be compatible with purely nonnegative local interactions? This connects the visible update rule with patterns that are apparent only when the whole system is considered.[3]

The swap example exposes the distinction between positive local weights and sign-changing global contrasts. Another useful subclass consists of matrices whose rows sum to one: each new coordinate is a weighted average of old coordinates. Spectral restrictions then help describe which rescaling and oscillating modes can coexist within averaging. The general inverse problem asks how such structural restrictions on entries constrain a whole spectrum; eigenvalues alone need not supply a full eigenvector decomposition of every matrix.[3] [4]