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

1, 2, 12, 216, 10143, 1128450, 279687570, 149055294640

Offset

0,2

Links

Table of n, a(n) for n=0..7.

Wikipedia, Faddeev-LeVerrier algorithm

Wikipedia, Intrinsic Function

Example

The a(2) = 12 2 X 2 matrices are:
  [0 0]  [0 0]  [0 1]  [0 1]  [0 1]  [1 1]
  [0 0], [1 0], [0 0], [1 0], [1 1], [1 0],
along with
  [0 0]  [0 0]  [0 1]  [1 0]  [1 0]      [1 1]
  [0 1], [1 1], [0 1], [0 0], [1 0], and [0 0].
These have characteristic polynomials of
x^2, x^2, x^2, x^2-1, x^2-x-1, x^2-x-1,
along with
x^2-x, x^2-x, x^2-x, x^2-x, x^2-x, and x^2-x respectively.

Mathematica

a[0] := 1;
a[n_] := Length[Select[
  Tuples[{0, 1}, {n, n}],
  Max[Abs[CoefficientList[CharacteristicPolynomial[#, x], x]]] == 1 &
]]

Prog

(Python)
from itertools import product
from sympy import Matrix
def A367051(n): return sum(1 for p in product((0, 1), repeat=n**2) if all(d==0 or d==-1 or d==1 for d in Matrix(n, n, p).charpoly().as_list())) if n else 1 # Chai Wah Wu, Nov 05 2023

Crossrefs

Cf. A272661, A367052.

Sequence in context: A292812 A153302 A123118 * A182161 A165950 A208651

Adjacent sequences: A367048 A367049 A367050 * A367052 A367053 A367054

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