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

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$$.

• I don't think the data is supportive enough. Have you tried $n=5$, where I expect 5 might show up as a factor? Nov 3, 2023 at 18:45
• That's fair, and I've edited the question. 2^25 is bigger than my Mathematica program can handle in reasonable time, but I agree that $5$s are likely to show up in there. I've modified my conjecture in response to this. Nov 3, 2023 at 19:12
• This pattern might be related to the fact that the group of $n\times n$ permutation matrices acts on the set of $0$-$1$ matrices with a certain characteristic polynomial by conjugation. This group has order $n!$, so it means the set decomposes into orbits of size dividing $n!$ by orbit-stabiliser (hence of size not having prime factors larger than $n$). However in general there are multiple orbits, and it's not obvious to me how many there are and how their sizes relate. I can't say if this suggests your conjecture is true or not. Nov 3, 2023 at 22:55
• Also, the $\mathrm{GL}_n(\Bbb Q)$-conjugacy classes of such matrices are determined by the possible rational canonical forms. With all the polynomials you've looked at, there's only one possible RCF because your polynomials are squarefree over $\Bbb Q$. I believe the first non-squarefree example is $x^7 - x^5 - x^3 - x^2 - x - 1$, indicating that there are behaviours that your data has not encountered. Also a very informal remark - polynomials with coefficients $0, 1, -1$ are famously associated with patterns that break for large $n$. Nov 3, 2023 at 23:11

## 2 Answers

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 :))

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. }}$$