The Boyle-Handelman Theorem
Resolving the spectral conjecture in symbolic dynamics: complete characterization of nonzero spectra realizable by primitive nonnegative matrices with auxiliary zero eigenvalues.
1. The Origin in Symbolic Dynamics
While the standard Nonnegative Inverse Eigenvalue Problem fixes the matrix dimension to the exact number of eigenvalues ($N = n$), a profoundly important related question arose from dynamical systems and ergodic theory in the 1970s and 1980s.
In the study of subshifts of finite type (SFTs)—which model topological Markov chains, data transmission coding, and hyperbolic dynamical systems—a shift space is defined by an adjacency matrix $A \in \mathcal{M}_N(\mathbb{Z}_{\ge 0})$. The topological entropy of the dynamical system is given by:
where $\lambda_1(A)$ is the dominant Perron-Frobenius eigenvalue. In 1973, R. F. Williams initiated the classification of shifts of finite type up to topological conjugacy and shift equivalence. A major open question emerged: Which algebraic numbers, and which multisets of nonzero complex numbers, can occur as the nonzero spectrum of the transition matrix of a mixing shift of finite type?
This question became known as the Spectral Conjecture of symbolic dynamics.
2. Statement of the Boyle-Handelman Theorem
In 1991, Mike Boyle and David Handelman published a landmark 50-page paper in the Annals of Mathematics ("The spectra of nonnegative matrices via symbolic dynamics"), definitively resolving the Spectral Conjecture:
The Boyle-Handelman Theorem (1991)
Let $\sigma = \{\lambda_1, \lambda_2, \dots, \lambda_k\}$ be a multiset of nonzero complex numbers closed under complex conjugation ($\sigma = \bar{\sigma}$).
There exists a primitive nonnegative matrix $A \in \mathcal{M}_N(\mathbb{R}_{\ge 0})$ of some finite size $N \ge k$ whose nonzero spectrum is precisely $\sigma$ (with $N - k$ auxiliary zero eigenvalues):
$$\sigma(A) = \sigma \cup \underbrace{\{0, 0, \dots, 0\}}_{N - k \text{ zeros}}$$if and only if the following two conditions hold:
- Strict Perron Dominance: There is a unique maximal eigenvalue $\lambda_1 \in \mathbb{R}_{> 0}$ such that: $$\lambda_1 > |\lambda_j| \quad \forall j = 2, 3, \dots, k$$
- Eventual Trace Positivity: For every integer $m \ge 1$: $$s_m = \sum_{i=1}^k \lambda_i^m > 0$$
A companion theorem in the same paper establishes that if the polynomial $\prod_{i=1}^k (\lambda - \lambda_i)$ has integer coefficients, the realizing matrix $A$ can be chosen with nonnegative integer entries ($A \in \mathcal{M}_N(\mathbb{Z}_{\ge 0})$), completely settling the symbolic dynamics conjecture.
3. Fixed Dimension vs. Asymptotic Augmentation
The contrast between the classical NIEP and the Boyle-Handelman setting offers profound mathematical insight:
| Feature | Fixed-Dimension NIEP | Boyle-Handelman Setting |
|---|---|---|
| Matrix Size | Strictly fixed to $N = n = |\sigma|$ | Augmented dimension $N \ge |\sigma|$ (allows auxiliary zeros) |
| Solvability Status | Open for all $n \ge 5$ | Completely Solved for all finite multisets! |
| Boundary Nature | Subtle semi-algebraic constraints on eigenvector angles | Purely algebraic trace positivity ($s_m > 0$) |
| Trace Sufficiency | Fails at $n=5$ (Laffey-Meehan counterexample) | Holds universally (with auxiliary zeros absorbed) |
Why does adding zero eigenvalues eliminate the obstructions that plague the classical NIEP?
In matrix theory, adding zero eigenvalues corresponds to enlarging the state space. In the graph of the matrix, auxiliary states act as "intermediate delay nodes" that separate conflicting feedback cycles. By introducing sufficiently many delay nodes, one can decouple conflicting eigenvector configurations without disturbing the nonzero eigenvalues!
4. Bounds on the Augmented Dimension $N$
Although Boyle and Handelman proved that a finite dimension $N$ always exists, their original proof relied on non-constructive compactness arguments and positive polynomial theory (Handelman's theorem on positive polynomials in ordered rings).
The Dimension Estimation Challenge
Given $\sigma$, what is the minimal dimension $N(\sigma)$ required to realize $\sigma$?
In general, if the spectral gap $\lambda_1 - \max_{j \ge 2} |\lambda_j|$ is very small, or if some power trace $s_m$ is positive but extremely close to zero, the required dimension $N$ can grow exponentially large.
In 2000, K. H. Kim, N. Ormes, and F. W. Roush developed explicit, constructive bounds on $N$ using state-splitting algorithms and polynomial division techniques.
5. Theoretical Significance for the NIEP
The Boyle-Handelman Theorem establishes that:
Eventual Realizability
Every candidate spectrum with a strictly dominant Perron root and positive power sums is eventually realizable if we relax the rigid fixed-dimension constraint.
The True Frontier of the NIEP
The genuine obstruction in the classical NIEP is not the realization of the spectrum itself, but the dimensional economy: cramming the realization into exactly $n$ dimensions without auxiliary slack.
6. See Also & Related Theory Pages
The Core NIEP
The fixed-dimension problem, dimensional solvability progress, and semi-algebraic geometry.
Perron Similarities
Non-orthogonal similarity transformations that preserve nonnegative matrix cones and realize non-symmetric spectra.
Symmetric NIEP (SNIEP)
Orthogonal eigenspaces, Soules bases, Fiedler theorems, and trace polytopes.
Karpelevič Region
Stochastic matrix eigenvalues, Farey boundary arcs, and Ito's algebraic polynomials.