A272661 -id:A272661 - cp's OEIS frontend

A272659 Number of distinct characteristic polynomials of n X n matrices with elements {0, 1, 2}.

1, 3, 22, 513, 58335, 40422490

Offset: 0

N. J. A. Sloane, May 15 2016

Robert M. Corless, Bohemian Eigenvalues, Talk Presented at Computational Discovery in Mathematics (ACMES 2), University of Western Ontario, May 12 2016. (Talk based on joint work with Steven E. Thornton, Sonia Gupta, Jonathan Brino-Tarasoff, Venkat Balasubramanian.)

Six classes of matrices mentioned in Rob Corless's talk: A272658, A272659, A272660, A272661, A272662, A272663.

from itertools import product
from sympy import Matrix
def A272659(n): return len({tuple(Matrix(n,n,p).charpoly().as_list()) for p in product(range(3),repeat=n**2)}) if n else 1 # Chai Wah Wu, Sep 30 2023

a(4) from Chai Wah Wu, Dec 03 2018
a(5) from Steven E. Thornton, Mar 09 2019
a(0)=1 prepended by Alois P. Heinz, Sep 28 2023

A272658 Number of distinct characteristic polynomials of n X n matrices with elements {-1, 0, +1}.

Original entry on oeis.org

1, 3, 16, 209, 8739, 1839102

Offset: 0

N. J. A. Sloane, May 15 2016

Robert M. Corless, Bohemian Eigenvalues, Talk Presented at Computational Discovery in Mathematics (ACMES 2), University of Western Ontario, May 12 2016. (Talk based on joint work with Steven E. Thornton, Sonia Gupta, Jonathan Brino-Tarasoff, Venkat Balasubramanian.)

Eunice Y. S. Chan, Algebraic Companions and Linearizations, The University of Western Ontario (Canada, 2019) Electronic Thesis and Dissertation Repository. 6414.
Eunice Y. S. Chan and Robert Corless, A new kind of companion matrix, Electronic Journal of Linear Algebra, Volume 32, Article 25, 2017, see p. 335.
Robert M. Corless et al., Bohemian Eigenvalues.
Robert Corless and Steven Thornton, The Bohemian Eigenvalue Project, 2017 poster.

Six classes of matrices mentioned in Rob Corless's talk: this sequence, A272659, A272660, A272661, A272662, A272663.

Other properties of this class of matrices: A271570, A271587, A271588. - Steven E. Thornton, Jul 13 2016

a[n_] := a[n] = Module[{m, cPolys}, m = Tuples[Tuples[{-1, 0, 1}, n], n]; cPolys = CharacteristicPolynomial[#, x] & /@ m; Length[DeleteDuplicates[cPolys]]]; Table[a[i], {i, 1, 3}] (* Robert P. P. McKone, Sep 16 2023 *)

from itertools import product
from sympy import Matrix
def A272658(n): return len({tuple(Matrix(n,n,p).charpoly().as_list()) for p in product((-1,0,1),repeat=n**2)}) if n else 1 # Chai Wah Wu, Sep 30 2023

a(n) <= 3^(n^2). - Robert P. P. McKone, Sep 16 2023

a(4) found by Daniel Lichtblau, May 13 2016
a(5) found by Daniel Lichtblau and Steven E. Thornton, May 19 2016
a(0)=1 prepended by Alois P. Heinz, Sep 28 2023

A272662 Number of distinct characteristic polynomials of n X n matrices with elements {-1, +1}.

Original entry on oeis.org

1, 2, 6, 28, 203, 3150, 131641

Offset: 0

N. J. A. Sloane, May 15 2016

Robert M. Corless, Bohemian Eigenvalues, Talk Presented at Computational Discovery in Mathematics (ACMES 2), University of Western Ontario, May 12 2016. (Talk based on joint work with Steven E. Thornton, Sonia Gupta, Jonathan Brino-Tarasoff, Venkat Balasubramanian.)

Six classes of matrices mentioned in Rob Corless's talk: A272658, A272659, A272660, A272661, A272662, A272663.

from itertools import product
from sympy import Matrix
def A272662(n): return len({tuple(Matrix(n,n,p).charpoly().as_list()) for p in product((-1,1),repeat=n**2)}) if n else 1 # Chai Wah Wu, Sep 30 2023

a(5) and a(6) from Steven E. Thornton, Mar 09 2019

a(0)=1 prepended by Alois P. Heinz, Sep 28 2023

A272660 Number of distinct characteristic polynomials of n X n matrices with elements {t, 1, 2} where t is an indeterminate.

Original entry on oeis.org

1, 3, 36, 1782, 760678

Offset: 0

N. J. A. Sloane, May 15 2016

			From _Robin Visser_, May 01 2025: (Start)
For n = 1, the a(1) = 3 possible characteristic polynomials are x - 2, x - 1, and x - t.
For n = 2, the a(2) = 36 possible characteristic polynomials are x^2 - 2x - 1, x^2 - 2x, x^2 + (-t-2)x, x^2 + (-t-2)x - t^2+2t, x^2 + (-t-1)x, x^2 + (-t-1)x - t^2+t, x^2 - 4x, x^2 - 4x + 2, x^2 - 4x + 3, x^2 - 3x - 2, x^2 - 3x, x^2 - 3x + 1, x^2 - 2tx + t^2-4, x^2 - 2tx + t^2-2, x^2 - 2tx + t^2-1, x^2 + (-t-2)x + t, x^2 - 4x - t+4, x^2 - 4x - t^2+4, x^2 - 2x - 3, x^2 - 2tx, x^2 - 2tx + t^2-t, x^2 - 2tx + t^2-2t, x^2 - 4x - 2t+4, x^2 - 3x - t^2+2, x^2 - 3x - t+2, x^2 - 3x - 2t+2, x^2 - 2x - t^2+1, x^2 - 2x - t+1, x^2 - 2x - 2t+1, x^2 + (-t-2)x + 2t-4, x^2 + (-t-2)x + 2t-2, x^2 + (-t-2)x + 2t-1, x^2 + (-t-1)x + t-4, x^2 + (-t-1)x + t-2, x^2 + (-t-1)x + t-1, and x^2 + (-t-1)x - t. (End)

Robert M. Corless, Bohemian Eigenvalues, Talk Presented at Computational Discovery in Mathematics (ACMES 2), University of Western Ontario, May 12 2016. (Talk based on joint work with Steven E. Thornton, Sonia Gupta, Jonathan Brino-Tarasoff, Venkat Balasubramanian.)

Six classes of matrices mentioned in Rob Corless's talk: A272658, A272659, A272660, A272661, A272662, A272663.

import itertools
def a(n):
    ans, t = set(), SR('t')
    W = itertools.product([t, 1, 2], repeat=n*n)
    for w in W: ans.add(Matrix(SR, n, n, w).charpoly())
    return len(ans)  # Robin Visser, May 01 2025

a(0)=1 prepended by Alois P. Heinz, Sep 28 2023

a(4) from Robin Visser, May 01 2025

A272663 Number of distinct characteristic polynomials of n X n matrices with elements {t, 1}, where t is an indeterminate.

Original entry on oeis.org

1, 2, 9, 68, 1161, 65348

Offset: 0

N. J. A. Sloane, May 15 2016

			From _Robin Visser_, May 01 2025: (Start)
For n = 1, the a(1) = 2 possible characteristic polynomials are x - 1 and x - t.
For n = 2, the a(2) = 9 possible characteristic polynomials are x^2 - 2*x, x^2 - 2*t*x, x^2 - 2*t*x + t^2 - t, x^2 + (-t - 1)*x, x^2 + (-t - 1)*x - t^2 + t, x^2 - 2*x - t^2 + 1, x^2 - 2*t*x + t^2 - 1, x^2 - 2*x - t + 1, and x^2 + (-t - 1)*x + t - 1. (End)

Robert M. Corless, Bohemian Eigenvalues, Talk Presented at Computational Discovery in Mathematics (ACMES 2), University of Western Ontario, May 12 2016. Rotman Institute of Philosophy, Youtube video. (Talk based on joint work with Steven E. Thornton, Sonia Gupta, Jonathan Brino-Tarasoff, Venkat Balasubramanian.)

Six classes of matrices mentioned in Rob Corless's talk: A272658, A272659, A272660, A272661, A272662, A272663.

import itertools
def a(n):
    ans, t = set(), SR('t')
    W = itertools.product([t, 1], repeat=n*n)
    for w in W: ans.add(Matrix(SR, n, n, w).charpoly())
    return len(ans)  # Robin Visser, May 01 2025

a(0)=1 prepended by Alois P. Heinz, Sep 28 2023

a(5) from Robin Visser, May 04 2025

A365926 Number of distinct characteristic polynomials for n X n matrices with entries in {0, 1, ..., n-1}.

Original entry on oeis.org

1, 1, 6, 513, 2875405

Offset: 0

Robert P. P. McKone, Sep 23 2023

Robert P. P. McKone, The distinct characteristic polynomials for a(2)-a(3).

Cf. A272661, A272659.

Cf. A272658, A272660, A272662, A272663.

a[n_] := Module[{polynomials = {}, polynomial}, Monitor[Do[polynomial = CharacteristicPolynomial[ArrayReshape[IntegerDigits[i, n, n^2], {n, n}], x]; If[Not[MemberQ[polynomials, polynomial]], AppendTo[polynomials, polynomial]];, {i, 0, n^(n^2) - 1}], {n, {i, n^(n^2) - 1}, ProgressIndicator[i, {0, n^(n^2) - 1}]}]; Length[polynomials]]; Table[a[n], {n, 1, 3}]

from itertools import product
from sympy import Matrix
def A365926(n): return len({tuple(Matrix(n,n,p).charpoly().as_list()) for p in product(range(n),repeat=n**2)}) if n else 1 # Chai Wah Wu, Sep 30 2023

a(4) from Robin Visser, May 04 2025

A306781 Number of distinct minimal polynomials of n X n matrices with elements {0, 1}.

Original entry on oeis.org

2, 8, 39, 369, 9391

Offset: 1

Steven E. Thornton, Mar 09 2019

S. E. Thornton, Properties of the Bohemian family of n x n matrices with population {0, 1}, Characteristic Polynomial Database.

Number of characteristic polynomials is in A272661.

A366158 Number of distinct determinants of 3 X 3 matrices with entries from {0, 1, ..., n}.

Original entry on oeis.org

1, 5, 25, 77, 179, 355, 609, 995, 1497, 2167, 2999, 4069, 5289, 6841, 8595, 10661, 13023, 15777, 18795, 22305, 26085, 30397, 35107, 40381, 45929, 52247, 58929, 66287, 74139, 82767, 91643, 101701, 112013, 123235

Offset: 0

Robert P. P. McKone, Oct 02 2023

These determinants a(n) equivalently represent the leading coefficient (coefficient of term with degree 0) of the characteristic polynomials for such matrices, thereby providing a direct measure and lower bound of the uniqueness of these polynomials within this matrix class.

The maximal determinant counted by a(n) is A033431(n) = 2*n^3.

Robert P. P. McKone, The distinct determinants for a(0)-a(18).

Cf. A058331 (distinct determinants for 2 X 2 matrices).
Cf. A272661, A272659.
Cf. A365926.
Cf. A272658, A272660, A272662, A272663.
Cf. A033431 (maximal determinant).
Cf. A097400 (distinct consecutive entries in 3 X 3 matrix).

mat[n_Integer?Positive] := mat[n] = Array[m, {n, n}]; flatMat[n_Integer?Positive] := flatMat[n] = Flatten[mat[n]]; detMat[n_Integer?Positive] := detMat[n] = Det[mat[n]] // FullSimplify; a[d_Integer?Positive, 0] = 1; a[d_Integer?Positive, n_Integer?Positive] := a[d, n] = Length[DeleteDuplicates[Flatten[ParallelTable[Evaluate[detMat[d]], ##] & @@ Table[{flatMat[d][[i]], 0, n}, {i, 1, d^2}]]]]; Table[a[3, n], {n, 0, 9}]

from itertools import product
def A366158(n): return len({a[0]*(a[4]*a[8] - a[5]*a[7]) - a[1]*(a[3]*a[8] - a[5]*a[6]) + a[2]*(a[3]*a[7] - a[4]*a[6]) for a in product(range(n+1),repeat=9)}) # Chai Wah Wu, Oct 06 2023

a(19)-a(26) from Robin Visser, May 08 2025

a(27)-a(33) from Robin Visser, Aug 26 2025

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

Original entry on oeis.org

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

Offset: 0

Peter Kagey, Nov 03 2023

			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.

Wikipedia, Faddeev-LeVerrier algorithm
Wikipedia, Intrinsic Function

Cf. A272661, A367052.

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

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

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

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

Original entry on oeis.org

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

Offset: 0

Peter Kagey, Nov 03 2023

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

			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.

Wikipedia, Faddeev-LeVerrier algorithm
Wikipedia, Intrinsic Function

Cf. A003024, A272661, A367051.

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

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

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

cp's OEIS Frontend

A272659 Number of distinct characteristic polynomials of n X n matrices with elements {0, 1, 2}.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A272658 Number of distinct characteristic polynomials of n X n matrices with elements {-1, 0, +1}.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A272662 Number of distinct characteristic polynomials of n X n matrices with elements {-1, +1}.

Views

Author

Keywords

References

Crossrefs

Programs

Python

Extensions

A272660 Number of distinct characteristic polynomials of n X n matrices with elements {t, 1, 2} where t is an indeterminate.

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Sage

Extensions

A272663 Number of distinct characteristic polynomials of n X n matrices with elements {t, 1}, where t is an indeterminate.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Extensions

A365926 Number of distinct characteristic polynomials for n X n matrices with entries in {0, 1, ..., n-1}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A306781 Number of distinct minimal polynomials of n X n matrices with elements {0, 1}.

Views

Author

Keywords

Links

Crossrefs

A366158 Number of distinct determinants of 3 X 3 matrices with entries from {0, 1, ..., n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Extensions

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

Views