login
A367052
Number of n X n matrices with elements {0, 1} whose characteristic polynomial has non-leading coefficients in {-1,0}.
2
1, 2, 12, 195, 7971, 754610, 157474968, 70513430631
OFFSET
0,2
COMMENTS
All of these matrices have the property that for m >= n, A^m = A^{m-i_1} + A^{m-i_2} + ... + A^{m-i_k} for some positive increasing sequence 0 < i_1 < i_2 < ... < i_k <= n.
Because A003024(n) gives the number of such matrices with characteristic polynomial equal to x^n, a(n) >= A003024(n).
Conjecture: The number of matrices with characteristic polynomial x^n - x^(n-1) is exactly n*A003024(n). (If so, (n+1)*A003024(n) is a lower bound for this sequence.)
EXAMPLE
For n = 3, there are a(3) = 195 3 X 3 matrices whose non-leading coefficients are in {-1,0}, eight of which are shown below.
[0 0 1] [0 0 1] [0 0 0] [0 1 0]
[0 0 0] [1 0 0] [1 0 1] [1 0 1]
[0 1 0], [0 1 0], [1 1 0], [1 0 0],
.
[1 0 0] [1 1 0] [1 1 0] [1 1 0]
[1 0 0] [0 0 1] [1 0 0] [1 0 1]
[1 1 0], [1 0 0], [1 1 0], and [1 0 0].
These have characteristic polynomials x^3, x^3 - 1, x^3 - x, x^3 - x - 1, x^3 - x^2, x^3 - x^2 - 1, x^3 - x^2 - x, and x^3 - x^2 - x - 1 respectively.
There are 25, 2, 21, 6, 75, 6, 48, and 12 matrices with each of these characteristic polynomials respectively.
MATHEMATICA
IsValid[matrix_, n_] := AllTrue[
CoefficientList[(-1)^n*CharacteristicPolynomial[matrix, x], x][[;; -2]],
-1 <= # <= 0 &
]
a[0] := 1
a[n_] := Length[Select[Tuples[{0, 1}, {n, n}], IsValid[#, n] &]]
PROG
(Python)
from itertools import product
from sympy import Matrix
def A367052(n): return sum(1 for p in product((0, 1), repeat=n**2) if all(d==0 or d==-1 for d in Matrix(n, n, p).charpoly().as_list()[1:])) if n else 1 # Chai Wah Wu, Nov 05 2023
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Peter Kagey, Nov 03 2023
EXTENSIONS
a(5)-a(6), using the Faddeev-LeVerrier algorithm, from Martin Ehrenstein, Nov 06 2023
a(7), using AVX2 Intrinsics, from Martin Ehrenstein, Nov 18 2023
STATUS
approved