So far, our polygons have been witnesses. To prove that a particular number $\lambda$ is a stochastic eigenvalue, we find a polygon $Q$ with at most $n$ vertices such that $\lambda Q\subseteq Q$.
Karpelevich now turns that picture into a description of the region itself. He finds special polygons $C$ for which every point of $C$ is a stochastic eigenvalue, using $C$ as its own witness. His Theorem A says that these polygons, taken together, cover the whole Karpelevich region.
The extra property is simple to state:
The interesting question is how the contact relations from the earlier posts produce polygons with this property.
What “cyclic” means here
Choose a complex number $\mu$ and a positive integer $h$, and write $\varepsilon=e^{2\pi i/h}$. Consider all the points
Start with the powers of $\mu$, then include their $h$ rotated copies. When their closed convex hull is a finite polygon, call it $C(\mu,h)$. This is the power-generated, rotational meaning of cyclic polygon used in this post.
We count actual vertices of the hull. A list of eight generators might have fewer than eight vertices. Also, taking the first few powers does not automatically give the hull of the entire infinite orbit: the next power might fall outside.
The closed-hull convention includes real-axis segments. In the nondegenerate examples below it agrees with the ordinary convex hull of the infinite generating set. Throughout the union statement we take $n\geq2$.
One closing relation captures an infinite orbit
Here is a finite certificate. Form
Suppose the next power satisfies
Then $P=C(\mu,h)$, and it has at most $hL$ vertices.
To see this, multiplication by $\varepsilon$ permutes the generating list, so $\varepsilon P=P$. Multiplication by $\mu$ advances every generator to the next power. The only images needing a check are the terminal ones, $\varepsilon^j\mu^L$; they lie in $P$ by the boxed condition and rotational symmetry. Hence
Induction now puts every later power and every rotated copy inside $P$. The finite hull already contains the entire infinite orbit.
Our four-state example from the roadmap makes this concrete. Put
Direct calculation gives
Thus the next power lies on the segment joining $1$ to $\mu$. With $h=1$ and $L=4$,
Figure 1. The amber point $\mu^4$ lies on $[1,\mu]$. Multiplication advances the first three generators and sends the fourth onto that edge. Every later power stays in the same quadrilateral.
Why every point in a cyclic polygon is realizable
Products of orbit points are orbit points:
Products of convex combinations are convex combinations too. If
where $a_s,b_t$ are orbit points and both coefficient lists are nonnegative and sum to one, then
The new coefficients are nonnegative and sum to one. Passing to limits handles the closed hull. Therefore $zw\in C$.
Fix any $z\in C$. We have proved $zC\subseteq C$. If $v_1,\ldots,v_k$ are its vertices, choose convex coefficients
These are the rows of a stochastic matrix $A$, and
The vector is nonzero because $1\in C$. Thus $z$ is an eigenvalue. If $k<n$, append a stochastic block. We have proved one entire inclusion in Theorem A:
This is stronger than checking the generator alone. The same polygon witnesses every convex combination of its points.
Figure 2. Take $C=C(i/2,2)=\operatorname{conv}\{1,i/2,-1,-i/2\}$ and $z=1/4+i/4$. The amber polygon is $zC$. The displayed matrix has eigenvector $(1,i/2,-1,-i/2)^T$ with eigenvalue $z$. Moving $z$ through $C$ gives further matrices.
Choose a point in the diamond C. Its four vertices form a fixed eigenvector; the convex coefficients form the rows of A(z).
A(z), with columns ordered as 1, i/2, −1, −i/2
v = (1, i/2, −1, −i/2)ᵀ
The sliders use x = u/120 and y = (1−|x|)v/240, with integer u,v between −120 and 120. They keep z inside C. Every displayed matrix entry and eigenvector check uses reduced rational arithmetic. The picture uses numerical coordinates.
Where the return equations enter
The finite certificate explains the shape of the theorem's proof. The earlier work has already produced power relations with positive convex weights; the angular information tells us which root choices belong to the geometric configuration.
For the eight-state example from the equations post,
By the angular estimate, the selected configuration has direction
Taking the square root of the polynomial relation leaves a genuine choice:
The sector rules out the plus sign. If the sign were positive, $\lambda^4$ would be a positive convex combination of $1$ and $\lambda$, so its argument would lie strictly between $0$ and $2\pi\theta$. But its principal direction is $4\theta-1$, and
That is beyond the direction of $\lambda$, a contradiction. The correct closing relation is therefore
Now include the half-turn copies:
The boxed relation places $\lambda^4$ on $[-1,\lambda]$; its negative closes the other chain. Our finite certificate applies with $h=2$, $L=4$. This is a cyclic polygon with at most eight vertices, and it contains $\lambda$.
Figure 3. In this algebraic instance of the eight-state relation, four initial powers do not suffice. Adding their negatives supplies the missing point $-1$ and the edge containing $\lambda^4$. The two convex closing relations certify all subsequent powers.
The rotational factor $h\geq 1$ is an essential part of Karpelevich’s definition: the eight-state calculation above already needed $h=2$ so that $-1$ could supply the missing closing endpoint. Đoković
Teal points are the initial powers. Amber points, when present, are their half-turn copies. The red point is the selected power. The dashed amber outline optionally shows μC. A convex closing identity proves containment of all later powers, including those beyond the slider.
The global input: cover the radial extrema
The eight-state calculation exhibits the mechanism. In the general construction, $\lambda$ may be a power of a new generator $\mu$. Extracting roots of the common-weight relations introduces roots of unity; these supply the finite rotational copies. Choosing those roots consistently and keeping the generating list within the vertex budget requires the general exponent and angle bookkeeping.
Theorem X supplies the result: a radial extremum new at order $n_*$, in the nonreal strict-contraction orientation treated by the proof, belongs to a cyclic polygon with at most $n_*$ vertices.
That is the global geometric input we use here. The general root-choice argument for both patterns is not reproduced by the worked example. Its angular hypotheses matter; an arbitrary root of one of the candidate equations is not being declared a boundary point.
Conjugation handles the opposite orientation. Unit-circle extrema are roots of unity and lie in their regular polygons. The real axis is covered by the cyclic segment $[-1,1]$. The remaining low-order nonreal case is covered by the regular triangle.
Why the order-three case needs only the triangle and the real segment
If a real $3\times3$ stochastic matrix has a nonreal eigenvalue $z=x+iy$, its eigenvalues are $1,z,\overline z$. Nonnegative diagonal entries give $1+2x=\operatorname{tr}A\geq0$, so $x\geq-1/2$.
Also,
Substituting the eigenvalues gives $y^2\leq(1-x)^2/3$. Together with $x\geq-1/2$ and $x\leq1$, these inequalities put $z$ in the triangle with vertices $1,e^{2\pi i/3},e^{4\pi i/3}$.
Every point of that triangle is realized by a convex combination of the identity and the two three-cycle permutation matrices. Real points in $[-1,1]$ are realized at order two. Thus the separate base cases are cyclic polygons too.
Fill the rays to obtain the whole region
Take any nonzero $z\in\mathcal K_n$. Compactness gives a farthest realizable point $\lambda$ on its ray, so
Choose the least order $n_*\leq n$ realizing $\lambda$. It is a radial extremum at that order and is new there. The preceding boundary-covering result, including its elementary exceptions, places $\lambda$ in a cyclic polygon $C$ with at most $n$ vertices.
If the generator has $|\mu|<1$, its powers tend to zero, so $0\in C$. If $|\mu|=1$, a finite polygon requires a finite unit-circle orbit; every nontrivial such orbit also has zero in its convex hull. The exceptional singleton $\{1\}$ can use $[-1,1]$. Convexity now gives
Figure 4. Theorem X supplies a polygon containing the radial extreme. Its convexity and the presence of zero fill the ray beneath that point. Different rays may use different cyclic polygons; the picture shows one such polygon.
Zero itself lies in $[-1,1]$. Combined with the inclusion proved in section 3, this proves the union description:
The union need not be convex. Each individual member is a convex region of realizable eigenvalues; their outer envelope is the Karpelevich boundary.
What remains for the final stop
Using Theorem X, we now have a description of the whole region. Assigning every boundary arc its final equation is the remaining task.
That distinction is useful. Theorem A asks whether a point lies in at least one cyclic polygon with the allowed number of vertices. Theorem B asks which of the candidate curves form the outside of their union, including the pieces inherited from smaller orders.
The next and final stop is Closing the Boundary: Old Arcs, New Arcs, and Induction.
Next in Inside Karpelevich’s Proof: Stop 9 — Closing the Boundary: Old Arcs, New Arcs, and Induction →. Or review Stop 7: Why Farey Neighbors Label the Arcs and the full Nine-Stop Proof Roadmap.
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 cyclic definition and Theorem A are on pp. 361–362; Theorem X and the deduction of Theorem A are on p. 379.
D. Ž. Đoković, Cyclic polygons, roots of polynomials with decreasing nonnegative coefficients, and eigenvalues of stochastic matrices (1990). Publisher record, for the connection between cyclic polygons, polynomials with decreasing nonnegative coefficients, and a streamlined proof of Karpelevich’s theorem.
This post proves the finite closing certificate, multiplication closure, stochastic realization of each polygon, the eight-state root-sign selection, the low-order cases, and the passage from radial coverage to the whole region. Theorem X supplies the general extremal covering statement. Diagrams use numerical drawing coordinates for exact algebraic constructions; the matrix explorer uses exact rational arithmetic. No numerical root tracking establishes a boundary claim.