Characteristic polynomials of { ± 1 } \{\pm 1\} -matrices modulo a power of 2 2

Gary Greaves, Huu An Phan · 2025

Read Characteristic polynomials of { ± 1 } \{\pm 1\} -matrices modulo a power of 2 2 by Gary Greaves, Huu An Phan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08333.txt.

Introduction

Gary Greaves and Huu An Phan count congruence classes of characteristic polynomials for matrices whose entries are plus or minus one, taken modulo a power of two. The matrices are symmetric or skew symmetric with constant diagonal, and the exponent is at least three with size large enough. Their symmetric count resolves a conjecture posed by Greaves and Yatsyna in 2019, with the answer depending on whether the matrix size is even or odd.

Matching formulas are proved for the skew symmetric case as well. The main new tool is the lift graph or lift tournament, built for this problem. A walk polynomial for graphs supports the construction, showing the needed lift tournaments actually exist for the required sizes.

Catalog record

CREATORGary Greaves, Huu An Phan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-08333

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characteristic polynomials of { ± 1 } \{\pm 1\} -matrices modulo a power of 2 2 Gary Greaves, Huu An Phan Abstract For a fixed integer e ⩾ 3 e\geqslant 3 and n n large enough, we show that the number of congruence classes modulo 2 e 2^{e} of characteristic polynomials of n × n n\times n symmetric { ± 1 } \{\pm 1\} -matrices with constant diagonal is equal to { 2 ( e − 2 2 ) , if n is even ; 2 ( e − 2 2 ) + 1 , if n is odd , \begin{cases}2^{\binom{e-2}{2}},&\text{ if $n$ is even};\\ 2^{\binom{e-2}{2}+1},&\text{ if $n$ is odd},\end{cases} thereby solving a conjecture of Greaves and Yatsyna from 2019. We also show that, for n n large enough, the number of congruence classes modulo 2 e 2^{e} of characteristic polynomials of n × n n\times n skew-symmetric { ± 1 } \{\pm 1\} -matrices with constant diagonal is equal to { 2 ⌊ e − 1 2 ⌋ ​ ⌊ e − 2 2 ⌋ , if n is even ; 2 ⌊ e − 2 2 ⌋ ​ ⌊ e − 3 2 ⌋ , if n is odd . \begin{cases}2^{\lfloor\frac{e-1}{2}\rfloor\lfloor\frac{e-2}{2}\rfloor},&\text{ if $n$ is even};\\ 2^{\lfloor\frac{e-2}{2}\rfloor\lfloor\frac{e-3}{2}\rfloor},&\text{ if $n$ is odd}.\end{cases} We introduce the concept of a lift graph/tournament , which serves as our main tool. We also introduce the notion of the walk polynomial of a graph, which enables us to show the existence of the requisite lift tournaments. 1 Introduction A fundamental problem in discrete random matrix theory is to understand the arithmetic and algebraic properties of random \{\pm 1\} -matrices. Tikhomirov [ 12 ] proved that the probability that a random \{\pm 1\} -matrix of order n is singular tends to 2^{-n} as n\to\infty . Eberhard [ 3 ] established that the characteristic polynomial of a random \{\pm 1\} -matrix is irreducible with high probability, using reductions modulo a prime p as a key ingredient. In this paper we consider the corresponding reduction modulo powers of 2 . Characteristic polynomials of \{\pm 1\} -matrices also arise naturally in combinatorial matrix theory, notably in the study of equiangular lines [ 5 , 6 , 7 , 8 ] . Let \mathsf{S}_{n}=\{\,M\in\textsf{Mat}_{n}(\{\pm 1\}):M^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}=M,\;[M]_{i,i}=1\ \text{for all }i\,\}, so that \mathsf{S}_{n} is the set of symmetric \{\pm 1\} -matrices with all diagonal entries equal to 1 . The determinant of any \{\pm 1\} -matrix of order n is divisible by 2^{n-1} . Greaves and Yatsyna [ 8 ] strengthened this observation as follows. Theorem 1.1 (Greaves–Yatsyna [ 8 ] ) . Let e\geqslant 3 . Then for all n\in\mathbb{N} , \left|\{\,\det(xI-S)\bmod 2^{e}:S\in\mathsf{S}_{n}\,\}\right|\leqslant\begin{cases}2^{\binom{e-2}{2}},&\text{if $n$ is even},\\[3.0pt] 2^{\binom{e-2}{2}+1},&\text{if $n$ is odd}.\end{cases} They conjectured [ 8 , Page 5 and Page 9] that this bound is sharp for every fixed e\geqslant 3 1 1 1 It was, in fact, conjectured for all e\in\mathbb{N} , however, when e\leqslant 2 , the cardinality of \mathcal{C}_{e}(\mathsf{S}_{n}) is just 1 for all n . and all sufficiently large n . Our first main result confirms this conjecture (Theorem 1.3 ). Analogous behaviour is observed for skew-symmetric matrices. Klanderman et al. [ 10 ] studied Seidel matrices of tournaments, i.e., skew-symmetric \{0,\pm 1\} -matrices with nonzero off-diagonal entries, and computed their characteristic polynomial coefficients. Their congruence patterns modulo powers of 2 mirror those of the symmetric case, leading naturally to a parallel investigation for skew-symmetric \{\pm 1\} -matrices. Our corresponding result is Theorem 1.4 . 1.1 Main definitions and results For a\in\mathbb{Z} and e\in\mathbb{N} , write \overline{a}^{(e)} for the residue class of a modulo 2^{e} . Given \mathsf{M}_{n}\subseteq\textsf{Mat}_{n}(\mathbb{Z}) , define \mathcal{C}_{e}(\mathsf{M}_{n})=\left\{\left(\overline{a_{2}}^{(e)},\overline{a_{3}}^{(e)},\dots,\overline{a_{e}}^{(e)}\right):\det(xI-M)=\sum_{i=0}^{n}a_{i}x^{n-i}\text{ for some }M\in\mathsf{M}_{n}\right\}. Let \mathsf{U}_{n} be the set of \{\pm 1\} -matrices with all diagonal entries equal to 1 . We call M\in\mathsf{U}_{n} skew-symmetric if (M-I)^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}=-(M-I) , and write \mathsf{S}_{n} and \mathsf{T}_{n} for the symmetric and skew-symmetric subsets of \mathsf{U}_{n} , respectively. Theorem 1.2 . For each e\in\mathbb{N} there exists N such that for all n>N , \mathcal{C}_{e}(\mathsf{U}_{n})=\left\{\,\left(\overline{a_{2}}^{(e)},\overline{a_{3}}^{(e)},\dots,\overline{a_{e}}^{(e)}\right):a_{i}\in\mathbb{Z}\text{ and }2^{i-1}\text{ divides }a_{i}\text{ for each }i=2,\dots,e\,\right\}. Theorem 1.2 is proved as a warm-up result in Section 3.1 . Theorem 1.3 . Let e\geqslant 3 . Then there exists N such that for all n>N , |\mathcal{C}_{e}(\mathsf{S}_{n})|=\begin{cases}2^{\binom{e-2}{2}},&\text{if $n$ is even},\\[3.0pt] 2^{\binom{e-2}{2}+1},&\text{if $n$ is odd}.\end{cases} The proof of Theorem 1.3 consists of Theorem 5.4 (for n odd) and Theorem 5.7 (for n even). Theorem 1.4 . Let e\geqslant 3 . Then there exists N such that for all n>N , |\mathcal{C}_{e}(\mathsf{T}_{n})|=\begin{cases}2^{\lfloor\frac{e-1}{2}\rfloor\lfloor\frac{e-2}{2}\rfloor},&\text{if $n$ is even},\\[3.0pt] 2^{\lfloor\frac{e-2}{2}\rfloor\lfloor\frac{e-3}{2}\rfloor},&\text{if $n$ is odd}.\end{cases} The proof of Theorem 1.4 consists of Theorem 7.5 (for n odd) and Theorem 7.8 (for n even). 1.2 Outline of the proofs Our arguments are elementary, relying on relations between elementary-symmetric and power-sum polynomials together with combinatorial constructions involving paths, cycles, and almost-transitive tournaments. A central tool is the notion of a lift graph , introduced in Section 3.2 . For the symmetric case, the relevant lift graphs can be constructed explicitly from unions of paths and cycles. The skew-symmetric case requires a non-explicit construction based on joins of 1 -almost transitive tournaments in the sense of [ 4 ] . We introduce the walk polynomial in Section 6.3 , which facilitates the verification of the required congruence conditions for the existence of the relevant lift tournaments. Our results determine, for each fixed e , the precise number of distinct congruence classes of characteristic polynomials of natural families of \{\pm 1\} -matrices for sufficiently large n . Our bounds on the minimal such n are recursive and, based on empirical evidence, far from optimal. We leave the problem of optimising these bounds as an avenue for further research. 1.3 Organisation In Section 2 , we outline preliminary definitions and results. In Section 3 , we prove Theorem 1.2 and motivate the notion of a lift graph, which is fundamental to our approach towards the proofs of Theorem 1.3 and Theorem 1.4 . Lift graphs are defined in Section 4 together with constructions of lift graphs of type I and type II. These constructions are explicit and consist of path and cycle graphs. Our proof of Theorem 1.3 is presented in Section 5 . Lift tournaments are defined in Section 6 together with constructions of lift tournaments of type I and type II. In contrast to lift graphs, our constructions of lift tournaments are not explicit and depend on a solution to a Vandermonde-type equation and corresponding joins of almost-transitive tournaments. Finally, our proof of Theorem 1.4 is presented in Section 7 . Acknowledgements. GG was supported by the Singapore Ministry of Education Academic Research Fund; grant numbers: RG14/24 (Tier 1) and MOE-T2EP20222-0005 (Tier 2). 2 Preliminaries Let p(x)=c_{0}\prod_{i=1}^{n}(x-\theta_{i})\in\mathbb{Q}[x] be a polynomial. Denote by \mathsf{c}_{k}(p) for the coefficient of x^{n-k} in p(x) . For k\in\{0,\dots,n\} , we define the corresponding elementary symmetric polynomial and the power sum polynomial in the zeros of p(x) as \mathsf{e}_{k}(p):=\sum_{1\leqslant i_{1}<i_{2}<\cdots<i_{k}\leqslant\deg p}\theta_{i_{1}}\theta_{i_{2}}\cdots\theta_{i_{k}}\quad\text{ and }\quad\mathsf{p}_{k}(p):=\sum^{\deg p}_{i=1}\theta_{i}^{k}. It follows from these definitions and from Newton’s identities that \mathsf{e}_{k}(p)=(-1)^{k}\mathsf{c}_{k}(p)/\mathsf{c}_{0}(p) and \mathsf{p}_{k}(p)=-\frac{1}{\mathsf{c}_{0}(p)}\left(\sum_{i=1}^{k-1}\mathsf{c}_{i}(p)\mathsf{p}_{k-i}(p)+k\mathsf{c}_{k}(p)\right). (1) We further remark here that, for polynomials p(x) and q(x) we have \mathsf{p}_{k}(p\cdot q)=\mathsf{p}_{k}(p)+\mathsf{p}_{k}(q). (2) For a nonzero integer a , the 2 -adic valuation \nu_{2}(a) of a is the multiplicity of 2 in the prime factorisation of

Read the complete text