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

1, 2, 12, 195, 7971, 754610, 157474968, 70513430631

Offset: 0

Author

Peter Kagey, Nov 03 2023

Keywords

• nonn
• hard
• more

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.)

Examples

			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.
		

Links

• Wikipedia, Faddeev-LeVerrier algorithm
• Wikipedia, Intrinsic Function

Crossrefs

Cf. A003024, A272661, A367051.

Programs

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] &]]

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

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