Counting (0,1)-matrices with a given characteristic polynomial

Question

Let $f_n\colon \{0,1\}^{n-1} \to \mathbb{N}$ be a function where $f_n(c_{n-1}, c_{n-2}, \dots, c_1)$ is the number of $n\times n$ matrices with coefficients in $\{0,1\}$ whose characteristic polynomial is $$x^n - c_{n-1} x^{n-1} - c_{n-2} x^{n-2} - \dots - c_2 x^2 - c_1 x - 1.$$

For all of the values of that I have checked ($n \leq 4$), it appears that $f_n(\vec{c}) = 2^a3^b$.

Does it hold in general that $$f_n(c_{n-1}, c_{n-2},\dots,c_2,c_1) = 2^{k_1} 3^{k_2} 5^{k_3} \cdots p_n^{k_n},$$ $k_j$ are integers and where $p_n$ is the greatest prime less than $n$? Is there a way of computing $f_n$ efficiently?

---

Supporting Data

Case $n = 1$:

$$ f_1() = 2^0 \cdot 3^0 = 1. $$

Case $n = 2$:

$$ f_2(0) = 2^0 \cdot 3^0 = 1.\\ f_2(1) = 2^1 \cdot 3^0 = 2. $$

Case $n = 3$:

$$ f_3(0,0) = 2^1 \cdot 3^0 = 2\\ f_3(0,1) = 2^1 \cdot 3^1 = 6\\ f_3(1,0) = 2^1 \cdot 3^1 = 6\\ f_3(1,1) = 2^2 \cdot 3^1 = 12. $$

Case $n = 4$:

$$ f_4(0,0,0) = 2^1 \cdot 3^1 = 6\\ f_4(0,0,1) = 2^3 \cdot 3^1 = 24\\ f_4(0,1,0) = 2^3 \cdot 3^1 = 24\\ f_4(0,1,1) = 2^5 \cdot 3^1 = 96\\ f_4(1,0,0) = 2^3 \cdot 3^1 = 24\\ f_4(1,0,1) = 2^3 \cdot 3^2 = 72\\ f_4(1,1,0) = 2^6 \cdot 3^1 = 192\\ f_4(1,1,1) = 2^6 \cdot 3^1 = 192. $$

---

Note that this does not seem to hold when our characteristic polynomial does not end with $-1$. For example, there are $2004 = 2^2\cdot 3 \cdot 167$ matrices of size $4 \times 4$ with coefficients in $\{0,1\}$ and characteristic polynomial $x^4-x^3-x^2$.

Answer 1

I've written some Sage code to compute this by unsophisticated brute force (I'm sure there are other languages that could have been faster, or probably functions within Sage that would be faster - I know more about Python than Sage.) If my code is correct then the pattern fails unceremoniously at $n = 5$. Here is my code:

import itertools, collections
def process(n):
    count = collections.Counter()
    for ind, entries in enumerate(itertools.product((0, 1), repeat=n ** 2)):
        if ind % 5000 == 0:
            print(f"{ind:10}/{2 ** (n ** 2)}")
        A = Matrix(entries, nrows=n)
        count[A.charpoly()] += 1
    return count
for n in range(1, 6):
    for poly, freq in process(n).items():
        if poly.subs(0) == -1 and all(c == -1 for c in poly.coefficients()[:-1]):
            print(poly, ":", freq)

For $n = 1, 2, 3, 4$ it agrees with your results:

x - 1 : 1

x^2 - 1 : 1
x^2 - x - 1 : 2

x^3 - 1 : 2
x^3 - x^2 - 1 : 6
x^3 - x - 1 : 6
x^3 - x^2 - x - 1 : 12

x^4 - 1 : 6
x^4 - x^3 - 1 : 24
x^4 - x - 1 : 24
x^4 - x^3 - x - 1 : 72
x^4 - x^2 - 1 : 24
x^4 - x^3 - x^2 - 1 : 192
x^4 - x^2 - x - 1 : 96
x^4 - x^3 - x^2 - x - 1 : 192

I left it running for a few hours to compute the results for $n = 5$. They are as follows:

x^5 - 1 : 24
x^5 - x^4 - 1 : 120
x^5 - x^2 - 1 : 120
x^5 - x^4 - x^2 - 1 : 1080
x^5 - x - 1 : 120
x^5 - x^4 - x - 1 : 480
x^5 - x^2 - x - 1 : 480
x^5 - x^4 - x^2 - x - 1 : 1440
x^5 - x^3 - 1 : 120
x^5 - x^4 - x^3 - 1 : 3120
x^5 - x^3 - x^2 - 1 : 480
x^5 - x^4 - x^3 - x^2 - 1 : 4560
x^5 - x^3 - x - 1 : 600
x^5 - x^4 - x^3 - x - 1 : 3840
x^5 - x^3 - x^2 - x - 1 : 1800
x^5 - x^4 - x^3 - x^2 - x - 1 : 6960

In particular we have $3120 = 2^{4} \cdot 3 \cdot 5 \cdot 13$, and $4560 = 2^{4} \cdot 3 \cdot 5 \cdot 19$, and $6960 = 2^{4} \cdot 3 \cdot 5 \cdot 29$.

As I mentioned in my comment, these sets of matrices are naturally acted on by conjugation by the group of permutation matrices. I modified my code a bit to work out what these orbit decompositions look like, and indeed for $n = 1, 2, 3, 4$, the sets happen to decompose into a number of identical-sized orbits.

x - 1 : 1
[1]

x^2 - 1 : 1
[1]
x^2 - x - 1 : 2
[2]

x^3 - 1 : 2
[2]
x^3 - x^2 - 1 : 6
[6]
x^3 - x - 1 : 6
[6]
x^3 - x^2 - x - 1 : 12
[6, 6]

x^4 - 1 : 6
[6]
x^4 - x^3 - 1 : 24
[24]
x^4 - x - 1 : 24
[24]
x^4 - x^3 - x - 1 : 72
[24, 24, 24]
x^4 - x^2 - 1 : 24
[24]
x^4 - x^3 - x^2 - 1 : 192
[24, 24, 24, 24, 24, 24, 24, 24]
x^4 - x^2 - x - 1 : 96
[24, 24, 24, 24]
x^4 - x^3 - x^2 - x - 1 : 192
[24, 24, 24, 24, 24, 24, 24, 24]

This to some extent explains why the pattern you observed was there - you picked some constraints on the characteristic polynomials that happened to constrain these orbits to this, resulting in sets whose size is a small multiple of $n!$, which cannot have a prime factor larger than $n$. This pattern seems to just break at $n = 5$, though. It's either the case that some orbits are different sizes when $n = 5$, or the orbits are the same size but the number of orbits becomes large enough to contribute a large prime factor.

(I haven't computed the sizes of the orbits for $n = 5$, because I didn't save the sets of matrices :))

Answer 2

I wrote one Mathematica code snippet to demonstrate it.

n = 4;

(*Generate all nxn 0-1 matrices*)allMatrices = Tuples[{0, 1}, {n, n}];

(*Define a function to calculate characteristic polynomial*)
charPoly[m_] := CharacteristicPolynomial[m, x];

(*Get characteristic polynomials of all matrices*)
allCharPolys = Map[charPoly, allMatrices];
polys = (allCharPolys // Tally)

(*Define a function to judge wether the polynomial we concern*)
checkPoly[poly_, var_] := 
 Module[{coeffs = CoefficientList[poly, var]}, 
  AllTrue[coeffs // Reverse // Drop[#, 1] &, (# >= -1 && # <= 0) &] &&
    coeffs[[1]] == -1]


(*Filter those polynomials we concern*)
selectedPolys = Select[polys, checkPoly[#[[1]], x] &]

For case $n=4$,

$$ \left( \begin{array}{cc} x^4-1 & 6 \\ x^4-x^3-1 & 24 \\ x^4-x-1 & 24 \\ x^4-x^3-x-1 & 72 \\ x^4-x^2-1 & 24 \\ x^4-x^3-x^2-1 & 192 \\ x^4-x^2-x-1 & 96 \\ x^4-x^3-x^2-x-1 & 192 \\ \end{array} \right) $$

For case $n=5$,

it takes too long to complete the computing task. $\color{blue}{\text{Any help would be appreciated. }}$