A348622 -id:A348622 - cp's OEIS frontend

A348015 Number of periodic n X n matrices over GF(2).

1, 2, 13, 365, 43801, 21725297, 43798198753, 355991759464385, 11619571028917526401, 1520025803718875133673217, 796153035368657542014822907393, 1668838669721233396228446711227874305, 13995815633937307151473642050515241531340801

Offset: 0

Geoffrey Critzer, Sep 24 2021

nonn

Here, T is a periodic matrix if T = T^k for some k > 1. T is periodic iff image(T) = image(T^2) iff x^2 does not divide the minimal polynomial of T.

			a(2) = 13 because there are 16 2 X 2 matrices over GF(2) and all are recurrent except for {{0,0},{1,0}}, {{0,1},{0,0}}, and {{1,1},{1,1}}.  16-3 = 13.

Alois P. Heinz, Table of n, a(n) for n = 0..57
Geoffrey Critzer, Enumeration of matrices over finite fields
Eric Weisstein's World of Mathematics, Periodic Matrix

Cf. A002884.

Row sums of A348622.

b:= proc(n) option remember; mul(2^n-2^i, i=0..n-1) end:
a:= n-> add(b(n)/b(n-k), k=0..n):
seq(a(n), n=0..14);  # Alois P. Heinz, Oct 30 2021

nn=12; q = 2; b[p_, i_] := Count[p, i];
s[p_, i_] := Sum[j b[p, j], {j, 1, i}] + i Sum[b[p, j], {j, i + 1, Total[p]}];
aut[deg_, p_] := Product[Product[q^(s[p, i] deg) - q^((s[p, i] - k) deg), {k, 1, b[p, i]}], {i, 1,Total[p]}]; \[Nu] =Table[1/n Sum[MoebiusMu[n/m] q^m, {m, Divisors[n]}], {n, 1,nn}];l[greatestpart_] := Level[Table[IntegerPartitions[n, {0, n}, Range[greatestpart]], {n, 0, nn}], {2}];
g1[u_, v_, deg_] :=Total[Map[v u^(deg Total[#])/aut[deg, #] &, l[1]]];
g2[u_, v_, deg_] :=Total[Map[v u^(deg Total[#])/aut[deg, #] &, l[nn]]];
Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0, nn}] CoefficientList[
  Series[g1[u, 1, 1] g2[u, 1, 1] Product[g2[u, 1, d]^\[Nu][[d]], {d, 2, nn}] , {u, 0, nn}], u]

a(n) = Sum_{d=0...n} A002884(n)/A002884(n-d). - Geoffrey Critzer, Oct 30 2021
Sum_{n>=0} a(n)u^n/A002884(n) = E(u)/(1-u) where E(u) = Sum_{n>=0} u^n/A002884(n). - Geoffrey Critzer, Oct 30 2021
Limit_{n->infinity} a(n)/2^(n^2) = (Product_{r>=1} (1-1/2^r)) * Sum_{n>=0} 1/A002884(n) = 0.62744086981206237307... . - Geoffrey Critzer, Oct 30 2021
Sum_{n>=0} a(n)*x^n/B(n) = e(x)*g(x) where e(x) = Sum_{n>=0} x^n/B(n), g(x) = Sum_{n>=0} Product_{i=0..n-1} (q^n-q^i)*x^n/B(n), B(n) = Product_{i=0..n-1} (q^n-q^i)/(q-1)^n and q=2. - Geoffrey Critzer, Jan 03 2025

Data terms for n >= 3 corrected by Geoffrey Critzer, Oct 30 2021

Title improved by Geoffrey Critzer, Sep 16 2022

A348958 Triangular array read by rows. T(n,k) = A002884(n)/A002884(n-k)*2^((n-k)(n-k-1)), n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 4, 6, 6, 64, 112, 168, 168, 4096, 7680, 13440, 20160, 20160, 1048576, 2031616, 3809280, 6666240, 9999360, 9999360, 1073741824, 2113929216, 4095737856, 7679508480, 13439139840, 20158709760, 20158709760, 4398046511104, 8727373545472, 17182016667648, 33290157293568, 62419044925440, 109233328619520, 163849992929280, 163849992929280

Offset: 0

Geoffrey Critzer, Nov 04 2021

Let ~ be the equivalence relation on the set of n X n matrices over GF(2) defined by A ~ B if and only if the dimension of the image of A^n is equal to the dimension of the image of B^n. Let A be a recurrent matrix (Cf A348622) of rank k. Then T(n,k) is the size of the equivalence class containing A.

Let X_n be the random variable that assigns to each n X n matrix A over GF(q) the value j = nullity(A^n). Then limit as n->oo of P(X_n = j) = Product_{i>=1}(1 - 1/q^i)*q^(j^2-j)/|GL_j(F_q)|. - Geoffrey Critzer, Jan 02 2025

			Triangle begins:
  1,
  1,       1,
  4,       6,       6,
  64,      112,     168,     168,
  4096,    7680,    13440,   20160,   20160,
  1048576, 2031616, 3809280, 6666240, 9999360, 9999360

Cf. A348622, A002884 (main diagonal), A053763 (column k=0).

R[n_, d_] := Product[q^n - q^i, {i, 0, n - 1}]/Product[q^(n - d) - q^i, {i, 0, n - d - 1}];Table[Table[R[n, d] q^((n - d) (n - d - 1)), {d, 0, n}], {n, 0,10}] // Grid

T(n,k) = A002884(n)/A002884(n-k)*2^((n-k)*(n-k-1)).

Sum_{n>=0} Sum_{k=0..n} T(n,k)*y^k*x^n/B(n) = f(x)*g(y*x) where f(x) = Sum_{n>=0} q^(n^2-n)*x^n/B(n), g(x) = Sum_{n>=0} Product_{i=0..n-1} (q^n-q^i)x^n/B(n), B(n) = Product_{i=0..n-1} (q^n-q^i)/(q-1)^n and q=2. - Geoffrey Critzer, Jan 02 2025

cp's OEIS Frontend

A348015 Number of periodic n X n matrices over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions