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

Abstract

For a fixed integer $e⩾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^{\left(\genfrac{}{}{0ex}{}{e-2}{2}\right)}$ if $n$ is even or $2^{\left(\genfrac{}{}{0ex}{}{e-2}{2}\right)+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.

27 pages