WorksMathematics
Nilpotent skew-symmetric tridiagonal Bohemian matrices: a proof of Corless's conjecture
Abstract
Corless studied the skew-symmetric tridiagonal matrices with superdiagonal . He showed that can be nilpotent only if and that the vectors 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 gives a necessary condition for nilpotency that is linear over \F. For 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 . Since 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 entry of the resolvent of a nilpotent is , with signs that determine . 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 :
Here skew-symmetric means , 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 , where is the unit roundoff, and these values produce conspicuous artefacts in plots of the eigenvalues of the whole family [5 Section 3]. A nilpotent consists of a single Jordan block (Remark 3.6); Corless calls such matrices coreless.
Corless proved that can be nilpotent only if for some [5 Theorem 4.1], and that the vectors obtained from the empty vector by repeated application of
give nilpotent matrices [5 Theorem 4.2]; here denotes reversed. This construction yields nilpotent matrices of dimension . He conjectured that there are no others [5 Conjecture 5.1] and verified this by exhaustive computation for .
Theorem 1.1. Let and . Then is nilpotent if and only if for some and is obtained from the empty vector by repeated application of (1). In particular, there are exactly nilpotent matrices of dimension , and none of any other dimension.
For the nilpotent vectors are and ; Figure 1 shows the 16 vectors for .
Figure 1. The 16 nilpotent vectors for , one per row; blue cells are 1, orange cells are . 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 . The characteristic polynomial of is , where is the matching polynomial of the path with vertices and edge weights ; see [5 Propositions 2.1 and 2.9]. Thus is nilpotent if and only if , which is a system of polynomial equations of degrees in the signs. Call a sign sequence folded if it has the form with ; the rule (1) produces such sequences. Folded sequences satisfy the identity (Lemma 2.3), which is implicit in the proof of [5 Theorem 4.2]. Hence a folded sequence satisfies if and only if , and the theorem follows by induction once we know that every nonempty with is folded.
To prove this we study the equation modulo 2 and modulo 4. Modulo 2 the signs disappear, and one obtains the restriction on the dimension. Modulo 4 they enter linearly: if with , then . In other words, modulo 4 the map coincides with its first-order Taylor expansion at , with the element 2 of in the role of an infinitesimal of square zero. The condition is therefore a linear system over in the unknowns . By the reflection symmetry of the path, the edges and have the same coefficient polynomial, so the system involves only the sums in . 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 , for which the equations are no longer linear, are not needed.
Tridiagonal sign matrices
The matrices also occur, in a different normalisation, in the spectral theory of non-self-adjoint operators. For let be the tridiagonal matrix with zero diagonal, superdiagonal and subdiagonal , so that . For put . 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 on the two off-diagonals is diagonally similar to one of them. So is , with (Lemma 2.1), and Theorem 1.1 therefore classifies the nilpotent tridiagonal sign matrices as well. To state the result in this setting, let be the set of sign sequences obtained from the empty sequence by applications of with ; under these are the vectors of Theorem 1.1.
Theorem 1.2. Let and let satisfy for all . Then is nilpotent if and only if for some and . In particular, a tridiagonal sign matrix is nilpotent if and only if for some and .
Some nilpotent tridiagonal sign matrices are implicit in this literature. Chandler-Wilde, Chonchaiya and Lindner [2] introduced the sign sequence
(we use the notation of [4]) and showed that the characteristic polynomials of the finite sections with have all their coefficients in . Chandler-Wilde and Davies showed that for these polynomials are monomials [4 Lemma 30], so that the corresponding matrices are nilpotent. Together with the symmetries [3 Lemma 3.4] and , this accounts for four of the nilpotent tridiagonal sign matrices of dimension . 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 is nilpotent, then the terminating continued fraction with partial numerators is a lacunary polynomial , whose signs are the choices made in the recursion. Equivalently, the entry of the resolvent of is . 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 are described in Section 6.
Matching polynomials
Throughout, , so if and if . Since is determined by , we identify a vector with its sign sequence . Corless’s rule (1) becomes
so the vectors of Theorem 1.1 correspond to the sequences in , which have length . Since and can be read off , we have , and is closed under , by induction on .
Let be the path with the vertices , in which the edge joins and (). For let
where runs through the matchings of , that is, the sets of pairwise disjoint edges, including the empty set. For we obtain the Fibonacci polynomials . More generally, for let be the matching polynomial of the subpath with the vertices and the signs . Thus , and if the subpath has at most one vertex. Distinguishing whether or not the last vertex is matched, we obtain
Lemma 2.1. Let with for all .
(i) Put . Then . In particular, is nilpotent if and only if .
(ii) Put , and let be the diagonal matrix with the entries and . Then .
Proof. The characteristic polynomials of the leading blocks of satisfy with and (cf. [5 Proposition 2.1]). By (4), so do the polynomials . This proves (i), and (ii) is verified entrywise. □
For the lemma gives and . We call a vector , and its sign sequence , nilpotent if is nilpotent, that is, if . Theorem 1.1 is equivalent to the following statement.
Theorem 2.2. Let and . Then if and only if and .
The rule (3) is explained by the following identity.
Lemma 2.3. Let and , and put . Then .
Proof. Deleting the middle vertex of the path of leaves two paths that are mirror images of each other, each with matching polynomial . Let 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
For the matrices 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 and .
(i) (mod 2).
(ii) In we have for all .
(iii) (mod 2) if and only if is a power of 2. In particular, if , then for some .
Proof. (i) holds because every is odd. For (ii), both sides are equal to 1 for and , and both satisfy the recurrence : the left side by (4), the right side because and are the roots of over . For (iii), note that the substitution is injective on . By (ii), (mod 2) if and only if in . This holds if is a power of 2. If with odd, then contains the term , and . 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 let . Deleting the endpoints of edge leaves paths with and vertices, so , the sum over the matchings of that contain . Write with . Since for every matching , summing over gives
Clearly , and for odd these are the only linear relations among the modulo 2:
Lemma 3.1. Let . The reductions of modulo 2 are linearly independent over .
Proof. Suppose for some nonempty . Since is a domain, . Substituting and using Lemma 2.4,
where has constant term 1, and . For we have , so the lowest-degree term of is . Comparing constant terms in shows that is even, hence . But the coefficient of in this sum is 1, because every other has lowest-degree term of higher degree. This is a contradiction. □
Proposition 3.2. Let with , and let . Then if and only if is folded, that is, for some and . Equivalently, , and for .
Proof. By Lemma 2.4, for some . By (5), is equivalent to
The pairs with partition , and . So the left side of (6) equals with . By Lemma 3.1, at most one vector satisfies (6).
Folded sequences satisfy the congruence. Indeed, if , then by Lemma 2.3, and by Lemma 2.4, because . Writing gives . A folded sequence has for , because its two halves are mirror images, and , because its two middle signs differ. Hence every with has , which means that is folded. □
Remark 3.3. The congruence places no condition on , so it has solutions. By Lemma 2.3, a solution satisfies if and only if .
Proof of Theorems 1.1 and 2.2. By Lemma 2.1 it suffices to prove Theorem 2.2 and the count. Suppose . By Lemma 2.4, for some . We show by induction on . For , is empty. Let . Since , Proposition 3.2 gives with of length . By Lemma 2.3, , and since this forces . By induction , hence .
Conversely, if , then by Lemma 2.3 and induction; this is [5 Theorem 4.2]. The count follows from , because distinct vectors give distinct matrices .
Example 3.4. For a folded sequence has , by Lemma 2.3. Thus four of the eight folded sequences are nilpotent, namely those with . For the others the congruence holds but the equation fails; for instance, has .
Proof of Theorem 1.2. Apply Lemma 2.1 and Theorem 2.2 with , and recall that is closed under negation. The statement on is the case , .
Corollary 3.5. If is nilpotent, then each pair is or .
Proof. This follows by induction on , since has even length in .
Remark 3.6. Deleting the first column and the last row of leaves a triangular matrix with the non-zero diagonal entries . Hence has rank at least , and a nilpotent consists of a single Jordan block.
The continued fraction of a nilpotent vector
All nilpotent matrices of a given dimension are similar (Remark 3.6). The entry of the resolvent distinguishes them: it is a polynomial in with coefficients in , 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 . By induction, the terminating continued fraction
equals . For a nilpotent vector the denominator is , so the continued fraction is the polynomial , where is without its first sign. To determine it we use the following simple identity.
Lemma 4.1. For ,
Proof. Let denote the left side. By (4), and for .
Proposition 4.2. Let and , and for let be the sign chosen in (3) at the step from to in the construction of ; thus . Then
In particular, is a bijection from onto the polynomials
Proof. For we have and . Let and write , where has the signs and length with . Let refer to the path of . The path of has the vertices and the middle vertex . Its right part has matching polynomial by Theorem 2.2, and without
its first vertex it has matching polynomial , by reflection. Classifying the matchings by how is covered, as in Lemma 2.3, and applying Lemma 4.1 with , which is odd, gives
where is without its first sign. Since is folded, say , we have , so , and (7) follows by induction on . Since is determined by , the map is a bijection.
Corollary 4.3. Let be nilpotent, with , and let be the signs of Proposition 4.2. Then
so for every that is not of the form with .
Proof. By Cramer’s rule and Lemma 2.1, applied to and to without its first row and column, , and (7) gives (8). The last claim follows by comparing coefficients in .
A doubling rule
By Corollary 3.5, a nilpotent sign sequence has the form . The next identity leads to a second recursive description of , in which new signs are interleaved with old ones.
Proposition 5.1. Let and . Then
Proof. Let and , and put , where refers to the path of . Then , and applying (4) three times gives, for ,
because and . This is the recurrence (4) for the path with the signs , with replaced by . Hence .
Corollary 5.2. Let and . For and put
Then is a bijection from onto .
Proof. Since , Proposition 5.1 gives , so by Theorem 2.2, if and only if . By Corollary 3.5, every is of the form , where and are determined by .
Remark 5.3. The sequence (2) is a fixed point of this rule in the following sense. Put and . Then (2) gives , and , that is, for . By Proposition 5.1, , so is nilpotent for . This gives another proof of [4 Lemma 30].
Remark 5.4. In terms of matrices, Proposition 5.1 reflects the fact that, with and as in its proof, the square of maps the span of the even-numbered basis vectors into itself and acts on it as . This is the finite counterpart of [4 Lemma 5], from which Chandler-Wilde and Davies deduce that the spectrum of the Feinberg–Zee hopping matrix is closed under taking square roots: if , then . The maps correspond to their maps .
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 , 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 corresponds to . 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 has length . 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 of Theorem 1.1 by an exhaustive search. Every nilpotent sign sequence satisfies and therefore solves the linear system (6), which has rank 31 for . This leaves of the sign sequences. For each of them we evaluated at two points modulo the prime , and we recomputed exactly whenever both values were equal to 1. Exactly 32 sequences have , namely the members of . The search takes about 20 seconds on 14 processor cores. We have also verified Theorem 1.2 for , and the results of § 4 and § 5 for , 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 and covers the population : since each sign sequence comes from vectors , there are nilpotent matrices of dimension . If 0 is admitted as an entry as well, the zero entries divide into (possibly empty) blocks , the matrix is the direct sum of the corresponding matrices , where is the length of , and it is nilpotent if and only if each of them is.
By Lemma 2.1, the multiplicity of the eigenvalue 0 of is . Corless observed that for the multiplicities 3, 5, 7, 11, 13 and 15 occur, but 9 does not [5 Section 5]; in other words, for all . It would be interesting to determine the degrees that can have for general . Theorem 2.2 settles the case , and conditions of the form 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]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]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]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]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]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]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]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]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]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]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]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]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.
