betaFeedback

WorksMathematics

Nilpotent skew-symmetric tridiagonal Bohemian matrices: a proof of Corless's conjecture

Abstract

Corless studied the skew-symmetric tridiagonal matrices Tm(u)T_m(u) with superdiagonal u∈{1,i}m−1u \in \{1, i\}^{m-1}. He showed that Tm(u)T_m(u) can be nilpotent only if m=2K−1m = 2^K - 1 and that the 2K−12^{K-1} vectors uu obtained from the empty vector by repeated application of u \mapsto (u, 1, i, \rev u) and u \mapsto (u, i, 1, \rev u) give nilpotent matrices, and he conjectured that there are no others. We prove this conjecture. Reducing the characteristic polynomial modulo 44 gives a necessary condition for nilpotency that is linear over \F. For m>1m > 1 it forces u = (v, 1, i, \rev v) or u = (v, i, 1, \rev v), and an identity implicit in Corless's proof then reduces the problem to vv. Since Tm(u)T_m(u) is diagonally similar to a finite section of the Feinberg–Zee hopping matrix, the theorem also determines the nilpotent tridiagonal sign matrices. We further show that the (1,1)(1,1) entry of the resolvent of a nilpotent Tm(u)T_m(u) is λ−1±λ−3±λ−7±⋯±λ−(2K−1)λ^{-1} \pm λ^{-3} \pm λ^{-7} \pm \dots \pm λ^{-(2^K - 1)}, with signs that determine uu. The proof of the main theorem has been formalised in Lean~4.

Introduction

A matrix family is called Bohemian if its entries are drawn from a fixed finite set, its population [5]. Corless [5] studied the skew-symmetric tridiagonal Bohemian matrices with population {1,i}\{1,i\}:

Tm(u)=(0u1−u10u2−u20⋱⋱⋱um−1−um−10),u=(u1,…,um−1)∈{1,i}m−1.T_m(u)=\begin{pmatrix} 0 & u_1 & & & \\ -u_1 & 0 & u_2 & & \\ & -u_2 & 0 & \ddots& \\ & & \ddots& \ddots& u_{m-1} \\ & & & -u_{m-1} & 0 \end{pmatrix}, \qquad u=(u_1,\ldots,u_{m-1})\in\{1,i\}^{m-1}.

Here skew-symmetric means TT=−TT^{\mathsf{T}}=-T, without complex conjugation. Nilpotent matrices are of particular interest in this family, because their computed eigenvalues are far from the true ones: a floating-point eigenvalue routine returns values of size about μ1/m\mu^{1/m}, where μ\mu is the unit roundoff, and these values produce conspicuous artefacts in plots of the eigenvalues of the whole family [5 Section 3]. A nilpotent Tm(u)T_m(u) consists of a single Jordan block (Remark 3.6); Corless calls such matrices coreless.

Corless proved that Tm(u)T_m(u) can be nilpotent only if m=2K−1m=2^K-1 for some K≥1K\geq1 [5 Theorem 4.1], and that the vectors obtained from the empty vector by repeated application of

u↦(u,1,i,rev⁡u)andu↦(u,i,1,rev⁡u)(1)u\mapsto(u,1,i,\operatorname{rev}u)\qquad\text{and}\qquad u\mapsto(u,i,1,\operatorname{rev}u) \tag*{(1)}

give nilpotent matrices [5 Theorem 4.2]; here rev⁡u\operatorname{rev}u denotes uu reversed. This construction yields 2K−12^{K-1} nilpotent matrices of dimension 2K−12^K-1. He conjectured that there are no others [5 Conjecture 5.1] and verified this by exhaustive computation for m≤31m\leq31.

Theorem 1.1. Let m≥1m \ge1 and u∈{1,i}m−1u \in\{1,i\}^{m-1}. Then Tm(u)T_m(u) is nilpotent if and only if m=2K−1m=2^K-1 for some K≥1K \ge1 and uu is obtained from the empty vector by repeated application of (1). In particular, there are exactly 2K−12^{K-1} nilpotent matrices Tm(u)T_m(u) of dimension m=2K−1m=2^K-1, and none of any other dimension.

For m=3m=3 the nilpotent vectors are (1,i)(1,i) and (i,1)(i,1); Figure 1 shows the 16 vectors for m=31m=31.

Figure 1. The 16 nilpotent vectors uu for m=31m=31, one per row; blue cells are 1, orange cells are ii. Consecutive entries are grouped in pairs (see Corollary 3.5), and the ticks mark the middle pair of each level of the recursion.

Outline of the proof

Put sk=uk2=±1s_k=u_k^2=\pm1. The characteristic polynomial of Tm(u)T_m(u) is λmDs(λ−2)\lambda^mD_s(\lambda^{-2}), where DsD_s is the matching polynomial of the path with mm vertices and edge weights s1,…,sm−1s_1,\ldots,s_{m-1}; see [5 Propositions 2.1 and 2.9]. Thus Tm(u)T_m(u) is nilpotent if and only if Ds=1D_s=1, which is a system of polynomial equations of degrees 1,2,…,⌊m/2⌋1,2,\ldots,\lfloor m/2\rfloor in the signs. Call a sign sequence folded if it has the form s=(σ,ε,−ε,rev⁡σ)s=(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma) with ε=±1\varepsilon=\pm1; the rule (1) produces such sequences. Folded sequences satisfy the identity Ds=Dσ2D_s=D_\sigma^2 (Lemma 2.3), which is implicit in the proof of [5 Theorem 4.2]. Hence a folded sequence satisfies Ds=1D_s=1 if and only if Dσ=1D_\sigma=1, and the theorem follows by induction once we know that every nonempty ss with Ds=1D_s=1 is folded.

To prove this we study the equation Ds=1D_s=1 modulo 2 and modulo 4. Modulo 2 the signs disappear, and one obtains the restriction on the dimension. Modulo 4 they enter linearly: if se=1−2tes_e=1-2t_e with te∈{0,1}t_e\in\{0,1\}, then ∏e(1−2te)≡1−2∑ete(mod4)\prod_e(1-2t_e)\equiv1-2\sum_e t_e\pmod4. In other words, modulo 4 the map s↦Dss\mapsto D_s coincides with its first-order Taylor expansion at s=(1,…,1)s=(1,\ldots,1), with the element 2 of Z/4Z\mathbb{Z}/4\mathbb{Z} in the role of an infinitesimal of square zero. The condition Ds≡1(mod4)D_s\equiv1\pmod4 is therefore a linear system over F2\mathbb{F}_2 in the unknowns tet_e. By the reflection symmetry of the path, the edges ee and m−em-e have the same coefficient polynomial, so the system involves only the sums te+tm−et_e+t_{m-e} in F2\mathbb{F}_2. Apart from this symmetry its coefficient polynomials are linearly independent (Lemma 3.1), so the system determines these sums. Since every folded sequence is a solution, the sums are those of a folded sequence, and every solution is folded (Proposition 3.2). The moduli 8,16,…8,16,\ldots, for which the equations are no longer linear, are not needed.

Tridiagonal sign matrices

The matrices Tm(u)T_m(u) also occur, in a different normalisation, in the spectral theory of non-self-adjoint operators. For a,c∈Cm−1a,c \in\mathbb{C}^{m-1} let Jm(a,c)J_m(a,c) be the m×mm \times m tridiagonal matrix with zero diagonal, superdiagonal aa and subdiagonal cc, so that Tm(u)=Jm(u,−u)T_m(u)=J_m(u,-u). For b∈{±1}m−1b \in\{\pm1\}^{m-1} put Amb=Jm((1,…,1),b)A_m^b=J_m((1,\ldots,1),b). These are the finite sections of the hopping matrix of Feinberg and Zee [8], whose spectrum has been studied in [2, 3, 4, 9]. Following Hagger [10], we call them tridiagonal sign matrices; every tridiagonal matrix with zero diagonal and entries ±1\pm1 on the two off-diagonals is diagonally similar to one of them. So is Tm(u)T_m(u), with bk=−uk2b_k=-u_k^2 (Lemma 2.1), and Theorem 1.1 therefore classifies the nilpotent tridiagonal sign matrices as well. To state the result in this setting, let FK⊂{±1}2K−2F_K \subset\{\pm1\}^{2^K-2} be the set of sign sequences obtained from the empty sequence by K−1K-1 applications of σ↦(σ,ε,−ε,rev⁡σ)\sigma\mapsto(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma) with ε=±1\varepsilon=\pm1; under sk=uk2s_k=u_k^2 these are the vectors of Theorem 1.1.

Theorem 1.2. Let m≥1m \ge1 and let a,c∈Cm−1a,c \in\mathbb{C}^{m-1} satisfy akck=±1a_kc_k=\pm1 for all kk. Then Jm(a,c)J_m(a,c) is nilpotent if and only if m=2K−1m=2^K-1 for some K≥1K \ge1 and (a1c1,…,am−1cm−1)∈FK(a_1c_1,\ldots,a_{m-1}c_{m-1}) \in F_K. In particular, a tridiagonal sign matrix AmbA_m^b is nilpotent if and only if m=2K−1m=2^K-1 for some K≥1K \ge1 and b∈FKb \in F_K.

Some nilpotent tridiagonal sign matrices are implicit in this literature. Chandler-Wilde, Chonchaiya and Lindner [2] introduced the sign sequence

c~1=1,c~2j=c~2j−1c~j,c~2j+1=−c~2j(j≥1)(2)\tilde{c}_1=1,\qquad\tilde{c}_{2j}=\tilde{c}_{2j-1}\tilde{c}_j,\qquad\tilde{c}_{2j+1}=-\tilde{c}_{2j}\qquad(j\ge1) \tag*{(2)}

(we use the notation of [4]) and showed that the characteristic polynomials of the finite sections AmbA_m^b with b=(c~2,…,c~m)b=(\tilde{c}_2,\ldots,\tilde{c}_m) have all their coefficients in {−1,0,1}\{-1,0,1\}. Chandler-Wilde and Davies showed that for m=2n−1m=2^n-1 these polynomials are monomials [4 Lemma 30], so that the corresponding matrices AmbA_m^b are nilpotent. Together with the symmetries b↦−bb\mapsto-b [3 Lemma 3.4] and b↦rev⁡bb\mapsto\operatorname{rev} b, this accounts for four of the 2n−12^{n-1} nilpotent tridiagonal sign matrices of dimension 2n−1≥72^n-1\ge7. We give another proof in Remark 5.3. To the best of our knowledge, neither the restriction on the dimension nor the classification appears in this literature. The resemblance between the eigenvalue plots of the two families was pointed out in [6], where the ring at the centre of [3 Figure 3] for dimension 15 is attributed to rounding errors caused by nilpotent matrices.

Further results

In Section 4 we show that if Tm(u)T_m(u) is nilpotent, then the terminating continued fraction with partial numerators u12x,…,um−12xu_1^2x,\ldots,u_{m-1}^2x is a lacunary polynomial 1±x±x3±x7±⋯±x2K−1−11\pm x\pm x^3\pm x^7\pm\cdots\pm x^{2^{K-1}-1}, whose signs are the choices made in the recursion. Equivalently, the (1,1)(1,1) entry of the resolvent of Tm(u)T_m(u) is λ−1±λ−3±λ−7±⋯±λ−(2K−1)\lambda^{-1}\pm\lambda^{-3}\pm\lambda^{-7}\pm\cdots\pm\lambda^{-(2^K-1)}. In Section 5 we show that the nilpotent sign sequences are also generated by a doubling rule, of which the sequence (2) is a fixed point. This rule is a finite analogue of the maps used in [4] to show that the spectrum of the Feinberg–Zee hopping matrix is closed under taking square roots. The proof of Theorem 1.1 has been formalised in Lean 4 [7] with the Mathlib library [12]; this and an exhaustive search for m=63m=63 are described in Section 6.

Matching polynomials

Throughout, sk=uk2s_k=u_k^2, so sk=1s_k=1 if uk=1u_k=1 and sk=−1s_k=-1 if uk=iu_k=i. Since uku_k is determined by sks_k, we identify a vector uu with its sign sequence s=(s1,…,sm−1)∈{±1}m−1s=(s_1,\ldots,s_{m-1})\in\{\pm1\}^{m-1}. Corless’s rule (1) becomes

σ↦(σ,ε,−ε,rev⁡σ),ε=±1,(3)\sigma\mapsto(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma),\qquad\varepsilon=\pm1, \tag*{(3)}

so the vectors of Theorem 1.1 correspond to the sequences in FKF_K, which have length 2K−22^K-2. Since σ\sigma and ε\varepsilon can be read off (σ,ε,−ε,rev⁡σ)(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma), we have ∣FK∣=2K−1|F_K|=2^{K-1}, and FKF_K is closed under s↦−ss\mapsto-s, by induction on KK.

Let PmP_m be the path with the vertices 1,…,m1,\ldots,m, in which the edge ee joins ee and e+1e+1 (1≤e≤m−11 \le e \le m-1). For s∈{±1}m−1s \in\{ \pm1 \}^{m-1} let

Ds(x)=∑M(∏e∈Mse)x∣M∣∈Z[x],D_s(x)=\sum_M\left(\prod_{e\in M}s_e\right)x^{|M|}\in\mathbb{Z}[x],

where MM runs through the matchings of PmP_m, that is, the sets of pairwise disjoint edges, including the empty set. For s=(1,…,1)s=(1,\ldots,1) we obtain the Fibonacci polynomials fm(x)=∑j(m−jj)xjf_m(x)=\sum_j\binom{m-j}{j}x^j. More generally, for 1≤a≤b+1≤m+11\le a\le b+1\le m+1 let Da,bD_{a,b} be the matching polynomial of the subpath with the vertices a,…,ba,\ldots,b and the signs sa,…,sb−1s_a,\ldots,s_{b-1}. Thus Ds=D1,mD_s=D_{1,m}, and Da,b=1D_{a,b}=1 if the subpath has at most one vertex. Distinguishing whether or not the last vertex is matched, we obtain

Da,b=Da,b−1+sb−1xDa,b−2(b≥a+1).(4)D_{a,b}=D_{a,b-1}+s_{b-1}xD_{a,b-2}\qquad(b\ge a+1). \tag*{(4)}

Lemma 2.1. Let a,c∈Cm−1a,c\in\mathbb{C}^{m-1} with akck=±1a_kc_k=\pm1 for all kk.

(i) Put sk=−akcks_k=-a_kc_k. Then det⁡(λI−Jm(a,c))=λmDs(λ−2)\det(\lambda I-J_m(a,c))=\lambda^mD_s(\lambda^{-2}). In particular, Jm(a,c)J_m(a,c) is nilpotent if and only if Ds=1D_s=1.

(ii) Put bk=akckb_k=a_kc_k, and let Δ\Delta be the diagonal matrix with the entries δ1=1\delta_1=1 and δk+1=δk/ak\delta_{k+1}=\delta_k/a_k. Then Jm(a,c)=ΔAmbΔ−1J_m(a,c)=\Delta A_m^b\Delta^{-1}.

Proof. The characteristic polynomials pkp_k of the leading k×kk\times k blocks of Jm(a,c)J_m(a,c) satisfy pk=λpk−1−ak−1ck−1pk−2p_k=\lambda p_{k-1}-a_{k-1}c_{k-1}p_{k-2} with p0=1p_0=1 and p1=λp_1=\lambda (cf. [5 Proposition 2.1]). By (4), so do the polynomials λkD1,k(λ−2)\lambda^kD_{1,k}(\lambda^{-2}). This proves (i), and (ii) is verified entrywise. □

For Tm(u)=Jm(u,−u)T_m(u)=J_m(u,-u) the lemma gives sk=uk2s_k=u_k^2 and bk=−uk2b_k=-u_k^2. We call a vector uu, and its sign sequence ss, nilpotent if Tm(u)T_m(u) is nilpotent, that is, if Ds=1D_s=1. Theorem 1.1 is equivalent to the following statement.

Theorem 2.2. Let m≥1m\ge1 and s∈{±1}m−1s\in\{\pm1\}^{m-1}. Then Ds=1D_s=1 if and only if m=2K−1m=2^K-1 and s∈FKs\in F_K.

The rule (3) is explained by the following identity.

Lemma 2.3. Let σ∈{±1}N−1\sigma\in\{\pm1\}^{N-1} and ϵ=±1\epsilon=\pm1, and put s=(σ,ϵ,−ϵ,rev⁡σ)s=(\sigma,\epsilon,-\epsilon,\operatorname{rev}\sigma). Then Ds=Dσ2D_s=D_\sigma^2.

Proof. Deleting the middle vertex of the path of ss leaves two paths that are mirror images of each other, each with matching polynomial DσD_\sigma. Let EE be the matching polynomial of either of them without the vertex next to the middle one. Classifying matchings by how the middle vertex is covered (not at all, by the left edge, or by the right edge) gives

Ds=Dσ2+ϵxEDσ−ϵxDσE=Dσ2.D_s=D_\sigma^2+\epsilon xED_\sigma-\epsilon xD_\sigma E=D_\sigma^2.

For the matrices Tm(u)T_m(u) this identity is implicit in the proof of [5 Theorem 4.2]: the first line of equation (17) there comes from a Laplace expansion along the central row and does not use nilpotency.

Modulo 2 all sign sequences give the same polynomial.

Lemma 2.4. Let m≥1m\ge1 and s∈{±1}m−1s\in\{\pm1\}^{m-1}.

(i) Ds≡fmD_s\equiv f_m (mod 2).

(ii) In F2[y]\mathbb{F}_2[y] we have fk(y+y2)=(1+y)k+1+yk+1f_k(y+y^2)=(1+y)^{k+1}+y^{k+1} for all k≥0k\ge0.

(iii) fm≡1f_m\equiv1 (mod 2) if and only if m+1m+1 is a power of 2. In particular, if Ds=1D_s=1, then m=2K−1m=2^K-1 for some K≥1K\ge1.

Proof. (i) holds because every ses_e is odd. For (ii), both sides are equal to 1 for k=0k=0 and k=1k=1, and both satisfy the recurrence gk=gk−1+(y+y2)gk−2g_k=g_{k-1}+(y+y^2)g_{k-2}: the left side by (4), the right side because yy and 1+y1+y are the roots of r2+r+(y+y2)r^2+r+(y+y^2) over F2\mathbb{F}_2. For (iii), note that the substitution x↦y+y2x\mapsto y+y^2 is injective on F2[x]\mathbb{F}_2[x]. By (ii), fm≡1f_m\equiv1 (mod 2) if and only if (1+y)m+1=1+ym+1(1+y)^{m+1}=1+y^{m+1} in F2[y]\mathbb{F}_2[y]. This holds if m+1m+1 is a power of 2. If m+1=2abm+1=2^a b with b>1b>1 odd, then (1+y)m+1=(1+y2a)b(1+y)^{m+1}=(1+y^{2^a})^b contains the term y2ay^{2^a}, and 2a<m+12^a<m+1. The last assertion follows from (i). □

The last assertion of Lemma 2.4 is [5 Theorem 4.1]; the proof given there uses Lucas’s theorem. The closed form (ii), which is Binet’s formula for the Fibonacci polynomials [11] read modulo 2, will be needed in the next section.

Reduction modulo 4 and proof of the main theorems

For 1≤e≤m−11 \le e \le m-1 let ce=xfe−1fm−1−e∈Z[x]c_e=x f_{e-1}f_{m-1-e}\in\mathbb{Z}[x]. Deleting the endpoints of edge ee leaves paths with e−1e-1 and m−1−em-1-e vertices, so ce=∑M∋ex∣M∣c_e=\sum_{M\ni e}x^{|M|}, the sum over the matchings of PmP_m that contain ee. Write se=1−2tes_e=1-2t_e with te∈{0,1}t_e\in\{0,1\}. Since ∏e∈M(1−2te)≡1−2∑e∈Mte(mod4)\prod_{e\in M}(1-2t_e)\equiv1-2\sum_{e\in M}t_e\pmod4 for every matching MM, summing over MM gives

Ds≡fm−2∑e=1m−1tece(mod4).(5)D_s\equiv f_m-2\sum_{e=1}^{m-1}t_ec_e\pmod4. \tag*{(5)}

Clearly ce=cm−ec_e=c_{m-e}, and for odd mm these are the only linear relations among the cec_e modulo 2:

Lemma 3.1. Let m=2N+1m=2N+1. The reductions of c1,…,cNc_1,\ldots,c_N modulo 2 are linearly independent over F2\mathbb{F}_2.

Proof. Suppose ∑e∈Sce≡0(mod2)\sum_{e\in S}c_e\equiv0\pmod2 for some nonempty S⊆{1,…,N}S\subseteq\{1,\ldots,N\}. Since F2[x]\mathbb{F}_2[x] is a domain, ∑e∈Sfe−1fm−1−e≡0\sum_{e\in S}f_{e-1}f_{m-1-e}\equiv0. Substituting x=y+y2x=y+y^2 and using Lemma 2.4,

fe−1fm−1−e⟼((1+y)e+ye)((1+y)m−e+ym−e)=A+φe,f_{e-1}f_{m-1-e}\longmapsto\bigl((1+y)^e+y^e\bigr)\bigl((1+y)^{m-e}+y^{m-e}\bigr)=A+\varphi_e,

where A=(1+y)m+ymA=(1+y)^m+y^m has constant term 1, and φe=ye(1+y)m−e+ym−e(1+y)e\varphi_e=y^e(1+y)^{m-e}+y^{m-e}(1+y)^e. For e≤Ne\le N we have m−e≥N+1>em-e\ge N+1>e, so the lowest-degree term of φe\varphi_e is yey^e. Comparing constant terms in ∣S∣A+∑e∈Sφe=0|S|A+\sum_{e\in S}\varphi_e=0 shows that ∣S∣|S| is even, hence ∑e∈Sφe=0\sum_{e\in S}\varphi_e=0. But the coefficient of ymin⁡Sy^{\min S} in this sum is 1, because every other φe\varphi_e has lowest-degree term of higher degree. This is a contradiction. □

Proposition 3.2. Let m=2N+1=2K−1m=2N+1=2^K-1 with K≥2K\ge2, and let s∈{±1}m−1s\in\{\pm1\}^{m-1}. Then Ds≡1(mod4)D_s\equiv1\pmod4 if and only if ss is folded, that is, s=(σ,ε,−ε,rev⁡σ)s=(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma) for some σ∈{±1}N−1\sigma\in\{\pm1\}^{N-1} and ε=±1\varepsilon=\pm1. Equivalently, sN=−sN+1s_N=-s_{N+1}, and sm−e=ses_{m-e}=s_e for 1≤e≤N−11\le e\le N-1.

Proof. By Lemma 2.4, fm=1+2gf_m=1+2g for some g∈Z[x]g\in\mathbb{Z}[x]. By (5), Ds≡1(mod4)D_s\equiv1\pmod4 is equivalent to

∑e=1m−1tece≡g(mod2).(6)\sum_{e=1}^{m-1}t_ec_e\equiv g\pmod2. \tag*{(6)}

The pairs {e,m−e}\{e,m-e\} with 1≤e≤N1\le e\le N partition {1,…,2N}\{1,\ldots,2N\}, and ce=cm−ec_e=c_{m-e}. So the left side of (6) equals ∑e=1Nwece\sum_{e=1}^Nw_ec_e with we=te+tm−e(mod2)w_e=t_e+t_{m-e}\pmod2. By Lemma 3.1, at most one vector w∈F2Nw\in\mathbb{F}_2^N satisfies (6).

Folded sequences satisfy the congruence. Indeed, if s=(σ,ε,−ε,rev⁡σ)s=(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma), then Ds=Dσ2D_s=D_\sigma^2 by Lemma 2.3, and Dσ≡fN≡1(mod2)D_\sigma\equiv f_N\equiv1\pmod2 by Lemma 2.4, because N+1=2K−1N+1=2^{K-1}. Writing Dσ=1+2hD_\sigma=1+2h gives Ds=1+4h+4h2≡1(mod4)D_s=1+4h+4h^2\equiv1\pmod4. A folded sequence has we=0w_e=0 for e<Ne<N, because its two halves are mirror images, and wN=1w_N=1, because its two middle signs differ. Hence every ss with Ds≡1(mod4)D_s\equiv1\pmod4 has w=(0,…,0,1)w=(0,\ldots,0,1), which means that ss is folded. □

Remark 3.3. The congruence places no condition on σ\sigma, so it has 2N2^N solutions. By Lemma 2.3, a solution satisfies Ds=1D_s=1 if and only if Dσ=1D_\sigma=1.

Proof of Theorems 1.1 and 2.2. By Lemma 2.1 it suffices to prove Theorem 2.2 and the count. Suppose Ds=1D_s=1. By Lemma 2.4, m=2K−1m=2^K-1 for some K≥1K\ge1. We show s∈FKs\in F_K by induction on KK. For K=1K=1, ss is empty. Let K≥2K\ge2. Since Ds≡1(mod4)D_s\equiv1\pmod4, Proposition 3.2 gives s=(σ,ε,−ε,rev⁡σ)s=(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma) with σ\sigma of length 2K−1−22^{K-1}-2. By Lemma 2.3, Dσ2=Ds=1D_\sigma^2=D_s=1, and since Dσ(0)=1D_\sigma(0)=1 this forces Dσ=1D_\sigma=1. By induction σ∈FK−1\sigma\in F_{K-1}, hence s∈FKs\in F_K.

Conversely, if s∈FKs \in F_K, then Ds=1D_s = 1 by Lemma 2.3 and induction; this is [5 Theorem 4.2]. The count follows from ∣FK∣=2K−1|F_K| = 2^{K-1}, because distinct vectors uu give distinct matrices Tm(u)T_m(u).

Example 3.4. For m=7m = 7 a folded sequence has Ds=(1+(s1+s2)x)2D_s = (1 + (s_1 + s_2)x)^2, by Lemma 2.3. Thus four of the eight folded sequences are nilpotent, namely those with s1=−s2s_1 = -s_2. For the others the congruence holds but the equation fails; for instance, s=(+,+,+,−,+,+)s = (+,+,+,-,+,+) has Ds=1+4x+4x2D_s = 1 + 4x + 4x^2.

Proof of Theorem 1.2. Apply Lemma 2.1 and Theorem 2.2 with sk=−akcks_k = -a_kc_k, and recall that FKF_K is closed under negation. The statement on AmbA_m^b is the case a=(1,…,1)a = (1,\ldots,1), c=bc = b.

Corollary 3.5. If Tm(u)T_m(u) is nilpotent, then each pair (u2j−1,u2j)(u_{2j-1},u_{2j}) is (1,i)(1,i) or (i,1)(i,1).

Proof. This follows by induction on KK, since σ\sigma has even length in (σ,ε,−ε,rev⁡σ)(\sigma,\varepsilon,-\varepsilon,\operatorname{rev}\sigma).

Remark 3.6. Deleting the first column and the last row of Jm(a,c)J_m(a,c) leaves a triangular matrix with the non-zero diagonal entries a1,…,am−1a_1,\ldots,a_{m-1}. Hence Jm(a,c)J_m(a,c) has rank at least m−1m-1, and a nilpotent Jm(a,c)J_m(a,c) consists of a single Jordan block.

The continued fraction of a nilpotent vector

All nilpotent matrices Tm(u)T_m(u) of a given dimension are similar (Remark 3.6). The (1,1)(1,1) entry of the resolvent distinguishes them: it is a polynomial in λ−1\lambda^{-1} with coefficients in {0,±1}\{0,\pm1\}, whose non-zero coefficients record the choices made in the recursion (Proposition 4.2 and Corollary 4.3). We compute it by means of a continued fraction.

Expanding at the first vertex instead of the last gives D1,m=D2,m+s1xD3,mD_{1,m} = D_{2,m} + s_1xD_{3,m}. By induction, the terminating continued fraction

11+s1x1+s2x1+⋱+sm−1x1\frac{1}{1+\cfrac{s_1x}{1+\cfrac{s_2x}{1+\ddots+\cfrac{s_{m-1}x}{1}}}}

equals D2,m/DsD_{2,m}/D_s. For a nilpotent vector the denominator is 11, so the continued fraction is the polynomial D2,m=Ds′D_{2,m} = D_{s'}, where s′s' is ss without its first sign. To determine it we use the following simple identity.

Lemma 4.1. For 2≤k≤m2 \le k \le m,

D1,kD2,k−1−D2,kD1,k−1=(−1)kxk−1∏e=1k−1se.D_{1,k}D_{2,k-1} - D_{2,k}D_{1,k-1} = (-1)^k x^{k-1}\prod_{e=1}^{k-1}s_e.

Proof. Let WkW_k denote the left side. By (4), W2=s1xW_2 = s_1x and Wk=−sk−1xWk−1W_k = -s_{k-1}xW_{k-1} for k≥3k \ge3.

Proposition 4.2. Let K≥2K \ge2 and s∈FKs \in F_K, and for 2≤j≤K2 \le j \le K let εj\varepsilon_j be the sign ε\varepsilon chosen in (3) at the step from Fj−1F_{j-1} to FjF_j in the construction of ss; thus εj=s2j−1−1\varepsilon_j = s_{2^{j-1}-1}. Then

Ds′=1−ε2x+∑j=3Kεjx2j−1−1.(7)D_{s'} = 1 - \varepsilon_2x + \sum_{j=3}^{K}\varepsilon_jx^{2^{j-1}-1}. \tag*{(7)}

In particular, s↦Ds′s \mapsto D_{s'} is a bijection from FKF_K onto the 2K−12^{K-1} polynomials 1+∑j=1K−1±x2j−1.1 + \sum_{j=1}^{K-1}\pm x^{2^j-1}.

Proof. For K=2K = 2 we have s=(ε2,−ε2)s = (\varepsilon_2,-\varepsilon_2) and Ds′=1−ε2xD_{s'} = 1 - \varepsilon_2x. Let K≥3K \ge3 and write s=(σ,εK,−εK,rev⁡σ)s = (\sigma,\varepsilon_K,-\varepsilon_K,\operatorname{rev}\sigma), where σ∈FK−1\sigma\in F_{K-1} has the signs ε2,…,εK−1\varepsilon_2,\ldots,\varepsilon_{K-1} and length N−1N-1 with N=2K−1−1N = 2^{K-1}-1. Let Da,bD_{a,b} refer to the path of ss. The path of s′s' has the vertices 2,…,2N+12,\ldots,2N+1 and the middle vertex c=N+1c = N+1. Its right part has matching polynomial Dσ=D1,N=1D_\sigma= D_{1,N} = 1 by Theorem 2.2, and without

its first vertex it has matching polynomial D1,N−1D_{1,N-1}, by reflection. Classifying the matchings by how cc is covered, as in Lemma 2.3, and applying Lemma 4.1 with k=Nk=N, which is odd, gives

Ds′=D2,N+εKx(D1,ND2,N−1−D2,ND1,N−1)=Dσ′−εKxN∏e=1N−1σe,D_{s}^{\prime}=D_{2,N}+\varepsilon_K x\left(D_{1,N}D_{2,N-1}-D_{2,N}D_{1,N-1}\right)=D_{\sigma^{\prime}}-\varepsilon_K x^N\prod_{e=1}^{N-1}\sigma_e,

where σ′\sigma^{\prime} is σ\sigma without its first sign. Since σ\sigma is folded, say σ=(τ,ε′,−ε′,rev⁡τ)\sigma=(\tau,\varepsilon^{\prime},-\varepsilon^{\prime},\operatorname{rev}\tau), we have ∏eσe=−(∏eτe)2=−1\prod_e\sigma_e=-\left(\prod_e\tau_e\right)^2=-1, so Ds′=Dσ′+εKxND_{s}^{\prime}=D_{\sigma^{\prime}}+\varepsilon_Kx^N, and (7) follows by induction on KK. Since ss is determined by ε2,…,εK\varepsilon_2,\ldots,\varepsilon_K, the map s↦Ds′s\mapsto D_s^{\prime} is a bijection.

Corollary 4.3. Let T=Tm(u)T=T_m(u) be nilpotent, with m=2K−1≥3m=2^K-1\ge3, and let εj\varepsilon_j be the signs of Proposition 4.2. Then

((λI−T)−1)11=λ−1−ε2λ−3+∑j=3Kεjλ−(2j−1).(8)\left((\lambda I-T)^{-1}\right)_{11}=\lambda^{-1}-\varepsilon_2\lambda^{-3}+\sum_{j=3}^{K}\varepsilon_j\lambda^{-(2j-1)}. \tag*{(8)}

so (Tk)11=0(T^k)_{11}=0 for every k≥0k\ge0 that is not of the form 2j−22^j-2 with 1≤j≤K1\le j\le K.

Proof. By Cramer’s rule and Lemma 2.1, applied to TT and to TT without its first row and column, ((λI−T)−1)11=λ−1Ds′(λ−2)\left((\lambda I-T)^{-1}\right)_{11}=\lambda^{-1}D_s^{\prime}(\lambda^{-2}), and (7) gives (8). The last claim follows by comparing coefficients in (λI−T)−1=∑k=0m−1Tkλ−k−1(\lambda I-T)^{-1}=\sum_{k=0}^{m-1}T^k\lambda^{-k-1}.

A doubling rule

By Corollary 3.5, a nilpotent sign sequence has the form (θ1,−θ1,…,θN,−θN)(\theta_1,-\theta_1,\ldots,\theta_N,-\theta_N). The next identity leads to a second recursive description of FKF_K, in which new signs are interleaved with old ones.

Proposition 5.1. Let N≥1N\ge1 and θ1,…,θN∈{±1}\theta_1,\ldots,\theta_N\in\{\pm1\}. Then

D(θ1,−θ1,θ2,−θ2,…,θN,−θN)(x)=D(θ1θ2,θ2θ3,…,θN−1θN)(x2).D_{(\theta_1,-\theta_1,\theta_2,-\theta_2,\ldots,\theta_N,-\theta_N)}(x)=D_{(\theta_1\theta_2,\theta_2\theta_3,\ldots,\theta_{N-1}\theta_N)}(x^2).

Proof. Let r=(θ1,−θ1,…,θN,−θN)r=(\theta_1,-\theta_1,\ldots,\theta_N,-\theta_N) and τ=(θ1θ2,…,θN−1θN)\tau=(\theta_1\theta_2,\ldots,\theta_{N-1}\theta_N), and put Qj=D1,2j+1Q_j=D_{1,2j+1}, where Da,bD_{a,b} refers to the path of rr. Then Q0=Q1=1Q_0=Q_1=1, and applying (4) three times gives, for 2≤j≤N2\le j\le N,

Qj=(1+(r2j−1+r2j)x)Qj−1−r2j−2r2j−1x2Qj−2=Qj−1+τj−1x2Qj−2,Q_j=(1+(r_{2j-1}+r_{2j})x)Q_{j-1}-r_{2j-2}r_{2j-1}x^2Q_{j-2}=Q_{j-1}+\tau_{j-1}x^2Q_{j-2},

because r2j−1+r2j=0r_{2j-1}+r_{2j}=0 and r2j−2r2j−1=−θj−1θjr_{2j-2}r_{2j-1}=-\theta_{j-1}\theta_j. This is the recurrence (4) for the path with the signs τ\tau, with xx replaced by x2x^2. Hence Dr(x)=QN(x)=Dτ(x2)D_r(x)=Q_N(x)=D_\tau(x^2).

Corollary 5.2. Let K≥2K\ge2 and N=2K−1−1N=2^{K-1}-1. For η=±1\eta=\pm1 and τ∈{±1}N−1\tau\in\{\pm1\}^{N-1} put

Φη(τ)=(θ1,−θ1,…,θN,−θN),θ1=η,θj+1=τjθj.\Phi_\eta(\tau)=(\theta_1,-\theta_1,\ldots,\theta_N,-\theta_N),\qquad\theta_1=\eta,\qquad\theta_{j+1}=\tau_j\theta_j.

Then (η,τ)↦Φη(τ)(\eta,\tau)\mapsto\Phi_\eta(\tau) is a bijection from {±1}×FK−1\{\pm1\}\times F_{K-1} onto FKF_K.

Proof. Since θjθj+1=τj\theta_j\theta_{j+1}=\tau_j, Proposition 5.1 gives DΦη(τ)(x)=Dτ(x2)D_{\Phi_\eta(\tau)}(x)=D_\tau(x^2), so by Theorem 2.2, Φη(τ)∈FK\Phi_\eta(\tau)\in F_K if and only if τ∈FK−1\tau\in F_{K-1}. By Corollary 3.5, every s∈FKs\in F_K is of the form Φη(τ)\Phi_\eta(\tau), where η=s1\eta=s_1 and τj=s2j−1s2j+1\tau_j=s_{2j-1}s_{2j+1} are determined by ss.

Remark 5.3. The sequence (2) is a fixed point of this rule in the following sense. Put b(K)=(c~2,…,c~2K−1)b^{(K)}=(\widetilde c_2,\ldots,\widetilde c_{2^K-1}) and θj=−c~2j\theta_j=-\widetilde c_{2j}. Then (2) gives −c~2j+1=−θj-\widetilde c_{2j+1}=-\theta_j, θ1=−1\theta_1=-1 and θjθj+1=−c~j+1\theta_j\theta_{j+1}=-\widetilde c_{j+1}, that is, −b(K)=Φ−1(−b(K−1))-b^{(K)}=\Phi_{-1}(-b^{(K-1)}) for K≥2K\ge2. By Proposition 5.1, D−b(K)(x)=D−b(K−1)(x2)=⋯=1D_{-b^{(K)}}(x)=D_{-b^{(K-1)}}(x^2)=\cdots=1, so Amb(K)A_m^{b^{(K)}} is nilpotent for m=2K−1m=2^K-1. This gives another proof of [4 Lemma 30].

Remark 5.4. In terms of matrices, Proposition 5.1 reflects the fact that, with rr and τ\tau as in its proof, the square of A2N+1−rA_{2N+1}^{-r} maps the span of the even-numbered basis vectors into itself and acts on it as AN−τA_N^{-\tau}. This is the finite counterpart of [4 Lemma 5], from which Chandler-Wilde and Davies deduce that the spectrum SS of the Feinberg–Zee hopping matrix is closed under taking square roots: if λ∈S\lambda\in S, then ±λ∈S\pm\sqrt{\lambda}\in S. The maps Φ±1\Phi_{\pm1} correspond to their maps Γ±\Gamma_\pm.

Formal verification and computations

We have formalised the proof of Theorem 1.1 in Lean 4 [7], version 4.36.0, using the Mathlib library [12]. The formalisation follows § 2 and § 3 and has about 1,150 lines. The matrix Tm(u)T_m(u), with rows and columns indexed from 0, is defined by

def T (m : ℕ) (u : ℕ → ℂ) : Matrix (Fin m) (Fin m) ℂ :=
  fun i j => if (j : ℕ) = i + 1 then u i else if (i : ℕ) = j + 1 then -u j else 0

and the vectors of Theorem 1.1 by the inductive predicate

inductive CorlessVec : ℕ → List ℂ → Prop
  | base : CorlessVec 0 []
  | step1 {k : ℕ} {u : List ℂ} :
      CorlessVec k u → CorlessVec (k + 1) (u ++ [1, Complex.I] ++ u.reverse)
  | step2 {k : ℕ} {u : List ℂ} :
      CorlessVec k u → CorlessVec (k + 1) (u ++ [Complex.I, 1] ++ u.reverse)

in which the index kk corresponds to K−1K - 1. The formal statements of Theorem 1.1 are

theorem corless_conjecture {u : List ℂ} (hu : ∀ x ∈ u, x = 1 ∨ x = Complex.I) :
    IsNilpotent (T (u.length + 1) (fun i => u.getD i 1)) ↔ ∃ k, CorlessVec k u

theorem card_nilpotent (k : ℕ) :
    {u : List ℂ | u.length = 2 ^ (k + 1) - 2 ∧ (∀ x ∈ u, x = 1 ∨ x = Complex.I) ∧
    IsNilpotent (T (u.length + 1) (fun i => u.getD i 1))}.ncard = 2 ^ k

The first of them includes the restriction on the dimension, since every vector satisfying CorlessVec kk has length 2k+1−22^{k+1} - 2. Both theorems depend only on the three standard axioms of Lean (propext, Classical.choice and Quot.sound). Theorem 1.2 and § 4 and § 5 have not been formalised.

As an independent check, we have verified the case m=63m = 63 of Theorem 1.1 by an exhaustive search. Every nilpotent sign sequence satisfies Ds≡1(mod4)D_s \equiv1 \pmod{4} and therefore solves the linear system (6), which has rank 31 for m=63m = 63. This leaves 2312^{31} of the 2622^{62} sign sequences. For each of them we evaluated DsD_s at two points modulo the prime 261−12^{61} - 1, and we recomputed DsD_s exactly whenever both values were equal to 1. Exactly 32 sequences have Ds=1D_s = 1, namely the members of F6F_6. The search takes about 20 seconds on 14 processor cores. We have also verified Theorem 1.2 for m≤9m \le9, and the results of § 4 and § 5 for K≤8K \le8, by exact computation. The formalisation and the programs are available at https://github.com/marcelbtec/corless-nilpotent and are archived at [1].

Concluding remarks

Theorem 1.2 with a=ua = u and c=−uc = -u covers the population {1,−1,i,−i}\{1, -1, i, -i\}: since each sign sequence comes from 2m−12^{m-1} vectors uu, there are 2K−1⋅2m−12^{K-1} \cdot2^{m-1} nilpotent matrices of dimension m=2K−1m = 2^K - 1. If 0 is admitted as an entry as well, the zero entries divide uu into (possibly empty) blocks vv, the matrix Tm(u)T_m(u) is the direct sum of the corresponding matrices T∣v∣+1(v)T_{|v|+1}(v), where ∣v∣|v| is the length of vv, and it is nilpotent if and only if each of them is.

By Lemma 2.1, the multiplicity of the eigenvalue 0 of Tm(u)T_m(u) is m−2deg⁡Dsm - 2 \deg D_s. Corless observed that for m=15m = 15 the multiplicities 3, 5, 7, 11, 13 and 15 occur, but 9 does not [5 Section 5]; in other words, deg⁡Ds≠3\deg D_s \ne3 for all s∈{±1}14s \in\{\pm1\}^{14}. It would be interesting to determine the degrees that DsD_s can have for general mm. Theorem 2.2 settles the case deg⁡Ds=0\deg D_s = 0, and conditions of the form deg⁡Ds≤d\deg D_s \le d might be accessible by the 2-adic method used here.

Acknowledgements

This work grew out of the paper [5] of R. M. Corless, which poses the problem and contains several ingredients of its solution.

Collaboration with an AI system

This paper is the result of a collaboration between the author and the AI system Claude (Anthropic; principally Opus 5.5 and Fable 5.2). The system wrote the Lean formalisation and the programs of § 6; the author contributed the sketch for the proof of Theorem 1.1, Theorem 1.2 and the results of § 4 and § 5 and wrote the second version of the paper, which the system checked and both revised. The author has checked all arguments and takes full responsibility for the paper.

Applied AI Research Lab, Lucerne University of Applied Sciences and Arts, Suurstoffi 1, 6343 Rotkreuz, Switzerland

Email address: [email protected]

URL: https://orcid.org/0009-0001-7188-673X

References

  1. [1]M. Blattner, Corless’s nilpotent conjecture: proof, Lean formalisation and computations, version 1.1.0, Zenodo, 2026. https://doi.org/10.5281/zenodo.24317787.
  2. [2]S. N. Chandler-Wilde, R. Chonchaya and M. Lindner, Eigenvalue problem meets Sierpinski triangle: computing the spectrum of a non-self-adjoint random operator, Operators and Matrices 5 (2011), no. 4, 633–648. https://doi.org/10.7153/oam-05-46.
  3. [3]S. N. Chandler-Wilde, R. Chonchaya and M. Lindner, On the spectra and pseudospectra of a class of non-self-adjoint random matrices and operators, Operators and Matrices 7 (2013), no. 4, 739–775. https://doi.org/10.7153/oam-07-43.
  4. [4]S. N. Chandler-Wilde and E. B. Davies, Spectrum of a Feinberg–Zee random hopping matrix, Journal of Spectral Theory 2 (2012), no. 2, 147–179. https://doi.org/10.4171/JST/25; arXiv:1110.0792.
  5. [5]R. M. Corless, Skew-symmetric tridiagonal Bohemian matrices, Maple Transactions 1 (2021), no. 2, Article 14360. https://doi.org/10.5206/mt.v12i2.14360.
  6. [6]R. M. Corless, G. Labahn, D. Piponi and L. Rafiee Sevyeri, Bohemian matrix geometry, in: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC 2022), ACM, 2022, 361–370. https://doi.org/10.1145/3476446.3536177; arXiv:2202.07769.
  7. [7]L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in: Automated Deduction – CADE 28, Lecture Notes in Computer Science 12699, Springer, 2021, 625–635. https://doi.org/10.1007/978-3-030-79876-5_37.
  8. [8]J. Feinberg and A. Zee, Non-Hermitian localization and delocalization, Physical Review E 59 (1999), no. 6, 6433–6443. https://doi.org/10.1103/PhysRevE.59.6433.
  9. [9]R. Hagger, Symmetric Feinberg–Zee random hopping matrix, Random Matrices: Theory and Applications 4 (2015), no. 4, 1550016. https://doi.org/10.1142/S2010326315500161.
  10. [10]R. Hagger, The eigenvalues of tridiagonal sign matrices are dense in the spectra of periodic tridiagonal sign operators, Journal of Functional Analysis 269 (2015), no. 5, 1563–1570. https://doi.org/10.1016/j.jfa.2015.01.019; arXiv:1412.1724.
  11. [11]V. E. Hoggatt, Jr. and M. Bicknell, Roots of Fibonacci polynomials, Fibonacci Quarterly 11 (1973), no. 3, 271–274. https://doi.org/10.1080/00150517.1973.12430825.
  12. [12]The mathlib Community, The Lean mathematical library, in: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, 367–381. https://doi.org/10.1145/3372885.3373824.

Paper details

vlnc:W_92ct9499
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents