Theory Wiki · Asymptotic Spectral Realization

The Boyle-Handelman Theorem

Resolving Williams' spectral conjecture in symbolic dynamics: the definitive characterization of nonzero spectra realizable by primitive nonnegative matrices with auxiliary zero eigenvalues.

1. The Origin in Symbolic Dynamics & Shifts of Finite Type

While the standard Nonnegative Inverse Eigenvalue Problem fixes the matrix dimension strictly to the cardinality of the candidate spectrum ($N = n = |\sigma|$), a 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, hyperbolic dynamical systems, and data transmission coding—a shift space $X_A$ is defined by a 0-1 or nonnegative integer adjacency matrix $A \in \mathcal{M}_N(\mathbb{Z}_{\ge 0})$. The topological entropy of the dynamical system is given by the logarithm of its spectral radius:

$$h(X_A) = \log \lambda_1(A)$$

where $\lambda_1(A)$ is the dominant Perron-Frobenius eigenvalue. In 1973, R. F. Williams (1973) initiated the classification of shifts of finite type up to topological conjugacy and shift equivalence. Williams formulated a central question concerning the spectral invariants of mixing shifts:

Question 1.1 (Williams' Spectral Conjecture, 1973)

Question

Let $\sigma = \{\lambda_1, \dots, \lambda_k\}$ be a multiset of nonzero complex numbers closed under complex conjugation. What algebraic and spectral conditions are necessary and sufficient for $\sigma$ to be the nonzero spectrum of an irreducible or primitive matrix $A \in \mathcal{M}_N(\mathbb{Z}_{\ge 0})$ of some finite dimension $N \ge k$?

This problem became known as the Spectral Conjecture of symbolic dynamics. Although the Strong Shift Equivalence Conjecture was later refuted by Ki Hang Kim and Fred W. Roush (1999), the spectral realization problem received a definitive affirmative answer.

2. Statement of the Boyle-Handelman Theorem

In 1991, Mike Boyle and David Handelman (1991) published their landmark paper in the Annals of Mathematics ("The spectra of nonnegative matrices via symbolic dynamics"), providing the complete characterization:

Theorem 2.1 (The Boyle-Handelman Theorem, 1991)

Theorem

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

$$\sigma(A) = \sigma \cup \underbrace{\{0, 0, \dots, 0\}}_{N - k \text{ zeros}}$$

if and only if the following two conditions hold:

  1. 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$$
  2. 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 the integral realization required for subshifts of finite type:

Theorem 2.2 (Integer Spectral Realization)

Theorem

If, in addition to the conditions of Theorem 2.1, the characteristic polynomial $p(t) = \prod_{i=1}^k (t - \lambda_i)$ has integer coefficients ($p \in \mathbb{Z}[t]$), then the realizing matrix $A$ can be chosen with nonnegative integer entries:

$$A \in \mathcal{M}_N(\mathbb{Z}_{\ge 0})$$

Consequently, $\sigma$ is realizable as the nonzero spectrum of a mixing shift of finite type, settling Williams' Spectral Conjecture affirmatively.

The proof developed by Boyle and Handelman merged symbolic dynamics (shift equivalence of Markov chains) with the algebraic theory of ordered rings and positive polynomials developed by David Handelman (1992).

3. Fixed Dimension vs. Asymptotic Augmentation

The contrast between the classical fixed-dimension NIEP and the Boyle-Handelman setting highlights why relaxing the matrix order removes traditional obstructions:

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 Semi-algebraic constraints on eigenvector cones Purely algebraic trace positivity ($s_m > 0$)
Trace Sufficiency Fails at $n=5$ (Laffey & Meehan 1999) Holds universally (with auxiliary zeros absorbed)

Combinatorial Mechanism of Auxiliary Zeros: In graph-theoretic terms, adding zero eigenvalues corresponds to enlarging the state space of the underlying directed graph. Auxiliary states act as delay nodes that decouple conflicting feedback cycles without disturbing the nonzero cyclic spectrum.

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 ordered ring theory:

Problem 4.1 (Minimal Augmented Dimension Estimation)

Problem

Given $\sigma$, determine the minimal dimension $N_{\min}(\sigma)$ required to realize $\sigma$ by a primitive nonnegative matrix. How does $N_{\min}(\sigma)$ depend on the spectral gap $\lambda_1 - \max_{j \ge 2}|\lambda_j|$ and the trace margin $\inf_{m \ge 1} s_m$?

In 2000, K. H. Kim, N. Ormes, and F. W. Roush (2000) developed explicit, constructive bounds on $N$ using state-splitting algorithms and formal power series:

Theorem 4.1 (Constructive Dimension Bounds; Kim, Ormes, & Roush, 2000)

Theorem

Let $\sigma = \{\lambda_1, \dots, \lambda_k\}$ satisfy the Boyle-Handelman conditions. There exists an algorithmic procedure using formal power series division and state-splitting that constructs an explicit primitive matrix $A \ge 0$ realizing $\sigma \cup \{0\}^{N-k}$, with $N$ bounded as a computable function of the minimal trace ratio and the spectral gap.

Subsequent structural analyses by Stephen Kirkland (2001) further explored dimension bounds for companion matrix perturbations and low-rank constructions.

5. Theoretical Significance for the NIEP

The Boyle-Handelman Theorem provides a fundamental perspective on the Nonnegative Inverse Eigenvalue Problem:

Eventual Realizability

Every candidate spectrum with a strictly dominant Perron root and positive power sums is eventually realizable once the rigid fixed-dimension constraint is relaxed.

The Dimensional Frontier

The primary mathematical difficulty of the classical NIEP is not the realization of the spectrum itself, but dimensional economy: packing the realization into exactly $n$ dimensions without auxiliary slack.

6. Key Literature & Academic Citations

Pioneering publications in symbolic dynamics, shifts of finite type, and augmented spectral realization

The publications below are sourced directly from the global NIEP Comprehensive Bibliography. Each record provides academic metadata, research notes, links to primary literature, and one-click BibTeX exports:

7. 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.
← Return to NIEP Research Hub