cp's OEIS Frontend

A367052 Number of n X n matrices with elements {0, 1} whose characteristic polynomial has non-leading coefficients in {-1,0}.

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