Introduction
For a fixed order n n n m m m m m m n n n
The Karpelevič theorem describes which individual eigenvalues are possible [7 , 4 ] . Asking which lists of eigenvalues can occur together is the stochastic form of the nonnegative inverse eigenvalue problem [5 ] . We call the least values of m m m
For a Markov chain, arrange the states in a fixed cyclic order and allow transition probabilities to vary independently on 2 m 2m 2 m m m m
Throughout, stochastic means row-stochastic: P ≥ 0 P \ge0 P ≥ 0 P 1 = 1 P\mathbf{1} = \mathbf{1} P 1 = 1 1 \mathbf{1} 1 J = 11 T / n J = \mathbf{1}\mathbf{1}^{T}/n J = 1 1 T / n 1 / n 1/n 1/ n ∥ ⋅ ∥ ∞ \lVert\cdot\rVert_{\infty} ∥ ⋅ ∥ ∞ 0 , … , n − 1 0,\ldots,n-1 0 , … , n − 1 0 ≤ m ≤ ⌊ n / 2 ⌋ 0 \le m \le\lfloor n/2 \rfloor 0 ≤ m ≤ ⌊ n /2 ⌋ n − 2 m n-2m n − 2 m m , … , n − m − 1 m,\ldots,n-m-1 m , … , n − m − 1 2 m 2m 2 m m m m
I n , m = { m , … , n − m − 1 } , B n , m = { 0 , … , n − 1 } ∖ I n , m . I_{n,m} = \{m,\ldots,n-m-1\}, \qquad B_{n,m} = \{0,\ldots,n-1\} \setminus I_{n,m}. I n , m = { m , … , n − m − 1 } , B n , m = { 0 , … , n − 1 } ∖ I n , m . Row i i i i i i n n n interior state when its index lies in I n , m I_{n,m} I n , m boundary state when its index lies in B n , m B_{n,m} B n , m Q n , m Q_{n,m} Q n , m n n n
P i j = a j − i ( i ∈ I n , m , 0 ≤ j < n ) (1) P_{ij} = a_{j-i} \qquad(i \in I_{n,m},\ 0 \le j < n) \tag*{(1)} P ij = a j − i ( i ∈ I n , m , 0 ≤ j < n ) (1) for some real coefficients a k a_k a k B n , m B_{n,m} B n , m Proposition 1.2 shows that the interior rows coincide with the corresponding rows of a stochastic circulant. Entries far from the main diagonal may be nonzero. Throughout, cyclic shifts of row vectors are to the right: a shift by one position moves the last entry to the first position. Successive interior rows differ by one such shift. Figure 1 shows these constraints and the cyclic ordering for n = 10 n=10 n = 10 m = 2 m=2 m = 2
Figure 1. The row constraints for n = 10 n = 10 n = 10 m = 2 m = 2 m = 2 2 , … , 7 2,\ldots,7 2 , … , 7 ( c 0 , … , c 9 ) (c_0,\ldots,c_9) ( c 0 , … , c 9 )
Let Θ n \Theta_n Θ n spec ( P ) \operatorname{spec}(P) spec ( P ) P P P S n \mathcal{S}_n S n n n n
Ω n , m = ⋃ P ∈ Q n , m spec ( P ) , S n , m = { spec ( P ) : P ∈ Q n , m } . \Omega_{n,m}=\bigcup_{P\in\mathcal{Q}_{n,m}}\operatorname{spec}(P),\qquad\mathcal{S}_{n,m}=\{\operatorname{spec}(P):P\in\mathcal{Q}_{n,m}\}. Ω n , m = P ∈ Q n , m ⋃ spec ( P ) , S n , m = { spec ( P ) : P ∈ Q n , m } . The two saturation thresholds are the least values of m m m Θ n \Theta_n Θ n S n \mathcal{S}_n S n
m n ∗ = min { m : Ω n , m = Θ n } , j n ∗ = min { m : S n , m = S n } . (2) m_n^*=\min\{m:\Omega_{n,m}=\Theta_n\},\qquad j_n^*=\min\{m:\mathcal{S}_{n,m}=\mathcal{S}_n\}. \tag*{(2)} m n ∗ = min { m : Ω n , m = Θ n } , j n ∗ = min { m : S n , m = S n } . (2) The boundary of Θ n \Theta_n Θ n e 2 π i p / q e^{2\pi ip/q} e 2 π i p / q p / q p/q p / q q q q A ⊂ ∂ Θ n A\subset\partial\Theta_n A ⊂ ∂ Θ n κ n ( A ) \kappa_n(A) κ n ( A ) m m m A A A
κ n ( A ) = min { m : A ⊆ Ω n , m } . \kappa_n(A)=\min\{m:A\subseteq\Omega_{n,m}\}. κ n ( A ) = min { m : A ⊆ Ω n , m } . Theorem 1.1 (Saturation thresholds). For n = 1 , 2 n=1,2 n = 1 , 2 m n ∗ = j n ∗ = 0 m_n^*=j_n^*=0 m n ∗ = j n ∗ = 0 n ≥ 3 n\geq3 n ≥ 3
m n ∗ = ⌊ n − 1 4 ⌋ , (3) m_n^*=\left\lfloor\frac{n-1}{4}\right\rfloor, \tag*{(3)} m n ∗ = ⌊ 4 n − 1 ⌋ , (3) j n ∗ = ⌊ n 2 ⌋ . (4) j_n^*=\left\lfloor\frac{n}{2}\right\rfloor. \tag*{(4)} j n ∗ = ⌊ 2 n ⌋ . (4) If a Karpelevič arc A A A q < s q<s q < s
κ n ( A ) = { 0 , q = 1 , ⌊ 1 2 ⌊ n q ⌋ ⌋ , q ≥ 2. (5) \kappa_n(A)=
\begin{cases}
0, & q=1,\\
\left\lfloor\frac{1}{2}\left\lfloor\frac{n}{q}\right\rfloor\right\rfloor, & q\geq2.
\end{cases} \tag*{(5)} κ n ( A ) = { 0 , ⌊ 2 1 ⌊ q n ⌋ ⌋ , q = 1 , q ≥ 2. (5) Thus the class attains the full Karpelevič region while retaining the Toeplitz pattern in about half of the rows. For n ≥ 3 n\geq3 n ≥ 3 n n n m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ n n n n n n n ≥ 4 n\geq4 n ≥ 4 m m m
j n ∗ − m n ∗ = n / 4 + O ( 1 ) . j_n^*-m_n^*=n/4+O(1). j n ∗ − m n ∗ = n /4 + O ( 1 ) . The three formulas in Theorem 1.1 are proved in § 2 –§ 5 ; they are independent of the boundary-polynomial rigidity result of § 6 .
Johnson and Paparella [6 ] , and Kirkland, Laffey and Šmigoc [8 ] , construct stochastic matrices from Ito polynomials. The polynomials and their types are introduced in § 2 . Kirkland and Šmigoc [9 ] classify Type 0 and Type I realisations and the sparsest Type II and Type III realisations. The subsequent classifications of non-degenerate full-degree Type II polynomials [15 ] and genuine Type III polynomials over their nonzero parameter range [14 ] concern all stochastic matrices with the specified characteristic polynomial. Munger, Nickerson and Paparella [11 ] study how selected roots trace the boundary arcs. Our chain construction places all rows departing from the circulant pattern in one consecutive block and gives the upper bounds on m m m m m m n n n 2 m 2m 2 m n n n m m m n n n
For even n ≥ 4 n \ge4 n ≥ 4 Q n , n / 2 − 1 \mathcal{Q}_{n,n/2-1} Q n , n /2 − 1 tr ( P 4 ) \operatorname{tr}(P^4) tr ( P 4 ) tr ( P ) \operatorname{tr}(P) tr ( P ) tr ( P 2 ) \operatorname{tr}(P^2) tr ( P 2 ) tr ( P k ) \operatorname{tr}(P^k) tr ( P k ) k k k 1 1 1 [2 ] and the obstructions for permutative matrices in [10 ] : here only two consecutive rows retain the Toeplitz pattern.
Section 6 starts from one nonreal boundary eigenvalue at its smallest realising order n ≥ 4 n \ge4 n ≥ 4 [16 ] while preserving the characteristic polynomial. The resulting cycle restrictions exclude every point between the endpoints of a minimal-order arc below its whole-arc saturation value.
Section 7 describes the radial geometry and the boundary angles at roots of unity, extending the star-convexity studied in [13 ] . The appendices give support bounds and local freedom of characteristic-polynomial coefficients.
Proposition 1.2. If n − 2 m ≥ 1 n-2m \ge1 n − 2 m ≥ 1 P ∈ Q n , m P \in\mathcal{Q}_{n,m} P ∈ Q n , m m , … , n − m − 1 m,\ldots,n-m-1 m , … , n − m − 1 C C C m m m m m m Q n , m \mathcal{Q}_{n,m} Q n , m
P = C + E , E i , ∗ = 0 ( i ∈ I n , m ) , rank E ≤ 2 m , (6) P=C+E,\qquad E_{i,*}=0\ (i\in I_{n,m}),\qquad\operatorname{rank}E\le2m, \tag*{(6)} P = C + E , E i , ∗ = 0 ( i ∈ I n , m ) , rank E ≤ 2 m , (6) where E i , ∗ E_{i,*} E i , ∗ i i i E E E
Proof. For consecutive interior rows, the Toeplitz identities give P i + 1 , j + 1 = P i j P_{i+1,j+1}=P_{ij} P i + 1 , j + 1 = P ij 0 ≤ j ≤ n − 2 0\le j\le n-2 0 ≤ j ≤ n − 2 P i + 1 , 0 = P i , n − 1 P_{i+1,0}=P_{i,n-1} P i + 1 , 0 = P i , n − 1 C C C E = P − C E=P-C E = P − C 2 m 2m 2 m 2 m 2m 2 m
If n − 2 m = 0 n-2m=0 n − 2 m = 0 C C C E = P − C E=P-C E = P − C (6) still hold. In this case, C C C P P P
For a probability vector c = ( c 0 , … , c n − 1 ) \boldsymbol{c}=(c_0,\ldots,c_{n-1}) c = ( c 0 , … , c n − 1 )
C ( c ) i j = c j − i m o d n ( 0 ≤ i , j < n ) . C(\boldsymbol{c})_{ij}=c_{j-i\ \mathrm{mod}\ n}\qquad(0\le i,j<n). C ( c ) ij = c j − i mod n ( 0 ≤ i , j < n ) . In particular, C n C_n C n 1 1 1 ( C n ) i , i + 1 m o d n = 1 (C_n)_{i,i+1\ \mathrm{mod}\ n}=1 ( C n ) i , i + 1 mod n = 1 ω = e 2 π i / n \omega=e^{2\pi i/n} ω = e 2 π i / n C ( c ) C(\boldsymbol{c}) C ( c )
λ r = ∑ k = 0 n − 1 c k ω r k ( 0 ≤ r < n ) . \lambda_r=\sum_{k=0}^{n-1}c_k\omega^{rk}\qquad(0\le r<n). λ r = k = 0 ∑ n − 1 c k ω r k ( 0 ≤ r < n ) . Each λ r \lambda_r λ r n n n ∑ k c k ω k \sum_k c_k\omega^k ∑ k c k ω k C ( c ) C(c) C ( c ) Proposition 1.2 , this gives
Ω n , 0 = H n : = conv { e 2 π i k / n : 0 ≤ k < n } . (7) \Omega_{n,0}=H_n:=\operatorname{conv}\{e^{2\pi i k/n}:0\le k<n\}. \tag*{(7)} Ω n , 0 = H n := conv { e 2 π ik / n : 0 ≤ k < n } . (7) For m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ Q n , ⌊ n / 2 ⌋ Q_{n,\lfloor n/2\rfloor} Q n , ⌊ n /2 ⌋ n n n Q n , m Q_{n,m} Q n , m m m m n ≥ 2 n\ge2 n ≥ 2 − 1 / ( n − 1 ) ≤ a ≤ 1 -1/(n-1)\le a\le1 − 1/ ( n − 1 ) ≤ a ≤ 1 M a = a I + ( 1 − a ) J M_a=aI+(1-a)J M a = a I + ( 1 − a ) J spec ( P ) = { 1 , λ 2 , … , λ n } \operatorname{spec}(P)=\{1,\lambda_2,\ldots,\lambda_n\} spec ( P ) = { 1 , λ 2 , … , λ n } t P + ( 1 − t ) M a tP+(1-t)M_a tP + ( 1 − t ) M a 1 1 1
λ k ( t ) = t λ k + ( 1 − t ) a ( 2 ≤ k ≤ n , 0 ≤ t ≤ 1 ) . (8) \lambda_k(t)=t\lambda_k+(1-t)a \qquad(2\le k\le n,\ 0\le t\le1). \tag*{(8)} λ k ( t ) = t λ k + ( 1 − t ) a ( 2 ≤ k ≤ n , 0 ≤ t ≤ 1 ) . (8) Indeed, use a basis whose first vector is 1 \mathbf{1} 1 P 1 = 1 P\mathbf{1}=\mathbf{1} P 1 = 1 J J J 1 \mathbf{1} 1
P = ( 1 ∗ 0 B ) , M a = ( 1 ∗ 0 a I n − 1 ) . P=\begin{pmatrix}1&*\\0&B\end{pmatrix},\qquad M_a=\begin{pmatrix}1&*\\0&aI_{n-1}\end{pmatrix}. P = ( 1 0 ∗ B ) , M a = ( 1 0 ∗ a I n − 1 ) . Here B B B λ 2 , … , λ n \lambda_2,\ldots,\lambda_n λ 2 , … , λ n t P + ( 1 − t ) M a tP+(1-t)M_a tP + ( 1 − t ) M a t B + ( 1 − t ) a I n − 1 tB+(1-t)aI_{n-1} tB + ( 1 − t ) a I n − 1 t λ k + ( 1 − t ) a t\lambda_k+(1-t)a t λ k + ( 1 − t ) a 2 ≤ k ≤ n 2\le k\le n 2 ≤ k ≤ n a = 0 , 1 a=0,1 a = 0 , 1 J J J I I I a a a
λ ∈ Ω n , m ⟹ conv { − 1 / ( n − 1 ) , 1 , λ } ⊆ Ω n , m . (9) \lambda\in\Omega_{n,m}\quad\Longrightarrow\quad\operatorname{conv}\{-1/(n-1),1,\lambda\}\subseteq\Omega_{n,m}. \tag*{(9)} λ ∈ Ω n , m ⟹ conv { − 1/ ( n − 1 ) , 1 , λ } ⊆ Ω n , m . (9) For λ = 1 \lambda=1 λ = 1 M a M_a M a
Boundary arcs and localised chain realisations
The Karpelevič–Ito theorem describes the boundary arcs using neighbouring fractions in the Farey sequence of order n n n [ 0 , 1 ] [0,1] [ 0 , 1 ] n n n e 2 π i p / q e^{2\pi i p/q} e 2 π i p / q e 2 π i p ′ / s e^{2\pi i p'/s} e 2 π i p ′ / s
q < s ≤ n , ∣ p s − p ′ q ∣ = 1 , q + s > n . q<s\le n,\qquad|ps-p'q|=1,\qquad q+s>n. q < s ≤ n , ∣ p s − p ′ q ∣ = 1 , q + s > n . For q ≥ 2 q\ge2 q ≥ 2 d = ⌊ n / q ⌋ d=\lfloor n/q\rfloor d = ⌊ n / q ⌋ β = 1 − α \beta=1-\alpha β = 1 − α 0 ≤ α ≤ 1 0\le\alpha\le1 0 ≤ α ≤ 1
χ n ; q , s , α ( z ) = z n − q d ( z q − β ) d − α d z n − s . (10) \chi_{n;q,s,\alpha}(z)=z^{n-qd}(z^q-\beta)^d-\alpha^d z^{n-s}. \tag*{(10)} χ n ; q , s , α ( z ) = z n − q d ( z q − β ) d − α d z n − s . (10) As α \alpha α (10) need not lie on the boundary. When q = 1 q=1 q = 1 1 1 1 e 2 π i / n e^{2\pi i/n} e 2 π i / n e − 2 π i / n e^{-2\pi i/n} e − 2 π i / n
For q ≥ 2 q\ge2 q ≥ 2
N = max ( q d , s ) . N=\max(qd,s). N = max ( q d , s ) . For every nonreal point λ \lambda λ N N N λ \lambda λ N N N (10) — by z n − N z^{n-N} z n − N N N N
Since q q q s s s q ≥ 2 q \ge2 q ≥ 2 s = q d s=qd s = q d n n n N N N Θ N \Theta_N Θ N Θ n \Theta_n Θ n [ − 1 , − 1 / 2 ] [-1,-1/2] [ − 1 , − 1/2 ]
The next construction allows the exponent d d d (10) to be replaced by a positive integer r r r n n n q q q r r r s s s α \alpha α
Theorem 2.1. Let q q q r r r s s s q ≥ 2 q \ge2 q ≥ 2 r ≥ 1 r \ge1 r ≥ 1 q r ≤ n qr \le n q r ≤ n r ≤ s ≤ n r \le s \le n r ≤ s ≤ n α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] P P P n n n
z n − q r ( z q − 1 + α ) r − α r z n − s . (11) z^{n-qr}(z^q-1+\alpha)^r-\alpha^r z^{n-s}. \tag*{(11)} z n − q r ( z q − 1 + α ) r − α r z n − s . (11) In every row outside a block of r r r i i i i + r i+r i + r n n n n n n Q n , ⌈ r / 2 ⌉ Q_{n,\lceil r/2\rceil} Q n , ⌈ r /2 ⌉ n + r n+r n + r
Proof. Partition the states 0 , … , n − 1 0,\ldots,n-1 0 , … , n − 1 r r r
H j = ( j , j + r , j + 2 r , … ) ( 0 ≤ j < r ) , H_j=(j,j+r,j+2r,\ldots) \qquad(0 \le j < r), H j = ( j , j + r , j + 2 r , … ) ( 0 ≤ j < r ) , stopping each chain before its labels reach n n n h j h_j h j H j H_j H j e j e_j e j q r ≤ n qr \le n q r ≤ n q q q n − r , … , n − 1 n-r,\ldots,n-1 n − r , … , n − 1
1 ≤ ℓ j ≤ h j , ∑ j = 0 r − 1 ℓ j = s . 1 \le\ell_j \le h_j,\qquad\sum_{j=0}^{r-1}\ell_j=s. 1 ≤ ℓ j ≤ h j , j = 0 ∑ r − 1 ℓ j = s . Such a choice exists: starting with every ℓ j = 1 \ell_j=1 ℓ j = 1 ∑ j h j = n \sum_j h_j=n ∑ j h j = n r ≤ s ≤ n r \le s \le n r ≤ s ≤ n
For each state other than the last state of a chain, the transition probability to the next state in that chain is 1. From e j e_j e j β = 1 − α \beta=1-\alpha β = 1 − α q q q H j H_j H j α \alpha α ℓ j + 1 \ell_{j+1} ℓ j + 1 H j + 1 H_{j+1} H j + 1 r r r P P P
For z ≠ 0 z \ne0 z = 0 x j = v e j x_j=v_{e_j} x j = v e j P v = z v Pv=zv P v = z v v e j − k r = z − k x j v_{e_j-kr}=z^{-k}x_j v e j − k r = z − k x j H j H_j H j
( z q − β ) x j = α z q − ℓ j + 1 x j + 1 . (z^q-\beta)x_j=\alpha z^{q-\ell_{j+1}}x_{j+1}. ( z q − β ) x j = α z q − ℓ j + 1 x j + 1 . To compute the characteristic polynomial with multiplicities, perform the same elimination on z I − P zI-P z I − P n − r n-r n − r z n − r z^{n-r} z n − r z β z 1 − q z^{\beta z^{1-q}} z β z 1 − q − α z 1 − ℓ j + 1 -\alpha z^{1-\ell_{j+1}} − α z 1 − ℓ j + 1 ( j , j + 1 ) (j,j+1) ( j , j + 1 ) r r r
z r ( 1 − q ) ( z q − β ) r − α r z r − s . z^{r(1-q)}(z^q-\beta)^r-\alpha^r z^{r-s}. z r ( 1 − q ) ( z q − β ) r − α r z r − s . When r = 1 r=1 r = 1 ℓ 0 = s \ell_0=s ℓ 0 = s
( z − β z 1 − q − α z 1 − s ) . \left(z-\beta z^{1-q}-\alpha z^{1-s}\right). ( z − β z 1 − q − α z 1 − s ) . Its determinant is this entry itself, which is exactly the preceding formula with r = 1 r=1 r = 1 z n − r z^{n-r} z n − r (11) . Since both sides are polynomials, the identity also holds at z = 0 z=0 z = 0
Only the rows indexed by e j e_j e j i ↦ i + r ( m o d n ) i\mapsto i+r\pmod n i ↦ i + r ( mod n ) m = ⌈ r / 2 ⌉ m=\lceil r/2\rceil m = ⌈ r /2 ⌉ r − m r-m r − m n n n m m m r − m r-m r − m r − m ≤ m r-m\le m r − m ≤ m m m m m m m i ↦ i + r ( m o d n ) i\mapsto i+r\pmod n i ↦ i + r ( mod n ) Q n , m Q_{n,m} Q n , m n − r n-r n − r r r r ( n − r ) + 2 r = n + r (n-r)+2r=n+r ( n − r ) + 2 r = n + r
Setting r = ⌊ n / q ⌋ r=\lfloor n/q\rfloor r = ⌊ n / q ⌋ (10) . The Type 0 segments are obtained from ( 1 − α ) I + α C n ± 1 (1-\alpha)I+\alpha C_n^{\pm1} ( 1 − α ) I + α C n ± 1
κ n ( A ) ≤ ⌊ 1 2 ⌊ n q ⌋ ⌋ ( q ≥ 2 ) , m n ∗ ≤ ⌊ n − 1 4 ⌋ . (12) \kappa_n(A)\le\left\lfloor\frac{1}{2}\left\lfloor\frac{n}{q}\right\rfloor\right\rfloor\quad(q\ge2),\qquad m_n^*\le\left\lfloor\frac{n-1}{4}\right\rfloor. \tag*{(12)} κ n ( A ) ≤ ⌊ 2 1 ⌊ q n ⌋ ⌋ ( q ≥ 2 ) , m n ∗ ≤ ⌊ 4 n − 1 ⌋ . (12) The largest value of the first bound occurs at q = 2 q=2 q = 2 ⌈ ( n − 1 ) / 4 ⌉ \lceil(n-1)/4\rceil ⌈( n − 1 ) /4 ⌉ z ∈ Θ n ∖ { 1 } z\in\Theta_n\setminus\{1\} z ∈ Θ n ∖ { 1 } w w w Θ n \Theta_n Θ n 1 1 1 1 1 1 z z z w w w ∂ Θ n \partial\Theta_n ∂ Θ n Θ n \Theta_n Θ n z z z 1 1 1 w w w (9) places z z z Ω n , m \Omega_{n,m} Ω n , m w w w
Invariant polygons and peripheral tangents
Let P P P v ≠ 0 v\ne0 v = 0 P v = λ v Pv=\lambda v P v = λ v i i i λ v i = ∑ j = 0 n − 1 P i j v j \lambda v_i=\sum_{j=0}^{n-1}P_{ij}v_j λ v i = ∑ j = 0 n − 1 P ij v j λ v i \lambda v_i λ v i
λ K ( v ) ⊆ K ( v ) , K ( v ) = conv { v 0 , … , v n − 1 } . (13) \lambda K(v)\subseteq K(v),\qquad K(v)=\operatorname{conv}\{v_0,\ldots,v_{n-1}\}. \tag*{(13)} λ K ( v ) ⊆ K ( v ) , K ( v ) = conv { v 0 , … , v n − 1 } . (13) Repeated application gives λ k K ( v ) ⊆ K ( v ) \lambda^kK(v)\subseteq K(v) λ k K ( v ) ⊆ K ( v ) k ≥ 0 k\ge0 k ≥ 0
Lemma 3.1. Let K ⊂ C K\subset\mathbb{C} K ⊂ C N ≥ 3 N\ge3 N ≥ 3 0 0 0 0 < θ < π / 2 0<\theta<\pi/2 0 < θ < π /2
− t e i θ K ⊆ K ( t ≥ 0 ) . -te^{i\theta}K\subseteq K\qquad(t\ge0). − t e i θ K ⊆ K ( t ≥ 0 ) . This map multiplies distances from 0 0 0 e − t cos θ e^{-t\cos\theta} e − t c o s θ 0 0 0 t sin θ t\sin\theta t sin θ θ ≤ π / 2 − π / N \theta\le\pi/2-\pi/N θ ≤ π /2 − π / N K K K N N N 0 0 0
Proof. List the vertices counterclockwise as z i = R i e i ϕ i z_i=R_i e^{i\phi_i} z i = R i e i ϕ i R i > 0 R_i>0 R i > 0 δ i \delta_i δ i z i − 1 z_{i-1} z i − 1 z i z_i z i 0 0 0 K K K
0 < δ i < π , ∑ i δ i = 2 π . 0<\delta_i<\pi,\qquad\sum_i\delta_i=2\pi. 0 < δ i < π , i ∑ δ i = 2 π . Let γ i \gamma_i γ i z i − 1 z_{i-1} z i − 1 z i z_i z i a i = ϕ i − γ i a_i=\phi_i-\gamma_i a i = ϕ i − γ i
− π 2 < a i − δ i < a i < π 2 , R i R i − 1 = cos ( a i − δ i ) cos a i = cos δ i + tan a i sin δ i . -\frac{\pi}{2}<a_i-\delta_i<a_i<\frac{\pi}{2},\qquad\frac{R_i}{R_{i-1}}=\frac{\cos(a_i-\delta_i)}{\cos a_i}=\cos\delta_i+\tan a_i\sin\delta_i. − 2 π < a i − δ i < a i < 2 π , R i − 1 R i = cos a i cos ( a i − δ i ) = cos δ i + tan a i sin δ i . The curve t ↦ e − t e i θ z i t\mapsto e^{-te^{i\theta}}z_i t ↦ e − t e i θ z i K K K − e i θ z i -e^{i\theta}z_i − e i θ z i − R i cos ( a i + θ ) -R_i\cos(a_i+\theta) − R i cos ( a i + θ ) a i a_i a i a i ≤ π / 2 − θ a_i\leq\pi/2-\theta a i ≤ π /2 − θ tan \tan tan ( − π / 2 , π / 2 ) (-\pi/2,\pi/2) ( − π /2 , π /2 )
0 < R i R i − 1 ≤ sin ( θ + δ i ) sin θ . (14) 0<\frac{R_i}{R_{i-1}}\leq\frac{\sin(\theta+\delta_i)}{\sin\theta}. \tag*{(14)} 0 < R i − 1 R i ≤ sin θ sin ( θ + δ i ) . (14) In particular, θ + δ i ∈ ( 0 , π ) \theta+\delta_i\in(0,\pi) θ + δ i ∈ ( 0 , π ) log sin \log\sin log sin ( 0 , π ) (0,\pi) ( 0 , π )
1 ≤ ∏ i sin ( θ + δ i ) sin θ ≤ [ sin ( θ + 2 π / N ) sin θ ] N . 1\leq\prod_i\frac{\sin(\theta+\delta_i)}{\sin\theta}\leq\left[\frac{\sin(\theta+2\pi/N)}{\sin\theta}\right]^N. 1 ≤ i ∏ sin θ sin ( θ + δ i ) ≤ [ sin θ sin ( θ + 2 π / N ) ] N . Hence sin ( θ + 2 π / N ) ≥ sin θ \sin(\theta+2\pi/N)\geq\sin\theta sin ( θ + 2 π / N ) ≥ sin θ θ < θ + 2 π / N < π \theta<\theta+2\pi/N<\pi θ < θ + 2 π / N < π θ + 2 π / N ≤ π − θ \theta+2\pi/N\leq\pi-\theta θ + 2 π / N ≤ π − θ θ ≤ π / 2 − π / N \theta\leq\pi/2-\pi/N θ ≤ π /2 − π / N
If equality holds, strict concavity of log sin \log\sin log sin δ i \delta_i δ i 2 π / N 2\pi/N 2 π / N (14) is then 1 for every i i i R i / R i − 1 R_i/R_{i-1} R i / R i − 1 K K K N N N
Theorem 3.2. Let P j P_j P j j = 1 , 2 , … j=1,2,\ldots j = 1 , 2 , … n n n P 0 P_0 P 0 P j → P 0 P_j\to P_0 P j → P 0 λ j ∈ spec ( P j ) \lambda_j\in\operatorname{spec}(P_j) λ j ∈ spec ( P j ) q q q ζ \zeta ζ q ≥ 2 q\geq2 q ≥ 2 w j = 1 − ζ ‾ λ j w_j=1-\overline{\zeta}\lambda_j w j = 1 − ζ λ j w j ≠ 0 w_j\neq0 w j = 0 arg w j → θ \arg w_j\to\theta arg w j → θ ζ \zeta ζ r r r P 0 P_0 P 0
∣ θ ∣ ≤ π 2 − π q r . (15) |\theta|\leq\frac{\pi}{2}-\frac{\pi}{qr}. \tag*{(15)} ∣ θ ∣ ≤ 2 π − q r π . (15) If n = q d n=qd n = q d ∣ θ ∣ = π / 2 − π / n > 0 |\theta|=\pi/2-\pi/n>0 ∣ θ ∣ = π /2 − π / n > 0 P 0 P_0 P 0 d d d q q q P j v j = λ j v j P_jv_j=\lambda_jv_j P j v j = λ j v j ∥ v j ∥ ∞ = 1 \|v_j\|_\infty=1 ∥ v j ∥ ∞ = 1 n n n n n n
Proof. Since ∣ λ j ∣ ≤ 1 |\lambda_j|\leq1 ∣ λ j ∣ ≤ 1 w j ≠ 0 w_j\neq0 w j = 0 ℜ w j > 0 \Re w_j>0 ℜ w j > 0 arg w j ∈ ( − π / 2 , π / 2 ) \arg w_j\in(-\pi/2,\pi/2) arg w j ∈ ( − π /2 , π /2 ) ∥ v j ∥ ∞ = 1 \|v_j\|_\infty=1 ∥ v j ∥ ∞ = 1 v j → v v_j\to v v j → v ∥ v ∥ ∞ = 1 \|v\|_\infty=1 ∥ v ∥ ∞ = 1 P 0 v = ζ v P_0v=\zeta v P 0 v = ζ v
For fixed t ≥ 0 t\geq0 t ≥ 0 k j = ⌊ t / ( q ∣ w j ∣ ) ⌋ k_j=\lfloor t/(q|w_j|)\rfloor k j = ⌊ t / ( q ∣ w j ∣ )⌋ λ j = ζ ( 1 − w j ) \lambda_j=\zeta(1-w_j) λ j = ζ ( 1 − w j ) ζ q = 1 \zeta^q=1 ζ q = 1
λ j q k j = ( 1 − w j ) q k j ⟶ e − t e i θ . \lambda_j^{qk_j}=(1-w_j)^{qk_j}\longrightarrow e^{-te^{i\theta}}. λ j q k j = ( 1 − w j ) q k j ⟶ e − t e i θ . Apply (13) repeatedly to obtain λ j q k j K ( v j ) ⊆ K ( v j ) \lambda_j^{qk_j}K(v_j)\subseteq K(v_j) λ j q k j K ( v j ) ⊆ K ( v j )
e − t e i θ K ( v ) ⊆ K ( v ) ( t ≥ 0 ) . (16) e^{-te^{i\theta}}K(v)\subseteq K(v)\qquad(t\geq0). \tag*{(16)} e − t e i θ K ( v ) ⊆ K ( v ) ( t ≥ 0 ) . (16) If θ = ± π / 2 \theta= \pm\pi/2 θ = ± π /2 K ( v ) K(v) K ( v ) θ = 0 \theta= 0 θ = 0 0 < θ < π / 2 0 < \theta< \pi/2 0 < θ < π /2 (16) , the orbit of any nonzero point of K ( v ) K(v) K ( v ) K ( v ) K(v) K ( v ) 2 π / 3 2\pi/3 2 π /3 0 0 0 K ( v ) K(v) K ( v ) 0 0 0 K ( v ) K(v) K ( v )
We next bound the number of vertices of K ( v ) K(v) K ( v ) P 0 P_0 P 0 P 0 P_0 P 0 ζ \zeta ζ q q q r r r v v v q q q a , ζ a , … , ζ q − 1 a a,\zeta a,\ldots,\zeta^{q-1}a a , ζ a , … , ζ q − 1 a a a a
Because P 0 q v = v P_0^qv=v P 0 q v = v v i v_i v i i i i v k v_k v k k k k v k v_k v k i i i P 0 q P_0^q P 0 q k k k { a , ζ a , … , ζ q − 1 a } \{a,\zeta a,\ldots,\zeta^{q-1}a\} { a , ζ a , … , ζ q − 1 a } K ( v ) K(v) K ( v ) q r qr q r Lemma 3.1 now gives (15) .
If n = q d n=qd n = q d ∣ θ ∣ = π / 2 − π / n > 0 |\theta|=\pi/2-\pi/n>0 ∣ θ ∣ = π /2 − π / n > 0 (15) gives q r ≥ n qr\ge n q r ≥ n r r r q q q q r ≤ n qr\le n q r ≤ n r = d r=d r = d q q q q q q N N N K ( v ) K(v) K ( v ) Lemma 3.1 gives ∣ θ ∣ ≤ π / 2 − π / N |\theta|\le\pi/2-\pi/N ∣ θ ∣ ≤ π /2 − π / N ∣ θ ∣ = π / 2 − π / n |\theta|=\pi/2-\pi/n ∣ θ ∣ = π /2 − π / n N ≥ n N\ge n N ≥ n n n n N ≤ n N\le n N ≤ n N = n N=n N = n Lemma 3.1 then shows that the polygon is regular, so the n n n v v v
Consider the arc followed clockwise from ζ = e 2 π i p / q \zeta=e^{2\pi ip/q} ζ = e 2 π i p / q e 2 π i p ′ / s e^{2\pi ip'/s} e 2 π i p ′ / s p s − p ′ q = 1 ps-p'q=1 p s − p ′ q = 1 d = ⌊ n / q ⌋ d=\lfloor n/q\rfloor d = ⌊ n / q ⌋ u = e − 2 π i / ( q d ) u=e^{-2\pi i/(qd)} u = e − 2 π i / ( q d ) α ↓ 0 \alpha\downarrow0 α ↓ 0
λ ( α ) = ζ ( 1 + u − 1 q α + O ( α 2 ) ) , arg ( 1 − ζ ‾ λ ( α ) ) ⟶ π 2 − π q d . (17) \lambda(\alpha)=\zeta\left(1+\frac{u-1}{q}\alpha+O(\alpha^2)\right),\qquad\arg(1-\overline{\zeta}\lambda(\alpha))\longrightarrow\frac{\pi}{2}-\frac{\pi}{qd}. \tag*{(17)} λ ( α ) = ζ ( 1 + q u − 1 α + O ( α 2 ) ) , arg ( 1 − ζ λ ( α )) ⟶ 2 π − q d π . (17) To obtain the expansion, write (10) for a nonzero root as
( z q − 1 + α ) d = α d z q d − s . (z^q-1+\alpha)^d=\alpha^d z^{qd-s}. ( z q − 1 + α ) d = α d z q d − s . Substitute z = ζ ( 1 + α a ) z=\zeta(1+\alpha a) z = ζ ( 1 + α a ) α d \alpha^d α d α → 0 \alpha\to0 α → 0 ζ q d − s = e − 2 π i / q \zeta^{qd-s}=e^{-2\pi i/q} ζ q d − s = e − 2 π i / q
( 1 + q a ) d = e − 2 π i / q . (1+qa)^d=e^{-2\pi i/q}. ( 1 + q a ) d = e − 2 π i / q . The clockwise boundary branch selects 1 + q a = u 1+qa=u 1 + q a = u a a a a = a ( α ) a=a(\alpha) a = a ( α ) a ( 0 ) = ( u − 1 ) / q a(0)=(u-1)/q a ( 0 ) = ( u − 1 ) / q
1 − u = 2 i e − π i / ( q d ) sin ( π q d ) , 1-u=2ie^{-\pi i/(qd)}\sin\left(\frac{\pi}{qd}\right), 1 − u = 2 i e − π i / ( q d ) sin ( q d π ) , so arg ( 1 − u ) = π / 2 − π / ( q d ) \arg(1-u)=\pi/2-\pi/(qd) arg ( 1 − u ) = π /2 − π / ( q d )
Proposition 3.3. Let A A A q < s q<s q < s ζ \zeta ζ q q q q q q n n n 2 m < ⌊ n / q ⌋ 2m<\lfloor n/q\rfloor 2 m < ⌊ n / q ⌋ A A A ζ \zeta ζ ζ \zeta ζ Ω n , m \Omega_{n,m} Ω n , m
Proof. Suppose instead that there are matrices P j ∈ Q n , m P_j \in\mathcal{Q}_{n,m} P j ∈ Q n , m α j \alpha_j α j 0 0 0 Q n , m \mathcal{Q}_{n,m} Q n , m P 0 ∈ Q n , m P_0 \in\mathcal{Q}_{n,m} P 0 ∈ Q n , m d = ⌊ n / q ⌋ d = \lfloor n/q \rfloor d = ⌊ n / q ⌋ r r r ζ \zeta ζ P 0 P_0 P 0 (15) and (17) , taking complex conjugates if necessary, gives r ≥ d r \ge d r ≥ d
Write P 0 = C + E P_0 = C + E P 0 = C + E (6) , with C C C rank E ≤ 2 m \operatorname{rank} E \le2m rank E ≤ 2 m C C C n n n 1 1 1 C C C n n n ζ \zeta ζ q q q q q q n n n n n n C − ζ I C-\zeta I C − ζ I
For every vector x x x P 0 x = ζ x P_0x = \zeta x P 0 x = ζ x
x = − ( C − ζ I ) − 1 E x . x = -(C-\zeta I)^{-1}Ex. x = − ( C − ζ I ) − 1 E x . The eigenspace is therefore contained in the image of a matrix of rank at most rank E ≤ 2 m \operatorname{rank} E \le2m rank E ≤ 2 m 2 m 2m 2 m r r r r ≥ d > 2 m r \ge d > 2m r ≥ d > 2 m
Divisor roots and local polygon boundaries
When q q q n n n ζ \zeta ζ n n n P = C + E P = C + E P = C + E C − ζ I C-\zeta I C − ζ I 2 m < n / q 2m < n/q 2 m < n / q Ω n , m \Omega_{n,m} Ω n , m H n H_n H n ζ \zeta ζ
Theorem 4.1 (Local equality with the circulant polygon). Suppose n = q d n = qd n = q d q ≥ 2 q \ge2 q ≥ 2 d ≥ 3 d \ge3 d ≥ 3 2 m < d 2m < d 2 m < d For every primitive q q q th root of unity ζ \zeta ζ there is an ε > 0 \varepsilon> 0 ε > 0 such that, with U = { z ∈ C : ∣ z − ζ ∣ < ε } U = \{z \in\mathbb{C} : |z-\zeta| < \varepsilon\} U = { z ∈ C : ∣ z − ζ ∣ < ε }
Ω n , m ∩ U = H n ∩ U . (18) \Omega_{n,m} \cap U = H_n \cap U. \tag*{(18)} Ω n , m ∩ U = H n ∩ U . (18) On each of the two Karpelevič boundary arcs meeting ζ \zeta ζ all points sufficiently close to ζ \zeta ζ but not equal to it therefore lie outside Ω n , m \Omega_{n,m} Ω n , m
The radius ε \varepsilon ε n n n m m m ζ \zeta ζ n n n Figure 2 illustrates the two boundaries for n = 9 n = 9 n = 9 m = 1 m = 1 m = 1
Figure 2. The circulant polygon H 9 H_9 H 9 ζ = e 2 π i / 3 \zeta=e^{2\pi i/3} ζ = e 2 π i /3 H 9 H_9 H 9 λ 7 ( α ) \lambda_7(\alpha) λ 7 ( α ) ζ \zeta ζ e 4 π i / 7 e^{4\pi i/7} e 4 π i /7 λ 8 ( α ) \lambda_8(\alpha) λ 8 ( α ) e 3 π i / 4 e^{3\pi i/4} e 3 π i /4 α \alpha α 0 ≤ α ≤ 1 / 2 0 \le\alpha\le1/2 0 ≤ α ≤ 1/2 x = Im ( ζ ‾ z ) x=\operatorname{Im}(\overline{\zeta}z) x = Im ( ζ z ) y = Re ( ζ ‾ z ) − 1 y=\operatorname{Re}(\overline{\zeta}z)-1 y = Re ( ζ z ) − 1 ζ \zeta ζ ( 0 , 0 ) (0,0) ( 0 , 0 ) H 9 H_9 H 9 α = 1 / 2 \alpha=1/2 α = 1/2 d j ( α ) = dist ( λ j ( α ) , L j ) d_j(\alpha)=\operatorname{dist}(\lambda_j(\alpha),L_j) d j ( α ) = dist ( λ j ( α ) , L j ) L j L_j L j ζ \zeta ζ Theorem 4.1 , Ω 9 , 1 \Omega_{9,1} Ω 9 , 1 H 9 H_9 H 9 ζ \zeta ζ
For m = 0 m = 0 m = 0 Ω n , 0 = H n \Omega_{n,0} = H_n Ω n , 0 = H n m ≥ 1 m \ge1 m ≥ 1 λ j ∈ Ω n , m ∖ H n \lambda_j \in\Omega_{n,m} \setminus H_n λ j ∈ Ω n , m ∖ H n ζ \zeta ζ P j ∈ Q n , m P_j \in\mathcal{Q}_{n,m} P j ∈ Q n , m P j P_j P j P 0 P_0 P 0 v j v_j v j ∥ v j ∥ ∞ = 1 \lVert v_j\rVert_\infty= 1 ∥ v j ∥ ∞ = 1 v v v arg ( 1 − ζ ‾ λ j ) \arg(1-\overline{\zeta}\lambda_j) arg ( 1 − ζ λ j )
Near ζ \zeta ζ ζ \zeta ζ Theorem 3.2 bounds the absolute value of the limit of arg ( 1 − ζ ‾ λ j ) \arg(1-\overline{\zeta}\lambda_j) arg ( 1 − ζ λ j ) π / 2 − π / n \pi/2-\pi/n π /2 − π / n q q q ζ \zeta ζ n n n u = e − 2 π i / n u = e^{-2\pi i/n} u = e − 2 π i / n
α j = q Re λ j − ζ ζ ( u − 1 ) . \alpha_j = q\operatorname{Re}\frac{\lambda_j-\zeta}{\zeta(u-1)}. α j = q Re ζ ( u − 1 ) λ j − ζ . Then α j > 0 \alpha_j > 0 α j > 0 j j j
λ j = ζ ( 1 + u − 1 q α j + o ( α j ) ) . \lambda_j = \zeta\left(1+\frac{u-1}{q}\alpha_j+o(\alpha_j)\right). λ j = ζ ( 1 + q u − 1 α j + o ( α j ) ) . The limit of arg ( 1 − ζ ‾ λ j ) \arg(1-\overline{\zeta}\lambda_j) arg ( 1 − ζ λ j ) π / 2 − π / n \pi/2-\pi/n π /2 − π / n Theorem 3.2 therefore implies that P 0 P_0 P 0 d d d q q q 1 1 1 v v v n n n 0 0 0 1 1 1 ∥ v ∥ ∞ = 1 \lVert v\rVert_\infty=1 ∥ v ∥ ∞ = 1
Every interior row i i i P 0 P_0 P 0 1 1 1 i + h ( m o d n ) i+h\pmod n i + h ( mod n ) h h h 2 m < d 2m<d 2 m < d B n , m B_{n,m} B n , m d d d I n , m I_{n,m} I n , m h h h n n n q q q
gcd ( h , n ) = d , R = C n h . \gcd(h,n)=d,\qquad R=C_n^h. g cd( h , n ) = d , R = C n h . The cycles of R R R d d d B n , m B_{n,m} B n , m 2 m < d 2m<d 2 m < d b ∈ B n , m b\in B_{n,m} b ∈ B n , m R ( b ) R(b) R ( b ) b b b 2 q 2q 2 q P 0 P_0 P 0 q q q P 0 = R P_0=R P 0 = R
Let K K K K v = u v Kv=uv K v = uv K K K n n n K K K R R R S = R K S=RK S = R K
A = 1 q ∑ k = 0 q − 1 R k . \mathcal{A}=\frac{1}{q}\sum_{k=0}^{q-1}R^k. A = q 1 k = 0 ∑ q − 1 R k . This is the orthogonal projection onto vectors constant on each R R R f f f I n , m I_{n,m} I n , m
∥ A f ∥ 2 ≥ κ ∥ f ∥ 2 , κ = d − 2 m n − 2 m > 0. (19) \lVert Af\rVert^2\geq\kappa\lVert f\rVert^2,\qquad\kappa=\frac{d-2m}{n-2m}>0. \tag*{(19)} ∥ A f ∥ 2 ≥ κ ∥ f ∥ 2 , κ = n − 2 m d − 2 m > 0. (19) Indeed, write f = c 1 + x f=c\mathbf{1}+x f = c 1 + x x x x B n , m B_{n,m} B n , m n c = − ∑ i x i nc=-\sum_i x_i n c = − ∑ i x i R R R
∥ f ∥ 2 = ∥ x ∥ 2 − ( ∑ i x i ) 2 n , ∥ A f ∥ 2 = ∥ x ∥ 2 q − ( ∑ i x i ) 2 n . \lVert f\rVert^2=\lVert x\rVert^2-\frac{(\sum_i x_i)^2}{n},\qquad\lVert Af\rVert^2=\frac{\lVert x\rVert^2}{q}-\frac{(\sum_i x_i)^2}{n}. ∥ f ∥ 2 = ∥ x ∥ 2 − n ( ∑ i x i ) 2 , ∥ A f ∥ 2 = q ∥ x ∥ 2 − n ( ∑ i x i ) 2 . The bound ( ∑ i x i ) 2 ≤ 2 m ∥ x ∥ 2 (\sum_i x_i)^2\leq2m\lVert x\rVert^2 ( ∑ i x i ) 2 ≤ 2 m ∥ x ∥ 2 (19) .
Lemma 4.2. Along the chosen subsequence,
P j = R + α j q ( S − R ) + o ( α j ) . (20) P_j=R+\frac{\alpha_j}{q}(S-R)+o(\alpha_j). \tag*{(20)} P j = R + q α j ( S − R ) + o ( α j ) . (20) Proof. First put η j = max i ( 1 − ( P j ) i , R ( i ) ) \eta_j=\max_i(1-(P_j)_{i,R(i)}) η j = max i ( 1 − ( P j ) i , R ( i ) ) P j − R = O ( η j ) P_j-R=O(\eta_j) P j − R = O ( η j ) ϕ i ( z ) = Re ( v i ‾ z ) \phi_i(z)=\operatorname{Re}(\overline{v_i}z) ϕ i ( z ) = Re ( v i z ) j j j ϕ i ( v j , i − v j , k ) ≥ c > 0 \phi_i(v_{j,i}-v_{j,k})\geq c>0 ϕ i ( v j , i − v j , k ) ≥ c > 0 k ≠ i k\ne i k = i ϕ i \phi_i ϕ i P j q v j = λ j q v j P_j^qv_j=\lambda_j^qv_j P j q v j = λ j q v j
c ∑ k ≠ i ( P j q ) i k ≤ ϕ i ( ( 1 − λ j q ) v j , i ) = O ( α j ) . c\sum_{k\ne i}(P_j^q)_{ik}\leq\phi_i((1-\lambda_j^q)v_{j,i})=O(\alpha_j). c k = i ∑ ( P j q ) ik ≤ ϕ i (( 1 − λ j q ) v j , i ) = O ( α j ) . A transition different from R R R q − 1 q-1 q − 1 R R R η j \eta_j η j η j ( 1 − η j ) q − 1 \eta_j(1-\eta_j)^{q-1} η j ( 1 − η j ) q − 1 η j → 0 \eta_j\to0 η j → 0 P j − R = O ( α j ) P_j-R=O(\alpha_j) P j − R = O ( α j )
Every subsequence now has a further subsequence on which ( P j − R ) / α j (P_j-R)/\alpha_j ( P j − R ) / α j A A A q q q
G = ∑ k = 0 q − 1 R k A R q − 1 − k , G v = ( u − 1 ) v = ( K − I ) v . G=\sum_{k=0}^{q-1}R^kAR^{q-1-k},\qquad Gv=(u-1)v=(K-I)v. G = k = 0 ∑ q − 1 R k A R q − 1 − k , G v = ( u − 1 ) v = ( K − I ) v . The off-diagonal entries of G G G v i v_i v i v K ( i ) − v i v_{K(i)}-v_i v K ( i ) − v i G = K − I G=K-I G = K − I
The matrix H = A R − 1 H=AR^{-1} H = A R − 1
∑ k = 0 q − 1 R k H R − k = K − I . \sum_{k=0}^{q-1}R^kHR^{-k}=K-I. k = 0 ∑ q − 1 R k H R − k = K − I . Its off-diagonal entries cannot cancel, so
A = diag ( a ) ( S − R ) , a i ≥ 0 , ∑ k = 0 q − 1 a R k ( i ) = 1. A=\operatorname{diag}(a)(S-R),\qquad a_i\geq0,\qquad\sum_{k=0}^{q-1}a_{R^k(i)}=1. A = diag ( a ) ( S − R ) , a i ≥ 0 , k = 0 ∑ q − 1 a R k ( i ) = 1. The interior entries A i , R ( i ) = − a i A_{i,R(i)}=-a_i A i , R ( i ) = − a i a − q − 1 1 a-q^{-1}\mathbf{1} a − q − 1 1 I n , m I_{n,m} I n , m (19) forces a = q − 1 1 a=q^{-1}\mathbf{1} a = q − 1 1 ( S − R ) / q (S-R)/q ( S − R ) / q
Completion of the proof of Theorem 4.1. The matrix S S S S ( i ) = i + h ′ S(i)=i+h' S ( i ) = i + h ′ n n n h ′ h' h ′ R R R R R R K = R − 1 S K=R^{-1}S K = R − 1 S n n n v v v v 0 = 1 v_0=1 v 0 = 1 n n n t j = n − 1 ∑ i ( P j ) i , S ( i ) t_j=n^{-1}\sum_i(P_j)_{i,S(i)} t j = n − 1 ∑ i ( P j ) i , S ( i ) j j j
P = R + t diag ( 1 + F ) ( S − R ) + t G , t ∼ α j / q , F → 0 , G → 0. (21) P=R+t\operatorname{diag}(1+F)(S-R)+tG,\qquad t\sim\alpha_j/q,\qquad F\to0,\qquad G\to0. \tag*{(21)} P = R + t diag ( 1 + F ) ( S − R ) + tG , t ∼ α j / q , F → 0 , G → 0. (21) Here F i = P i , S ( i ) / t − 1 F_i=P_{i,S(i)}/t-1 F i = P i , S ( i ) / t − 1 I n , m I_{n,m} I n , m R , S R,S R , S G i k = P i k / t ≥ 0 G_{ik}=P_{ik}/t\geq0 G ik = P ik / t ≥ 0 S S S R R R
ℓ ( G ) = ∑ i ∑ k ∉ { R ( i ) , S ( i ) } G i k , ∥ G ∥ ≤ C ℓ ( G ) , \ell(G)=\sum_i\sum_{k\notin\{R(i),S(i)\}}G_{ik},\qquad\lVert G\rVert\leq C\ell(G), ℓ ( G ) = i ∑ k ∈ / { R ( i ) , S ( i )} ∑ G ik , ∥ G ∥ ≤ C ℓ ( G ) , the total outside mass controls G G G
Let V = diag ( v ) V=\operatorname{diag}(v) V = diag ( v ) G ^ = ζ − 1 V ∗ G V \widehat{G}=\zeta^{-1}V^*GV G = ζ − 1 V ∗ G V λ = ζ ( 1 + t σ ) \lambda=\zeta(1+t\sigma) λ = ζ ( 1 + t σ ) σ → u − 1 \sigma\to u-1 σ → u − 1 x → v x\to v x → v x ^ = V ∗ x = y + z \widehat{x}=V^*x=y+z x = V ∗ x = y + z y = A x ^ y=A\widehat{x} y = A x z = ( I − A ) x ^ z=(I-A)\widehat{x} z = ( I − A ) x y = 1 + h y=\mathbf{1}+h y = 1 + h 1 ∗ h = 0 \mathbf{1}^*h=0 1 ∗ h = 0
[ R + t diag ( 1 + F ) R ( u K − I ) + t G ^ ] x ^ = ( 1 + t σ ) x ^ . [R+t\operatorname{diag}(1+F)R(uK-I)+t\widehat{G}]\widehat{x}=(1+t\sigma)\widehat{x}. [ R + t diag ( 1 + F ) R ( u K − I ) + t G ] x = ( 1 + t σ ) x . The operator R − I R-I R − I Fix ( R ) \operatorname{Fix}(R) Fix ( R ) R ( u K − I ) R(uK-I) R ( u K − I ) z = O ( t ( ∥ F ∥ + ∥ G ∥ ) ) z=O(t(\lVert F\rVert+\lVert G\rVert)) z = O ( t (∥ F ∥ + ∥ G ∥))
σ y = D ( u K − I ) y + A G ^ y + ϵ , D = diag ( 1 + g ) , g = A F , ∥ ϵ ∥ ≤ C t ( ∥ F ∥ + ∥ G ∥ ) 2 . (22) \sigma y=D(uK-I)y+A\widehat{G}y+\epsilon,
\qquad
D=\operatorname{diag}(1+g),\qquad
g=AF,\qquad
\lVert\epsilon\rVert\leq Ct(\lVert F\rVert+\lVert G\rVert)^2. \tag*{(22)} σ y = D ( u K − I ) y + A G y + ϵ , D = diag ( 1 + g ) , g = A F , ∥ ϵ ∥ ≤ C t (∥ F ∥ + ∥ G ∥ ) 2 . (22) Here ε = A [ diag ( F ) R ( u K − I ) + G ^ ] z \varepsilon=A[\operatorname{diag}(F)R(uK-I)+\widehat{G}]z ε = A [ diag ( F ) R ( u K − I ) + G ] z
Projecting this equation onto mean-zero vectors gives
∣ u − 1 ∣ ∥ g ∥ ≤ C ( ∥ h ∥ + ∥ g ∥ ∥ h ∥ + ∥ G ∥ + t ( ∥ F ∥ + ∥ G ∥ ) 2 ) . |u-1|\|g\|\le C(\|h\|+\|g\|\|h\|+\|G\|+t(\|F\|+\|G\|)^2). ∣ u − 1∣∥ g ∥ ≤ C ( ∥ h ∥ + ∥ g ∥∥ h ∥ + ∥ G ∥ + t ( ∥ F ∥ + ∥ G ∥ ) 2 ) . Since ∥ g ∥ ≥ κ ∥ F ∥ \|g\|\ge\sqrt{\kappa}\|F\| ∥ g ∥ ≥ κ ∥ F ∥ (19) and t , F , G , h → 0 t,F,G,h\to0 t , F , G , h → 0
∥ F ∥ ≤ C ( ∥ h ∥ + ∥ G ∥ ) , ∥ ε ∥ ≤ C t ( ∥ h ∥ 2 + ∥ G ∥ 2 ) . (23) \|F\|\le C(\|h\|+\|G\|),\qquad\|\varepsilon\|\le Ct(\|h\|^2+\|G\|^2). \tag*{(23)} ∥ F ∥ ≤ C ( ∥ h ∥ + ∥ G ∥ ) , ∥ ε ∥ ≤ C t ( ∥ h ∥ 2 + ∥ G ∥ 2 ) . (23) Put n ( w ) = Im ( w / ( u − 1 ) ) n(w)=\operatorname{Im}(w/(u-1)) n ( w ) = Im ( w / ( u − 1 )) Fix ( R ) \operatorname{Fix}(R) Fix ( R ) K K K d d d u ρ u\rho u ρ n n n u u u 1 1 1 u ρ u\rho u ρ 1 1 1 u u u K K K 1 ∗ h = 0 1^*h=0 1 ∗ h = 0 c > 0 c>0 c > 0
n ( y ∗ ( u K − I ) y ) ≤ − c ∥ h ∥ 2 . n(y^*(uK-I)y)\le-c\|h\|^2. n ( y ∗ ( u K − I ) y ) ≤ − c ∥ h ∥ 2 . Multiply (22) by y ∗ D − 1 y^*D^{-1} y ∗ D − 1 D D D j j j D − 1 y ∈ Fix ( R ) D^{-1}y\in\operatorname{Fix}(R) D − 1 y ∈ Fix ( R ) G G G G i k G_{ik} G ik
G i k y i ‾ 1 + g i ( ζ − 1 v i ‾ v k y k − y i ) . G_{ik}\frac{\overline{y_i}}{1+g_i}\left(\zeta^{-1}\overline{v_i}v_k y_k-y_i\right). G ik 1 + g i y i ( ζ − 1 v i v k y k − y i ) . At y = 1 y=1 y = 1 g = 0 g=0 g = 0 ζ − 1 v i ‾ v k \zeta^{-1}\overline{v_i}v_k ζ − 1 v i v k n n n 1 , u 1,u 1 , u y → 1 y\to1 y → 1 g → 0 g\to0 g → 0 (23) , we obtain fixed a , c , C > 0 a,c,C>0 a , c , C > 0
n ( σ ) y ∗ D − 1 y ≤ − c ∥ h ∥ 2 − a ℓ ( G ) + C t ( ∥ h ∥ 2 + ℓ ( G ) 2 ) ≤ 0 n(\sigma)y^*D^{-1}y\le-c\|h\|^2-a\ell(G)+Ct(\|h\|^2+\ell(G)^2)\le0 n ( σ ) y ∗ D − 1 y ≤ − c ∥ h ∥ 2 − a ℓ ( G ) + C t ( ∥ h ∥ 2 + ℓ ( G ) 2 ) ≤ 0 eventually. The factor y ∗ D − 1 y y^*D^{-1}y y ∗ D − 1 y Im ( ( λ − ζ ) / ( ζ ( u − 1 ) ) ) = t n ( σ ) > 0 \operatorname{Im}((\lambda-\zeta)/(\zeta(u-1)))=tn(\sigma)>0 Im (( λ − ζ ) / ( ζ ( u − 1 ))) = t n ( σ ) > 0 (18) , since H n ⊆ Ω n , m H_n\subseteq\Omega_{n,m} H n ⊆ Ω n , m
It remains to show that each Karpelevič arc meeting ζ \zeta ζ s s s (10) gives
λ ( α ) = ζ ( 1 + a α + b α 2 + O ( α 3 ) ) , \lambda(\alpha)=\zeta(1+a\alpha+b\alpha^2+O(\alpha^3)), λ ( α ) = ζ ( 1 + a α + b α 2 + O ( α 3 )) , a = u − 1 q , b u − 1 = u ( n − s ) d q 2 − ( q − 1 ) ( u − 1 ) 2 q 2 . a=\frac{u-1}{q},\qquad\frac{b}{u-1}=\frac{u(n-s)}{dq^2}-\frac{(q-1)(u-1)}{2q^2}. a = q u − 1 , u − 1 b = d q 2 u ( n − s ) − 2 q 2 ( q − 1 ) ( u − 1 ) . Consequently,
Im λ ( α ) − ζ ζ ( u − 1 ) = sin ( 2 π / n ) q 2 ( q − 1 2 − n − s d ) α 2 + O ( α 3 ) > 0 \operatorname{Im}\frac{\lambda(\alpha)-\zeta}{\zeta(u-1)}
=\frac{\sin(2\pi/n)}{q^2}\left(\frac{q-1}{2}-\frac{n-s}{d}\right)\alpha^2+O(\alpha^3)>0 Im ζ ( u − 1 ) λ ( α ) − ζ = q 2 sin ( 2 π / n ) ( 2 q − 1 − d n − s ) α 2 + O ( α 3 ) > 0 for small positive α \alpha α q + s > n q+s>n q + s > n n − s ≤ q − 1 n-s\le q-1 n − s ≤ q − 1 ( q − 1 ) ( 1 / 2 − 1 / d ) > 0 (q-1)(1/2-1/d)>0 ( q − 1 ) ( 1/2 − 1/ d ) > 0 d ≥ 3 d\ge3 d ≥ 3 H n H_n H n Ω n , m \Omega_{n,m} Ω n , m
Proof of the individual and arc assertions in Theorem 1.1.
The upper bounds are given by (12) . For q ≥ 2 q\ge2 q ≥ 2 q q q n n n n = q d n=qd n = q d d ≥ 3 d\ge3 d ≥ 3 m = 0 m=0 m = 0
It remains to consider n = 2 q n=2q n = 2 q m = 1 m=1 m = 1 q < s < n q<s<n q < s < n s = 2 q s=2q s = 2 q 2 q 2q 2 q q q q s s s n n n n n n H n = Ω n , 0 H_n = \Omega_{n,0} H n = Ω n , 0 m = 0 m = 0 m = 0 m = 1 m = 1 m = 1
The largest of these minimum values occurs at q = 2 q = 2 q = 2 ⌈ ⌊ n / 2 ⌋ / 2 ⌉ = ⌈ ( n − 1 ) / 4 ⌉ \lceil\lfloor n/2\rfloor/2\rceil= \lceil(n - 1)/4\rceil ⌈⌊ n /2 ⌋ /2 ⌉ = ⌈( n − 1 ) /4 ⌉ Θ n \Theta_n Θ n (12) fills the whole region from its boundary. This proves (3) .
For n = 2 n = 2 n = 2 { 1 , t } \{1,t\} { 1 , t } − 1 ≤ t ≤ 1 -1 \le t \le1 − 1 ≤ t ≤ 1
1 2 ( 1 + t 1 − t 1 − t 1 + t ) \frac{1}{2}
\begin{pmatrix}
1+t & 1-t \\
1-t & 1+t
\end{pmatrix} 2 1 ( 1 + t 1 − t 1 − t 1 + t ) so m 2 ∗ = 0 m_2^* = 0 m 2 ∗ = 0 n = 1 n = 1 n = 1 [ 1 ] [1] [ 1 ] m 1 ∗ = 0 m_1^* = 0 m 1 ∗ = 0
Complete spectra and the two-row problem
To show that our family cannot reproduce every complete stochastic spectrum, we seek an eigenvalue list that occurs for a stochastic matrix of order n n n Q n , m Q_{n,m} Q n , m 1 1 1
det ( z I − P ) = z n + c n − 1 z n − 1 + ⋯ + c 0 , coeff ( P ) = ( c n − 1 , … , c 0 ) ∈ R n . (24) \begin{aligned}
\det(zI-P) &= z^n + c_{n-1}z^{n-1} + \cdots+ c_0,\\
\operatorname{coeff}(P) &= (c_{n-1},\ldots,c_0) \in\mathbb{R}^n. \tag*{(24)}
\end{aligned} det ( z I − P ) coeff ( P ) = z n + c n − 1 z n − 1 + ⋯ + c 0 , = ( c n − 1 , … , c 0 ) ∈ R n . (24) Each coefficient list determines the eigenvalues with multiplicity. The map P ↦ coeff ( P ) P \mapsto\operatorname{coeff}(P) P ↦ coeff ( P ) n ≥ 4 n \ge4 n ≥ 4 n = 3 n = 3 n = 3
In even order, the remaining step is to find eigenvalue lists that cannot be reproduced by a matrix with two consecutive interior rows. In the general construction, we choose eigenvalues so that every stochastic matrix P P P tr ( P 4 ) \operatorname{tr}(P^4) tr ( P 4 ) tr P \operatorname{tr} P tr P tr ( P 2 ) \operatorname{tr}(P^2) tr ( P 2 ) tr ( P k ) \operatorname{tr}(P^k) tr ( P k ) k k k 1 1 1 − 1 -1 − 1
Three homogeneous rows
For n ≥ 3 n \ge3 n ≥ 3 n = 3 k + r n = 3k + r n = 3 k + r r ∈ { 0 , 1 , 2 } r \in\{0,1,2\} r ∈ { 0 , 1 , 2 }
b i = i 100 n 3 ( 1 ≤ i ≤ k ) , J n = I r ⊕ ⨁ i = 1 k [ b i I 3 + ( 1 − b i ) C 3 ] . (25) b_i = \frac{i}{100n^3}\quad(1 \le i \le k),\qquad
J_n = I_r \oplus\bigoplus_{i=1}^{k}\left[b_i I_3 + (1-b_i)C_3\right]. \tag*{(25)} b i = 100 n 3 i ( 1 ≤ i ≤ k ) , J n = I r ⊕ i = 1 ⨁ k [ b i I 3 + ( 1 − b i ) C 3 ] . (25) Here ⊕ \oplus ⊕ 0 0 0 i i i b i b_i b i 1 − b i 1-b_i 1 − b i I r I_r I r r r r r = 0 r = 0 r = 0
Theorem 5.1. Every stochastic matrix with the same eigenvalues as J n J_n J n J n J_n J n
Proof. Let P P P J n J_n J n δ = 3 ∑ i b i < 1 \delta= 3\sum_i b_i < 1 δ = 3 ∑ i b i < 1 B B B y > 0 y > 0 y > 0
y T ( 1 − B 1 ) = 0. y^{\mathsf{T}}(1-B\mathbf{1})=0. y T ( 1 − B 1 ) = 0. The vector in parentheses is nonnegative, so B 1 = 1 B\mathbf{1}=1 B 1 = 1 P P P
Each block contributes one simple eigenvalue 1, so there are k + r k+r k + r f f f
3 k + r ≥ f + 3 ( k + r − f ) , f ≤ tr P = r + δ < r + 1. 3k+r \ge f+3(k+r-f), \qquad f \le\operatorname{tr} P=r+\delta<r+1. 3 k + r ≥ f + 3 ( k + r − f ) , f ≤ tr P = r + δ < r + 1. Hence f = r f=r f = r k k k
Each three-state block D D D
b i + ( 1 − b i ) ω , b i + ( 1 − b i ) ω ‾ , ω = e 2 π i / 3 . b_i+(1-b_i)\omega,\qquad b_i+(1-b_i)\overline{\omega},\qquad\omega=e^{2\pi i/3}. b i + ( 1 − b i ) ω , b i + ( 1 − b i ) ω , ω = e 2 π i /3 . Thus tr D = 3 b i \operatorname{tr}D=3b_i tr D = 3 b i tr D 2 = 3 b i 2 \operatorname{tr}D^2=3b_i^2 tr D 2 = 3 b i 2
0 = ∑ j = 1 3 ( D j j − b i ) 2 + 2 ∑ j < ℓ D j ℓ D ℓ j . 0=\sum_{j=1}^{3}(D_{jj}-b_i)^2+2\sum_{j<\ell}D_{j\ell}D_{\ell j}. 0 = j = 1 ∑ 3 ( D j j − b i ) 2 + 2 j < ℓ ∑ D j ℓ D ℓ j . All diagonal entries equal b i b_i b i 1 − b i > 0 1-b_i>0 1 − b i > 0 1 − b i 1-b_i 1 − b i D = b i I 3 + ( 1 − b i ) C 3 D=b_iI_3+(1-b_i)C_3 D = b i I 3 + ( 1 − b i ) C 3
Corollary 5.2. If n ≥ 4 n\ge4 n ≥ 4 n − 2 m ≥ 3 n-2m\ge3 n − 2 m ≥ 3 Q n , m Q_{n,m} Q n , m J n J_n J n
j n ∗ = n − 1 2 for odd n ≥ 3 , n 2 − 1 ≤ j n ∗ ≤ n 2 for even n ≥ 4. j_n^*=\frac{n-1}{2}\quad\text{for odd }n\ge3,\qquad
\frac{n}{2}-1\le j_n^*\le\frac{n}{2}\quad\text{for even }n\ge4. j n ∗ = 2 n − 1 for odd n ≥ 3 , 2 n − 1 ≤ j n ∗ ≤ 2 n for even n ≥ 4. Proof. Suppose that P ∈ Q n , m P\in Q_{n,m} P ∈ Q n , m J n J_n J n Theorem 5.1 , each value b i b_i b i
If there are three, their states must form one of the closed three-state cycles. The circulant matrix determined by these rows is then
C = b ℓ I + ( 1 − b ℓ ) C n s C=b_\ell I+(1-b_\ell)C_n^s C = b ℓ I + ( 1 − b ℓ ) C n s for some ℓ \ell ℓ 1 ≤ s < n 1\le s<n 1 ≤ s < n i i i i i i i + s i+s i + s n n n s s s n n n
I n , m = { m , m + 1 , … , n − m − 1 } . I_{n,m}=\{m,m+1,\ldots,n-m-1\}. I n , m = { m , m + 1 , … , n − m − 1 } . This is a nonempty proper interval in the cyclic order. Its first state, m m m m m m s = 0 s = 0 s = 0 n n n
For odd n ≥ 5 n \ge5 n ≥ 5 m < ( n − 1 ) / 2 m < (n-1)/2 m < ( n − 1 ) /2 m = ( n − 1 ) / 2 m = (n-1)/2 m = ( n − 1 ) /2 n = 3 n = 3 n = 3 { 1 , 1 , − 1 } \{1, 1, -1\} { 1 , 1 , − 1 } 1 1 1 1 1 1 − 1 -1 − 1 j 3 ∗ = 1 j_3^* = 1 j 3 ∗ = 1
For even n n n m < n / 2 − 1 m < n/2 - 1 m < n /2 − 1 m = n / 2 m = n/2 m = n /2 n / 2 − 1 ≤ j n ∗ ≤ n / 2 n/2 - 1 \le j_n^* \le n/2 n /2 − 1 ≤ j n ∗ ≤ n /2
For even n ≥ 4 n \ge4 n ≥ 4 J n J_n J n Q n , n / 2 − 1 Q_{n,n/2-1} Q n , n /2 − 1 b i I + ( 1 − b i ) C n b_i I + (1-b_i)C_n b i I + ( 1 − b i ) C n
Two homogeneous rows in even order
Proposition 5.3. For n = 4 n = 4 n = 4 j 4 ∗ = 2 j_4^* = 2 j 4 ∗ = 2
Proof. Choose 0 < b < a < 1 0 < b < a < 1 0 < b < a < 1 3 a − b > 2 3a - b > 2 3 a − b > 2
( 0 1 0 0 1 0 0 0 1 − a 0 a 0 1 − b 0 0 b ) \begin{pmatrix}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
1-a & 0 & a & 0 \\
1-b & 0 & 0 & b
\end{pmatrix} 0 1 1 − a 1 − b 1 0 0 0 0 0 a 0 0 0 0 b has eigenvalues { 1 , − 1 , a , b } \{1, -1, a, b\} { 1 , − 1 , a , b }
In any stochastic matrix with these eigenvalues, the eigenvalue − 1 -1 − 1 i i i − i -i − i 0 0 0 a , b > 0 a, b > 0 a , b > 0 1 1 1 1 1 1
The submatrix on the other two states has the form
T = ( d 1 x y d 2 ) , d 1 + d 2 = a + b , d 1 d 2 − x y = a b > 0. T = \begin{pmatrix} d_1 & x \\ y & d_2 \end{pmatrix}, \qquad d_1 + d_2 = a + b,\qquad d_1d_2 - xy = ab > 0. T = ( d 1 y x d 2 ) , d 1 + d 2 = a + b , d 1 d 2 − x y = ab > 0. Both d 1 d_1 d 1 d 2 d_2 d 2 0 0 0
Suppose now that a matrix in Q 4 , 1 Q_{4,1} Q 4 , 1
In the second case, d 1 = d 2 = c = ( a + b ) / 2 d_1 = d_2 = c = (a+b)/2 d 1 = d 2 = c = ( a + b ) /2 x y = ( a − b ) 2 / 4 xy = (a-b)^2/4 x y = ( a − b ) 2 /4 c c c x x x y y y
1 ≥ c + x + y ≥ a + b 2 + 2 x y = 3 a − b 2 > 1 , 1 \ge c + x + y \ge\frac{a+b}{2} + 2\sqrt{xy} = \frac{3a-b}{2} > 1, 1 ≥ c + x + y ≥ 2 a + b + 2 x y = 2 3 a − b > 1 , ::: again a contradiction. Thus m = 1 m = 1 m = 1 m = 2 m = 2 m = 2
For the remaining even orders, we seek complete eigenvalue lists of stochastic matrices that no matrix in Q n , n / 2 − 1 \mathcal{Q}_{n,n/2-1} Q n , n /2 − 1
We call a row’s diagonal entry, together with the multiset of all its entries, its row profile . The multiset records each entry with its repetitions. Rows of one circulant matrix have the same row profile, so matching row profiles is a necessary condition for obtaining the second interior row by shifting the first cyclically one position to the right. To compare dimensions, we represent each eigenvalue list by the coefficients of its monic characteristic polynomial.
Lemma 5.4. Let n = 2 q n = 2q n = 2 q b > 0 b > 0 b > 0 0 < δ ≤ b / ( 100 n 2 ) 0 < \delta\le b/(100n^2) 0 < δ ≤ b / ( 100 n 2 ) w = b 2 w = b^2 w = b 2 A A A n n n
tr A = q δ , tr A 2 = q ( δ 2 + 2 w ) , tr A 4 = q ( δ 4 + 4 w δ 2 + 2 w 2 ) . (26) \operatorname{tr} A = q\delta,\qquad\operatorname{tr} A^2 = q(\delta^2 + 2w),\qquad\operatorname{tr} A^4 = q(\delta^4 + 4w\delta^2 + 2w^2). \tag*{(26)} tr A = q δ , tr A 2 = q ( δ 2 + 2 w ) , tr A 4 = q ( δ 4 + 4 w δ 2 + 2 w 2 ) . (26) Then the n n n q q q { i , j } \{i,j\} { i , j } d = A i i d = A_{ii} d = A ii e = A j j e = A_{jj} e = A j j
d + e = δ , A i j A j i = w + d e . (27) d + e = \delta,\qquad A_{ij}A_{ji} = w + de. \tag*{(27)} d + e = δ , A ij A j i = w + d e . (27) If i i i j j j A i j A j i = 0 A_{ij}A_{ji} = 0 A ij A j i = 0 i → j i \to j i → j A i j > 0 A_{ij} > 0 A ij > 0
Proof. Choose u , v > 0 u, v > 0 u , v > 0 u − v = δ u - v = \delta u − v = δ u v = b 2 uv = b^2 uv = b 2 μ 1 , … , μ n \mu_1,\ldots,\mu_n μ 1 , … , μ n
∑ i μ i = q δ , ∑ i μ i 2 = q ( δ 2 + 2 b 2 ) \sum_i \mu_i = q\delta,\qquad\sum_i \mu_i^2 = q(\delta^2 + 2b^2) i ∑ μ i = q δ , i ∑ μ i 2 = q ( δ 2 + 2 b 2 ) obey
∑ i μ i 4 ≥ q ( δ 4 + 4 b 2 δ 2 + 2 b 4 ) , (28) \sum_i \mu_i^4 \ge q(\delta^4 + 4b^2\delta^2 + 2b^4), \tag*{(28)} i ∑ μ i 4 ≥ q ( δ 4 + 4 b 2 δ 2 + 2 b 4 ) , (28) with equality precisely when the list consists of q q q u u u q q q − v -v − v
Minimise ∑ i μ i 4 \sum_i \mu_i^4 ∑ i μ i 4
∑ i ( μ i 2 − b 2 − δ 2 2 ) 2 ≤ n δ 2 ( b 2 + δ 2 4 ) . \sum_i \left(\mu_i^2 - b^2 - \frac{\delta^2}{2}\right)^2 \le n\delta^2\left(b^2 + \frac{\delta^2}{4}\right). i ∑ ( μ i 2 − b 2 − 2 δ 2 ) 2 ≤ n δ 2 ( b 2 + 4 δ 2 ) . In particular, each μ i \mu_i μ i ∣ ∣ μ i ∣ − b ∣ ≤ 2 n δ < b / 50 \lvert\lvert\mu_i\rvert- b\rvert\le2\sqrt{n}\delta< b/50 ∣∣ μ i ∣ − b ∣ ≤ 2 n δ < b /50 n + n_+ n + n − n_- n −
∣ ( n + − n − ) b ∣ ≤ n δ / 2 + 2 n n δ < b , \lvert(n_+ - n_-)b\rvert\le n\delta/2 + 2n\sqrt{n}\delta< b, ∣( n + − n − ) b ∣ ≤ n δ /2 + 2 n n δ < b , so n + = n − = q n_+ = n_- = q n + = n − = q
4 μ i 3 − 2 η μ i − ξ = 0 4\mu_i^3 - 2\eta\mu_i - \xi= 0 4 μ i 3 − 2 η μ i − ξ = 0 for every i i i b / 50 b/50 b /50 b b b − b -b − b q q q u u u − v -v − v (28) .
Now define the symmetric nonnegative matrix
B i j = A i j A j i . B_{ij}=\sqrt{A_{ij}A_{ji}}. B ij = A ij A j i . We have tr B = tr A \operatorname{tr} B=\operatorname{tr} A tr B = tr A tr B 2 = tr A 2 \operatorname{tr} B^2=\operatorname{tr} A^2 tr B 2 = tr A 2 B B B i → j → k → ℓ → i i \to j \to k \to\ell\to i i → j → k → ℓ → i
p = A i j A j k A k ℓ A ℓ i , p r e v = A i ℓ A ℓ k A k j A j i . p=A_{ij}A_{jk}A_{k\ell}A_{\ell i},\qquad p_{\mathrm{rev}}=A_{i\ell}A_{\ell k}A_{kj}A_{ji}. p = A ij A j k A k ℓ A ℓ i , p rev = A i ℓ A ℓ k A k j A j i . for the products along the walk and its reverse. The corresponding product for B B B
B i j B j k B k ℓ B ℓ i = p p r e v ≤ p + p r e v 2 . B_{ij}B_{jk}B_{k\ell}B_{\ell i}=\sqrt{p p_{\mathrm{rev}}}\leq\frac{p+p_{\mathrm{rev}}}{2}. B ij B j k B k ℓ B ℓ i = p p rev ≤ 2 p + p rev . Summing over all ordered quadruples ( i , j , k , ℓ ) (i,j,k,\ell) ( i , j , k , ℓ ) tr B 4 ≤ tr A 4 \operatorname{tr} B^4\leq\operatorname{tr} A^4 tr B 4 ≤ tr A 4 A A A (26) , the right-hand side equals the lower bound in (28) . We therefore have equality, and the eigenvalues of B B B u u u − v -v − v q q q B B B u u u − v -v − v r r r
0 ≤ u − ( r − 1 ) v , r ≤ 1 + u / v < 3. 0\leq u-(r-1)v,\qquad r\leq1+u/v<3. 0 ≤ u − ( r − 1 ) v , r ≤ 1 + u / v < 3. Thus every component has one or two indices. Each two-index component contributes one eigenvalue − v -v − v q q q 2 q 2q 2 q q q q B i i = A i i B_{ii}=A_{ii} B ii = A ii B i j 2 = A i j A j i B_{ij}^2=A_{ij}A_{ji} B ij 2 = A ij A j i (27) . Between different pairs, B i j = 0 B_{ij}=0 B ij = 0 A i j A j i = 0 A_{ij}A_{ji}=0 A ij A j i = 0
Each closed walk contributing to tr A 4 \operatorname{tr} A^4 tr A 4 q ( u 4 + v 4 ) q(u^4+v^4) q ( u 4 + v 4 )
Lemma 5.5. Let q = 3 q=3 q = 3 q ≥ 5 q\geq5 q ≥ 5 n = 2 q n=2q n = 2 q Lemma 5.4 . Define u , v > 0 u,v>0 u , v > 0 u − v = δ u-v=\delta u − v = δ u v = w uv=w uv = w
a k = q ( u k + ( − v ) k ) , R = 1 − δ . a_k=q\left(u^k+(-v)^k\right),\qquad R=1-\delta. a k = q ( u k + ( − v ) k ) , R = 1 − δ . Assume w < R w<R w < R P P P n n n s k = tr ( P k ) s_k=\operatorname{tr}(P^k) s k = tr ( P k )
s k = a k ( 1 ≤ k < q ) , s q > a q , s q + 1 = a q + 1 . (29) s_k=a_k\quad(1\leq k<q),\qquad s_q>a_q,\qquad s_{q+1}=a_{q+1}. \tag*{(29)} s k = a k ( 1 ≤ k < q ) , s q > a q , s q + 1 = a q + 1 . (29) After applying the same permutation to its rows and columns, we can group the states into q q q i i i x i x_i x i y i y_i y i 0 ≤ i < q 0\leq i<q 0 ≤ i < q
P x i x i = δ , P x i y i = r i , P x i x i + 1 = R − r i , P y i x i = w / r i , P y i y i + 1 = 1 − w / r i . (30) \begin{aligned}
P_{x_i x_i}&=\delta, & P_{x_i y_i}&=r_i, & P_{x_i x_{i+1}}&=R-r_i,\\
P_{y_i x_i}&=w/r_i, & P_{y_i y_{i+1}}&=1-w/r_i. \tag*{(30)}
\end{aligned} P x i x i P y i x i = δ , = w / r i , P x i y i P y i y i + 1 = r i , = 1 − w / r i . P x i x i + 1 = R − r i , (30) Here i + 1 i+1 i + 1 q q q 0 0 0
w < r i ≤ R , ∏ i ( R − r i ) = 0. (31) w<r_i\leq R,\qquad\prod_i(R-r_i)=0. \tag*{(31)} w < r i ≤ R , i ∏ ( R − r i ) = 0. (31) Thus at least one entry P x i x i + 1 P_{x_i x_{i+1}} P x i x i + 1 0 0 0 n n n (29) is irreducible: its directed graph has a path from every index to every other index. This conclusion does not require the row sums to be 1 1 1
:::`
Proof. Let P P P n n n s k = tr ( P k ) s_k=\operatorname{tr}(P^k) s k = tr ( P k ) (29) . These conditions contain all three equalities required by Lemma 5.4 . The one for tr ( P 4 ) \operatorname{tr}(P^4) tr ( P 4 ) s q + 1 = a q + 1 s_{q+1}=a_{q+1} s q + 1 = a q + 1 q = 3 q=3 q = 3 s 4 = a 4 s_4=a_4 s 4 = a 4 q ≥ 5 q\ge5 q ≥ 5 q q q L ( z ) = z 2 − δ z − w L(z)=z^2-\delta z-w L ( z ) = z 2 − δ z − w a k a_k a k tr ( P k ) \operatorname{tr}(P^k) tr ( P k )
Consequently, no directed cycle visiting states from more than one pair has length less than q q q q q q (29) excludes every cycle of length q + 1 q+1 q + 1 q q q q + 1 q+1 q + 1
Each pair has diagonal entries summing to δ > 0 \delta>0 δ > 0 q q q y 0 , … , y q − 1 y_0,\ldots,y_{q-1} y 0 , … , y q − 1 x i x_i x i P y i y i = 0 P_{y_i y_i}=0 P y i y i = 0 P x i x i = δ P_{x_i x_i}=\delta P x i x i = δ
Consider an arrow between different pairs, and write its destination pair as i + d i+d i + d 1 ≤ d < q 1\le d<q 1 ≤ d < q q q q y y y x j ↔ y j x_j\leftrightarrow y_j x j ↔ y j
Table 20.
Every arrow in the table except y i → y i + 1 y_i\to y_{i+1} y i → y i + 1 x i → x i + 1 x_i\to x_{i+1} x i → x i + 1 q q q q + 1 q+1 q + 1 q q q x i x_i x i q q q x i → x i + 1 x_i\to x_{i+1} x i → x i + 1
The arrows x i ↔ y i x_i\leftrightarrow y_i x i ↔ y i y i y_i y i P P P P P P r i = P x i y i r_i=P_{x_i y_i} r i = P x i y i (30) . The positive entries on the y y y x x x (31) .
Conversely, in a matrix of this form, any directed cycle that visits states from more than one pair must visit all q q q y i y_i y i q q q y y y x x x y y y q + 2 q+2 q + 2 q q q q + 1 q+1 q + 1 y i y_i y i q q q
We now fix r q − 1 = R r_{q-1}=R r q − 1 = R (30) and let the other q − 1 q-1 q − 1 w < r i < R w<r_i<R w < r i < R x x x x q − 1 → x 0 x_{q-1}\to x_0 x q − 1 → x 0 Figure 3 . To prove that the corresponding characteristic polynomials form a family of dimension q − 1 q-1 q − 1 q − 1 q-1 q − 1
Figure 3. We choose r q − 1 = R = 1 − δ r_{q-1}=R=1-\delta r q − 1 = R = 1 − δ x q − 1 x_{q-1} x q − 1 x 0 x_0 x 0 R − r i R-r_i R − r i x i → x i + 1 x_i\to x_{i+1} x i → x i + 1 1 − w / r i 1-w/r_i 1 − w / r i y i → y i + 1 y_i\to y_{i+1} y i → y i + 1 q q q y i y_i y i { x i , y i } \{x_i,y_i\} { x i , y i } w w w (29) force every stochastic matrix satisfying them to have this pattern after relabelling, with at least one transition x i → x i + 1 x_i\to x_{i+1} x i → x i + 1
Lemma 5.6. Consider the matrices P P P (30) with
r q − 1 = R , w < r i < R ( 0 ≤ i < q − 1 ) . r_{q-1}=R,\qquad w<r_i<R\quad(0\le i<q-1). r q − 1 = R , w < r i < R ( 0 ≤ i < q − 1 ) . As r 0 , … , r q − 2 r_0,\ldots,r_{q-2} r 0 , … , r q − 2 det ( z I − P ) \det(zI-P) det ( z I − P ) q − 1 q-1 q − 1
Proof. Replace r 0 , … , r q − 2 r_0,\ldots,r_{q-2} r 0 , … , r q − 2
α i = r i + 1 ( R − r i ) r i − w , r i = R r i + 1 + w α i r i + 1 + α i ( 0 ≤ i < q − 1 ) . (32) \alpha_i=\frac{r_{i+1}(R-r_i)}{r_i-w},\qquad
r_i=\frac{Rr_{i+1}+w\alpha_i}{r_{i+1}+\alpha_i}
\quad(0\le i<q-1). \tag*{(32)} α i = r i − w r i + 1 ( R − r i ) , r i = r i + 1 + α i R r i + 1 + w α i ( 0 ≤ i < q − 1 ) . (32) Starting from r q − 1 = R r_{q-1}=R r q − 1 = R r i r_i r i w < r i < R w<r_i<R w < r i < R α q − 1 = 0 \alpha_{q-1}=0 α q − 1 = 0 β i = 1 − w / r i \beta_i=1-w/r_i β i = 1 − w / r i E = ∏ i β i E=\prod_i\beta_i E = ∏ i β i
( z − δ ) X i = r i Y i + ( R − r i ) X i + 1 , z Y i = ( w / r i ) X i + β i Y i + 1 . (z-\delta)X_i=r_iY_i+(R-r_i)X_{i+1},\qquad zY_i=(w/r_i)X_i+\beta_iY_{i+1}. ( z − δ ) X i = r i Y i + ( R − r i ) X i + 1 , z Y i = ( w / r i ) X i + β i Y i + 1 . Eliminate X i X_i X i U i = ( ∏ j < i β j ) Y i U_i=\left(\prod_{j<i}\beta_j\right)Y_i U i = ( ∏ j < i β j ) Y i L ( z ) = z 2 − δ z − w L(z)=z^2-\delta z-w L ( z ) = z 2 − δ z − w
L U i − ( ( 1 + α i ) z − δ ) U i + 1 + α i U i + 2 = 0 , U i + q = E U i . LU_i-\left((1+\alpha_i)z-\delta\right)U_{i+1}+\alpha_iU_{i+2}=0,\qquad U_{i+q}=EU_i. L U i − ( ( 1 + α i ) z − δ ) U i + 1 + α i U i + 2 = 0 , U i + q = E U i . Define the backward recurrence
K q = 1 , K q − 1 = z − δ , K i = ( ( 1 + α i ) z − δ ) K i + 1 − α i L K i + 2 ( i = q − 2 , … , 0 ) . (33) \begin{aligned}
K_q&=1,\qquad K_{q-1}=z-\delta,\\
K_i&=\left((1+\alpha_i)z-\delta\right)K_{i+1}-\alpha_iLK_{i+2}\qquad(i=q-2,\ldots,0). \tag*{(33)}
\end{aligned} K q K i = 1 , K q − 1 = z − δ , = ( ( 1 + α i ) z − δ ) K i + 1 − α i L K i + 2 ( i = q − 2 , … , 0 ) . (33) Then
f ( z ) = det ( z I − P ) = L ( z ) q − E K 0 ( z ) . (34) f(z)=\det(zI-P)=L(z)^q-EK_0(z). \tag*{(34)} f ( z ) = det ( z I − P ) = L ( z ) q − E K 0 ( z ) . (34) To verify the determinant, perform the same elimination on z I − P zI-P z I − P − w / r i -w/r_i − w / r i L L L − ( ( 1 + α i ) z − δ ) -\left((1+\alpha_i)z-\delta\right) − ( ( 1 + α i ) z − δ ) α i \alpha_i α i
E ( α q − 2 e q − 2 − ( z − δ ) e q − 1 ) e 0 T . E\left(\alpha_{q-2}e_{q-2}-(z-\delta)e_{q-1}\right)e_0^{\mathsf{T}}. E ( α q − 2 e q − 2 − ( z − δ ) e q − 1 ) e 0 T . Here the e i e_i e i R q \mathbb{R}^q R q L q L^q L q (34) when L ≠ 0 L\ne0 L = 0 L L L
The recurrence makes K 0 K_0 K 0 q q q − q δ -q\delta − q δ q − 1 q-1 q − 1 q = 2 q=2 q = 2 K 0 = ( z − δ ) 2 + w α 0 K_0=(z-\delta)^2+w\alpha_0 K 0 = ( z − δ ) 2 + w α 0 α 0 = 0 \alpha_0=0 α 0 = 0 K 0 = ( z − δ ) K 1 K_0=(z-\delta)K_1 K 0 = ( z − δ ) K 1 α 1 , … , α q − 2 \alpha_1,\ldots,\alpha_{q-2} α 1 , … , α q − 2 z = δ z=\delta z = δ
∂ K 0 ∂ α 0 ∣ z = δ = δ K 1 ( δ ) + w K 2 ( δ ) > 0. \left.\frac{\partial K_0}{\partial\alpha_0}\right|_{z=\delta}=\delta K_1(\delta)+wK_2(\delta)>0. ∂ α 0 ∂ K 0 z = δ = δ K 1 ( δ ) + w K 2 ( δ ) > 0. Indeed, K i ( δ ) = α i [ δ K i + 1 ( δ ) + w K i + 2 ( δ ) ] K_i(\delta)=\alpha_i[\delta K_{i+1}(\delta)+wK_{i+2}(\delta)] K i ( δ ) = α i [ δ K i + 1 ( δ ) + w K i + 2 ( δ )] i ≤ q − 2 i\le q-2 i ≤ q − 2 α 0 \alpha_0 α 0
Finally, stochasticity gives E = L ( 1 ) q / K 0 ( 1 ) E=L(1)^q/K_0(1) E = L ( 1 ) q / K 0 ( 1 ) f f f E K 0 = L q − f EK_0=L^q-f E K 0 = L q − f K 0 K_0 K 0 q − 1 q-1 q − 1 □ \square □
Theorem 5.7. For every even n ≥ 4 n\ge4 n ≥ 4 n n n Q n , n / 2 − 1 Q_{n,n/2-1} Q n , n /2 − 1 j n ∗ = n / 2 j_n^*=n/2 j n ∗ = n /2
Proof. Proposition 5.3 handles n = 4 n=4 n = 4 n = 2 q n=2q n = 2 q q ≥ 3 q\ge3 q ≥ 3 b = 1 / 2 b=1/2 b = 1/2 0 < δ ≤ 1 / ( 200 n 2 ) 0<\delta\le1/(200n^2) 0 < δ ≤ 1/ ( 200 n 2 )
Rows labelled x i x_i x i δ \delta δ y i y_i y i x x x y y y i , j i,j i , j
x rows : r i = r j or r i + r j = R , y rows : r i = r j or r i r j = w ( r i + r j ) . (35) \begin{aligned}
x\text{ rows}:&\quad r_i=r_j\quad\text{or}\quad r_i+r_j=R,\\
y\text{ rows}:&\quad r_i=r_j\quad\text{or}\quad r_ir_j=w(r_i+r_j). \tag*{(35)}
\end{aligned} x rows : y rows : r i = r j or r i + r j = R , r i = r j or r i r j = w ( r i + r j ) . (35) A subset of R k \mathbb{R}^k R k semialgebraic if it is a finite union of sets defined by finitely many polynomial equations and inequalities. A map is semialgebraic if its graph is such a set; see [1 ] .
Rotate the pair labels so that an absent x x x r q − 1 = R r_{q-1}=R r q − 1 = R q − 1 q-1 q − 1 w < r i ≤ R w<r_i\le R w < r i ≤ R (35) is a proper polynomial equation on this domain. Their finite union has dimension at most q − 2 q-2 q − 2 q − 1 q-1 q − 1 Q n , n / 2 − 1 Q_{n,n/2-1} Q n , n /2 − 1
For an order divisible by four, write n = 2 q + 2 n=2q+2 n = 2 q + 2 q ≥ 3 q\ge3 q ≥ 3 δ = 0 \delta=0 δ = 0 α = 0 \alpha=0 α = 0 2 q 2q 2 q
f 0 ( z ) = ( z 2 − w ) q − ( 1 − w ) q z q . f_0(z)=(z^2-w)^q-(1-w)^qz^q. f 0 ( z ) = ( z 2 − w ) q − ( 1 − w ) q z q . The polynomials f 0 ( z ) f_0(z) f 0 ( z ) f 0 ( − z ) f_0(-z) f 0 ( − z ) q q q − 2 ( 1 − w ) q z q -2(1-w)^qz^q − 2 ( 1 − w ) q z q f 0 ( 0 ) = ( − w ) q ≠ 0 f_0(0)=(-w)^q\ne0 f 0 ( 0 ) = ( − w ) q = 0 z , − z z,-z z , − z δ \delta δ α \alpha α δ \delta δ A A A
Add the eigenvalues 1 , − 1 1,-1 1 , − 1 A A A C 2 C_2 C 2 Λ \Lambda Λ − 1 -1 − 1 A A A z , − z z,-z z , − z Λ \Lambda Λ C 2 C_2 C 2
Deleting those two rows and columns leaves a matrix M M M 2 q 2q 2 q A A A M M M 1 − M 1 \mathbf{1}-M\mathbf{1} 1 − M 1 1 \mathbf{1} 1 0 0 0 M M M M M M C 2 C_2 C 2
No two rows of M M M A A A M M M C 2 C_2 C 2 C 2 C_2 C 2 1 1 1 − 1 -1 − 1 n n n n > 2 n>2 n > 2 Q n , n / 2 − 1 \mathcal{Q}_{n,n/2-1} Q n , n /2 − 1 Λ \Lambda Λ m = n / 2 m=n/2 m = n /2
Corollary 5.8. For every even n ≥ 4 n\geq4 n ≥ 4 n n n n n n Q n , n / 2 − 1 \mathcal{Q}_{n,n/2-1} Q n , n /2 − 1
Proof. By Theorem 5.7 , choose a stochastic matrix whose coefficient vector lies outside the image of Q n , n / 2 − 1 \mathcal{Q}_{n,n/2-1} Q n , n /2 − 1 J J J Q Q Q
Consider Q ε = ( 1 − ε ) Q + ε C n Q_\varepsilon=(1-\varepsilon)Q+\varepsilon C_n Q ε = ( 1 − ε ) Q + ε C n ε \varepsilon ε ε = 1 \varepsilon=1 ε = 1 C n C_n C n ε \varepsilon ε
Boundary-polynomial rigidity and arc exclusion
Proposition 3.3 and Theorem 4.1 excluded points sufficiently close to an endpoint of a Karpele\u{i}č arc. We now consider an arc whose points between the endpoints first occur as eigenvalues of stochastic matrices at order n ≥ 4 n\geq4 n ≥ 4 2 2 2 m m m Ω n , m \Omega_{n,m} Ω n , m n n n
The Type III and Type II classifications in [14 , 15 ] describe stochastic matrices with a prescribed characteristic polynomial. Here the polynomial is first forced by the boundary eigenvalue. We then use those classifications to count the rows with two positive entries.
Theorem 6.1 (A boundary eigenvalue determines the characteristic polynomial). Let λ \lambda λ n ≥ 4 n\geq4 n ≥ 4 λ \lambda λ λ ∈ Θ n ∖ Θ n − 1 \lambda\in\Theta_n\setminus\Theta_{n-1} λ ∈ Θ n ∖ Θ n − 1 q < s q<s q < s d = ⌈ n / q ⌉ d=\lceil n/q\rceil d = ⌈ n / q ⌉ 0 < α < 1 0<\alpha<1 0 < α < 1 q ≥ 2 q\geq2 q ≥ 2 λ \lambda λ (10) ; for q = 1 q=1 q = 1 λ = ( 1 − α ) + α e ± 2 π i / n \lambda=(1-\alpha)+\alpha e^{\pm2\pi i/n} λ = ( 1 − α ) + α e ± 2 π i / n β = 1 − α \beta=1-\alpha β = 1 − α P P P n n n λ \lambda λ
z n − q d ( z q − β ) d − α d z n − s . (36) z^{n-qd}(z^q-\beta)^d-\alpha^d z^{n-s}. \tag*{(36)} z n − q d ( z q − β ) d − α d z n − s . (36) In Type III, where s = n > q d s=n>qd s = n > q d λ \lambda λ p / q < r / s p/q<r/s p / q < r / s 0 , … , n − 1 0,\ldots,n-1 0 , … , n − 1 λ \lambda λ
R ( i ) = i + r ( m o d n ) , S ( i ) = i + r − 1 ( m o d n ) . R(i)=i+r \pmod n,\qquad S(i)=i+r-1 \pmod n. R ( i ) = i + r ( mod n ) , S ( i ) = i + r − 1 ( mod n ) . In this labelling, P i , R ( i ) > 0 P_{i,R(i)}>0 P i , R ( i ) > 0 i i i i i i 0 0 0 P i , S ( i ) P_{i,S(i)} P i , S ( i )
We use Dmitriev and Dynkin’s theorem on the polygon formed by an eigenvector’s coordinates. Besides identifying the two possible nonzero entries in each row, we need its conclusion that the coefficient a i a_i a i i i i
Lemma 6.2 (Dmitriev–Dynkin contact theorem). Let λ ∈ Θ n ∖ Θ n − 1 \lambda\in\Theta_n \setminus\Theta_{n-1} λ ∈ Θ n ∖ Θ n − 1 t λ ∉ Θ n t\lambda\notin\Theta_n t λ ∈ / Θ n t > 1 t>1 t > 1 λ \lambda λ Θ n \Theta_n Θ n λ \lambda λ K K K n n n λ K ⊆ K \lambda K \subseteq K λ K ⊆ K λ \lambda λ K K K v 0 , … , v n − 1 v_0,\ldots,v_{n-1} v 0 , … , v n − 1 1 ≤ κ < n 1 \le\kappa< n 1 ≤ κ < n i i i
λ v i − κ = γ i v i − 1 + a i v i ∈ ( v i − 1 , v i ] , 0 ≤ γ i < 1 , a i = 1 − γ i > 0. (37) \lambda v_{i-\kappa}=\gamma_i v_{i-1}+a_i v_i \in(v_{i-1},v_i], \qquad0\le\gamma_i<1,\qquad a_i=1-\gamma_i>0. \tag*{(37)} λ v i − κ = γ i v i − 1 + a i v i ∈ ( v i − 1 , v i ] , 0 ≤ γ i < 1 , a i = 1 − γ i > 0. (37) All indices are read modulo $n. Thus λ v i − κ \lambda v_{i-\kappa} λ v i − κ v i − 1 v_{i-1} v i − 1 v i v_i v i v i v_i v i v i − 1 v_{i-1} v i − 1 n n n n n n λ v j \lambda v_j λ v j
In particular, let v v v λ \lambda λ A A A n n n K K K A A A
A = C κ B ( γ ) , ( C x ) i = x i + 1 , ( B ( γ ) x ) i = γ i x i − 1 + a i x i . A=C^\kappa B(\gamma), \qquad(Cx)_i=x_{i+1}, \qquad(B(\gamma)x)_i=\gamma_i x_{i-1}+a_i x_i. A = C κ B ( γ ) , ( C x ) i = x i + 1 , ( B ( γ ) x ) i = γ i x i − 1 + a i x i . The conclusion of the Dmitriev–Dynkin contact theorem that λ v i − κ \lambda v_{i-\kappa} λ v i − κ v i − 1 v_{i-1} v i − 1 v i v_i v i [3 §2] . Its footnote gives the strict positivity used here, and its proof in §13 shows that each segment, with one endpoint excluded, contains exactly one image vertex. An English translation appears in [12 Appendix A, pp. A-5 and A-16] . The footnote rules out γ i = 0 \gamma_i=0 γ i = 0 a j = 0 a_j=0 a j = 0 i , j i,j i , j γ i \gamma_i γ i a i a_i a i a i > 0 a_i>0 a i > 0 i i i K K K
Now let v v v λ \lambda λ A A A n n n K K K
λ v i = ∑ j A i j v j , A i j ≥ 0 , ∑ j A i j = 1 \lambda v_i=\sum_j A_{ij}v_j,\qquad A_{ij}\ge0,\qquad\sum_j A_{ij}=1 λ v i = j ∑ A ij v j , A ij ≥ 0 , j ∑ A ij = 1 give λ v i ∈ K \lambda v_i\in K λ v i ∈ K i i i λ K ⊆ K \lambda K\subseteq K λ K ⊆ K K K K n n n λ \lambda λ λ \lambda λ λ ∉ Θ n − 1 \lambda\notin\Theta_{n-1} λ ∈ / Θ n − 1 n n n λ v i − κ \lambda v_{i-\kappa} λ v i − κ v i − 1 v_{i-1} v i − 1 v i v_i v i A v = λ v Av=\lambda v A v = λ v A A A
The next lemma computes a characteristic polynomial from the directed cycles in the graph of a matrix.
Lemma 6.3. Let q , s , d q,s,d q , s , d q < s ≤ n q<s\le n q < s ≤ n q d ≤ n qd\le n q d ≤ n n n n A A A
Suppose every simple directed cycle with positive weight is one of C 1 , … , C d , D C_1,\ldots,C_d,D C 1 , … , C d , D C j C_j C j q q q D D D s s s
each C j C_j C j b j b_j b j C j C_j C j D D D ∏ j = 1 d ( 1 − b j ) \prod_{j=1}^{d}(1-b_j) ∏ j = 1 d ( 1 − b j ) C j C_j C j b j = 0 b_j=0 b j = 0 A A A
z n − q d ∏ j = 1 d ( z q − b j ) − z n − s ∏ j = 1 d ( 1 − b j ) . (38) z^{n-qd}\prod_{j=1}^{d}(z^q-b_j)-z^{n-s}\prod_{j=1}^{d}(1-b_j). \tag*{(38)} z n − q d j = 1 ∏ d ( z q − b j ) − z n − s j = 1 ∏ d ( 1 − b j ) . (38) Proof. We use the usual permutation expansion of det ( z I − A ) \det(zI-A) det ( z I − A ) z − A i i z-A_{ii} z − A ii z z z − A i i -A_{ii} − A ii − A -A − A z z z
A selected cycle of length ℓ \ell ℓ ( − 1 ) ℓ − 1 (-1)^{\ell-1} ( − 1 ) ℓ − 1 ℓ \ell ℓ − A -A − A ( − 1 ) ℓ (-1)^\ell ( − 1 ) ℓ
First select any subset J ⊆ { 1 , … , d } J\subseteq\{1,\ldots,d\} J ⊆ { 1 , … , d } C j C_j C j q ∣ J ∣ q|J| q ∣ J ∣
( − 1 ) ∣ J ∣ z n − q ∣ J ∣ ∏ j ∈ J b j . (-1)^{|J|}z^{n-q|J|}\prod_{j\in J}b_j. ( − 1 ) ∣ J ∣ z n − q ∣ J ∣ j ∈ J ∏ b j . Summing over all choices gives
∑ J ⊆ { 1 , … , d } ( − 1 ) ∣ J ∣ z n − q ∣ J ∣ ∏ j ∈ J b j = z n − q d ∏ j = 1 d ( z q − b j ) . \sum_{J\subseteq\{1,\ldots,d\}}(-1)^{|J|}z^{n-q|J|}\prod_{j\in J}b_j
=z^{n-qd}\prod_{j=1}^{d}(z^q-b_j). J ⊆ { 1 , … , d } ∑ ( − 1 ) ∣ J ∣ z n − q ∣ J ∣ j ∈ J ∏ b j = z n − q d j = 1 ∏ d ( z q − b j ) . This is the first term of (38) : the j j j z q z^q z q C j C_j C j − b j -b_j − b j
If D D D C j C_j C j D D D D D D s s s
− z n − s ∏ j = 1 d ( 1 − b j ) . -z^{n-s}\prod_{j=1}^{d}(1-b_j). − z n − s j = 1 ∏ d ( 1 − b j ) . By hypothesis there are no other positive-weight simple cycles. These choices therefore account for every nonzero term in the determinant expansion and give the full characteristic polynomial, including algebraic multiplicities.
Lemma 6.4. Under the hypotheses of Theorem 6.1 , let P P P n n n λ \lambda λ A A A P P P C 1 , … , C d , D C_1,\ldots,C_d,D C 1 , … , C d , D C j C_j C j q q q 0 ≤ b j < 1 0\leq b_j<1 0 ≤ b j < 1 D D D s s s C j C_j C j ∏ j ( 1 − b j ) \prod_j(1-b_j) ∏ j ( 1 − b j ) λ \lambda λ [16 Theorem 4.1] . The reduction can keep fixed the contact index κ \kappa κ ∏ i a i \prod_i a_i ∏ i a i Lemma 6.2 .
Proof. Let f f f P P P Lemma 6.2 , we have P = C κ B ( γ ) P=C^\kappa B(\gamma) P = C κ B ( γ ) a i > 0 a_i>0 a i > 0 i i i f f f κ \kappa κ c = ∏ i a i > 0 c=\prod_i a_i>0 c = ∏ i a i > 0 ( A , v ) (A,v) ( A , v ) A = C κ B ( γ ) A=C^\kappa B(\gamma) A = C κ B ( γ ) f f f ∏ i a i = c \prod_i a_i=c ∏ i a i = c v v v λ \lambda λ max i ∣ v i ∣ = 1 \max_i|v_i|=1 max i ∣ v i ∣ = 1 a i ≥ c > 0 a_i\geq c>0 a i ≥ c > 0 a i ≤ 1 a_i\leq1 a i ≤ 1 c c c n n n γ i \gamma_i γ i ( A , v ) (A,v) ( A , v ) conv { v 0 , … , v n − 1 } \operatorname{conv}\{v_0,\ldots,v_{n-1}\} conv { v 0 , … , v n − 1 }
Suppose γ i = t > 0 \gamma_i=t>0 γ i = t > 0 γ i + 1 = 0 \gamma_{i+1}=0 γ i + 1 = 0 U i ( t ) U_i(t) U i ( t ) i i i ( U i ( t ) x ) i = ( 1 − t ) x i + t x i − 1 (U_i(t)x)_i=(1-t)x_i+tx_{i-1} ( U i ( t ) x ) i = ( 1 − t ) x i + t x i − 1 t < 1 t<1 t < 1 i i i B B B i i i B ^ \widehat{B} B H = C κ B ^ H=C^\kappa\widehat{B} H = C κ B
A = H U i ( t ) , A ′ = U i ( t ) H = U i ( t ) A U i ( t ) − 1 . A=HU_i(t),\qquad A'=U_i(t)H=U_i(t)AU_i(t)^{-1}. A = H U i ( t ) , A ′ = U i ( t ) H = U i ( t ) A U i ( t ) − 1 . Thus A ′ A' A ′ f f f
The calculation in [16 Lemma 2.4] gives
a i ′ = 1 , a i + κ ′ = a i a i + κ , a j ′ = a j ( j ∉ { i , i + κ } ) . a_i'=1,\qquad a_{i+\kappa}'=a_i a_{i+\kappa},\qquad a_j'=a_j\quad(j\notin\{i,i+\kappa\}). a i ′ = 1 , a i + κ ′ = a i a i + κ , a j ′ = a j ( j ∈ / { i , i + κ }) . These identities preserve c c c a j a_j a j v ′ = U i ( t ) v v'=U_i(t)v v ′ = U i ( t ) v v i v_i v i v i − 1 v_{i-1} v i − 1 v i v_i v i κ \kappa κ
The number of positive γ i \gamma_i γ i i i i i + κ i+\kappa i + κ n n n [16 Proposition 2.5] therefore applies, with f f f κ \kappa κ c c c
The first-return theorem [16 Theorem 3.5] requires boundary contact for every invariant polygon with at most n n n λ \lambda λ f f f c c c [16 Theorem 4.1] .
A return base is a selected state at which one of these paths begins. If gcd ( n , κ ) = 1 \gcd(n,\kappa)=1 g cd( n , κ ) = 1 d d d d d d γ i \gamma_i γ i b j = 0 b_j=0 b j = 0 q q q b j b_j b j 1 − b j 1-b_j 1 − b j q q q s = n s=n s = n gcd ( n , κ ) > 1 \gcd(n,\kappa)>1 g cd( n , κ ) > 1 i ↦ i + κ ( m o d n ) i\mapsto i+\kappa\pmod n i ↦ i + κ ( mod n ) d d d q q q s < n = q d s<n=qd s < n = q d s s s q q q
Adding the changes of argument along these return paths identifies the Farey interval between the endpoints of the given arc and gives the argument identity in [16 Theorem 4.1] . □
Proof of Theorem 6.1. Let P P P n n n λ \lambda λ A A A ( z I − A ) (zI-A) ( z I − A ) 0 ≤ b j < 1 0 \le b_j < 1 0 ≤ b j < 1 λ \lambda λ [16 Theorem 5.2] . Equality forces every b j b_j b j β \beta β β > 0 \beta> 0 β > 0 b j = β = 1 − α b_j=\beta=1-\alpha b j = β = 1 − α
det ( z I − P ) = det ( z I − A ) = z n − q d ( z q − β ) d − α d z n − s . \det(zI-P)=\det(zI-A)=z^{n-qd}(z^q-\beta)^d-\alpha^d z^{n-s}. det ( z I − P ) = det ( z I − A ) = z n − q d ( z q − β ) d − α d z n − s . Thus every stochastic matrix of order n n n λ \lambda λ (36) .
Now suppose the arc is of Type III and its endpoints are ordered p / q < r / n p/q<r/n p / q < r / n i → i + r ( m o d n ) i\to i+r\pmod n i → i + r ( mod n ) 2 π ( r − 1 ) / n 2\pi(r-1)/n 2 π ( r − 1 ) / n 2 π r / n 2\pi r/n 2 π r / n i i i i + r − 1 i+r-1 i + r − 1 i + r i+r i + r n n n
Complex conjugation reflects the arc across the real axis and reverses the order of its endpoint fractions. The endpoints of the conjugate arc are therefore
n − r n < q − p q . \frac{n-r}{n}<\frac{q-p}{q}. n n − r < q q − p . In particular, its endpoint of denominator n n n
Suppose the probabilities of i → i + r i\to i+r i → i + r i ↦ i + κ ′ i\mapsto i+\kappa' i ↦ i + κ ′ κ ′ = n − r + 1 \kappa'=n-r+1 κ ′ = n − r + 1
If gcd ( n , κ ′ ) = 1 \gcd(n,\kappa')=1 g cd( n , κ ′ ) = 1 κ ′ / n \kappa'/n κ ′ / n n n n n n n
If gcd ( n , κ ′ ) > 1 \gcd(n,\kappa')>1 g cd( n , κ ′ ) > 1 n n n q q q q ≥ 2 q\ge2 q ≥ 2 q r − p n = 1 qr-pn=1 q r − p n = 1 q ∣ n q\mid n q ∣ n
The conjugate arc has a unique pair of Farey endpoint fractions, so both cases are impossible. Consequently, in the original ordering, P i , i + r > 0 P_{i,i+r}>0 P i , i + r > 0 i i i n n n
For the remainder of this section, let λ \lambda λ n n n λ \lambda λ q < s q<s q < s q ≥ 2 q\ge2 q ≥ 2 d = ⌊ n / q ⌋ d=\lfloor n/q\rfloor d = ⌊ n / q ⌋ 0 < β < 1 0<\beta<1 0 < β < 1 q + s > n q+s>n q + s > n n = max ( q d , s ) n=\max(qd,s) n = max ( q d , s )
Lemma 6.5. Under the standing minimal-order assumptions, suppose d ≥ 2 d\ge2 d ≥ 2 t t t P P P
n = q d : d ≤ t ≤ d + n − s , n = s > q d : d ≤ t ≤ d + n − q d . \begin{aligned}
n=qd &: \qquad d\le t\le d+n-s,\\
n=s>qd &: \qquad d\le t\le d+n-qd.
\end{aligned} n = q d n = s > q d : d ≤ t ≤ d + n − s , : d ≤ t ≤ d + n − q d . In the first case, the graph contains d d d q q q β \beta β
Proof. Theorem 6.1 identifies the characteristic polynomial before either classification is applied. For Type II, 1 ≤ n − s < q 1\le n-s<q 1 ≤ n − s < q gcd ( q , n − s ) = 1 \gcd(q,n-s)=1 g cd( q , n − s ) = 1 0 < α < 1 0<\alpha<1 0 < α < 1 [15 Theorem 4.1] arranges the states into d d d q q q β \beta β q q q q q q
Let S j S_j S j j j j 1 ≤ j ≤ d 1\le j\le d 1 ≤ j ≤ d h 1 , … , h d h_1,\ldots,h_d h 1 , … , h d ∑ j h j = n − s \sum_j h_j=n-s ∑ j h j = n − s S j S_j S j h j + 1 h_j+1 h j + 1
t = ∑ j = 1 d ∣ S j ∣ , d ≤ t ≤ ∑ j = 1 d ( h j + 1 ) = d + n − s . t=\sum_{j=1}^{d}|S_j|,\qquad d\leq t\leq\sum_{j=1}^{d}(h_j+1)=d+n-s. t = j = 1 ∑ d ∣ S j ∣ , d ≤ t ≤ j = 1 ∑ d ( h j + 1 ) = d + n − s . For Type III, 1 ≤ n − q d < q 1\leq n-qd<q 1 ≤ n − q d < q gcd ( q , n ) = 1 \gcd(q,n)=1 g cd( q , n ) = 1 n n n [14 Theorem 1.2 and Lemma 3.2] divides the t t t d d d q q q
List the branching states in the order of that cycle. A gap is the number of forward edges from one listed state to the next, including the gap from the last back to the first. The t t t n n n k k k d ≥ 2 d\geq2 d ≥ 2 k ≥ d k\geq d k ≥ d k k k q q q
n ≥ k q + ( t − k ) ≥ d q + t − d . n\geq kq+(t-k)\geq dq+t-d. n ≥ k q + ( t − k ) ≥ d q + t − d . The nonempty groups also give t ≥ d t\geq d t ≥ d d ≤ t ≤ d + n − q d d\leq t\leq d+n-qd d ≤ t ≤ d + n − q d
Theorem 6.6. Let n ≥ 4 n\geq4 n ≥ 4 A A A q < s q<s q < s q ≥ 2 q\geq2 q ≥ 2 λ \lambda λ A A A n n n λ \lambda λ
1 ≤ m < ⌊ n / q 2 ⌋ , 1\leq m<\left\lfloor\frac{n/q}{2}\right\rfloor, 1 ≤ m < ⌊ 2 n / q ⌋ , then the only points of A A A Ω n , m \Omega_{n,m} Ω n , m m m m ⌊ n / q ⌋ ≥ 3 \lfloor n/q\rfloor\geq3 ⌊ n / q ⌋ ≥ 3
Proof. Suppose that P ∈ Q n , m P\in\mathcal{Q}_{n,m} P ∈ Q n , m λ \lambda λ A A A
P i j = c j − i mod n ( i ∈ I n , m ) P_{ij}=c_{j-i\ \operatorname{mod}\ n}\qquad(i\in I_{n,m}) P ij = c j − i mod n ( i ∈ I n , m ) for one probability vector c c c d = ⌊ n / q ⌋ d=\lfloor n/q\rfloor d = ⌊ n / q ⌋ b = 2 m < d b=2m<d b = 2 m < d m ≥ 1 m\geq1 m ≥ 1 d ≥ 3 d\geq3 d ≥ 3
The Dmitriev–Dynkin contact theorem (Lemma 6.2) places λ \lambda λ P P P P P P t t t c c c t ≤ b < d t\leq b<d t ≤ b < d Lemma 6.5 . Thus c c c n − b ≤ t n-b\leq t n − b ≤ t
First suppose n = q d n=qd n = q d z = n − s z=n-s z = n − s 1 ≤ z ≤ q − 1 1\leq z\leq q-1 1 ≤ z ≤ q − 1 q ≥ 3 q\geq3 q ≥ 3 t ≤ d + z t\leq d+z t ≤ d + z
n − b − ( d + z ) ≥ d ( q − 2 ) + 1 − z ≥ ( d − 1 ) ( q − 2 ) > 0. n-b-(d+z)\geq d(q-2)+1-z\geq(d-1)(q-2)>0. n − b − ( d + z ) ≥ d ( q − 2 ) + 1 − z ≥ ( d − 1 ) ( q − 2 ) > 0. For q = 2 q=2 q = 2 n = 2 d n=2d n = 2 d b = d − 1 b=d-1 b = d − 1 t = d + 1 t=d+1 t = d + 1 d + 1 d+1 d + 1 1 1 1 d d d β \beta β 2 d 2d 2 d { x , y } \{x,y\} { x , y } x → y x \to y x → y y → x y \to x y → x P x y P y x = β P_{xy}P_{yx}=\beta P x y P y x = β 1 1 1 1 > β 1>\beta 1 > β d − 1 d-1 d − 1
In a pair consisting of one boundary state and one interior state, the transition from the boundary state to the interior state has probability 1 1 1 β \beta β β \beta β c c c 1 1 1 β \beta β β \beta β γ ≠ β \gamma\ne\beta γ = β γ 2 = β \gamma^2=\beta γ 2 = β
Let h h h γ \gamma γ i i i i + h i+h i + h 2 d 2d 2 d 2 h = 0 2h=0 2 h = 0 2 d 2d 2 d h ≠ 0 h\ne0 h = 0 h = d h=d h = d
Write the interior interval as { a , a + 1 , … , a + d } \{a,a+1,\ldots,a+d\} { a , a + 1 , … , a + d } 2 d 2d 2 d d d d I ′ = { a + 1 , … , a + d − 1 } I'=\{a+1,\ldots,a+d-1\} I ′ = { a + 1 , … , a + d − 1 } I ′ I' I ′ β \beta β k k k c c c I ′ I' I ′ B n , m B_{n,m} B n , m I ′ + k = B n , m I'+k=B_{n,m} I ′ + k = B n , m I ′ I' I ′ d d d { a + d + 1 , … , a + 2 d − 1 } \{a+d+1,\ldots,a+2d-1\} { a + d + 1 , … , a + 2 d − 1 }
I ′ + k = B n , m = I ′ + d . I' + k = B_{n,m} = I' + d. I ′ + k = B n , m = I ′ + d . A proper cyclic interval has no nontrivial translation symmetry, so k = d = h k=d=h k = d = h c c c
Now suppose n = s = q d + r n=s=qd+r n = s = q d + r 0 < r < q 0<r<q 0 < r < q n − b ≤ t ≤ d + r n-b\le t\le d+r n − b ≤ t ≤ d + r b ≥ d ( q − 1 ) ≥ d b\ge d(q-1)\ge d b ≥ d ( q − 1 ) ≥ d
The chain construction in Theorem 2.1 realises both endpoints with m = 1 m=1 m = 1 m ≥ 1 m\ge1 m ≥ 1
Geometry below saturation
The preceding results determine when Ω n , m = Θ n \Omega_{n,m}=\Theta_n Ω n , m = Θ n m m m 0 0 0 Theorem 4.1 gives local equality with the circulant polygon near certain roots of unity whose orders divide n n n m m m
Proposition 7.1. If 3 ≤ k ≤ n 3\le k\le n 3 ≤ k ≤ n m ≥ ⌈ ( k − 1 ) / 4 ⌉ m\ge\lceil(k-1)/4\rceil m ≥ ⌈( k − 1 ) /4 ⌉
Θ k ⊆ Ω n , m . (39) \Theta_k \subseteq\Omega_{n,m}. \tag*{(39)} Θ k ⊆ Ω n , m . (39) For every m ≥ 1 m\ge1 m ≥ 1 Ω n , m \Omega_{n,m} Ω n , m n n n
Proof. For a boundary arc of Θ k \Theta_k Θ k q ≥ 2 q\ge2 q ≥ 2 r = ⌊ k / q ⌋ r=\lfloor k/q\rfloor r = ⌊ k / q ⌋ s s s Theorem 2.1 gives a stochastic matrix of order n n n
z n − k χ k ; q , s , α ( z ) . z^{n-k}\chi_{k;q,s,\alpha}(z). z n − k χ k ; q , s , α ( z ) . Thus each point of the arc occurs as an eigenvalue of one of these matrices. Because r ≤ ⌊ k / 2 ⌋ ≤ 2 m r \le\lfloor k/2\rfloor\le2m r ≤ ⌊ k /2 ⌋ ≤ 2 m Q n , m Q_{n,m} Q n , m
For the two Type 0 arcs, use a Markov chain on n n n k k k P P P P P P i ↦ i + 1 ( m o d n ) i \mapsto i+1\pmod n i ↦ i + 1 ( mod n ) P ∈ Q n , 1 P \in Q_{n,1} P ∈ Q n , 1 0 ≤ t ≤ 1 0 \le t \le1 0 ≤ t ≤ 1
P t = ( 1 − t ) I + t P . P_t = (1-t)I+tP. P t = ( 1 − t ) I + tP . At each step, this chain stays in its current state with probability 1 − t 1-t 1 − t P P P t t t P t P_t P t Q n , 1 Q_{n,1} Q n , 1 1 − t + t e ± 2 π i / k 1-t+te^{\pm2\pi i/k} 1 − t + t e ± 2 π i / k t t t ∂ Θ k \partial\Theta_k ∂ Θ k Θ k \Theta_k Θ k (9) puts that whole segment in Ω n , m \Omega_{n,m} Ω n , m
The same chain with a final cycle of length q q q 1 ≤ q ≤ n 1 \le q \le n 1 ≤ q ≤ n q q q m = 1 m=1 m = 1 h h h h h h h h h h ≤ n h \le n h ≤ n
At order 2, m = 0 m=0 m = 0 Θ 2 = [ − 1 , 1 ] \Theta_2=[-1,1] Θ 2 = [ − 1 , 1 ] Θ 2 ⊆ Ω n , 0 \Theta_2 \subseteq\Omega_{n,0} Θ 2 ⊆ Ω n , 0 n n n − 1 ∉ Ω n , 0 = H n -1 \notin\Omega_{n,0}=H_n − 1 ∈ / Ω n , 0 = H n m = 0 m=0 m = 0 m m m k = 4 k=4 k = 4 (39) gives Θ 4 ⊆ Ω n , m \Theta_4 \subseteq\Omega_{n,m} Θ 4 ⊆ Ω n , m n ≥ 4 n \ge4 n ≥ 4 m ≥ 1 m \ge1 m ≥ 1
Theorem 7.2. Let n ≥ 4 n \ge4 n ≥ 4 0 ≤ m ≤ ⌊ n / 2 ⌋ 0 \le m \le\lfloor n/2\rfloor 0 ≤ m ≤ ⌊ n /2 ⌋ R n , m R_{n,m} R n , m
Ω n , m = { r u : ∣ u ∣ = 1 , 0 ≤ r ≤ R n , m ( u ) } . (40) \Omega_{n,m}=\{ru: |u|=1,\ 0 \le r \le R_{n,m}(u)\}. \tag*{(40)} Ω n , m = { r u : ∣ u ∣ = 1 , 0 ≤ r ≤ R n , m ( u )} . (40) Thus R n , m ( u ) R_{n,m}(u) R n , m ( u ) u u u u ↦ R n , m ( u ) u u \mapsto R_{n,m}(u)u u ↦ R n , m ( u ) u z = x + i y z=x+iy z = x + i y F ( x , y ) = 0 F(x,y)=0 F ( x , y ) = 0 F F F
Proof. For m = 0 m=0 m = 0 (7) . Assume m ≥ 1 m \ge1 m ≥ 1 J J J 1 / n 1/n 1/ n (8) , each segment from 0 to a non-Perron eigenvalue lies in the region; the segment [ 0 , 1 ] [0,1] [ 0 , 1 ] H n H_n H n R n , m ( u ) R_{n,m}(u) R n , m ( u ) (39) , the region contains Θ 4 \Theta_4 Θ 4 H 4 H_4 H 4
For nonreal λ ∈ Ω n , m \lambda\in\Omega_{n,m} λ ∈ Ω n , m 0 < t < 1 0<t<1 0 < t < 1 t λ t\lambda t λ (9) . Thus every such t λ t\lambda t λ
Compactness gives lim sup v → u R n , m ( v ) ≤ R n , m ( u ) \limsup_{v\to u} R_{n,m}(v) \le R_{n,m}(u) lim sup v → u R n , m ( v ) ≤ R n , m ( u ) u u u R n , m R_{n,m} R n , m u = ± 1 u=\pm1 u = ± 1 R n , m ( ± 1 ) = 1 R_{n,m}(\pm1)=1 R n , m ( ± 1 ) = 1 H 4 H_4 H 4 R n , m R_{n,m} R n , m
r u ⟼ r R n , m ( u ) u , ∣ u ∣ = 1 , 0 ≤ r ≤ 1 , ru \longmapsto rR_{n,m}(u)u,\qquad|u|=1,\quad0 \le r \le1, r u ⟼ r R n , m ( u ) u , ∣ u ∣ = 1 , 0 ≤ r ≤ 1 , with 0 ↦ 0 0 \mapsto0 0 ↦ 0
Finally,
x + i y ∈ Ω n , m ⟺ ∃ P ∈ Q n , m : x+iy \in\Omega_{n,m} \Longleftrightarrow\exists P \in\mathcal{Q}_{n,m}: x + i y ∈ Ω n , m ⟺ ∃ P ∈ Q n , m : Re det ( ( x + i y ) I − P ) = Im det ( ( x + i y ) I − P ) = 0. (41) \operatorname{Re}\det((x+iy)I-P)=\operatorname{Im}\det((x+iy)I-P)=0. \tag*{(41)} Re det (( x + i y ) I − P ) = Im det (( x + i y ) I − P ) = 0. (41) Here ∃ P \exists P ∃ P x , y x,y x , y Ω n , m \Omega_{n,m} Ω n , m Q \mathbb{Q} Q [1 ] . The boundary is therefore a one-dimensional semialgebraic set. Its decomposition into real-analytic algebraic arcs is finite, and its being a simple closed curve makes the remaining points endpoints of those arcs.
The conclusions do not hold at order 3 in general. For m = 1 m=1 m = 1
Ω 3 , 1 = Θ 3 = H 3 ∪ [ − 1 , − 1 / 2 ] . \Omega_{3,1}=\Theta_3=H_3\cup[-1,-1/2]. Ω 3 , 1 = Θ 3 = H 3 ∪ [ − 1 , − 1/2 ] . The radial function equals 1 at direction − 1 -1 − 1 1 / 2 1/2 1/2 Figure 4 shows this exception.
Figure 4. At order 3, Ω 3 , 1 = Θ 3 = H 3 ∪ [ − 1 , − 1 / 2 ] \Omega_{3,1}=\Theta_3=H_3\cup[-1,-1/2] Ω 3 , 1 = Θ 3 = H 3 ∪ [ − 1 , − 1/2 ] H 3 H_3 H 3 1 / 2 1/2 1/2 − 3 / 4 -3/4 − 3/4
Corollary 7.3. For n ≥ 4 n\ge4 n ≥ 4 0 ≤ m ≤ ⌊ n / 2 ⌋ 0\le m\le\lfloor n/2\rfloor 0 ≤ m ≤ ⌊ n /2 ⌋ R n , m R_{n,m} R n , m L > 0 L>0 L > 0
∣ R n , m ( u ) − R n , m ( v ) ∣ ≤ L ∣ u − v ∣ ( ∣ u ∣ = ∣ v ∣ = 1 ) . \lvert R_{n,m}(u)-R_{n,m}(v)\rvert\le L\lvert u-v\rvert\qquad(\lvert u\rvert=\lvert v\rvert=1). ∣ R n , m ( u ) − R n , m ( v )∣ ≤ L ∣ u − v ∣ (∣ u ∣ = ∣ v ∣ = 1 ) . As a function of the angle, R n , m ( e i θ ) R_{n,m}(e^{i\theta}) R n , m ( e i θ ) θ \theta θ 2 π 2\pi 2 π
Proof. The polygon H n H_n H n m = 0 m=0 m = 0 m ≥ 1 m \ge1 m ≥ 1 λ ∈ Ω n , m \lambda\in\Omega_{n,m} λ ∈ Ω n , m (9) gives
B ( t λ , ( 1 − t ) ∣ Im λ ∣ n ) ⊆ Ω n , m ( 1 / 2 ≤ t < 1 ) . (42) B\left(t\lambda,\frac{(1-t)|\operatorname{Im}\lambda|}{n}\right) \subseteq\Omega_{n,m} \qquad(1/2 \le t < 1). \tag*{(42)} B ( t λ , n ( 1 − t ) ∣ Im λ ∣ ) ⊆ Ω n , m ( 1/2 ≤ t < 1 ) . (42) Indeed, using ∣ λ ∣ ≤ 1 |\lambda| \le1 ∣ λ ∣ ≤ 1 t ∣ Im λ ∣ t|\operatorname{Im}\lambda| t ∣ Im λ ∣
On any closed arc K K K ± 1 \pm1 ± 1
c = n − 1 min u ∈ K ∣ Im ( R n , m ( u ) u ) ∣ > 0. c=n^{-1}\min_{u\in K}|\operatorname{Im}(R_{n,m}(u)u)|>0. c = n − 1 u ∈ K min ∣ Im ( R n , m ( u ) u ) ∣ > 0. For u , v ∈ K u,v\in K u , v ∈ K 0 < δ = ∣ u − v ∣ < c / 4 0<\delta=|u-v|<c/4 0 < δ = ∣ u − v ∣ < c /4 t = 1 − 2 δ / c t=1-2\delta/c t = 1 − 2 δ / c (42) , centred at t R n , m ( u ) u tR_{n,m}(u)u t R n , m ( u ) u t R n , m ( u ) v tR_{n,m}(u)v t R n , m ( u ) v R n , m ( v ) ≥ t R n , m ( u ) R_{n,m}(v)\ge tR_{n,m}(u) R n , m ( v ) ≥ t R n , m ( u ) u , v u,v u , v ∣ R n , m ( u ) − R n , m ( v ) ∣ ≤ 2 ∣ u − v ∣ / c |R_{n,m}(u)-R_{n,m}(v)|\le2|u-v|/c ∣ R n , m ( u ) − R n , m ( v ) ∣ ≤ 2∣ u − v ∣/ c
Near any direction e i ϕ e^{i\phi} e i ϕ u ( s ) = e i ϕ ( 1 − s 2 + 2 i s ) / ( 1 + s 2 ) u(s)=e^{i\phi}(1-s^2+2is)/(1+s^2) u ( s ) = e i ϕ ( 1 − s 2 + 2 i s ) / ( 1 + s 2 ) f ( s ) = R n , m ( u ( s ) ) f(s)=R_{n,m}(u(s)) f ( s ) = R n , m ( u ( s )) f ′ f' f ′ [1 ] . At ϕ = 0 , π \phi=0,\pi ϕ = 0 , π H 4 H_4 H 4 f ( s ) = 1 + O ( ∣ s ∣ ) f(s)=1+O(|s|) f ( s ) = 1 + O ( ∣ s ∣ ) f ′ f' f ′ R n , m R_{n,m} R n , m
These neighbourhoods cover the unit circle: every point belongs to at least one of them. Compactness lets us choose finitely many that still cover the whole circle. Let M M M u , v u,v u , v ∣ R n , m ( u ) − R n , m ( v ) ∣ |R_{n,m}(u)-R_{n,m}(v)| ∣ R n , m ( u ) − R n , m ( v ) ∣ M M M ( π / 2 ) ∣ u − v ∣ (\pi/2)|u-v| ( π /2 ) ∣ u − v ∣
∣ R n , m ( u ) − R n , m ( v ) ∣ ≤ π M 2 ∣ u − v ∣ . |R_{n,m}(u)-R_{n,m}(v)|\le\frac{\pi M}{2}|u-v|. ∣ R n , m ( u ) − R n , m ( v ) ∣ ≤ 2 π M ∣ u − v ∣. This gives a global Lipschitz constant L = π M / 2 L=\pi M/2 L = π M /2 2 π 2\pi 2 π
Theorem 7.4. Let m ≥ 1 m\ge1 m ≥ 1 ζ \zeta ζ q q q 2 ≤ q ≤ n 2\le q\le n 2 ≤ q ≤ n
N n , m ( q ) = { n , q ∣ n , q min { 2 m , ⌊ n / q ⌋ } , q ∤ n . N_{n,m}(q)=
\begin{cases}
n, & q\mid n,\\
q\min\{2m,\lfloor n/q\rfloor\}, & q\nmid n.
\end{cases} N n , m ( q ) = { n , q min { 2 m , ⌊ n / q ⌋} , q ∣ n , q ∤ n . To measure how λ \lambda λ ζ \zeta ζ ζ \zeta ζ 1 1 1 1 − ζ ‾ λ 1-\overline{\zeta}\lambda 1 − ζ λ λ ∈ Ω n , m ∖ { ζ } \lambda\in\Omega_{n,m}\setminus\{\zeta\} λ ∈ Ω n , m ∖ { ζ } ζ \zeta ζ
[ − π 2 + π N n , m ( q ) , π 2 − π N n , m ( q ) ] . (43) \left[-\frac{\pi}{2}+\frac{\pi}{N_{n,m}(q)},\frac{\pi}{2}-\frac{\pi}{N_{n,m}(q)}\right]. \tag*{(43)} [ − 2 π + N n , m ( q ) π , 2 π − N n , m ( q ) π ] . (43) Proof. Choose matrices P j ∈ Q n , m P_j\in\mathcal{Q}_{n,m} P j ∈ Q n , m λ j → ζ \lambda_j\to\zeta λ j → ζ P 0 P_0 P 0 r r r ζ \zeta ζ P 0 P_0 P 0 Theorem 3.2 , any limiting angle has absolute value at most π / 2 − π / ( q r ) \pi/2-\pi/(qr) π /2 − π / ( q r ) q r ≤ n qr\le n q r ≤ n q ∤ n q\nmid n q ∤ n Proposition 3.3 gives r ≤ 2 m r\le2m r ≤ 2 m q r ≤ N n , m ( q ) qr\le N_{n,m}(q) q r ≤ N n , m ( q ) (43) .
If q ∣ n q \mid n q ∣ n H n H_n H n ζ \zeta ζ q ∤ n q \nmid n q ∤ n
r = min { 2 m , ⌊ n / q ⌋ } . r=\min\{2m,\lfloor n/q\rfloor\}. r = min { 2 m , ⌊ n / q ⌋} . Write ζ = e 2 π i p / q \zeta=e^{2\pi ip/q} ζ = e 2 π i p / q s 0 ∈ { 1 , … , q − 1 } s_0\in\{1,\ldots,q-1\} s 0 ∈ { 1 , … , q − 1 } p s 0 ≡ 1 ( m o d q ) ps_0\equiv1\pmod q p s 0 ≡ 1 ( mod q ) s = ( r − 1 ) q + s 0 s=(r-1)q+s_0 s = ( r − 1 ) q + s 0 r ≤ s < q r ≤ n r\le s<qr\le n r ≤ s < q r ≤ n Theorem 2.1 belong to Q n , m Q_{n,m} Q n , m ⌈ r / 2 ⌉ ≤ m \lceil r/2\rceil\le m ⌈ r /2 ⌉ ≤ m (17) , applied to their polynomial, gives an analytic eigenvalue branch
λ ( α ) = ζ [ 1 + u − 1 q α + O ( α 2 ) ] , u = e − 2 π i / ( q r ) . \lambda(\alpha)=\zeta\left[1+\frac{u-1}{q}\alpha+O(\alpha^2)\right],\qquad u=e^{-2\pi i/(qr)}. λ ( α ) = ζ [ 1 + q u − 1 α + O ( α 2 ) ] , u = e − 2 π i / ( q r ) . Hence 1 − ζ ˉ λ ( α ) 1-\bar{\zeta}\lambda(\alpha) 1 − ζ ˉ λ ( α ) arg ( 1 − u ) = π / 2 − π / ( q r ) \arg(1-u)=\pi/2-\pi/(qr) arg ( 1 − u ) = π /2 − π / ( q r ) p s 0 ≡ − 1 ( m o d q ) ps_0\equiv-1\pmod q p s 0 ≡ − 1 ( mod q ) u = e 2 π i / ( q r ) u=e^{2\pi i/(qr)} u = e 2 π i / ( q r )
For either extreme, let P ( α ) P(\alpha) P ( α )
1 − ζ ˉ λ ( α ) = A α + O ( α 2 ) , Re A > 0. 1-\bar{\zeta}\lambda(\alpha)=A\alpha+O(\alpha^2),\qquad\operatorname{Re} A>0. 1 − ζ ˉ λ ( α ) = A α + O ( α 2 ) , Re A > 0. For fixed c ≥ 0 c\ge0 c ≥ 0 α > 0 \alpha>0 α > 0
P ~ c ( α ) = ( 1 − c α ) P ( α ) + c α J \widetilde{P}_c(\alpha)=(1-c\alpha)P(\alpha)+c\alpha J P c ( α ) = ( 1 − c α ) P ( α ) + c α J belongs to the same class and has eigenvalue λ ~ c ( α ) = ( 1 − c α ) λ ( α ) \widetilde{\lambda}_c(\alpha)=(1-c\alpha)\lambda(\alpha) λ c ( α ) = ( 1 − c α ) λ ( α )
1 − ζ ˉ λ ~ c ( α ) = ( A + c ) α + O ( α 2 ) . 1-\bar{\zeta}\widetilde{\lambda}_c(\alpha)=(A+c)\alpha+O(\alpha^2). 1 − ζ ˉ λ c ( α ) = ( A + c ) α + O ( α 2 ) . As c c c arg ( A + c ) \arg(A+c) arg ( A + c ) 0 0 0 c = 0 c=0 c = 0 ( 1 − α ) P ( 0 ) + α J (1-\alpha)P(0)+\alpha J ( 1 − α ) P ( 0 ) + α J ( 1 − α ) ζ (1-\alpha)\zeta ( 1 − α ) ζ 0 0 0
Corollary 7.5. Let n ≥ 4 n\ge4 n ≥ 4 m ≥ 1 m\ge1 m ≥ 1 ζ = e i ϕ \zeta=e^{i\phi} ζ = e i ϕ q q q 2 ≤ q ≤ n 2\le q\le n 2 ≤ q ≤ n N = N n , m ( q ) N=N_{n,m}(q) N = N n , m ( q )
R n , m ( e i ( ϕ + h ) ) = 1 − tan ( π / N ) ∣ h ∣ + o ( ∣ h ∣ ) ( h → 0 ) . (44) R_{n,m}(e^{i(\phi+h)})=1-\tan(\pi/N)|h|+o(|h|)\qquad(h\to0). \tag*{(44)} R n , m ( e i ( ϕ + h ) ) = 1 − tan ( π / N ) ∣ h ∣ + o ( ∣ h ∣ ) ( h → 0 ) . (44) This shows that the radius has left derivative tan ( π / N ) \tan(\pi/N) tan ( π / N ) − tan ( π / N ) -\tan(\pi/N) − tan ( π / N ) ϕ \phi ϕ ζ = 1 \zeta=1 ζ = 1 N = n N=n N = n m m m
Proof. For q ≥ 2 q\ge2 q ≥ 2 N > 2 N>2 N > 2
R h = R n , m ( e i ( ϕ + h ) ) , λ h = R h e i ( ϕ + h ) . R_h=R_{n,m}(e^{i(\phi+h)}),\qquad\lambda_h=R_he^{i(\phi+h)}. R h = R n , m ( e i ( ϕ + h ) ) , λ h = R h e i ( ϕ + h ) . Then
1 − ζ ˉ λ h = 1 − R h cos h − i R h sin h . 1-\bar{\zeta}\lambda_h=1-R_h\cos h-iR_h\sin h. 1 − ζ ˉ λ h = 1 − R h cos h − i R h sin h . Since R h → 1 R_h\to1 R h → 1 − h + o ( h ) -h+o(h) − h + o ( h ) 1 − R h + O ( h 2 ) 1-R_h+O(h^2) 1 − R h + O ( h 2 ) h → 0 h\to0 h → 0 1 − ζ ˉ λ h 1-\bar{\zeta}\lambda_h 1 − ζ ˉ λ h π / 2 − π / N \pi/2-\pi/N π /2 − π / N Theorem 7.4 . Comparing the real part with the absolute value of the imaginary part therefore gives
lim inf h → 0 1 − R h ∣ h ∣ ≥ tan ( π / N ) . \liminf_{h\to0}\frac{1-R_h}{|h|}\ge\tan(\pi/N). h → 0 lim inf ∣ h ∣ 1 − R h ≥ tan ( π / N ) . To obtain the reverse bound, use the branches attaining the two extreme angles; if q ∣ n q\mid n q ∣ n H n H_n H n θ ( α ) \theta(\alpha) θ ( α ) θ ( 0 ) = ϕ \theta(0)=\phi θ ( 0 ) = ϕ α \alpha α ϕ \phi ϕ h = θ ( α ) − ϕ h=\theta(\alpha)-\phi h = θ ( α ) − ϕ
1 − ∣ λ ( α ) ∣ = tan ( π / N ) ∣ h ∣ + o ( ∣ h ∣ ) . 1-|\lambda(\alpha)|=\tan(\pi/N)|h|+o(|h|). 1 − ∣ λ ( α ) ∣ = tan ( π / N ) ∣ h ∣ + o ( ∣ h ∣ ) . The maximum radius R h R_h R h ∣ λ ( α ) ∣ |\lambda(\alpha)| ∣ λ ( α ) ∣
lim sup h → 0 1 − R h ∣ h ∣ ≤ tan ( π / N ) , \limsup_{h\to0}\frac{1-R_h}{|h|}\le\tan(\pi/N), h → 0 lim sup ∣ h ∣ 1 − R h ≤ tan ( π / N ) , which proves the formula for q ≥ 2 q\ge2 q ≥ 2
At ζ = 1 \zeta=1 ζ = 1 e ± 2 π i / n e^{\pm2\pi i/n} e ± 2 π i / n Θ n \Theta_n Θ n N = n N=n N = n
Matching the extreme angles does not imply matching nearby boundary points: for n = 9 n=9 n = 9 m = 1 m=1 m = 1 Theorem 4.1 gives local equality with H 9 H_9 H 9 Figure 2 .
Remaining questions
For m < j n ∗ m<j^*_n m < j n ∗ n n n Q n , m Q_{n,m} Q n , m
Let A A A ∂ Θ n \partial\Theta_n ∂ Θ n ∂ Θ N \partial\Theta_N ∂ Θ N N < n N<n N < n A ∩ Ω n , m A\cap\Omega_{n,m} A ∩ Ω n , m P ∈ Q n , m P\in Q_{n,m} P ∈ Q n , m λ ∈ A \lambda\in A λ ∈ A c k c_k c k P b j P_{bj} P bj b ∈ B n , m b\in B_{n,m} b ∈ B n , m
For each even n ≥ 4 n\ge4 n ≥ 4 P P P Q n , n / 2 − 1 Q_{n,n/2-1} Q n , n /2 − 1 P P P coeff ( Q n , n / 2 − 1 ) \operatorname{coeff}(Q_{n,n/2-1}) coeff ( Q n , n /2 − 1 ) Q ∈ Q n , n / 2 − 1 Q\in Q_{n,n/2-1} Q ∈ Q n , n /2 − 1 P P P
Feasibility and support reductions
The eigenvector equations give membership criteria and bounds on the positive entries needed in the shared interior row and the free boundary rows. At boundary points of Ω n , m \Omega_{n,m} Ω n , m
Proposition A.1. A number λ ∈ C \lambda\in\mathbb{C} λ ∈ C Ω n , m \Omega_{n,m} Ω n , m c = ( c 0 , … , c n − 1 ) ∈ R n c=(c_0,\ldots,c_{n-1})\in\mathbb{R}^n c = ( c 0 , … , c n − 1 ) ∈ R n v = ( v 0 , … , v n − 1 ) ∈ C n v=(v_0,\ldots,v_{n-1})\in\mathbb{C}^n v = ( v 0 , … , v n − 1 ) ∈ C n
λ v i = ∑ k = 0 n − 1 c k v i + k ( i ∈ I n , m ) , (45) \lambda v_i=\sum_{k=0}^{n-1}c_kv_{i+k}\qquad(i\in I_{n,m}), \tag*{(45)} λ v i = k = 0 ∑ n − 1 c k v i + k ( i ∈ I n , m ) , (45) λ v b ∈ conv { v 0 , … , v n − 1 } ( b ∈ B n , m ) . (46) \lambda v_b\in\operatorname{conv}\{v_0,\ldots,v_{n-1}\}\qquad(b\in B_{n,m}). \tag*{(46)} λ v b ∈ conv { v 0 , … , v n − 1 } ( b ∈ B n , m ) . (46) Here I n , m = { m , … , n − m − 1 } I_{n,m} = \{m,\ldots,n-m-1\} I n , m = { m , … , n − m − 1 } B n , m B_{n,m} B n , m m m m (45) are read modulo n n n c c c min { n , 2 ∣ I n , m ∣ + 1 } \min\{n,2|I_{n,m}|+1\} min { n , 2∣ I n , m ∣ + 1 } λ \lambda λ v v v c c c min { n , ∣ I n , m ∣ + 1 } \min\{n,|I_{n,m}|+1\} min { n , ∣ I n , m ∣ + 1 }
Proof. Use the cyclic shifts of c c c P ∈ Q n , m P \in\mathcal{Q}_{n,m} P ∈ Q n , m P v = λ v Pv=\lambda v P v = λ v
For fixed v v v R 2 \mathbb{R}^{2} R 2 c c c 2 ∣ I n , m ∣ + 1 2|I_{n,m}|+1 2∣ I n , m ∣ + 1 λ \lambda λ v v v R \mathbb{R} R c c c ∣ I n , m ∣ + 1 |I_{n,m}|+1 ∣ I n , m ∣ + 1
Proposition A.2. Every nonreal λ ∈ ∂ Ω n , m \lambda\in\partial\Omega_{n,m} λ ∈ ∂ Ω n , m P ∈ Q n , m P \in\mathcal{Q}_{n,m} P ∈ Q n , m 2 m 2m 2 m c c c min { n , 2 ∣ I n , m ∣ + 1 } \min\{n,2|I_{n,m}|+1\} min { n , 2∣ I n , m ∣ + 1 } A ∈ Q n , m A \in\mathcal{Q}_{n,m} A ∈ Q n , m λ \lambda λ λ \lambda λ λ \lambda λ
Proof. When m = 0 m=0 m = 0 c c c n n n m ≥ 1 m \ge1 m ≥ 1 λ ∈ ∂ Ω n , m \lambda\in\partial\Omega_{n,m} λ ∈ ∂ Ω n , m P ∈ Q n , m P \in\mathcal{Q}_{n,m} P ∈ Q n , m λ \lambda λ b ∈ B n , m b \in B_{n,m} b ∈ B n , m p j = P b j p_j=P_{bj} p j = P bj p j ≥ 0 p_j \ge0 p j ≥ 0 ∑ j p j = 1 \sum_j p_j=1 ∑ j p j = 1
For each column j j j P ( j ) P^{(j)} P ( j ) P P P b b b 1 1 1 j j j 0 0 0
f j ( z ) = det ( z I − P ( j ) ) . f_j(z)=\det(zI-P^{(j)}). f j ( z ) = det ( z I − P ( j ) ) . The b b b z I − P zI-P z I − P p j p_j p j b b b z I − P ( j ) zI-P^{(j)} z I − P ( j )
det ( z I − P ) = ∑ j p j f j ( z ) , 0 = ∑ j p j f j ( λ ) . \det(zI-P)=\sum_j p_j f_j(z), \qquad0=\sum_j p_j f_j(\lambda). det ( z I − P ) = j ∑ p j f j ( z ) , 0 = j ∑ p j f j ( λ ) . Consider the complex numbers f j ( λ ) f_j(\lambda) f j ( λ ) p j > 0 p_j>0 p j > 0 0 0 0 0 0 0 f j ( z ) f_j(z) f j ( z ) z z z 0 0 0 z z z λ \lambda λ z z z q j q_j q j 1 1 1
∑ j q j f j ( z ) = 0. \sum_j q_j f_j(z)=0. j ∑ q j f j ( z ) = 0. Replacing row b b b Q n , m \mathcal{Q}_{n,m} Q n , m z z z λ \lambda λ Ω n , m \Omega_{n,m} Ω n , m λ ∈ ∂ Ω n , m \lambda\in\partial\Omega_{n,m} λ ∈ ∂ Ω n , m
The complex numbers f j ( λ ) f_j(\lambda) f j ( λ ) p j > 0 p_j>0 p j > 0 0 0 0 b b b λ \lambda λ λ \lambda λ b b b
Apply the same argument to each remaining boundary row of the current matrix. All interior rows stay fixed throughout these changes. Finally, choose an eigenvector v v v λ \lambda λ c c c Proposition A.1 . This gives the stated bound on the number of positive entries of c c c v v v c c c
Fix a number λ ∉ H n \lambda\notin H_n λ ∈ / H n Ω n , m \Omega_{n,m} Ω n , m Proposition A.1 , we must find a probability vector c c c v v v ( λ I − C ( c ) ) v (\lambda I-C(c))v ( λ I − C ( c )) v I n , m I_{n,m} I n , m
( λ I − C ( c ) ) v = U B h , (\lambda I-C(c))v=U_Bh, ( λ I − C ( c )) v = U B h , where h ∈ C ∣ B n , m ∣ h\in\mathbb{C}^{|B_{n,m}|} h ∈ C ∣ B n , m ∣ U B U_B U B n n n
Every eigenvalue of C ( c ) C(c) C ( c ) H n H_n H n λ I − C ( c ) \lambda I-C(c) λ I − C ( c ) c c c h h h
v = ( λ I − C ( c ) ) − 1 U B h , ∥ h ∥ 2 = 1 , λ v b ∈ conv { v 0 , … , v n − 1 } ( b ∈ B n , m ) . (47) \begin{aligned}
v&=(\lambda I-C(c))^{-1}U_Bh,\qquad\lVert h\rVert_2=1,\\
\lambda v_b&\in\operatorname{conv}\{v_0,\ldots,v_{n-1}\}\qquad(b\in B_{n,m}). \tag*{(47)}
\end{aligned} v λ v b = ( λ I − C ( c ) ) − 1 U B h , ∥ h ∥ 2 = 1 , ∈ conv { v 0 , … , v n − 1 } ( b ∈ B n , m ) . (47) The residual U B h U_Bh U B h v ≠ 0 v\ne0 v = 0 v v v ∥ h ∥ 2 = 1 \lVert h\rVert_2=1 ∥ h ∥ 2 = 1 2 m 2m 2 m h h h n n n v v v c k c_k c k c c c h h h v v v
For arcs inherited from smaller orders, the next proposition also bounds the number of positive entries in the shared probability vector c c c
Proposition A.3. Let λ ∈ Θ n \lambda\in\Theta_n λ ∈ Θ n t λ ∉ Θ n t\lambda\notin\Theta_n t λ ∈ / Θ n t > 1 t>1 t > 1 N N N λ \lambda λ P ∈ Q n , m P\in\mathcal{Q}_{n,m} P ∈ Q n , m λ \lambda λ p p p
( p − 2 ) ( N − 2 m ) ≤ p ( n − N ) . (p-2)(N-2m)\le p(n-N). ( p − 2 ) ( N − 2 m ) ≤ p ( n − N ) . In particular, let λ \lambda λ q < s q<s q < s q ≥ 2 q\ge2 q ≥ 2 d = ⌊ n / q ⌋ d=\lfloor n/q\rfloor d = ⌊ n / q ⌋ 1 ≤ m < ⌈ d / 2 ⌉ 1\le m<\lceil d/2\rceil 1 ≤ m < ⌈ d /2 ⌉ P ∈ Q n , m P\in\mathcal{Q}_{n,m} P ∈ Q n , m λ \lambda λ Q n , m \mathcal{Q}_{n,m} Q n , m λ \lambda λ
Proof. Put b = 2 m b=2m b = 2 m S S S P P P A A A λ \lambda λ 0 < ρ ≤ 1 0<\rho\le1 0 < ρ ≤ 1 ρ < 1 \rho<1 ρ < 1 u u u D = diag ( u ) D=\operatorname{diag}(u) D = diag ( u ) ρ − 1 D − 1 A D \rho^{-1}D^{-1}AD ρ − 1 D − 1 A D λ / ρ \lambda/\rho λ / ρ ρ = 1 \rho=1 ρ = 1 A 1 = 1 A\mathbf{1}=\mathbf{1} A 1 = 1 S S S
Choose v ≠ 0 v\ne0 v = 0 A v = λ v Av=\lambda v A v = λ v K = conv { v i : i ∈ S } K=\operatorname{conv}\{v_i:i\in S\} K = conv { v i : i ∈ S } K K K h h h λ \lambda λ h h h λ \lambda λ h ≥ N h\ge N h ≥ N λ v i \lambda v_i λ v i ∂ K \partial K ∂ K i i i A v = λ v Av=\lambda v A v = λ v A ′ A' A ′ π > 0 \pi>0 π > 0 λ ≠ 1 \lambda\ne1 λ = 1 π T v = 0 \pi^\mathsf{T}v=0 π T v = 0
A ε = A ′ − ε e e i π T satisfies A ε v = λ v . A_\varepsilon=A'-\varepsilon e e_i\pi^\mathsf{T}\quad\text{satisfies}\quad A_\varepsilon v=\lambda v. A ε = A ′ − ε e e i π T satisfies A ε v = λ v . For small ε > 0 \varepsilon> 0 ε > 0
Choose one state for each vertex of K K K V ⊆ S V \subseteq S V ⊆ S M = ∣ S ∩ I n , m ∣ M = |S \cap I_{n,m}| M = ∣ S ∩ I n , m ∣ e = n − h e = n - h e = n − h S S S ∂ K \partial K ∂ K V V V e e e n n n
p ( M − e ) ≤ 2 M . p(M-e) \le2M. p ( M − e ) ≤ 2 M . For p ≥ 2 p \ge2 p ≥ 2 M ≥ N − b M \ge N-b M ≥ N − b e ≤ n − N e \le n-N e ≤ n − N ( p − 2 ) ( N − b ) ≤ p ( n − N ) (p-2)(N-b) \le p(n-N) ( p − 2 ) ( N − b ) ≤ p ( n − N ) p = 1 p=1 p = 1 b ≤ n b \le n b ≤ n
For the stated arc, N = max { q d , s } N = \max\{qd,s\} N = max { q d , s } r = n − N < q r = n-N < q r = n − N < q b < d b < d b < d d ≥ 3 d \ge3 d ≥ 3
N − b − 3 r ≥ ( d − 3 ) ( q − 1 ) + 1 > 0. N-b-3r \ge(d-3)(q-1)+1 > 0. N − b − 3 r ≥ ( d − 3 ) ( q − 1 ) + 1 > 0. If p ≥ 3 p \ge3 p ≥ 3 N − b ≤ p r / ( p − 2 ) ≤ 3 r N-b \le pr/(p-2) \le3r N − b ≤ p r / ( p − 2 ) ≤ 3 r λ ∈ ∂ Θ n ∩ Ω n , m \lambda\in\partial\Theta_n \cap\Omega_{n,m} λ ∈ ∂ Θ n ∩ Ω n , m ∂ Ω n , m \partial\Omega_{n,m} ∂ Ω n , m
Fix n n n m m m λ \lambda λ λ ∈ Ω n , m \lambda\in\Omega_{n,m} λ ∈ Ω n , m P ∈ Q n , m P \in\mathcal{Q}_{n,m} P ∈ Q n , m λ \lambda λ c c c
First choose two possible positions in c c c t 0 t_0 t 0 1 − t 0 1-t_0 1 − t 0 c c c b ∈ B n , m b \in B_{n,m} b ∈ B n , m t b t_b t b 1 − t b 1-t_b 1 − t b b b b c c c P ∈ Q n , m P \in\mathcal{Q}_{n,m} P ∈ Q n , m 2 m + 1 2m+1 2 m + 1 t 0 t_0 t 0 2 m 2m 2 m t b t_b t b [ 0 , 1 ] [0,1] [ 0 , 1 ]
We must find values of these parameters together with a vector v = ( v 0 , … , v n − 1 ) ∈ C n v=(v_0,\ldots,v_{n-1}) \in\mathbb{C}^n v = ( v 0 , … , v n − 1 ) ∈ C n v ≠ 0 v \ne0 v = 0 P v = λ v Pv=\lambda v P v = λ v v v v 2 m + 1 2m+1 2 m + 1 λ \lambda λ
Corollary A.4. Fix n , m n,m n , m If λ \lambda λ λ ∈ Ω n , m \lambda\in\Omega_{n,m} λ ∈ Ω n , m λ \lambda λ
If n ≥ 4 n \ge4 n ≥ 4 A A A Θ n \Theta_n Θ n A ∩ Ω n , m A \cap\Omega_{n,m} A ∩ Ω n , m
Proof. By definition, λ = x + i y \lambda=x+iy λ = x + i y Ω n , m \Omega_{n,m} Ω n , m P P P det ( ( x + i y ) I − P ) = 0 \det((x+iy)I-P)=0 det (( x + i y ) I − P ) = 0 P P P (41) . Algorithms in real algebraic geometry turn the question of whether this system has a solution into equivalent polynomial conditions on x , y x,y x , y [1 ] . This procedure is called real quantifier elimination. For algebraic x , y x,y x , y
For n ≥ 4 n \ge4 n ≥ 4 Theorem 7.2 describes ∂ Θ n \partial\Theta_n ∂ Θ n Q \mathbb{Q} Q A A A ∂ Θ n \partial\Theta_n ∂ Θ n A A A A ∩ Ω n , m A \cap\Omega_{n,m} A ∩ Ω n , m
Local freedom of characteristic-polynomial coefficients
We isolate the relation on two consecutive rows of a matrix. Let P P P n × n n \times n n × n n ≥ 3 n \ge3 n ≥ 3 1 1 1 1 1 1 0 0 0 2 , … , n − 1 2,\ldots,n-1 2 , … , n − 1 n n n Q n , n / 2 − 1 Q_{n,n/2-1} Q n , n /2 − 1 P i j ≥ 0 P_{ij} \ge0 P ij ≥ 0
Every such P P P 1 \mathbf{1} 1 1 \mathbf{1} 1 ( n − 1 ) (n-1) ( n − 1 ) 1 1 1
Write [ x ] [x] [ x ] x x x
V = R n / span { 1 } , L = { P ∈ R n × n : P 1 = 1 , P 1 , j + 1 = P 0 j for every j } , V = \mathbb{R}^n / \operatorname{span}\{\mathbf{1}\}, \qquad\mathcal{L} = \{P \in\mathbb{R}^{n \times n} : P\mathbf{1} = \mathbf{1},\ P_{1,j+1} = P_{0j}\text{ for every }j\}, V = R n / span { 1 } , L = { P ∈ R n × n : P 1 = 1 , P 1 , j + 1 = P 0 j for every j } , with indices modulo n n n P 1 = 1 P\mathbf{1} = \mathbf{1} P 1 = 1
P ‾ ( [ x ] ) = [ P x ] \overline{P}([x]) = [Px] P ([ x ]) = [ P x ] is independent of the representative x x x V V V End ( V ) \operatorname{End}(V) End ( V ) V V V
A row-sum-one lift of M ∈ End ( V ) M \in\operatorname{End}(V) M ∈ End ( V ) A A A A 1 = 1 A\mathbf{1} = \mathbf{1} A 1 = 1 [ A x ] = M [ x ] [Ax] = M[x] [ A x ] = M [ x ] x x x V V V V V V A A A M M M A A A 1 \mathbf{1} 1
This initial lift need not satisfy the relation between rows 0 0 0 1 1 1 d j = A 0 j − A 1 , j + 1 d_j = A_{0j} - A_{1,j+1} d j = A 0 j − A 1 , j + 1
w j + 1 − w j = d j , ∑ j w j = 0. w_{j+1} - w_j = d_j,\qquad\sum_j w_j = 0. w j + 1 − w j = d j , j ∑ w j = 0. The two rows of A A A 1 1 1 ∑ j d j = 0 \sum_j d_j = 0 ∑ j d j = 0 w 0 w_0 w 0 w n = w 0 w_n = w_0 w n = w 0
Set P = A + 1 w T P = A + \mathbf{1}w^{\mathsf{T}} P = A + 1 w T w T w^{\mathsf{T}} w T P 1 , j + 1 = P 0 j P_{1,j+1} = P_{0j} P 1 , j + 1 = P 0 j 1 ( w T x ) \mathbf{1}(w^{\mathsf{T}}x) 1 ( w T x ) x x x P P P M M M P ∈ L P \in\mathcal{L} P ∈ L M M M
If two matrices in L \mathcal{L} L V V V 1 u T \mathbf{1}u^{\mathsf{T}} 1 u T ∑ j u j = 0 \sum_j u_j = 0 ∑ j u j = 0 u j + 1 = u j u_{j+1} = u_j u j + 1 = u j u u u P ↦ P ‾ P \mapsto\overline{P} P ↦ P L \mathcal{L} L End ( V ) \operatorname{End}(V) End ( V ) L L L
Writing χ A ( z ) = det ( z I − A ) \chi_A(z)=\det(zI-A) χ A ( z ) = det ( z I − A ) A A A R n \mathbb{R}^n R n 1 1 1 P = L ( M ) P=L(M) P = L ( M ) 1 1 1 M M M
χ L ( M ) ( z ) = ( z − 1 ) χ M ( z ) . \chi_{L(M)}(z)=(z-1)\chi_M(z). χ L ( M ) ( z ) = ( z − 1 ) χ M ( z ) . A row vector defines a functional on V V V ℓ [ x ] = x 0 − x 1 \ell[x]=x_0-x_1 ℓ [ x ] = x 0 − x 1 e 0 T − e 1 T e_0^{\mathsf T}-e_1^{\mathsf T} e 0 T − e 1 T r = ℓ M r=\ell M r = ℓ M P = L ( M ) P=L(M) P = L ( M ) r r r 0 0 0 1 1 1 P P P p p p
r j = p j − p j − 1 , ∑ j p j = 1. r_j=p_j-p_{j-1},\qquad\sum_j p_j=1. r j = p j − p j − 1 , j ∑ p j = 1. These equations uniquely determine p p p
Lemma B.1. For each d d d d × d d\times d d × d M M M χ M \chi_M χ M d d d
Proof. If u u u d × d d\times d d × d M M M u , M u , … , M d − 1 u u,Mu,\ldots,M^{d-1}u u , M u , … , M d − 1 u
χ M + u w ( z ) = χ M ( z ) − w adj ( z I − M ) u . \chi_{M+uw}(z)=\chi_M(z)-w\operatorname{adj}(zI-M)u. χ M + u w ( z ) = χ M ( z ) − w adj ( z I − M ) u . for every row vector w w w w ↦ w adj ( z I − M ) u w\mapsto w\operatorname{adj}(zI-M)u w ↦ w adj ( z I − M ) u d − 1 d-1 d − 1 resolvent of M M M ( z I − M ) − 1 (zI-M)^{-1} ( z I − M ) − 1 z z z ∣ z ∣ |z| ∣ z ∣
( z I − M ) − 1 = ∑ k = 0 ∞ M k z k + 1 . (zI-M)^{-1}=\sum_{k=0}^{\infty}\frac{M^k}{z^{k+1}}. ( z I − M ) − 1 = k = 0 ∑ ∞ z k + 1 M k . If w adj ( z I − M ) u w\operatorname{adj}(zI-M)u w adj ( z I − M ) u χ M ( z ) \chi_M(z) χ M ( z ) w M k u = 0 wM^ku=0 w M k u = 0 0 ≤ k < d 0\leq k<d 0 ≤ k < d w = 0 w=0 w = 0 d d d M M M
For arbitrary M M M 2 × 2 2\times2 2 × 2 M M M χ M \chi_M χ M □ \square □
Proposition B.2. Let n ≥ 3 n\geq3 n ≥ 3 P ∈ L P\in\mathcal{L} P ∈ L 2 , … , n − 1 2,\ldots,n-1 2 , … , n − 1 e 0 T e_0^{\mathsf T} e 0 T L \mathcal{L} L P P P L \mathcal{L} L n n n 1 1 1 e 0 T e_0^{\mathsf T} e 0 T 1 1 1
Proof. Put M = P ‾ M=\overline{P} M = P r = ℓ M r=\ell M r = ℓ M ℓ \ell ℓ a ∈ V a\in V a ∈ V ℓ a = 0 \ell a=0 ℓ a = 0 r a = 1 ra=1 r a = 1 t > 0 t>0 t > 0 S = I − t a r S=I-ta r S = I − t a r ℓ S = ℓ \ell S=\ell ℓ S = ℓ
ℓ ( S − 1 M S ) = r S = ( 1 − t ) r . \ell(S^{-1}MS)=rS=(1-t)r. ℓ ( S − 1 M S ) = r S = ( 1 − t ) r . Its lift has first row ( 1 − t ) p + t 1 T / n (1-t)p+t1^{\mathsf T}/n ( 1 − t ) p + t 1 T / n r = λ ℓ r=\lambda\ell r = λ ℓ
p 0 = 1 + ( n − 1 ) λ n , p j = 1 − λ n ( j ≠ 0 ) . p_0=\frac{1+(n-1)\lambda}{n},\qquad p_j=\frac{1-\lambda}{n}\quad(j\ne0). p 0 = n 1 + ( n − 1 ) λ , p j = n 1 − λ ( j = 0 ) . For − 1 / ( n − 1 ) < λ < 1 -1/(n-1)<\lambda<1 − 1/ ( n − 1 ) < λ < 1 λ = 1 \lambda=1 λ = 1 λ ∗ = − 1 / ( n − 1 ) \lambda_*=-1/(n-1) λ ∗ = − 1/ ( n − 1 ) P 00 P_{00} P 00 P 11 P_{11} P 11 p 0 p_0 p 0 M M M 1 / n 1/n 1/ n ℓ M \ell M ℓ M g g g g ∈ V g\in V g ∈ V ( 0 , − ( n − 1 ) / n , … , − 1 / n ) T (0,-(n-1)/n,\ldots,-1/n)^{\mathsf T} ( 0 , − ( n − 1 ) / n , … , − 1/ n ) T p 0 = 1 / n + ( ℓ M ) g p_0=1/n+(\ell M)g p 0 = 1/ n + ( ℓ M ) g ℓ g = ( n − 1 ) / n \ell g=(n-1)/n ℓ g = ( n − 1 ) / n ( λ ∗ I − M ) g ≠ 0 (\lambda_*I-M)g\ne0 ( λ ∗ I − M ) g = 0 H H H ℓ H ( λ ∗ I − M ) g > 0 \ell H(\lambda_*I-M)g>0 ℓ H ( λ ∗ I − M ) g > 0 M ( t ) = ( I + t H ) − 1 M ( I + t H ) M(t)=(I+tH)^{-1}M(I+tH) M ( t ) = ( I + t H ) − 1 M ( I + t H )
p 0 ′ ( 0 ) = ℓ H ( λ ∗ I − M ) g > 0. p_0'(0)=\ell H(\lambda_*I-M)g>0. p 0 ′ ( 0 ) = ℓ H ( λ ∗ I − M ) g > 0. Both zero entries become positive, and all other entries stay positive. If M g = λ ∗ g Mg=\lambda_*g M g = λ ∗ g a ∈ ker ℓ a\in\ker\ell a ∈ ker ℓ ( M − λ ∗ I ) a ≠ 0 (M-\lambda_*I)a\ne0 ( M − λ ∗ I ) a = 0 a a a M = λ ∗ I M=\lambda_*I M = λ ∗ I V = span { g } ⊕ ker ℓ V=\operatorname{span}\{g\}\oplus\ker\ell V = span { g } ⊕ ker ℓ T s = I + s a ℓ / ( ℓ g ) T_s=I+sa\ell/(\ell g) T s = I + s a ℓ / ( ℓ g ) N = T s − 1 M T s N=T_s^{-1}MT_s N = T s − 1 M T s
ℓ N = λ ∗ ℓ , ( N − λ ∗ I ) g = s ( M − λ ∗ I ) a ≠ 0. \ell N=\lambda_*\ell,\qquad(N-\lambda_*I)g=s(M-\lambda_*I)a\ne0. ℓ N = λ ∗ ℓ , ( N − λ ∗ I ) g = s ( M − λ ∗ I ) a = 0. The lift keeps both constrained rows fixed, so the preceding argument applies arbitrarily close to P P P L ( λ ∗ I ) = λ ∗ I + ( 1 − λ ∗ ) J L(\lambda_*I)=\lambda_*I+(1-\lambda_*)J L ( λ ∗ I ) = λ ∗ I + ( 1 − λ ∗ ) J P P P Lemma B.1 show that this neighbourhood realises a neighbourhood of χ P \chi_P χ P { 0 , 1 } \{0,1\} { 0 , 1 } p = e 0 T p=e_0^{\mathsf T} p = e 0 T P P P 1 + ε 1+\varepsilon 1 + ε L L L χ P \chi_P χ P
The authors wanted to gain more understanding about how eigenvalue regions change. Discussions with AI tools led to the idea of using a Toeplitz interior. The main mathematical ideas originated with the authors and developed through one author’s presentation and other talks and discussions at the ILAS 2026 meeting. The manuscript was developed through collaboration between the authors and AI tools. Discussions with GPT-6 Astra helped develop arguments and close gaps in the proofs. OpenAI Codex, using GPT-6.1 Sol, assisted with rewriting the exposition, preparing the figures, and writing and running code for numerical checks. The authors take full responsibility for the mathematical claims, proofs, computations, figures, and final text.
