The chip game gives us a simpler polygon. What does the rest of the proof do with it?
It reads the polygon’s contact pattern as arithmetic, uses geometric variations to force rigidity, and turns the resulting relations into equations. A final argument places those equations in the right angular sectors and assembles the boundary.
This guide maps that nine-stop journey. Each stop identifies a question, the result that answers it, and the next piece it makes possible, followed by a shared notation table and a proof ledger recording what is proved in the series, what is cited from 1946–1951, and where the modern literature completes the boundary description.
The destination: one region, two descriptions
Write
We want to know exactly what this region looks like. The unit circle provides landmarks: the possible eigenvalues on it are roots of unity whose orders are at most $n$. Between consecutive landmarks, the boundary follows particular algebraic arcs.
Karpelevich’s original paper
| Conclusion | What it describes |
|---|---|
| Theorem A: cyclic polygons | The entire region as a union of a special family of polygons with at most $n$ vertices. |
| Theorem B: boundary arcs | The boundary through its unit-circle endpoints and equations for the intervening arcs. |
These conclusions share much of the same machinery. Our map keeps both visible, and states both theorems explicitly in the standardized notation used throughout the series:
Theorem A — Cyclic-Polygon Covering (Karpelevich 1951)
Stop 8For every $\mu\in\mathbb C$ and integer $h\geq1$ with $\varepsilon=e^{2\pi i/h}$, let $C(\mu,h)$ denote the closed convex hull of the orbit $\{\mu^m\varepsilon^j:m\geq0,\ 0\leq j<h\}$ whenever that hull is a finite polygon. For every $n\geq2$,
Theorem B — Boundary Arcs in Ito’s Unified Form (Karpelevich 1951; Ito 1997)
Stop 6 · Stop 7 · Stop 9The region $\mathcal K_n$ ($n\geq2$) is compact, star-shaped with respect to $0$, and symmetric across the real axis. Its intersection with the unit circle consists of all roots of unity $e^{2\pi i a/b}$ with $a/b\in F_n$. For each adjacent pair $a/b<c/d$ in the Farey sequence $F_n$, put
Then the outer boundary of $\mathcal K_n$ in the angular sector $[2\pi a/b,2\pi c/d]$ is the curve connecting $e^{2\pi i a/b}$ to $e^{2\pi i c/d}$ traced by the unique root of maximum modulus in each direction of the reduced equation
which reduces to Family I, $\lambda^\tau(\lambda^\ell-t)^m=(1-t)^m$ with $\tau=s-\ell m$, when $s\geq\ell m$, and to Family II, $(\lambda^\ell-t)^m=(1-t)^m\lambda^\sigma$ with $\sigma=\ell m-s$, when $s<\ell m$.
Figure 1. A dependency map of the main ideas. The numbers identify the stops below. The cyclic-polygon conclusion uses the extremal relations and angular estimates; the boundary branch continues through Farey bookkeeping and induction on the order.
Select a stop to see its input, its operation, and the result the next steps can use.
Matrices → polygons
Extremal contacts
The chip game
Return arithmetic
Geometric rigidity
Algebraic relations
Angular placement
Cyclic polygons
Boundary induction
Replace a matrix by an invariant polygon
The first change is one of viewpoint. For a stochastic matrix, the eigenvector equation says
The complex coordinates of the eigenvector therefore form a polygon
Conversely, convex coefficients for the image vertices of an invariant polygon give the rows of a stochastic matrix. Fewer than $n$ vertices can be accommodated by adjoining a stochastic block.
What this accomplishes: the existence of a matrix becomes the existence of a polygon that contains its rotated and scaled image.
The foundational post also explains normalization, conjugate symmetry, nested orders, and radial sections. For an irreducible nonnegative matrix, the familiar normalization uses a positive Perron eigenvector; Stop 1 proves the Frobenius block reduction that handles reducible matrices without losing any nonreal eigenvalue.
Published · Stop 1 From Matrix Rows to Convex Hulls →
Ask what a genuinely extremal polygon must do
Fix an angle and consider the farthest realizable point along that ray. For nonreal directions, write its modulus as
To study a new part of the boundary at order $n$, separate it from points already realizable at smaller order. The extremal contact theorem then organizes the image vertices along the polygon’s edges. In the orientation used in our game post, it gives
Indices are cyclic, and $k$ is fixed for the configuration. The conjugate orientation handles the complementary case.
What this accomplishes: a general invariant polygon acquires a controlled contact pattern. Each image is either a vertex contact or an interior point of a specified edge.
This is an important input from Dmitriev and Dynkin
Published · Stop 2 What Extremality Forces →
Play the game to concentrate the edge contacts
Place a chip at each vertex whose image lies in the interior of an edge. A legal jump corresponds to replacing a corner of the polygon while preserving
The game lets us choose a simpler representative of the same eigenvalue. For the nonreal strict-contraction case under the contact hypotheses, the edge-contact vertices can be concentrated into one consecutive block. The possible reduced block sizes are further restricted by records in the orbit $0,k,2k,\ldots\pmod n$.
What this accomplishes: the later proof can work with one organized block of edge contacts and the deterministic chains attached to it.
This is the stage covered in Karpelevich’s Game. The reduction concerns representatives: a scattered pattern may occur, but it need not receive its own case in the boundary analysis.
Published · Stop 3 Karpelevich’s Game →
Read the deterministic chains using the Euclidean algorithm
Away from an edge contact, the equation is exact:
Following these equalities gives chains
that eventually reach an edge-contact relation. The index map $i\mapsto i+k\pmod n$ controls when that happens.
Here the modular records from the game connect to the Euclidean algorithm. For example,
encodes much more than the fact that $7$ and $3$ are coprime: the remainder structure organizes the returns. In the original proof, Theorems III and IV give the return relations for the two cases determined by the block size and $\gcd(n,k)$.
What this accomplishes: the polygon’s vertices fall into power-generated chains whose lengths and connections can be described arithmetically.
Published · Stop 4 Why the Euclidean Algorithm Appears in an Eigenvalue Problem →
Use variations to force geometric rigidity
The game simplifies a configuration. Geometric variation places stronger restrictions on the configurations that survive.
The strategy is to move selected generating vertices and propagate those moves along their chains. If the perturbed polygon remains invariant while an image vertex moves into its interior, it contradicts the extremal contact theorem. This eliminates certain return patterns. Further variations force the relevant edge-contact coefficients to agree.
Figure 2. The logical role of a variation. A proposed motion must preserve polygon invariance. If it also creates an interior image contact, the assumed extremal configuration cannot persist. This is a schematic of the argument, not a claim that every direction of motion is permissible.
One striking ingredient is projective geometry. Successive projections turn a displacement on one line into a fractional linear return map. Comparing the returned displacement with the starting one supplies the needed variation in the nondegenerate cases.
What this accomplishes: a collection of separate contact coefficients collapses to a common parameter, and only particular chain structures remain. Theorem V and the variation arguments in Theorems VI–VII occupy the core of §4.
Published · Stop 5 Moving Polygons Until the Weights Agree →
Eliminate the vertices and obtain equations
Once the chain relations and contact weights are controlled, the coordinates can be eliminated. In our standardized series notation, the two characteristic forms are
and
Here $\ell$ is the chain length, $m=\lfloor n/\ell\rfloor$ is the number of repeated chains, $\tau$ ($0\leq\tau<\ell$) is the closing tail in the first form ($n=\ell m+\tau$), and $\sigma$ ($0<\sigma<\ell$) is the closing shift in the second ($n=\ell m$). Both combine into Ito’s unified equation $\lambda^s(\lambda^\ell-t)^m=(1-t)^m\lambda^{\ell m}$.
These are the two reduced equation families. For instance, the running example below is the first family with $\tau=1$, $\ell=3$, $m=1$: it reads $\lambda(\lambda^3-t)=1-t$, and indeed $\ell m+\tau=4=n$.
The detailed post defines their exponents precisely and derives them from the contact equations.
What this accomplishes: geometry produces a small set of algebraic candidates for the boundary. Identifying the appropriate root branch and proving its extremality remain part of the argument.
Published · Stop 6 Where the Boundary Equations Come From →
A small example to keep in view
One simple family makes the preceding transformations concrete:
For an eigenvalue $\lambda$, the vector $(1,\lambda,\lambda^2,\lambda^3)^T$ closes up precisely when
There are three deterministic steps and one convex-combination relation. The upper nonreal root traces a curve from $i$ to $e^{2\pi i/3}$. At $t=5/8$, one point is exactly
Figure 3. The teal curve follows the upper nonreal root of the displayed polynomial. Its endpoints are $i$ and $e^{2\pi i/3}$. The amber point is the exact example at $t=5/8$; the right-hand drawing is its invariant polygon.
The matrix realizes this curve. Its role as an outer boundary arc requires the extremal argument. Coordinates in the explorer are numerical; the identity and the point at t = 5/8 are exact in the article. At t = 1, two listed powers coincide and the polygon becomes a triangle.
The matrix proves realizability of this curve. The remaining proof machinery explains why the corresponding curve is the outer boundary in this angular sector. This example will serve as a guide when the general notation becomes more involved.
Locate the curves using angles and Farey neighbors
An equation can have several roots. Its unit-circle limits can also contain several roots of unity. We need to determine which roots belong to a particular boundary arc.
Geometric angle estimates and integer congruences provide that information. The relevant rational angles are organized by the Farey sequence of order $n$: the reduced fractions in $[0,1]$ with denominator at most $n$.
For consecutive fractions $a/b<c/d$ in that sequence,
Their associated landmarks are $e^{2\pi ia/b}$ and $e^{2\pi ic/d}$. The same integer arithmetic that controlled the contact chains now helps place the candidate curves in angular order.
The running example fits this pattern. Its endpoints $i=e^{2\pi i\cdot 1/4}$ and $e^{2\pi i\cdot 1/3}$ come from the neighbours $1/4<1/3$ in the Farey sequence of order $4$: here $4\cdot1-1\cdot3=1$ and $4+3>4$.
What this accomplishes: algebraic relations acquire angular locations and identified endpoints. The angular estimates are Theorems VIII–IX; the Farey organization enters the final assembly in §5.
Published · Stop 7 Why Farey Neighbors Label the Arcs →
Follow the other branch: cyclic polygons
Before finishing the boundary description, the original proof obtains another geometric result. Its extremal relations lead to membership in a cyclic polygon, and this yields Theorem A’s union description of $\mathcal K_n$.
Here “cyclic” means generated by geometric progressions, with a possible finite rotational symmetry. It is a specific definition in the paper. It does not mean merely that a polygon has vertices on a circle.
There are also two different uses of polygons to distinguish. An invariant eigenvector polygon is a witness for one eigenvalue: it contains its own image under multiplication by that eigenvalue. The polygons in Theorem A collectively describe the eigenvalue region itself.
What this accomplishes: the argument gives a geometric description of the whole region, alongside its eventual boundary equations. Theorem X and the deduction of Theorem A appear on p. 379.
Published · Stop 8 Cyclic Polygons and the Whole Region →
Assemble the boundary by induction on the order
The regions are nested:
Consequently, the boundary at order $n$ can include pieces inherited from a smaller order, as well as newly exposed pieces. The final stage must determine which are which.
Karpelevich uses induction, angular sectors, and the preceding equation families to complete that comparison. The analysis also rules out putative boundary points that admit an invariant polygon with strictly interior image vertices: such a polygon has room for a small radial expansion.
What this accomplishes: the candidate pieces become a complete boundary description. Every nonreal outer boundary point is accounted for, the endpoints are placed in circular order, and the appropriate equations are assigned to the arcs. The low-order cases and unit-circle endpoints supply the necessary starting and limiting cases.
Published · Stop 9 Closing the Boundary: Old Arcs, New Arcs, and Induction →
The series at a glance
| Stop | The question for its post |
|---|---|
| 1. Matrices and polygons | Why does a stochastic eigenvalue have an invariant polygon witness? |
| 2. Extremal contacts | What does radial extremality force, and under which hypotheses? |
| 3. The game | How can we simplify contacts while keeping the eigenvalue? |
| 4. Return arithmetic | How do the Euclidean remainders determine the chains? |
| 5. Geometric rigidity | Which patterns admit a variation, and why must weights agree? |
| 6. Equations | How do the polygon coordinates disappear? |
| 7. Angles and Farey neighbors | Which roots and endpoints belong together? |
| 8. Cyclic polygons | How does the proof describe the whole region? |
| 9. Induction | Why do the identified pieces exhaust the boundary? |
The game sits near the start of this structure. It prepares a polygon that arithmetic can read. Rigidity then makes that arithmetic restrictive enough to produce equations, and the final geometric and inductive arguments turn those equations into a theorem about the region.
Standard notation across the series
Karpelevich’s 1951 paper reuses letters across sections ($q$ for chip count, Euclidean step count, and tail exponent; $d$ for $\gcd(n,k)$, chain count, and cyclic-polygon symmetry). Throughout this monograph series we use a single collision-free notation:
| Symbol | Meaning | Where introduced |
|---|---|---|
| $n,\ \mathcal K_n$ | Matrix order and the region of eigenvalues of $n\times n$ row-stochastic matrices. | Stop 1 |
| $k,\ g=\gcd(n,k)$ | Fixed cyclic contact shift $\lambda z_i=\alpha_i z_{i+k-1}+\beta_i z_{i+k}$ and cycle count of $i\mapsto i+k\pmod n$. | Stop 2, Stop 3 |
| $\varphi,\ r$ | Reduced consecutive edge-contact run length $\varphi$ and Euclidean remainder $r\equiv\varphi\pmod{r_{2j-1}}$. | Stop 3, Stop 4 |
| $p,q$ and $U,L$ | Record return times ($p,q$) and spatial gaps ($U,L$) in the subtractive Euclidean identity $pU+qL=n$. | Stop 4 |
| $F_n,\ a/b<c/d$ | Farey sequence of order $n$ and neighboring reduced fractions satisfying $bc-ad=1$ and $b+d>n$. | Stop 7 |
| $f/b<k/n$ | Farey predecessor $f/b$ of the reduced fraction $k/n$ in the chosen orientation ($kb-nf=g$). | Stop 7, Stop 9 |
| $\ell=\min(b,d),\ s=\max(b,d)$ | Smaller and larger Farey denominators; $\ell$ is the chain length and $m=\lfloor n/\ell\rfloor$ is the repetition count. | Stop 6, Stop 7 |
| $\tau=s-\ell m,\ \sigma=\ell m-s$ | Closing tail $\tau$ ($0\leq\tau<\ell$) in Family I and closing shift $\sigma$ ($0<\sigma<\ell$) in Family II. | Stop 5, Stop 6 |
| $t\in[0,1]$ | Common local-return weight ($t=\alpha$ in the forward branch, $t=\beta$ in the gcd branch). | Stop 5, Stop 6 |
| $C(\mu,h)$ | Cyclic polygon generated by powers $\mu^m$ and $h$th roots of unity $\varepsilon=e^{2\pi i/h}$. | Stop 8 |
| $n_*<n$ | Smaller comparison order satisfying $\Gamma_{n-1}\cap S_{n,k}=\Gamma_{n_*}\cap S_{n,k}$. | Stop 9 |
Proof ledger and where the modern route enters
To make the logical status of every step completely transparent, the table below records what is proved in full in the nine stops, what is used as an explicit cited input from Dmitriev–Dynkin (1946) and Karpelevich (1951), and where the series switches to the modern literature (1997–2024) to complete the boundary-arc description cleanly.
| Stop | Proved in full in the post | Cited input & modern completion |
|---|---|---|
| Stop 1 | Matrix rows $\leftrightarrow$ invariant polygons $\lambda Q\subseteq Q$; Perron normalization; Frobenius block reduction for reducible matrices; $0\in\operatorname{int}Q$; unit disk, star-shapedness, compactness, and root-of-unity landmarks. | Classical Perron–Frobenius theorem for irreducible nonnegative matrices; Bolzano–Weierstrass compactness. |
| Stop 2 | Elementary radial-expansion lemma (why all image vertices cannot be strictly interior); resolvent proof that no single image vertex is interior; supporting-line sparsity; $n=2,3$ base regions. | Dmitriev–Dynkin (1946) cyclic-shift ordering $\lambda z_i=\alpha_i z_{i+k-1}+\beta_i z_{i+k}$ (Karpelevich §2, Theorem I). |
| Stop 3 | Corner-cut invariance $\lambda Q'\subseteq\lambda Q\subseteq Q'$; Concentration Lemma onto the window $W=\{0,\ldots,g-1\}$ ($g=\gcd(n,k)$); single consecutive run of length $\varphi$ via strict modular records. | Karpelevich §3, Theorem II (elimination of multiple separate runs via the record-gap game). |
| Stop 4 | Subtractive Euclidean invariant $pU+qL=n$; two-length first-return theorem ($p$ and $p+q$) in both the forward branch ($\varphi>g$) and gcd branch ($\varphi=g$); vertex-budget identity $n=p\varphi+qr$. | Self-contained (Karpelevich §3, Lemma 2 & Theorems III–IV). |
| Stop 5 | Fractional linear return map $u(s)=as/(1+cs)$ under central projection; inward perturbation lemma ($u'(0)\neq1$ and $u'(0)=1$); barycentric two-weight slide forcing $\alpha_1=\cdots=\alpha_m=t$ in both branches. | Karpelevich §4, Theorem V ($r=1\implies g=1$ in the forward branch and the full-block reduction $\varphi=n\implies k=1$). |
| Stop 6 | Elimination along chains for Family I ($\lambda^\tau(\lambda^\ell-t)^m=(1-t)^m$) and Family II ($(\lambda^\ell-t)^m=(1-t)^m\lambda^\sigma$); cycle-expansion determinant proof; equivalence with Ito’s unified equation and matrix realization of all reduced Ito roots. | Ito (1997) |
| Stop 7 | Farey neighbor criterion ($bc-ad=1,\ b+d>n$) and mediant threshold; forward-branch angular lift $f/\ell<\theta<k/n$; Exponent Dictionary identifying $(\ell,s,m,\tau,\sigma)$ for all $\varphi>1$ and $g\geq2$. | Karpelevich §5, Theorems VIII–IX (gcd-branch angle bound); Ito (1997) |
| Stop 8 | Finite closing certificate $\mu^L\in P\implies P=C(\mu,h)$; multiplicative closure $z,w\in C\implies zw\in C$; stochastic matrix realization of every $z\in C$; $n=3$ trace-inequality proof; deduction of Theorem A from radial coverage. | Karpelevich §5, Theorem X (root-extraction covering of new radial extrema by cyclic polygons); Đoković (1990) |
| Stop 9 | Denominator divisibility test ($b\mid n$ or $d\mid n$); comparison-order identity $\Gamma_{n-1}\cap S_{n,k}=\Gamma_{n_*}\cap S_{n,k}$; quantitative interior-image lemma $B(\mu,\delta/M)\subseteq\mathcal K_n$; explicit $n=6$ hexagon witness. | Dmitriev–Dynkin interior-image construction (p. 382); Ito (1997) |
Reading the original paper alongside the series
The original paper has five numbered sections. This series divides it by mathematical task, so several posts will draw on the same section.
| Original location | Main role in our map |
|---|---|
| §1, pp. 361–363 | Statements of Theorems A and B; examples of boundary equations. |
| §2, p. 363 | Stochastic formulation, invariant polygons, and the quoted extremal contact theorem. |
| §3, pp. 364–371 | The game, modular records, Euclidean arithmetic, and return relations. |
| §4, pp. 372–377 | Polygon variations, coefficient rigidity, and the two equation families. |
| §5, pp. 377–383 | Angular estimates, cyclic polygons, Farey bookkeeping, and boundary induction. |
F. I. Karpelevich, On the characteristic roots of matrices with nonnegative elements, Izv. Akad. Nauk SSSR Ser. Mat. 15 (1951), 361–383. Original paper and scan. English translation: American Mathematical Society Translations, Series 2, 140 (1988), 79–100.
This roadmap outlines the nine-stop argument, standardizes the notation across all chapters, and records where the modern formulations of Ito (1997), Johnson–Paparella (2017), Kirkland–Laffey–Šmigoc (2020), and Munger–Nickerson–Paparella (2024) complete the boundary-arc description.
From Matrix Rows to Convex Hulls: an eigenvector becomes a geometric witness. Or begin with the game: Karpelevich’s Game.