Karpelevič's Theorem & The Karpelevič Region
The complete geometric determination of all complex numbers realizable as eigenvalues of $n \times n$ stochastic matrices, Farey sequence boundary points, and algebraic boundary arcs.
1. Kolmogorov's 1937 Problem & Historical Genesis
In 1937, the celebrated Soviet mathematician Andrey Nikolaevich Kolmogorov posed a deceptively natural question concerning finite-state discrete-time Markov chains:
Kolmogorov's Problem (1937)
What is the set $\mathcal{K}_n$ of all complex numbers that can arise as an eigenvalue of an $n \times n$ stochastic matrix (a nonnegative matrix with all row sums equal to $1$)?
By the classical Perron-Frobenius theorem, any stochastic matrix $A \ge 0$ has spectral radius $\rho(A) = 1$, and $\lambda_0 = 1$ is always an eigenvalue associated with the right all-ones eigenvector $\mathbf{1} = (1, 1, \dots, 1)^T$. Consequently, all eigenvalues lie in the closed unit disk $\overline{\mathbb{D}} = \{z \in \mathbb{C} : |z| \le 1\}$. However, only a strict subset of the unit disk can ever be realized.
In 1946, Nikolai Dmitriev and Eugene Dynkin made the first major breakthrough by establishing the region for dimensions $n = 2, 3, 4$:
- $n = 2$: The interval $[-1, 1]$ along the real axis.
- $n = 3$: An equilateral triangle with vertices at $1, e^{i 2\pi/3}, e^{i 4\pi/3}$, together with the real interval $[-1/2, 1]$, bounded by curved segments connecting the roots of unity to the negative real axis.
- $n = 4$: A shape bounded by chords and curvilinear arcs connecting $1, i, -1, -i$, and the third roots of unity.
In 1951, Fridrikh Izrailevich Karpelevič published a monumental 70-page paper in Izvestiya Rossiiskoi Akademii Nauk delivering the complete, definitive answer for all finite dimensions $n$. This crowning achievement is universally celebrated today as Karpelevič's Theorem.
2. Precise Statement of Karpelevič's Theorem
Let $\mathcal{P}_n$ denote the set of all $n \times n$ stochastic matrices. The Karpelevič region is defined by:
Karpelevič showed that $\mathcal{K}_n$ possesses several fundamental structural properties:
⭐ Star-Shaped at Origin
If $\lambda \in \mathcal{K}_n$, then the entire radial segment $[0, \lambda] = \{t\lambda : 0 \le t \le 1\} \subset \mathcal{K}_n$. In particular, $\mathcal{K}_n$ is simply connected.
Conjugate Symmetry
Since $A$ has real entries, its characteristic polynomial has real coefficients, so $\lambda \in \mathcal{K}_n \iff \bar{\lambda} \in \mathcal{K}_n$.
Roots of Unity
The intersection of $\mathcal{K}_n$ with the unit circle $\partial \mathbb{D}$ consists exactly of all roots of unity of degree $q \le n$: $\mathcal{K}_n \cap \{z : |z|=1\} = \{e^{i 2\pi p/q} : 0 \le p < q \le n\}$.
Monotonic Tower
Any stochastic matrix of size $m < n$ can be embedded into an $n \times n$ stochastic matrix, guaranteeing $\mathcal{K}_2 \subsetneq \mathcal{K}_3 \subsetneq \cdots \subsetneq \mathcal{K}_n \subsetneq \mathbb{D}$.
3. Boundary Geometry & The Farey Sequence
The boundary $\partial \mathcal{K}_n$ in the upper half-plane $\operatorname{Im}(z) \ge 0$ is a continuous piecewise curve connecting consecutive roots of unity. The ordering of these boundary vertices is governed by the Farey sequence of order $n$, denoted $\mathcal{F}_n$.
Definition: Farey Sequence $\mathcal{F}_n$
The Farey sequence $\mathcal{F}_n$ is the sequence of completely reduced fractions between $0$ and $1$ whose denominators do not exceed $n$, arranged in increasing order:
$$\mathcal{F}_n = \left\{ \frac{p}{q} : 0 \le p \le q \le n, \; \gcd(p, q) = 1 \right\}$$Let $p_1/q_1 < p_2/q_2$ be two consecutive fractions in $\mathcal{F}_n$. A classical property of Farey fractions guarantees that $p_2 q_1 - p_1 q_2 = 1$. Let $z_1 = e^{i 2\pi p_1/q_1}$ and $z_2 = e^{i 2\pi p_2/q_2}$ be the corresponding roots of unity on $\partial \mathbb{D}$. Karpelevič proved that the boundary arc $\Gamma(z_1, z_2)$ connecting $z_1$ and $z_2$ falls into exactly one of two geometric regimes:
| Denominator Sum | Geometric Boundary Nature | Realizing Family | Visual Appearance |
|---|---|---|---|
| $q_1 + q_2 > n$ | Straight Line Segment (Chord) joining $z_1$ and $z_2$: $$\{(1-t)z_1 + t z_2 : 0 \le t \le 1\}$$ | Direct convex combination of permutation matrices of cycles $q_1$ and $q_2$ | Flat facet on $\partial \mathcal{K}_n$ |
| $q_1 + q_2 \le n$ | Curvilinear Arc bowing inward toward the origin, given by the parametric curve of roots of a characteristic polynomial | Rank-one perturbed cyclic permutation blocks with varying weights | Smooth concave-inward arc touching $0$ or intermediate points |
When $q_1 + q_2 \le n$, the boundary arc curves strictly inside the unit disk. As $n$ increases, the number of straight segments diminishes relative to curvilinear arcs, and $\mathcal{K}_n$ gradually fills the unit disk $\mathbb{D}$ as $n \to \infty$.
4. Ito's Algebraic Polynomial Formulation (1997)
For nearly fifty years after Karpelevič's 1951 paper, his theorem was considered notoriously difficult to implement numerically or verify algebraically because his original parametric description required finding roots of a high-degree transcendentally weighted polynomial pencil.
In 1997, Hisashi Ito published a monumental simplification in Linear Algebra and its Applications, deriving closed-form implicit algebraic equations for every curvilinear boundary arc of $\mathcal{K}_n$.
Ito's Theorem (1997)
Let $p_1/q_1$ and $p_2/q_2$ be adjacent in $\mathcal{F}_n$ with $q_1 + q_2 \le n$, and let $k = \lfloor (n - q_1) / q_2 \rfloor$. The curved boundary arc between $e^{i 2\pi p_1/q_1}$ and $e^{i 2\pi p_2/q_2}$ in polar coordinates $z = r e^{i\theta}$ is an algebraic curve satisfying:
$$(r^{q_2} \cos(q_2 \theta) - 1)(r^{q_1} \sin(q_1 \theta)) = (r^{q_2} \sin(q_2 \theta))(r^{q_1} \cos(q_1 \theta) - \alpha(r, \theta))$$where $\alpha(r, \theta)$ is an explicit rational function of $r$ and $n$, yielding an exact polynomial relation $P_{p_1, q_1, p_2, q_2}(r, \theta) = 0$.
Ito's breakthrough allowed rapid, exact computer visualization of $\mathcal{K}_n$ for arbitrary $n$, and enabled Charles Johnson, Raphael Loewy, and others to formulate fast containment algorithms to determine whether an arbitrary candidate eigenvalue $\lambda \in \mathbb{C}$ belongs to $\mathcal{K}_n$.
5. Significance for the General NIEP
How does Karpelevič's region relate to the general Nonnegative Inverse Eigenvalue Problem?
Individual Eigenvalue Localization
If a multiset $\sigma = \{\lambda_0, \lambda_1, \dots, \lambda_{n-1}\}$ is realizable by an $n \times n$ nonnegative matrix with spectral radius $\lambda_0$, then every single eigenvalue must satisfy: $$\frac{\lambda_j}{\lambda_0} \in \mathcal{K}_n \quad \forall j=1, \dots, n-1$$ This provides the ultimate single-eigenvalue necessary condition for the NIEP.
The Multiset Gap
Containment $\lambda_j / \lambda_0 \in \mathcal{K}_n$ is necessary for each individual eigenvalue, but far from sufficient for the joint multiset $\sigma$. For example, all $\lambda_j$ may lie in $\mathcal{K}_n$, but their sum (trace) may be negative, violating $\operatorname{Tr}(A) \ge 0$.
Consequently, the Karpelevič region represents the 1-dimensional projection of the full $n$-dimensional semi-algebraic realizability domain $\mathcal{E}_n$ onto a single eigenvalue coordinate in the complex plane.
6. Interactive Visualizer & Real-Time Exploration
Our research hub includes an interactive visualization engine that renders the exact Karpelevič boundary $\partial \mathcal{K}_n$ for dimensions $n = 2$ through $n = 8$, displaying Farey vertices, curvilinear arcs, and testing user-entered test points $(\operatorname{Re}(\lambda), \operatorname{Im}(\lambda))$.
Interactive Karpelevič Region Viewer
Explore the boundary curves, adjust matrix dimension $n$, and test arbitrary complex eigenvalues live in Canvas.
7. See Also & Related Articles
NIEP Theoretical Survey
Master background covering Perron-Frobenius foundations, trace inequalities, and semi-algebraic geometry.
Symmetric NIEP (SNIEP)
Orthogonal eigenspaces, Soules bases, Fiedler matrices, and polyhedral spectra geometry.
Real NIEP (RNIEP)
Real spectra realized by non-symmetric nonnegative matrices and the Laffey-Loewy separation spectrum.
Suleimanova Spectra
Spectra with a single positive eigenvalue, trace sufficiency, and constructive companion/Fiedler realizations.