Characteristic polynomials of $\{\pm 1\}$-matrices modulo a power of $2$
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912702180360192 |
|---|---|
| author | Greaves, Gary Phan, Huu An |
| author_facet | Greaves, Gary Phan, Huu An |
| contents | For a fixed integer $e \geqslant 3$ and $n$ large enough, we show that the number of congruence classes modulo $2^e$ of characteristic polynomials of $n \times n$ symmetric $\{\pm 1\}$-matrices with constant diagonal is equal to $2^{\binom{e-2}{2}}$ if $n$ is even or $2^{\binom{e-2}{2}+1}$ if $n$ is odd, thereby solving a conjecture of Greaves and Yatsyna from 2019. We also show that, for $n$ large enough, the number of congruence classes modulo $2^e$ of characteristic polynomials of $n \times n$ skew-symmetric $\{\pm 1\}$-matrices with constant diagonal is equal to $2^{\lfloor \frac{e-1}{2} \rfloor\lfloor \frac{e-2}{2} \rfloor}$ if $n$ is even or $2^{\lfloor \frac{e-2}{2} \rfloor\lfloor \frac{e-3}{2} \rfloor}$ if $n$ is odd. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08333 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Characteristic polynomials of $\{\pm 1\}$-matrices modulo a power of $2$ Greaves, Gary Phan, Huu An Combinatorics For a fixed integer $e \geqslant 3$ and $n$ large enough, we show that the number of congruence classes modulo $2^e$ of characteristic polynomials of $n \times n$ symmetric $\{\pm 1\}$-matrices with constant diagonal is equal to $2^{\binom{e-2}{2}}$ if $n$ is even or $2^{\binom{e-2}{2}+1}$ if $n$ is odd, thereby solving a conjecture of Greaves and Yatsyna from 2019. We also show that, for $n$ large enough, the number of congruence classes modulo $2^e$ of characteristic polynomials of $n \times n$ skew-symmetric $\{\pm 1\}$-matrices with constant diagonal is equal to $2^{\lfloor \frac{e-1}{2} \rfloor\lfloor \frac{e-2}{2} \rfloor}$ if $n$ is even or $2^{\lfloor \frac{e-2}{2} \rfloor\lfloor \frac{e-3}{2} \rfloor}$ if $n$ is odd. 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. |
| title | Characteristic polynomials of $\{\pm 1\}$-matrices modulo a power of $2$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.08333 |