Karpelevič's Theorem & The Karpelevič Region

The spectral theory of stochastic matrices began with a question formulated by Andrey Nikolaevich Kolmogorov concerning the asymptotic behavior of finite Markov chains.

Bibliographic Note on Origin Date: Many mathematical treatises, tracing back to Felix Gantmacher's 1959 textbook The Theory of Matrices, cite Kolmogorov's problem as having appeared in 1937. As documented by Joanne Swift (1972), Kolmogorov originally presented this question in a 1938 publication in the Bulletin of Moscow University.

1.2 Dmitriev & Dynkin's Invariant Polygon Duality (1946)

In 1946, Nikolai Dmitriev and Eugene Dynkin established a fundamental geometric duality relating stochastic matrix spectra to contracting polygonal rotations in the complex plane.

Dmitriev and Dynkin completely determined $\mathcal{K}_n$ for $n \le 4$:

• $n = 2$: The real segment $[-1, 1]$.
• $n = 3$: The union of the equilateral triangle with vertices $\{1, e^{i 2\pi/3}, e^{i 4\pi/3}\}$, the curvilinear arcs connecting these roots of unity to the negative real axis at $-1/2$, and the real segment $[-1, -1/2]$.
• $n = 4$: The region bounded by chords connecting 4th roots of unity $\{1, i, -1, -i\}$ and 3rd roots of unity, and curvilinear arcs between adjacent vertices.

1.3 Joanne Swift's Thesis & Western Dissemination (1972)

Because the foundational papers of Dmitriev and Dynkin (1946) and H. R. Suleĭmanova (1949) were published exclusively in Russian journals during the early postwar period, their direct technical methods remained difficult to access in Western literature.

In 1972, Joanne Swift completed her Master's thesis at McGill University, titled "The location of characteristic roots of stochastic matrices". Swift's work provided:

• Primary English Translations: Complete translations of Dmitriev and Dynkin (1946) in Appendix A and Suleĭmanova (1949) in Appendix B.
• Systematic Boundary Contact Analysis: An exposition of the boundary contact principle, showing that for an eigenvalue $\lambda$ to reside on the radial boundary of $\mathcal{K}_n$, every vertex image $\lambda v_i$ must lie on the boundary edges of the polygon $P$.
• Citation Rectification: Documentation tracing the 1938 origin of Kolmogorov's problem.

1.4 Karpelevič's Extremal Boundary Game

In his 1951 paper, Karpelevič characterized the boundary $\partial\mathcal{K}_n$ by formulating an extremal geometric problem that can be understood as a game between radial expansion and polygonal support constraints.

Methodological Evolution: In Karpelevič's original 1951 deduction, analyzing all admissible sequences of branching contacts, tower heights, and transition weights required 70 pages of case-by-case calculations. While foundational, this game-theoretic combinatorial machinery has been largely superseded by modern algebraic and structural approaches:

• Đoković (1990): Reduced the search space via cyclic polygons generated by powers $1, \lambda, \lambda^2, \dots$.
• Ito (1997): Replaced transcendental pencils with algebraic polynomial equations $P_\alpha(t) = 0$.
• Johnson & Paparella (2017): Provided explicit matrix realization constructions for every boundary polynomial.
• Kirkland, Laffey, & Šmigoc (2020): Replaced multi-root searches with a single univariate trigonometric radius equation.
• Verbeken & Ginis (2026): Eliminated tower casework entirely through intermediate convex hull monotonicity and projective transfer.

In 1951, Fridrikh Izrailevich Karpelevič provided the definitive characterization of the stochastic eigenvalue region for all matrix orders $n$.

2.2 Radially Extremal Points vs. Boundary Points

A point $\lambda \in \mathcal{K}_n$ is called radially extremal (denoted $\lambda \in E_n$) if $\gamma \lambda \notin \mathcal{K}_n$ for all $\gamma > 1$. Karpelevič asserted that $\partial\mathcal{K}_n = E_n$ because $\mathcal{K}_n$ is closed. As clarified by Munger, Nickerson, and Paparella (2023), this assertion requires qualification for small dimensions.

The boundary $\partial\mathcal{K}_n$ in the upper half-plane is organized by the Farey sequence of order $n$.

Let $z_1 = e^{i 2\pi p/q}$ and $z_2 = e^{i 2\pi r/s}$ with $q < s$. The geometry of the boundary curve $\Gamma(z_1, z_2)$ is determined by the denominator sum:

3.2 Classification of Reduced Ito Polynomials

In 1997, Hisashi Ito formulated algebraic equations for Karpelevič's boundary arcs. With $d = \lfloor n/q \rfloor$ and $\beta = 1 - \alpha$, the boundary arcs correspond to four reduced polynomial families (Johnson & Paparella 2017; Munger, Nickerson & Paparella 2023):

Powers of Boundary Arcs: As established by Joshi, Kirkland, and Šmigoc (2023) and Munger et al. (2023), many Type II and Type III boundary arcs are pointwise integer powers of simpler Type I arcs, connecting higher-order boundary geometry to lower-dimensional cyclic companion matrices.

Given a Farey pair $(p/q, r/s)$ in $\mathcal{F}_n$, Ito's theorem asserts that boundary points satisfy $P_\alpha(t) = 0$ for $\alpha \in [0, 1]$. However, as identified by Kirkland, Laffey, and Šmigoc (2020), this formulation possesses an inherent root selection ambiguity: the reduced polynomial $P_\alpha(t)$ may possess multiple distinct roots inside the exact same angular sector $[2\pi p/q, 2\pi r/s]$.

For example, when $n = 12$ and $(p/q, r/s) = (3/10, 1/3)$, the reduced Ito polynomial is $f_\alpha(t) = (t^3 - \beta)^4 - \alpha^4 t^2$. For $\alpha \in [0, 0.3986]$, $f_\alpha(t)$ has two distinct roots inside the sector $[3\pi/5, 2\pi/3]$. Neither Karpelevič nor Ito provided an analytical test to determine which candidate root belongs to $\partial\mathcal{K}_n$.

4.3 The Universal Subdominance Theorem

For any stochastic matrix $A \in \mathcal{P}_n$, an eigenvalue $\lambda$ is subdominant if its modulus is second-largest after the Perron eigenvalue $\rho(A) = 1$. The subdominant modulus governs the asymptotic mixing rate and spectral gap $1 - |\lambda|$ of the Markov chain.

In "Demystifying the Karpelevič Theorem" (arXiv:2309.03849v5, 2023), Munger, Nickerson, and Paparella developed an elementary programme to establish Karpelevič's theorem without invoking Karpelevič's 1951 paper. The programme organizes around three assertions:

1. Realizability: Every root of an Ito polynomial belongs to $\mathcal{K}_n$ (proven by Johnson & Paparella 2017).
2. Continuous Path Existence & Simpleness: A continuous curve of roots connects the Farey endpoints $\omega_q^p$ and $\omega_s^r$ with strictly monotonic argument.
3. Radial Extremality: The curve of roots lies on the boundary $\partial\mathcal{K}_n$ (proven for $n > 3$).

In 2026, Brecht Verbeken and Vincent Ginis (arXiv:2609.26058v2) provided a completely self-contained structural proof of Karpelevič's Theorem that derives the boundary equations directly from an arbitrary radial extremum of least order $N \ge 4$.

6.1 Structural Architecture

The proof proceeds through four structural stages:

• Positive Perron Deflation: Let $A$ be an irreducible stochastic matrix with stationary vector $\pi^T$. Removing stationary mass $B = A - u\pi^T$ and diagonally normalizing shows that if any vertex image $T(v_i)$ were in $\operatorname{int}(P)$, non-Perron eigenvalues could be scaled radially outward, contradicting minimality. Hence, every image vertex satisfies $T(v_i) \in \partial P$ (hereditary saturation).
• Branching Count Monotonicity: Let $b_T(P)$ be the number of vertex images in the relative interior of edges. Verbeken and Ginis prove $b_T(Q) \le b_T(P)$ under intermediate convex hulls. Invertible elementary stochastic factors $S_i(t)$ transport branching contacts, localizing all branching into a single contiguous interval (branch-minimal normal form).
• Arithmetic Suspension & Projective Transfer: Using Farey record arithmetic, indices partition into towers of heights $q$ and $q+h$. Face persistence (the dimension of the smallest face containing an orbit point cannot decrease) enables projective coordinate transfers across towers without separate tower-height cases.
• Cyclic Product & Logarithmic Convexity: The dynamics contract to a cyclic product with an exact real phase: $$\prod_{j=1}^m (\omega^q - \beta_j) = \alpha^m \omega^{mq-s}, \quad \sum_{j=1}^m \arg(\omega^q - \beta_j) = \text{prescribed phase}$$

6.2 Asymptotics of the Radial Deficit ($1 - \rho_N(\theta)$)

From their scalar boundary equation, Verbeken and Ginis established the asymptotic convergence rate of $\mathcal{K}_N$ toward the unit disk $\mathbb{D}$ as $N \to \infty$:

The Karpelevič region provides the primary single-eigenvalue localization criterion for the general Nonnegative Inverse Eigenvalue Problem (NIEP).

7.1 Individual Eigenvalue Localization vs. Multiset Sufficiency

If a multiset $\sigma = \{\lambda_0, \lambda_1, \dots, \lambda_{n-1}\}$ with Perron root $\lambda_0$ is realizable by an $n \times n$ nonnegative matrix, then:

While containment $\lambda_j/\lambda_0 \in \mathcal{K}_n$ is strictly necessary for each individual eigenvalue, it is not sufficient for the joint spectrum $\sigma$. Joint realizability additionally requires trace nonnegativity $\sum \lambda_j \ge 0$, Loewy-London inequalities, and higher Newton power-sum conditions.

7.2 Structured Stochastic Subclasses

• Stochastic Leslie Matrices (Kirkland 1992): Single-eigenvalue regions for Leslie matrices form a strict subregion of $\mathcal{K}_n$ bounded by roots of Type I polynomials.
• Cycle-Plus-Diagonal Matrices (Ran & Teng 2016; Verbeken et al.): Matrices supported on a single directed cycle and diagonal entries satisfy one-factor logarithmic convexity.
• Doubly Stochastic Matrices (Perfect–Mirsky Problem): Characterizing the set of eigenvalues of doubly stochastic matrices is solved for $n \le 4$, but remains open for $n \ge 5$.

The research hub provides an interactive visualization engine that computes the exact Karpelevič boundary $\partial\mathcal{K}_n$ for dimensions $n = 2$ through $n = 8$, displaying Farey vertices, curvilinear arcs, and testing candidate eigenvalues $(\operatorname{Re}(\lambda), \operatorname{Im}(\lambda))$:

The publications below are sourced directly from the global NIEP Comprehensive Bibliography. Each record provides academic metadata, research context, source/preprint links, and one-click BibTeX exports.