Put a few chips around a circle. A chip can jump forward, but only when the next space is empty. Land on another chip and remove it.
It sounds like a puzzle from a recreational mathematics book. It is also a step in the original proof of the Karpelevich region: the set of possible eigenvalues of stochastic matrices.
The surprise is what a move accomplishes. We change a polygon, and therefore change a realizing matrix, while preserving the eigenvalue we are trying to understand. Complicated configurations can be replaced by simpler ones. Eventually, the surviving possibilities are controlled by a short list of modular records.
Let’s play the game, then unpack why it belongs in a proof about matrices.
First, turn the eigenvector into a polygon
A row-stochastic matrix has nonnegative entries and each row sums to one. If
then its $i$th row says
View the complex coordinates $v_1,\ldots,v_n$ as points in the plane. Each image $\lambda v_i$ is a convex combination of those points. Consequently,
Multiplication by $\lambda$ rotates the polygon by $\arg\lambda$ and scales it by $|\lambda|$. An eigenvalue becomes a rotation and contraction that fits a polygon inside itself.
Figure 1. A concrete example: take $\zeta=e^{2\pi i/5}$ and $\lambda=(1-t)\zeta+t\zeta^2$. For the regular pentagon, numbered counterclockwise, every image is the displayed convex combination of two adjacent vertices. A common rotation of all vertices leaves the construction unchanged. This illustrates invariance; it does not assert radial extremality.
Move the convex-combination weight. The green image vertices stay on the original pentagon’s edges.
λ = (1 − t)ζ + tζ², with ζ = exp(2πi/5). At the endpoints the image equals the pentagon. This demonstration illustrates invariance, not extremal geometry.
The implication also runs backward. Given a nontrivial polygon with $m\leq n$ vertices and $\lambda Q\subseteq Q$, choose convex coefficients for each image vertex. These coefficients form an $m\times m$ stochastic matrix with eigenvalue $\lambda$. If necessary, adjoin an identity block to reach order $n$.
That correspondence lets us work with polygons instead of matrix entries.
The contact pattern we will study
The interesting boundary question is radial: for a fixed angle, how large can $|\lambda|$ be?
We begin after the extremal contact reduction used in the original proof. Its hypotheses matter: $\lambda$ is a nonreal radial extremum of least realizing order $n$. In the orientation considered below, the vertices of an invariant polygon can be numbered counterclockwise so that, for a fixed integer $1\leq k < n$,
All indices are taken modulo $n$. The opposite orientation is handled by complex conjugation. The same contact reduction applies to the invariant polygons obtained during the argument. We use this result as an input; it is the Dmitriev–Dynkin theorem
There are two possibilities:
| Contact | Equation | Board symbol |
|---|---|---|
| Vertex contact | $\alpha_i=0$, so $\lambda z_i=z_{i+k}$ | Empty site |
| Edge contact | $\alpha_i>0$, so $\lambda z_i$ lies strictly inside the indicated edge | Chip |
The board records which vertices have edge contacts. It does not record their positions or the values of the coefficients.
The rules
Number the $n$ sites counterclockwise, $0,1,\ldots,n-1$. Keep the jump length $k$ fixed.
- Choose an occupied site $i$.
- The next site, $i+1$, must be empty.
- Move the chip to $i+k$.
- If the landing site was occupied, remove the chip already there. One chip remains at the destination.
Equivalently, if $S$ is the set of occupied sites, a legal move is
Only the immediately next site is checked. The landing site is allowed to be occupied. These are the rules introduced in Karpelevich’s §3, p. 364
Here is a complete example with $n=7$ and $k=3$:
Figure 2. The occupied sets are $\{0,2,4\}\to\{0,4,5\}\to\{0,1,4\}\to\{0,4\}\to\{0\}$. The moving sites are $2,5,1,4$. The last two moves capture a chip. This is a combinatorial example, without a claim that the starting board comes from a particular extremal polygon.
The search finds a shortest legal path to either one run with a record complement or fewer than g = gcd(n, k) chips. It searches the finite board graph; it does not test whether a board comes from an extremal polygon. A reduced board need not have the globally smallest possible chip count.
Why a legal move preserves the eigenvalue
Suppose there is a chip at $i$ and site $i+1$ is empty. Write $j=i+k$. The two contacts are
Replace the corner $z_j$ by the point $y=\lambda z_i$. Call the resulting polygon $Q'$.
Figure 3. A local schematic. The amber triangle is removed. The next image contact is already at $z_{j+1}$, so the removed corner contains no image vertex that needs to be retained. The diagram shows the contact geometry, rather than a numerically fitted global extremal polygon.
Every image vertex remains in the smaller polygon: the image at $i$ is its new corner $y$, the image at $i+1$ is $z_{j+1}$, and all other image contacts lie on retained edges. Thus
Now apply $\lambda$ to the second inclusion:
So $Q'$ is invariant for the same $\lambda$.
We can also check the chip bookkeeping. Site $i$ is now empty because $\lambda z_i=y$ is a vertex. At the replacement vertex,
Both coefficients are positive, and the two points on the right are distinct and belong to $Q'$. The extremal contact input places $\lambda y$ on the boundary of $Q'$. A strict convex combination of two distinct points on a supporting line lies in the relative interior of an edge. Therefore site $j$ carries a chip. All other contact types stay unchanged.
That is exactly the board move. A capture means two edge contacts have become one.
This is Karpelevich’s corner-replacement lemma in geometric form (§3, Lemma 1)
What does it mean to win?
Call a maximal consecutive string of chips a run. A full board counts as one run.
We want a reachable board with as few runs as possible, and among those, as few chips as possible. This is a finite choice: there are only $2^n$ boards.
It is not an instruction to make every move decrease those numbers. Intermediate moves may make the board look worse. A single chip can keep moving forever. We are selecting a simplest reachable representative.
Let
Concentration lemma
Karpelevich §3, Lemma 3 & Thm. I(a)A simplest reachable nonempty board has either one run, or fewer than $g$ chips.
The key observation is that a run can be moved forward by $k$ by moving its leading chip first, then working backward through the run. In a simplest board, this sweep cannot produce a capture or merge: its final board would have no more runs and would improve one of our two counts.
A complete proof of the concentration lemma
Choose a reachable board minimizing the pair (number of runs, number of chips), in that order. Suppose it has at least two runs.
First, a run of length $L$ must satisfy $L\leq n-k$. Otherwise its leading chip jumps onto another chip of the same run. Removing that leading chip leaves a run, so this would reduce the chip count without increasing the run count.
For $L\leq n-k$, sweep the run from its leading chip backward. Every next site is empty when needed, and no moving chip captures a chip still waiting to move in its own run. The final occupied set is the union of the translated run and the other runs. It has no more runs than before. A capture would reduce its chip count; a merger would reduce its run count. Both contradict minimality. Thus any chosen run can be translated by $k$, with the other runs fixed, and the board remains a minimizer.
Because every translation step keeps the board a minimizer, no step can ever capture a chip or merge two runs: either event would lower one of the two counts. Fix one run $F$ and rotate the labels so that its trailing chip is at site $0$. Then $F$ occupies $0,1,\ldots,L_F-1$. Mark the window $W=\{0,1,\ldots,g-1\}$ of $g$ consecutive sites.
Take another run $G$, of length $L_G$, and translate it repeatedly by $k$. The multiples of $k$ modulo $n$ are exactly the multiples of $g$, so its leading chip visits every site of its residue class modulo $g$. Stop the first time that chip lands at a site $s\in W$. At that moment $G$ occupies $s-L_G+1,\ldots,s$. It cannot overlap or touch $F$, since that would be a capture or a merger. Its sites therefore lie in $L_F+1,\ldots,s$, inside $W$, with an empty site separating it from $F$. In particular $F$ itself lies in $W$.
Place every remaining run the same way, keeping the runs already placed fixed. Each new run also lands inside $W$, separated from the others by empty sites. All chips now lie in the $g$ sites of $W$, and at least one of those sites is empty. Hence there are fewer than $g$ chips.
This proves the lemma: a minimizer with at least two runs has fewer than $g$ chips.
Why geometry rules out the small alternative
The arithmetic map
has $g$ disjoint cycles, each of length $n/g$. They are the residue classes modulo $g$.
Figure 4. With $n=8$ and $k=2$, the even sites form one cycle and the odd sites form another. Fewer than two chips leave one entire cycle without an edge contact.
If there are fewer than $g$ chips, at least one cycle is completely empty. On that cycle every contact is deterministic:
The origin lies inside a nontrivial invariant polygon for a nonreal strict contraction. To see this, first iterate any nonzero point: its images approach the origin, so $0\in Q$. A supporting line through $0$ would put its entire rotation orbit in a closed half-plane, which is impossible for a nonreal rotation. Thus $0$ is interior, and no vertex equals $0$. We obtain
For a strict contraction, $0 < |\lambda| < 1$, this is impossible.
Combine this observation with the concentration lemma: for the strict-contraction extremal case, we can choose an invariant polygon whose edge-contact vertices form one consecutive run. Unit-circle eigenvalues require their own treatment; the contradiction just used does not apply there.
Notice what we have eliminated. A scattered configuration may occur. It simply does not need its own case in the boundary proof, because a simpler polygon realizes the same eigenvalue.
One run is still not an arbitrary run
There is one more reduction. Form the modular orbit
using representatives in $\{0,\ldots,n-1\}$. Keep an entry only when it exceeds every earlier entry. Include $a_0=0$. These entries are the record maxima.
Record condition
Karpelevich §3, Thm. I(b)If a simplest one-run board has $\varphi\geq g$ chips, then $n-\varphi$ is a record maximum of the modular orbit $a_j = jk \bmod n$.
Why the number of empty sites must be a record
The full board gives $n-\varphi=0$, our initial record. Otherwise rotate the board so that its occupied sites are
Keep every chip except the one at $0$ fixed. Move that chip repeatedly by $k$. Its positions follow $a_0,a_1,a_2,\ldots$.
The first time it reaches the interval $\{n-\varphi,\ldots,n-1\}$, it either lands at $n-\varphi$, immediately before the stationary run, or captures one of its chips. A capture would leave a single run with fewer chips, contradicting our choice of board. It must therefore reach $n-\varphi$ first, with all its earlier positions strictly smaller.
Why must it reach this interval at all? The orbit visits every multiple of $g$, and an interval of $\varphi\geq g$ consecutive sites contains one. Thus the moving chip cannot circulate forever without encountering it.
Its first encounter is exactly a record maximum, as claimed.
For $n=7$ and $k=3$,
has records $0,3,6$. The candidate run lengths are therefore
Figure 5. Record heights select the number of empty sites. The complementary numbers select the chip counts. This is a restriction on reduced representatives, not a claim that every listed board is geometrically realizable.
Green tiles mark strict record maxima, including the initial 0. These give necessary candidates for the reduced representative. Geometric realizability is a further question.
For comparison:
| $n$ | $k$ | $g$ | Record maxima | Candidate one-run chip counts with $\varphi\geq g$ |
|---|---|---|---|---|
| $7$ | $3$ | $1$ | $0,3,6$ | $7,4,1$ |
| $8$ | $3$ | $1$ | $0,3,6,7$ | $8,5,2,1$ |
| $8$ | $2$ | $2$ | $0,2,4,6$ | $8,6,4,2$ |
Together, the concentration argument and the record argument give the game reduction in Karpelevich’s Theorems I and II (§3, pp. 367–368)
Where the series goes next
An arbitrary stochastic eigenvector gave us a polygon. Extremality supplied a contact pattern. The corner cut turned that pattern into a game, and the game reduced it to a consecutive block whose size is constrained by modular arithmetic.
The remaining vertices are connected by chains of exact equations $\lambda z_i=z_{i+k}$. The next question is how long those chains are before they meet the block of edge contacts. Karpelevich organizes those return times using the Euclidean algorithm.
Why the Euclidean algorithm appears in an eigenvalue problem: following the deterministic chains $\lambda z_i = z_{i+k}$ until they meet the block of edge contacts in Why the Euclidean Algorithm Appears in an Eigenvalue Problem →. Or see the series roadmap and Stop 6 (Where the Boundary Equations Come From).
Source and scope
[1] 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. The contact input is in §2, p. 363; the corner cut and game are in §3, p. 364; the game reductions are Theorems I–II, pp. 367–368. English translation: American Mathematical Society Translations, Series 2, 140 (1988), 79–100.
The exposition, illustrations, examples, and interactive boards here are newly prepared. The post proves the game reduction and explains its geometric implementation, taking the stated extremal contact theorem as an input. It does not attempt to derive the complete boundary description or certify arbitrary boards as extremal polygons.