|
%I #35 Nov 18 2023 08:38:13
%S 1,2,12,195,7971,754610,157474968,70513430631
%N Number of n X n matrices with elements {0, 1} whose characteristic polynomial has non-leading coefficients in {-1,0}.
%C 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.
%C Because A003024(n) gives the number of such matrices with characteristic polynomial equal to x^n, a(n) >= A003024(n).
%C 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.)
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Faddeev-LeVerrier_algorithm">Faddeev-LeVerrier algorithm</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Intrinsic_function#C_and_C++">Intrinsic Function</a>
%e 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.
%e [0 0 1] [0 0 1] [0 0 0] [0 1 0]
%e [0 0 0] [1 0 0] [1 0 1] [1 0 1]
%e [0 1 0], [0 1 0], [1 1 0], [1 0 0],
%e .
%e [1 0 0] [1 1 0] [1 1 0] [1 1 0]
%e [1 0 0] [0 0 1] [1 0 0] [1 0 1]
%e [1 1 0], [1 0 0], [1 1 0], and [1 0 0].
%e 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.
%e There are 25, 2, 21, 6, 75, 6, 48, and 12 matrices with each of these characteristic polynomials respectively.
%t IsValid[matrix_, n_] := AllTrue[
%t CoefficientList[(-1)^n*CharacteristicPolynomial[matrix, x], x][[;;-2]],
%t -1 <= # <= 0 &
%t ]
%t a[0] := 1
%t a[n_] := Length[Select[Tuples[{0, 1}, {n, n}], IsValid[#, n] &]]
%o (Python)
%o from itertools import product
%o from sympy import Matrix
%o 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
%Y Cf. A003024, A272661, A367051.
%K nonn,hard,more
%O 0,2
%A _Peter Kagey_, Nov 03 2023
%E a(5)-a(6), using the Faddeev-LeVerrier algorithm, from _Martin Ehrenstein_, Nov 06 2023
%E a(7), using AVX2 Intrinsics, from _Martin Ehrenstein_, Nov 18 2023
| 