Where the
Boundary Equations
Come From

A familiar equation, read as a chain

Recall the four-state example from the roadmap:

The first three rows propagate the eigenvector coordinates as

The final row closes the chain:

Rearranging gives

This already has the shape of the first family. The general case contains several such contact relations, followed by one closing condition.

What the geometry supplies

At this point in the proof, deterministic contacts give equations of the form

Following a sequence of them produces powers of $\lambda$ (as tracked arithmetically in Stop 4: Why the Euclidean Algorithm Appears). At an edge contact, an image is a convex combination of two coordinates. After the preceding rigidity arguments have equated the relevant weights, one repeatedly encounters

Here the $z_i$ are selected generating coordinates, rather than a fresh numbering of every polygon vertex. The integer $\ell$ counts steps up to and including the weighted transition. There are $\ell-1$ deterministic steps followed by that transition.

Figure 1. The example $\ell=3$. Arrows are row transitions: an arrow of weight $1$ from $u$ to $v$ means $\lambda u=v$. At the last state, the outgoing weights are $t$ and $1-t$.

We take the canonical chain structures and equality of weights as inputs from the earlier geometric part of the proof. The elimination below is complete. For that elimination, assume $0<t<1$, a nonreal eigenvalue $\lambda$, and a nonzero generating coordinate $z_0$. The endpoint matrices will be considered afterward.

First family: close through an extra tail

Suppose the contact relations are

and the final generating point returns to the first through $\tau$ deterministic steps:

The symbols have specific meanings:

Move the local return term to the left:

Apply this successively, keeping the common factor visible:

Multiply the last equation by $\lambda^\tau$, use the closing condition, and cancel the nonzero coordinate $z_0$. The result is

The count of states gives the degree $n=\ell m+\tau$. This is the first equation family in the original paper. The exponent $m$ appears because we repeat the same contact relation $m$ times. The factor $\lambda^\tau$ accounts for the closing tail. Throughout the series, $t$ always denotes the weight of the local return: the coefficient on the chain’s own generator.

A seven-state example

Take $\ell=3$, $m=2$, and $\tau=1$. The relations are

Two applications of the contact relation give

The final step supplies the remaining factor:

Figure 2. Two chains contribute six states. The extra state $z_2$ closes the configuration through $\lambda z_2=z_0$, bringing the order to seven. The two edges of weight $1-t$ advance between chains; the edges of weight $t$ return locally.

Second family: close at a point already in a chain

Now suppose there are $m$ contact chains of length $\ell$. Write

The difference lies in the closing identification:

The final target is already the $\sigma$th point along the first chain. It contributes no extra states. There are $\ell m$ states altogether.

The same repeated substitution now gives

Cancel $z_0$:

The geometry puts $\lambda^\sigma$ on the right because the closing target is $\lambda^\sigma z_0$. This is the second equation family.

In Karpelevich’s canonical second case, $m=g=\gcd(n,k)$ is the greatest common divisor of the order and the cyclic contact shift, and $\ell=n/g$. The closing shift is determined by the same arithmetic: Stop 7 shows that $\sigma=n-b$, where $b$ is the denominator of the other endpoint of the angular sector. Here we derive the equation from those data.

A six-state example

Take $\ell=3$, $m=2$, and $\sigma=1$:

Consequently,

Figure 3. The first six states agree with Figure 2. The last forward edge now lands at $\lambda z_0$, an existing state in the first chain. Its target explains both the right-hand factor $\lambda$ and the absence of a seventh state.

The distinction is visible in one table:

Why the common weight matters

The repeated factor also records a geometric fact. If the weights were $t_0,\ldots,t_{m-1}$, the first calculation would instead produce

The common weight turns this product into the power $(\lambda^\ell-t)^m$. Equality of the weights is supplied by the earlier variation arguments. The present calculation explains what that rigidity buys us algebraically.

These are characteristic polynomials

The arrows in Figures 2 and 3 define stochastic matrices: each deterministic row has one entry $1$, and each branching row has the entries $t$ and $1-t$. All omitted entries are zero. The same construction works for general chain lengths; coincident targets have their weights added. In the determinant expansion, those weights can be expanded separately by distributivity.

We can compute the characteristic polynomials directly from their directed cycles. This also verifies multiplicities and covers the endpoint parameters, including any zero eigenvalues.

For a weighted directed graph with adjacency matrix $A$, the determinant expansion gives

Here $\mathcal C$ ranges over collections of pairwise vertex-disjoint directed cycles, including the empty collection. Its weight $w(\mathcal C)$ is the product of the edge weights in its cycles, and $v(\mathcal C)$ counts their vertices. Each directed cycle contributes one minus sign; every uncovered vertex contributes $\lambda$.

First graph: short cycles and one full cycle

Each contact chain has a local cycle of length $\ell$ and weight $t$. These $m$ short cycles are disjoint. Summing their possible selections, with the $\tau$ tail vertices uncovered, gives

There is also one cycle that takes every forward branch and traverses the tail. It uses all $n$ vertices and has weight $(1-t)^m$. It intersects every short cycle, so it cannot be combined with any of them in a disjoint collection. Its contribution is $-(1-t)^m$.

Those are all the possibilities: a simple cycle either returns locally or advances through all the contact chains before it closes. Therefore

Second graph: the forward cycle skips the first $\sigma$ states

The $m$ disjoint local cycles now have length $\ell$, yielding

The cycle taking all forward branches lands at the $\sigma$th state of the first chain. It visits $\ell m-\sigma$ vertices, leaving the first $\sigma$ states uncovered. Its weight is $(1-t)^m$, and its contribution is therefore

Again this forward cycle intersects every local cycle, since $\sigma<\ell$. We obtain

This is a second way to see why the closing shift appears on the right. In the determinant, it counts the vertices outside the forward cycle.

Figure 4. Two selected root paths of the concrete matrix families, with equal scales on the real and imaginary axes. The full polynomials have other roots, including the Perron eigenvalue $1$. The paths illustrate the equations; their boundary interpretation uses the additional extremal analysis.

The endpoints are not arbitrary. The extra-tail path runs from $e^{2\pi i\cdot 2/7}$ to $e^{2\pi i\cdot 1/3}$, and $2/7<1/3$ are neighbours in the Farey sequence of order $7$: $7\cdot1-2\cdot3=1$ and $7+3>7$. The shifted-closure path runs from $e^{2\pi i\cdot 2/5}$ to $e^{2\pi i\cdot 1/3}$, and $1/3<2/5$ are neighbours in the Farey sequence of order $6$: $3\cdot2-1\cdot5=1$ and $3+5>6$. Why Farey neighbours label the arcs is the subject of Stop 7.

What happens at the endpoints?

The geometric elimination used $0<t<1$ and a nonzero generating coordinate. The determinant identities are polynomial identities and remain valid at $t=0$ and $t=1$.

At $t=0$, all forward transitions are active. The first graph becomes a cycle on all its states. The second has a cycle of length $\ell m-\sigma$, with $\sigma$ transient states feeding into it.

At $t=1$, the local cycles remain: $m$ cycles of length $\ell$ in either family. The first family’s tail contributes $\tau$ zero eigenvalues. When $\tau=0$, there are no such additional zeros.

The Perron eigenvalue is visible throughout. Substituting $\lambda=1$ into either polynomial gives zero, as it must for a stochastic matrix.

The same equations in Ito’s form

Later work packages both families into one equation . Let $a/b<c/d$ be neighbours in the Farey sequence $F_n$, write $\ell=\min(b,d)$ and $s=\max(b,d)$ for the smaller and larger denominators, and put $m=\lfloor n/\ell\rfloor$. Ito’s equation for the arc between $e^{2\pi ia/b}$ and $e^{2\pi ic/d}$ is

Ito writes $\beta=1-\alpha$ for the parameter we call $t$. Dividing by the common power of $\lambda$ gives exactly our two families:

The ranges match as well. In the first case $\tau=s-\ell m\leq n-\ell\lfloor n/\ell\rfloor<\ell$. In the second, the neighbour condition $\ell+s>n$ gives $\sigma=\ell m-s<\ell m-n+\ell\leq\ell$. Setting $t=1$ leaves the factor $(\lambda^\ell-1)^m$, whose root in the sector is the landmark with denominator $\ell$; setting $t=0$ leaves $\lambda^s=1$, the landmark with denominator $s$.

The cycle expansion above therefore proves a general inclusion. Every root of every reduced Ito polynomial is an eigenvalue of an explicit stochastic matrix whose order is the reduced degree, $s$ or $\ell m$. Both are at most $n$, so padding with an identity block places the root in $\mathcal K_n$. Johnson and Paparella construct realizing matrices for Ito’s polynomials ; the chain matrices of this post give a self-contained proof of the same inclusion.

What the equations establish

We have derived the two families from explicit chain relations, explained every exponent, and proved exact characteristic-polynomial identities for the corresponding stochastic constructions. Every root of those characteristic polynomials is consequently realizable, with its algebraic multiplicity.

To identify a boundary arc, the original proof also needs the admissible integer data from its geometric and arithmetic reductions, the relevant root branch, and the final extremality argument. Those tasks locate the equations in the Karpelevich region.

The mechanism producing the equations is now visible: repeat a contact relation, then use the closing identification. The generating coordinates cancel, leaving only powers of $\lambda$ and the common weight.

Source and place in the series

The original source is §4, Theorems VI–VII, pp. 375–377 of 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.

We write the common weights as $t$ and $1-t$ and reindex the second family in the forward direction. In the first case, the original closing relation $\lambda^{\ell+\tau}z_m=tz_0+(1-t)z_1$ combines with the first contact relation to give $\lambda^\tau z_m=z_0$. In the second, reversing the order of the generating coordinates gives the closure used here.

The chain drawings, matrix constructions, cycle-expansion explanation, and interactive examples are prepared for this exposition. They make the elimination explicit while leaving the preceding geometric rigidity and subsequent angular classification to their own posts.