A132186 -id:A132186 - cp's OEIS frontend

A346677 Triangular array read by rows. T(n,k) is the number of n X n matrices over GF(2) that can be decomposed as the direct sum of k cyclic matrices, 0<=k<=n, n>=0.

1, 0, 2, 0, 8, 8, 0, 132, 322, 58, 0, 10752, 36412, 17570, 802, 0, 3185280, 16923024, 11693324, 1731970, 20834, 0, 5279662080, 26989750656, 30003846992, 6109974636, 335190786, 1051586, 0, 28343145922560, 196717668747264, 247267921788288, 84586214764240, 5906325116460, 128574848514, 102233986

Offset: 0

Geoffrey Critzer, Jul 28 2021

			Triangle begins:
  1;
  0,       2;
  0,       8,        8;
  0,     132,      322,       58;
  0,   10752,    36412,    17570,     802;
  0, 3185280, 16923024, 11693324, 1731970, 20834;
  ...

Joseph Kung, The Cycle Structure of a Linear Transformation over a Finite Field, Linear Algebra and its Applications, Vol 36, 1981, pages 141-155.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A002416 (row sums) A132186 (main diagonal).

nn = 6; q = 2; b[p_, i_] := Count[p, i];
d[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^(d[p, i] deg) - q^((d[p, i] - k) deg), {k, 1, b[p, i]}], {i, 1, Total[p]}];
A001037 = Table[1/n Sum[MoebiusMu[n/d] q^d, {d, Divisors[n]}], {n, 1, nn}];
g[u_, v_, deg_] :=  Total[Map[v^Length[#] u^(deg Total[#])/aut[deg, #] &, Level[Table[IntegerPartitions[n], {n, 0, nn}], {2}]]];
Table[Take[(Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0, nn}] CoefficientList[Series[Product[g[u, v, deg]^A001037[[deg]], {deg, 1, nn}], {u, 0, nn}], {u, v}])[[n]], n], {n, 1, nn}] // Grid

A357410 a(n) is the number of covering relations in the poset P of n X n idempotent matrices over GF(2) ordered by A <= B if and only if AB = BA = A.

Original entry on oeis.org

0, 1, 12, 224, 6960, 397792, 42001344, 8547291008, 3336917303040, 2565880599084544, 3852698988517260288, 11517943538435677485056, 67829192662051610706309120, 799669932659456441970547744768, 18652191511341505602408972738871296, 873360272626100960024734923878091948032

Offset: 0

Geoffrey Critzer, Sep 26 2022

nonn

The order given for P in the title is equivalent to the ordering: A <= B if and only if image(A) is contained in image(B) and null(A) contains null(B). Then A is covered by B if and only if there is a 1-dimensional subspace U such that image(B) = image(A) direct sum U. If such a subspace U exists then it is unique and is equal to the intersection of null(A) with image(B). The number of maximal chains in P is A002884(n). The set of all idempotent matrices over GF(q) with this ordering is a binomial poset with factorial function |GL_n(F_q)|/(q-1)^n. (see Stanley reference).

			a(2) = 12 because there are A132186(2) = 8 idempotent 2 X 2 matrices over GF(2).  The identity matrix covers 6 rank 1 matrices each of which covers the zero matrix for a total of 12 covering relations.  Cf. A296548.

R. P. Stanley, Enumerative Combinatorics, Vol I, second edition, page 320.

Wikipedia, Covering relation

Cf. A132186, A342245, A002884, A296548.

nn = 15; B[q_, n_] := Product[q^n - q^i, {i, 0, n - 1}]/(q - 1)^n;
e[q_, u_] := Sum[u^n/B[q, n], {n, 0, nn}];Table[B[2, n], {n, 0, nn}] CoefficientList[Series[e[2, u] u e[2, u], {u, 0, nn}], u]

Sum_{n>=0} a(n) x^n/B(n) = x * (Sum_{n>=0} x^n/B(n))^2 where B(n) = A002884(n).

cp's OEIS Frontend

A346677 Triangular array read by rows. T(n,k) is the number of n X n matrices over GF(2) that can be decomposed as the direct sum of k cyclic matrices, 0<=k<=n, n>=0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica