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
Examples
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.
Links
- Wikipedia, Faddeev-LeVerrier algorithm
- Wikipedia, Intrinsic Function
Programs
-
Mathematica
a[0] := 1; a[n_] := Length[Select[ Tuples[{0, 1}, {n, n}], Max[Abs[CoefficientList[CharacteristicPolynomial[#, x], x]]] == 1 & ]] -
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
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