We have reached the last comparison. The contact equations produce algebraic candidates. The angular estimates place them between the right roots of unity. The cyclic polygons describe the whole eigenvalue region. What remains is to decide which pieces form its boundary at each order.
The regions are nested:
An old boundary point stays realizable. It may remain on the outside, or the larger order may put new realizable points beyond it. Karpelevich's final induction separates those possibilities.
The answer involves a surprisingly simple arithmetic test. The geometric reason behind it is that a polygon whose image vertices all lie strictly inside has room to realize nearby multipliers.
Nested regions do not have nested boundaries
Write directions in turns, and let
Compactness makes this maximum exist. The invariant-polygon correspondence gives the radial segment beneath it. Nesting tells us $R_n(\theta)\geq R_{n-1}(\theta)$; it does not decide whether equality holds.
Let $\Gamma_n$ denote this radial outer frontier. We will work in open angular sectors between the unit-circle landmarks, treating the landmarks and the real-axis endpoints separately.
Our running example is the sector
between $i$ and $\omega=e^{2\pi i/3}$. Its order-four arc survives unchanged at order five. At order six it moves outward, although its two endpoint labels stay the same.
Figure 1. These curves are drawn from explicit algebraic parameterizations, without numerical root tracking. Gray is the common order-four and order-five arc; teal is the order-six arc. The amber point is $\lambda_0=(-1+i\sqrt{11})/4$ on the old arc.
This cannot be explained by inserting a new unit-circle landmark: the first fraction between $1/4$ and $1/3$ has denominator $4+3=7$.
The final arithmetic test
Take neighboring reduced fractions $a/b<c/d$ in the Farey sequence $F_n$. From stop 7,
The final induction gives the following rule for the open arc in that sector, with the order-four case supplied as the base:
| Denominators at order $n$ | What happens to the arc |
|---|---|
| Neither $b$ nor $d$ divides $n$ | It is inherited from order $n-1$. |
| At least one of $b,d$ divides $n$ | Its open outer arc is new at order $n$. |
“New” here means outside $\mathcal K_{n-1}$. It does not require new endpoint landmarks.
There are two ways the second row can occur. A denominator equal to $n$ introduces a new primitive $n$th root. A proper divisor of $n$ is an existing endpoint whose neighboring arc can change when the order increases.
The elementary identity behind the bookkeeping is
If neither denominator divides $n$, both already occur in $F_{n-1}$, the pair is still neighboring there, and the relevant division quotients remain unchanged. This preserves the inductive equation data. The geometric argument below is what proves that the old curve remains outermost.
Figure 2. An angular map for order eight: gray gaps are inherited from order seven; teal gaps carry new arcs. The guide semicircle shows directions, not the boundary's radius. Four upper-half arcs are inherited and seven are new. Some new arcs have two existing endpoints.
The colors follow the denominator rule established by the induction. The semicircle is an angular guide and assigns no boundary radius. An inherited interval retains both its endpoints and its old outer arc; a new interval can also have two existing endpoints.
For our running sector the test is immediate:
| Order | Endpoint denominators | Outcome |
|---|---|---|
| $4$ | $4,3$ | The order-four base arc. |
| $5$ | $4,3$ | Neither divides five: inherited. |
| $6$ | $4,3$ | Three divides six: a new outer arc. |
We now need the reason that “new” really means farther out.
Strictly interior images exclude a boundary point
Here is the local lemma doing the decisive work.
Suppose $Q$ is a genuine two-dimensional convex polygon with vertices $v_1,\ldots,v_k$, where $k\leq n$, and every $\mu v_j$ lies in its interior. Put
If $|\nu-\mu|<\delta/M$, then
Every $\nu v_j$ is still inside $Q$. Convexity gives $\nu Q\subseteq Q$, so the polygon correspondence realizes $\nu$ at order at most $n$. Consequently,
The point $\mu$ is an interior point of the eigenvalue region. In particular, if $\mu\ne0$, a small radial expansion $(1+\varepsilon)\mu$ is realizable. Thus $\mu$ cannot remain on the radial outer frontier.
One interior image would not suffice for this lemma: the positive minimum requires all image vertices to be strictly interior. This differs from the variation contradictions used earlier for a new extremum, where the contact theorem already required every image vertex to be on the contour.
An exact old point that order six buries
Return to
Its four-state closing relation is
At order six, use the regular hexagon
This hexagon is described by
For $\lambda_0$, both inequalities are strict: $\sqrt{11}/4<\sqrt3/2$ and $(1+\sqrt{11/3})/4<1$. Rotational symmetry places every $\lambda_0v_j$ strictly inside $Q$. The lemma therefore proves that $\lambda_0$ is interior to $\mathcal K_6$.
We can even exhibit an exact outward move:
For this point, the first hexagon inequality follows from
For the other inequality, use $\sqrt{11/3}<2$ to obtain $33(1+\sqrt{11/3})/128<99/128<1$. Again all six image vertices are strictly interior.
Figure 3. The regular hexagon is the invariant witness. Gray marks the images under $\lambda_0$; amber marks the images under $(33/32)\lambda_0$. Both lie strictly inside. This certifies one exact instance of an old boundary point becoming interior; a fixed regular hexagon is not claimed to handle the entire old arc.
The first contact with this hexagon occurs at $r=\sqrt{12/11}$.
The slider uses r=1+u/1024 for integer u from 0 to 128. In this range, the other hexagon inequalities stay strict, so the sign of 12−11r² decides whether all six image vertices are strictly interior. A failed hexagon test makes no claim about the full eigenvalue region. No boundary curve is inferred from the slider.
How the induction applies this exclusion everywhere needed
Assume the boundary description is known at every smaller order, starting from the order-four result of Dmitriev and Dynkin. Recall the chosen-orientation sectors from the angular estimates:
where the predecessor is specified by
Thus $f/b$ is the Farey predecessor of the reduced fraction $k/n$. The opposite contact orientation is handled by conjugation.
Karpelevich first identifies the old boundary visible in each such sector with a boundary at a smaller comparison order $n_*<n$:
Here intersections with an interval mean intersections with its open angular sector. In a compact version of the original bookkeeping,
where $\ell$ is the smaller denominator of the two Farey neighbors bracketing $k/n$ when it is reduced, and $b$ is the predecessor denominator when $g>1$.
For example, at $n=6,k=2$, the sector is $(1/4,1/3)$ and $n_*=4$: it is precisely the old order-four arc that is visible at order five. At $n=8,k=3$, the bracketing denominators are three and five, giving $n_*=3\lfloor7/3\rfloor=6$.
Why these comparison orders preserve the inductive data
If $g=1$, the two neighbors bracketing $k/n$ have denominators $b_-,b_+$ with $b_-+b_+=n$. They were neighbors in $F_{n-1}$. Put $\ell=\min(b_-,b_+)$ and $s=\max(b_-,b_+)$. Then $s\leq n_*\leq n-1$, the pair is still neighboring in $F_{n_*}$, and division by either denominator gives the same quotient at $n_*$ as at $n-1$. The special end sectors give $n_*=n-1$.
If $g>1$, write $k/n=c/d$ in lowest terms, so $n=gd$. The predecessor denominator satisfies $n-d<b<n$. In particular $b>n/2$ and $\lfloor b/d\rfloor=\lfloor(n-1)/d\rfloor=g-1$. The same Farey interval and quotient data already occur at order $b$.
Applying the inductive equation rules gives the displayed old-boundary comparison. These are the divisions checked in §5(c), equations (30)–(34), of the original paper.
The remaining geometric input is crucial: for every old boundary point in this open sector, an order-$n$ polygon can be constructed with all image vertices strictly interior. The original paper invokes methods of Dmitriev and Dynkin for this construction on p. 382. We use that general construction as a cited input; the hexagon calculation above supplies one fully explicit instance.
Now suppose an order-$n$ outer point in $S_{n,k}$ were already in $\mathcal K_{n-1}$. It would have to lie on $\Gamma_{n-1}$, since a farther old point would contradict its order-$n$ extremality. The comparison puts it on $\Gamma_{n_*}$. The interior-image construction and our lemma then make it interior to $\mathcal K_n$, a contradiction.
Therefore the open order-$n$ frontier in $S_{n,k}$ is new. The canonical contact relations apply to it.
The two cases now exhaust the boundary
Take any Farey interval $(a/b,c/d)$ at order $n$.
If neither denominator divides $n$, this interval is outside every new sector $S_{n,k}$ and its conjugate. Indeed, an endpoint represented as $k/n$ has reduced denominator dividing $n$. The angular estimates therefore exclude a new extremum here. The outer point is old, hence lies on the inherited boundary. The unchanged quotient data preserve its equation.
If an endpoint denominator divides $n$, write that endpoint as $k/n$; use conjugation if it is the left endpoint. This is one of the sectors just treated. Its old boundary lies inside the larger region, and its new frontier has one of the two canonical relations from stop 6:
or
For a Farey pair $(a/b,c/d)$ with smaller denominator $\ell=\min(b,d)$, larger denominator $s=\max(b,d)$, and repetition count $m=\lfloor n/\ell\rfloor$, the exponent dictionary of Stop 7 gives $\tau=s-\ell m$ ($n=\ell m+\tau$) in the first family and $\sigma=\ell m-s$ ($n=\ell m$) in the second. Both are cases of Ito’s unified equation $\lambda^s(\lambda^\ell-t)^m=(1-t)^m\lambda^{\ell m}$. Inherited arcs retain their smaller-order equations, which are given by the exact same formula because $\lfloor n/\ell\rfloor=\lfloor(n-1)/\ell\rfloor$ whenever neither $b$ nor $d$ divides $n$.
Figure 4. Angular coverage rules out new extrema in the inherited case. In a new sector, the smaller-order comparison and strict-interior construction rule out old outer points. These complementary exclusions complete the selection of the boundary pieces.
For the running example, the equations are
In the open sector $(1/4,1/3)$, the second relation selects $\lambda^3+(1-t)\lambda-t=0$: the imaginary part of $\lambda^3$ is negative, so the negative square-root sign is forced. Selecting that cubic factor retains the six-state realization of the full characteristic relation.
An exact way to draw the two worked arcs
The order-four polynomial has a factor $\lambda-1$. Factoring its remaining cubic at its real root $-u$ gives, for $0\leq u\leq1$,
For the selected order-six cubic, let $u$ be its positive real root. Then
Both formulas are exact substitutions into the displayed equations. Their drawing coordinates are evaluated numerically. The inductive argument, rather than the drawing, establishes their boundary role.
Taking the angular sectors in circular order, adjoining their unit-circle endpoints, and reflecting in the real axis yields the boundary described by Theorem B. Every open sector has been assigned to one of the two cases.
Route change: how the modern literature closes the boundary description
Modern completion · 1997–2024Karpelevich’s 1951 paper finishes Theorem B by combining his multi-branch contact classification with the general Dmitriev–Dynkin interior-image perturbation on pp. 380–383. Rather than reconstructing that perturbation for arbitrary Farey sectors or the single-contact branch selection noted in Stop 7, we close the remaining steps using four modern results:
- Unified sector equation (Ito 1997)
. For every adjacent Farey pair $a/b<c/d$ in $F_n$, with $\ell=\min(b,d)$, $s=\max(b,d)$, and $m=\lfloor n/\ell\rfloor$, the boundary of $\mathcal K_n$ in the closed sector $[2\pi a/b,2\pi c/d]$ is governed by the single reduced equation $\lambda^s(\lambda^\ell-t)^m=(1-t)^m\lambda^{\ell m}$ ($0\leq t\leq1$), unifying the forward branch, the gcd branch, and inherited arcs. - Stochastic matrix realization (Stop 6; Johnson–Paparella 2017)
. Every root of every reduced Ito polynomial for $t\in[0,1]$ is an eigenvalue of an explicit $n\times n$ stochastic companion-chain matrix constructed in Stop 6. - Unique polar boundary branch (Kirkland–Laffey–Šmigoc 2020)
. In each open Farey sector $(2\pi a/b,2\pi c/d)$, the reduced Ito equation has a unique root of maximum modulus in each direction $\theta$, tracing a $C^1$ boundary arc connecting $e^{2\pi i a/b}$ to $e^{2\pi i c/d}$. - Simple monotone arcs and radial extremality (Munger–Nickerson–Paparella 2024)
. The reduced Ito arc in each Farey sector is a simple curve whose argument varies strictly monotonically with $t\in[0,1]$, establishing radial extremality for $n>3$ directly from the reduced polynomials.
What the series has established
The original proof gives two descriptions of the same region. Theorem A covers it with cyclic polygons. Theorem B identifies its outside through ordered unit-circle landmarks and the equations of the intervening arcs.
The chip game prepared a polygon whose chains could be read arithmetically. Variations forced the common weights. Elimination produced equations, and angles placed their roots. The last induction decides which equations remain visible at each order.
The final selection rests on both sides of the argument: the inherited sectors admit no new extremum, while the new sectors admit no surviving old outer point. That completes the route from stochastic matrix rows to the Karpelevich boundary.
You have reached the conclusion of the nine-stop guide through F. I. Karpelevič’s 1951 proof. Return to the Series Roadmap to review the dependency map, jump to Stop 1: From Matrix Rows to Convex Hulls, or explore the Interactive Karpelevič Region Explorer.
Source and scope
F. I. Karpelevich, On the characteristic roots of matrices with nonnegative elements, Izv. Akad. Nauk SSSR Ser. Mat. 15:4 (1951), 361–383. Original paper. The final induction is §5, pp. 380–383: angular coverage in (a)–(b), smaller-order comparisons and the interior-image construction in (c), then arc selection in (d)–(e).
This post proves the arithmetic checks, the local interior-image lemma, and the exact hexagon example, and explains the assembly of the induction. It uses the earlier contact and angle theorems, the inductive equation rules, and the original paper's general interior-image polygon construction, and records how Ito (1997), Johnson–Paparella (2017), Kirkland–Laffey–Šmigoc (2020), and Munger–Nickerson–Paparella (2024) complete the explicit arc parameterization and radial-extremality verification. The diagrams and explorers illustrate these steps; numerical drawing coordinates do not establish extremality.