An invariant polygon can have plenty of room inside it. Its rotated, contracted image can sit comfortably away from every edge.
An extremal eigenvalue behaves differently. At its least realizing order, every image vertex must touch the polygon’s boundary. A theorem of Dmitriev and Dynkin
This is the missing step between the matrix–polygon correspondence and Karpelevich’s chip game. We will separate the elementary lack-of-slack argument from the stronger contact theorem, prove the no-interior-contact conclusion, and work through an exact extremal example.
Two hypotheses do different jobs
Write $\mathcal K_n$ for the eigenvalues of stochastic matrices of order $n$. Recall the geometric translation:
Throughout the main argument, $\lambda$ is nonreal. Its invariant polygons have the origin in their interior.
We need two additional hypotheses:
| Hypothesis | Exact meaning | Its role |
|---|---|---|
| Radial extremality at order $n$ | $\lambda\in\mathcal K_n$ and $c\lambda\notin\mathcal K_n$ for every real $c>1$ | Rules out an outward improvement along the same ray |
| New at order $n$ | $\lambda\notin\mathcal K_{n-1}$ | Rules out a realization with fewer states or fewer polygon vertices |
In particular, every witness with at most $n$ vertices must have exactly $n$ vertices. Otherwise the reverse construction from Stop 1 would put $\lambda$ in $\mathcal K_{n-1}$.
The order matters. Padding a smaller matrix with an identity block does not produce a new least-order configuration. Nor can we apply the contact theorem merely because a point lies somewhere on the topological boundary: the hypothesis here is specifically radial extremality.
If the whole image is interior, expand it
Suppose every image vertex lies strictly inside $Q$. There are finitely many vertices and edges, so a small outward expansion still fits:
The same polygon now realizes a larger eigenvalue on the same ray. Such a $\lambda$ cannot be radially extremal.
Figure 1. For $Q=\operatorname{conv}\{1,i,-1,-i\}$ and $\lambda=1/4+i/2$, invariance of $c\lambda Q$ is equivalent to $3c/4\leq1$. Thus the initial image has room to expand. At $c=4/3$, its vertices reach the edges. This calculation concerns the fixed square; it does not establish the outer boundary of the full order-four region.
$\lambda=\frac14+\frac12i$
This test concerns the fixed square. A failed containment test does not exclude a different polygon. Readouts are rounded; the first-contact factor 4/3 is exact.
A finite-inequality proof of the expansion claim
Write the polygon as an intersection of supporting half-planes,
where each $h_\ell$ is a real linear functional. The origin is interior, so each $b_\ell>0$. If the vertices are $z_i$, strict containment says
These are finitely many strict inequalities. By continuity they remain valid when each left side is multiplied by $1+\varepsilon$ for sufficiently small $\varepsilon>0$. Taking convex hulls proves the claim.
This argument only shows that at least one contact is necessary. If one image point already touches an edge, expanding the whole image may fail immediately, even while other image vertices are interior. Getting every image vertex onto the boundary requires an additional argument.
Why even one interior image is impossible
Here is the stronger conclusion, under both hypotheses from Section 1:
One way to understand it is to allow the polygon to move while the multiplier moves. If an image vertex is interior, its convex-combination equation has room to adjust. We can keep the other matrix rows fixed, solve their equations continuously, and use that room to close the remaining row for a slightly larger multiplier.
The following proof makes that idea exact. It is an analytic explanation of the no-interior-contact conclusion; the stronger cyclic organization comes afterward.
A complete proof using one adjustable matrix row
Suppose $\lambda z_i$ is interior. Choose stochastic realizing rows for the polygon and call the matrix $P$. This matrix must be irreducible. Otherwise a smaller diagonal block containing $\lambda$ has spectral radius $\rho\leq1$. Stochastic normalization, as in Stop 1, realizes $\lambda/\rho$ at that smaller order. If $\rho=1$, this contradicts least order; if $\rho<1$, it contradicts radial extremality. Here $\rho>0$ because $\lambda$ is nonreal.
Delete row and column $i$, leaving a nonnegative principal submatrix $B$. Then $\rho(B)<1$. To see this directly, regard $P$ as a finite irreducible Markov chain. From every remaining state there is a positive-probability path to the deleted state. For some common finite number of steps, every row of the corresponding power of $B$ has sum strictly less than one. Hence $\rho(B)<1$.
Also $\lambda\notin\operatorname{spec}B$. Otherwise $\rho(B)>0$ and the nonnegative matrix $B/\rho(B)$, of order $n-1$, would realize $\lambda/\rho(B)$ after stochastic normalization. Since $\rho(B)<1$, that is an outward improvement along the same ray, contradicting extremality at order $n$.
No polygon vertex is zero, so scale all coordinates to make $z_i=1$. Let $z_J$ collect the other coordinates, and let $c$ be column $i$ of $P$ with its $i$th entry removed. The unchanged rows say
For a complex number $\mu$ sufficiently close to $\lambda$, define
These coordinates vary continuously and equal the original coordinates at $\mu=\lambda$. All rows except row $i$ already satisfy the eigenvector equation for $\mu$.
Originally $\lambda v_i(\lambda)=\lambda$ is strictly inside the hull of the coordinates. Interior membership persists when both the point and these finitely many vertices move sufficiently little. Therefore, for all sufficiently close $\mu$,
Choose convex coefficients for this last inclusion as row $i$. Together with the unchanged rows they form a stochastic matrix having eigenvalue $\mu$. In particular, choose $\mu=(1+\varepsilon)\lambda$ for small $\varepsilon>0$. This contradicts radial extremality and proves the claim.
For completeness, the stability assertion follows from supporting functionals: a small disk centered at $\lambda$ lies in the original hull. Moving every vertex by less than half the disk’s radius changes every unit supporting value by at most that amount, leaving a smaller disk available for the moving point.
This explains why the least-order hypothesis is useful even in a geometric statement: it prevents the realizing matrix from splitting into smaller pieces when we try to move it.
A supporting edge forces a sparse row
Now let an image point $\lambda z_i$ lie on an edge $[z_a,z_b]$. Choose a supporting functional $h$ with
In any stochastic representation of this image,
we obtain
Every summand is nonnegative. A vertex off that supporting edge has $b-h(z_j)>0$, so its coefficient must vanish. Only the two endpoints can participate:
If the image is itself a vertex, its row has just one nonzero entry. For a fixed eigenvector polygon, the coefficients are now determined by the image point’s position on its supporting face.
Figure 2. In the exact example below, $\lambda z_1$ is the midpoint of $[z_2,z_0]$. A positive coefficient at $z_1$, which lies strictly off that supporting line, would pull the average away from the line. Its coefficient must be zero.
We have obtained a row with at most two nonzero entries. We still have to determine which edge each image can occupy.
The fixed cyclic shift is the deeper input
Number the vertices counterclockwise as $z_0,\ldots,z_{n-1}$, and use indices modulo $n$. The Dmitriev–Dynkin contact theorem
Under the two hypotheses above, there is an integer $k$ corresponding to
such that every image satisfies
Here $1\leq k\leq n$, with $0<\arg\lambda<2\pi$. At a sector endpoint, take a compatible choice of $k$. The theorem also rules out the simultaneous occurrence of an $\alpha_i=0$ and a $\beta_j=0$. Thus either every $\alpha_i$ is positive or every $\beta_i$ is positive, possibly both
The formula says much more than “each image lies on some edge.” The same index shift works at every vertex, even when the polygon is very irregular. In matrix language, all the nonzero entries occupy two specified cyclic diagonals.
The global shift and the prohibition on mixed zero endpoints are the part of the Dmitriev–Dynkin theorem we invoke as a cited input. The supporting-line calculation proves sparsity once the contact edge is known; it does not prove that global organization.
An exact extremal polygon
Set
The three vertices are numbered counterclockwise. Direct multiplication gives
So this is an invariant triangle, with realizing matrix
It is genuinely extremal at order three. A real stochastic $3\times3$ matrix with nonreal eigenvalue $\mu$ has spectrum $1,\mu,\overline\mu$. Its nonnegative diagonal gives
Our $\lambda$ has real part $-1/2$. Every outward multiple $c\lambda$, $c>1$, violates that trace inequality. And $\lambda$ is new at order three: the second eigenvalue of a stochastic $2\times2$ matrix is real.
Figure 3. Here $n=3$ and $k=2$. The three target edges are $[z_1,z_2]$, $[z_2,z_0]$, and $[z_0,z_1]$. Two images hit the second endpoint; the remaining image is a midpoint. The modulus is $1/\sqrt2$.
The contact coefficients are
Every $\beta_i$ is positive, exactly as the game convention requires.
Image polygon Selected image and target edge
Every displayed multiplier is radially extremal at order three: it has real part −1/2, while every outward multiple violates the trace inequality. The family stops before t = 3/4, where nonreality and the triangle would be lost. Rounded displays illustrate the exact formulas proved below.
The exact boundary family behind the explorer
For $0\leq t<3/4$, take the lower nonreal root
Use the counterclockwise vertices $(1,\lambda_t^2,\lambda_t)$. Their realizing matrix and coefficients are
The identity $\lambda_t^3=(1-t)+t\lambda_t$ closes the middle row. The same trace argument proves radial extremality for every member of this nonreal family. At $t=0$ the multiplier is a cube root of unity and all contacts are vertex contacts. For $0<t<3/4$ it is a strict contraction with one edge contact. The endpoint $t=3/4$ is excluded: the multiplier becomes real and the triangle degenerates.
Why the choice of orientation matters
Reflect the worked example across the real axis. Its eigenvalue is now $(-1+i)/2$. Counterclockwise order becomes
Again $k=2$, but this time
The first two contacts are now at the first endpoint of their designated edges. We cannot simply declare those zero $\beta$ coefficients positive while retaining the same counterclockwise convention.
The theorem’s no-mixed-zero conclusion provides the remedy: choose the conjugate orientation in which every $\beta_i>0$. The explorer lets you see the endpoint roles switch. No eigenvalue is lost from the eventual description, since the region is symmetric under conjugation.
More generally, reflection followed by counterclockwise renumbering swaps the two coefficient families and changes the shift to $n-k+1$. The game can use $1\leq k<n$: if the provisional shift is $n$, nonreality forces all first-endpoint coefficients to be positive, and reflection supplies shift $1$ with every second-endpoint coefficient positive.
The board is finally defined
In this chosen orientation, the contact equation reads
There are precisely two cases:
| Geometry | Coefficients | Chip-game symbol |
|---|---|---|
| Image is the vertex $z_{i+k}$ | $\alpha_i=0$, $\beta_i=1$ | Empty site at $i$ |
| Image is strictly inside the edge $[z_{i+k-1},z_{i+k}]$ | $\alpha_i>0$, $\beta_i>0$ | Chip at $i$ |
Figure 4. The worked triangle has a chip only at site $1$. Sites $0$ and $2$ are empty because their images are vertices. A chip records the type of contact of the source vertex, rather than the location of the image point in the plane.
The contact theorem applies to every invariant witness with at most $n$ vertices for this same extremal $\lambda$. This makes it reusable during the proof. Whenever a replacement satisfies
we automatically have $\lambda Q'\subseteq Q'$. If $Q'$ has at most $n$ vertices, least order forces it to have exactly $n$, and the contact conclusions apply again. A valid invariant variation cannot leave an image vertex strictly interior.
Karpelevich’s game now has its geometric foundation: a legal move replaces a corner while preserving the multiplier, and the resulting contacts still obey the theorem. The next stop uses those moves to collect scattered edge contacts into a simpler configuration.
With the circular board and contact rules established, play the corner-cutting game to concentrate scattered edge contacts into a single run: Karpelevich’s Game →
Sources and scope
[1] N. Dmitriev and E. Dynkin, On characteristic roots of stochastic matrices, Izv. Akad. Nauk SSSR Ser. Mat. 10:2 (1946), 167–184, §2, main theorem (formulation 5.1 and its endpoint qualification). Original journal record.
[2] F. I. Karpelevich, On the characteristic roots of matrices with nonnegative elements, Izv. Akad. Nauk SSSR Ser. Mat. 15:4 (1951), 361–383, §2, p. 363. Original paper.
Karpelevich takes the Dmitriev–Dynkin theorem as an input. This post does the same for the fixed-shift and endpoint conclusions, while giving proofs of the expansion, no-interior-contact, supporting-face, and example claims. The resolvent argument is presented as an explanatory proof here, rather than as a reconstruction of Dmitriev and Dynkin’s geometric proof. The diagrams and explorer are newly prepared for this exposition.