Take a complex eigenvector and plot its coordinates as points in the plane. Connect their outermost points. A matrix problem has just produced a polygon.
For a stochastic matrix, the eigenvector equation says something remarkably concrete about this picture: multiplying the polygon by the eigenvalue sends it into itself.
This is the first major change of viewpoint in our proof roadmap. We will prove the correspondence in both directions, build an exact example, and see how much of the region’s geometry follows before the boundary analysis even begins.
Every row is a weighted average
A row-stochastic matrix $P=(p_{ij})$ satisfies
If $Pv=\lambda v$, its $i$th row reads
The numbers $v_j$ are complex, so we can regard them as points in a plane. The coefficients in that row are nonnegative and sum to one. Thus the point $\lambda v_i$ is a convex combination of the eigenvector coordinates.
Here is one row with no approximation:
Figure 1. The three nonzero weights locate the amber point inside the triangle with vertices $1,i,-1$. Their sum is one. This is one row of the matrix below.
Each matrix row gives another such statement. We now put them together.
The eigenvector hull contains its own image
Let
Every image $\lambda v_i$ belongs to $Q$. Multiplication by $\lambda$ preserves convex combinations, so
That proves the forward direction:
If $\lambda=re^{i\theta}$, the map rotates by $\theta$ about the origin and scales distances by $r$. The polygon contains the result of that rotation and scaling.
For our running example, set
The first row is Figure 1. The other rows are its quarter-turns, and direct substitution gives $Pv=\lambda v$.
Figure 2. The original hull has vertices $1,i,-1,-i$. The four image coordinates form the smaller teal square. Here $|\lambda|=\sqrt5/4$, and all four image points lie strictly inside the original polygon.
The orange point and matrix row represent the same convex combination. The other slider adjusts at the diamond’s edge so all coefficients remain nonnegative. This diamond is the admissible multiplier region for this fixed square; the full Karpelevich region also uses other witnesses.
An exact construction behind the explorer
For $\lambda=x+iy$ with $|x|+|y|\leq1$, use the weights
at the points $1,i,-1,-i$. They are nonnegative, sum to one, and their weighted point is $x+iy$. Cyclic shifts of these weights give the other matrix rows. The fixed eigenvector remains $(1,i,-1,-i)^T$.
The explorer includes real parameters as well; this particular square construction remains valid there.
Go backward: build matrix rows from a polygon
Now start with a convex polygon
For each vertex, choose coefficients expressing its image as a convex combination:
Use those coefficients as the rows of $P$. Then $P$ is stochastic, and
The coordinate vector is nonzero, so $\lambda$ is an eigenvalue. If $m<n$, adjoin an identity block, $P\oplus I_{n-m}$. This gives a stochastic matrix of order $n$ with the same chosen eigenvalue.
The polygon correspondence
Dmitriev–Dynkin · Karpelevich §2For a nonreal number $\lambda$, the following are equivalent:
- $\lambda$ is an eigenvalue of an $n\times n$ stochastic matrix.
- There is a convex polygon $Q$ with at most $n$ vertices, with $0$ in its interior, such that $\lambda Q\subseteq Q$.
The only remaining point in the forward implication is why the origin is interior. We prove that next.
Two useful details already follow from the construction. First, coordinates of the original eigenvector can repeat or lie inside their hull: the hull may have fewer vertices than the matrix has rows. Second, choosing new rows from just those vertices preserves the selected eigenvalue; the other eigenvalues can change.
To find sparse rows, triangulate the polygon. Every image point lies in one of its triangles, so each row can be chosen with at most three nonzero entries. An image on an edge needs at most two, and an image at a vertex needs only one. These are existence statements about a choice of realizing rows.
Why the origin is inside
Let $Q$ be a compact convex set, not just $\{0\}$, with $\lambda Q\subseteq Q$, where $\lambda$ is nonreal.
Choose a point of maximum modulus. Its image is still in $Q$, so $|\lambda|\leq1$. The repeated images of any nonzero point remain in $Q$. Their averages approach the origin, forcing $0\in Q$.
The origin cannot lie on a supporting line of $Q$. Such a line would confine every repeated image to one closed half-plane through $0$. A nonreal rotation eventually leaves that half-plane. Thus
In particular, the hull is genuinely two-dimensional and none of its vertices is zero.
The averaging and half-plane arguments in full
Choose $z\in Q$ with $z\ne0$. Convexity gives
Since $\lambda\ne1$ and $|\lambda|\leq1$,
Closedness gives $0\in Q$. If $0$ is not interior, a supporting line through $0$ puts $Q$ in a closed half-plane. After rotating the picture and, if necessary, conjugating it, that half-plane has arguments in $[0,\pi]$ and the multiplier has argument $\theta\in(0,\pi)$.
Starting from a nonzero point of argument $\phi\in[0,\pi]$, choose the first integer $k$ for which $\phi+k\theta>\pi$. Then
The point $\lambda^kz$ is outside the half-plane, contradicting invariance. This proves the assertion, including when $|\lambda|=1$.
The nonreal hypothesis matters: a real eigenvalue can have a segment as its natural witness. Our polygon theorem is stated for the nonreal case, where the two-dimensional picture is automatic.
Why stochastic matrices are the right normalization
The original problem is posed for nonnegative matrices with fixed spectral radius. A positive Perron eigenvector explains the passage to stochastic matrices.
Suppose $A\geq0$ is irreducible, with spectral radius $\rho>0$ and positive Perron eigenvector $u$. Put $D=\operatorname{diag}(u_1,\ldots,u_n)$. Then
Thus $P$ is stochastic, and its spectrum is the spectrum of $A$ divided by $\rho$.
A reducible matrix can lack a strictly positive Perron eigenvector. For example,
has Perron eigenvectors proportional to $(1,0)^T$. Nevertheless, its eigenvalues are realized stochastically by
The general repair uses diagonal blocks.
A complete block construction for the reducible case
Assume $\rho(A)=1$. Put $A$ in Frobenius block triangular form, with irreducible diagonal blocks and possible scalar zero blocks. The characteristic polynomial is the product of the characteristic polynomials of its diagonal blocks.
In each irreducible block, scale by its positive Perron eigenvector, without dividing by that block’s spectral radius. Its rows then sum to a number $\rho_j\leq1$. A scalar zero block already has row sum zero. At least one block has $\rho_j=1$; choose one such block as the receiving block.
Place these scaled blocks on a block diagonal, with the receiving block last. For every row in every other block, add the missing mass $1-\rho_j$ to one fixed column of the receiving block. The receiving block’s own rows already sum to one.
The resulting matrix is nonnegative and stochastic. It is block upper triangular with the same diagonal-block characteristic polynomials as $A$, so it has exactly the same eigenvalues, with algebraic multiplicities. Eigenvectors and Jordan structure can change.
This proves that the normalized nonnegative eigenvalue problem and the stochastic formulation have the same region at the same order.
The region lets the polygon change
For a fixed polygon $Q$, the condition $\lambda Q\subseteq Q$ describes the eigenvalues that this particular witness can realize. The Karpelevich region allows every polygon with at most $n$ vertices.
For our square, $Q=\operatorname{conv}\{1,i,-1,-i\}$, invariance is equivalent to
Necessity follows by applying the multiplier to the vertex $1$. For sufficiency, the square is invariant under quarter-turns, so all four images belong to $Q$ whenever $\lambda\in Q$.
There are also four-state eigenvalues outside this diamond. One exact example is
Change the witness to
The first three images are listed vertices, and the fourth satisfies
So $\lambda_*Q_*\subseteq Q_*$. The coefficients give a stochastic matrix directly:
This is the $t=5/8$ member of the four-state family in the roadmap’s running example.
Figure 3. At the fixed value $\lambda_*$, the square’s image vertices lie outside it. The power-generated quadrilateral contains its image. Each witness has four vertices.
Dark outline: the witness polygon. Colored outline and points: its image under the same fixed λ*. Teal indicates containment; red shows failure. The power-polygon identity and its stochastic matrix are exact in the text above.
This is the geometric freedom the later proof must control: many different polygons can witness the same eigenvalue, and changing the polygon can enlarge the set of eigenvalues we can realize.
Basic geometry of the eigenvalue region
Write $\mathcal K_n$ for the eigenvalues realizable by stochastic matrices of order $n$. For this discussion, take $n\geq3$.
The unit disk. If $|v_i|$ is a largest eigenvector coordinate, the row equation gives
so $|\lambda|\leq1$.
Conjugate symmetry. The matrices are real, so conjugating $Pv=\lambda v$ gives $P\overline v=\overline\lambda\,\overline v$. Geometrically, reflect the witness across the real axis.
Nested orders. Adjoining an identity block gives $\mathcal K_m\subseteq\mathcal K_n$ for $m\leq n$.
Star-shapedness. If $\lambda$ is nonreal and $\lambda Q\subseteq Q$, then $0\in Q$ and convexity gives
The reverse construction realizes every $s\lambda$ in the same order, including the endpoint $0$. Real points cause no difficulty: every $x\in[-1,1]$ is already an eigenvalue of
Padding this two-state realization proves the real part of the claim. Thus every segment from $0$ to a point of $\mathcal K_n$ lies in $\mathcal K_n$.
Compactness. The stochastic matrices form a compact set, their eigenvalues stay in the closed unit disk, and $\det(\lambda I-P)=0$ is a closed condition. Projecting this compact matrix–eigenvalue set onto the $\lambda$ coordinate shows that $\mathcal K_n$ is compact.
In particular, each nonreal angular direction has a farthest realizable point. A regular triangle with circumradius $1$ and inradius $1/2$ is invariant under every multiplier with $|\lambda|\leq1/2$: all its image vertices lie in that contained disk. Thus positive radii are available in every direction. This makes the radial boundary question precise:
On the unit circle, the vertices are permuted
Suppose $|\lambda|=1$ and $\lambda$ is nonreal. An invariant polygon and its image have equal area. Since $\lambda Q\subseteq Q$, equality of area forces
Multiplication by $\lambda$ therefore permutes the polygon’s vertices. Following one nonzero vertex around its permutation cycle gives
Conversely, a cyclic permutation matrix of order $q$ realizes every $q$th root of unity. Pad it if $q<n$. The real unit-circle points $1$ and $-1$ have orders one and two and are handled directly.
Figure 4. For $\lambda=e^{2\pi i/5}$, multiplication cycles through the five vertices. There is no radial contraction, so the image polygon equals the original one.
We have obtained the unit-circle landmarks of the Karpelevich region from the polygon picture alone: roots of unity of order at most $n$.
What changes at the boundary?
So far, the images are allowed anywhere inside the polygon. Our first example has four strictly interior image points. The correspondence itself imposes no requirement that images touch edges.
The next stop asks what happens at a nonreal radial extremum, particularly when its realizing order cannot be reduced. The extremal contact theorem supplies additional constraints that organize those image points along the boundary. That is the input that will make the chip game possible.
The foundation is now in place: a stochastic eigenvalue is a rotation and scaling with a polygonal witness. We can move in either direction between convex coefficients and matrix rows.
At a nonreal radial extremum, the image points are pushed onto the edges in a controlled pattern: What Extremality Forces →. Or continue to Stop 3: Karpelevich’s Game and the series roadmap.
Sources and scope
The invariant-polygon correspondence is due to N. Dmitriev and E. Dynkin, On characteristic roots of stochastic matrices, Izv. Akad. Nauk SSSR Ser. Mat. 10 (1946), 167–184. Journal record. Karpelevich recalls it, together with the stochastic formulation, in §2, p. 363 of On the characteristic roots of matrices with nonnegative elements, 15 (1951), 361–383. Original paper.
The proofs and visual examples here are prepared for this exposition. We use the Perron–Frobenius theorem for irreducible blocks and the standard Frobenius block decomposition in the normalization argument. The correspondence concerns a chosen eigenvalue; the separate block normalization preserves the full normalized spectrum. No extremal contact theorem is assumed in this post.