A296548 -id:A296548 - cp's OEIS frontend

A373396 Matrix inverse of triangle A296548, read by rows.

1, -1, 1, 5, -6, 1, -113, 140, -28, 1, 10879, -13560, 2800, -120, 1, -4324129, 5395984, -1120960, 49600, -496, 1, 6984271295, -8717444064, 1813050624, -80709120, 833280, -2016, 1, -45479775838337, 56768157085760, -11809230892032, 526302695424, -5466697728, 13655040, -8128, 1

Offset: 0

Geoffrey Critzer, Jun 03 2024

Let P_n be the set of n X n idempotent matrices over GF(2) with the ordering: E<=F iff EF=E=FE. Then T(n,k) = Sum mu(0,E) where the sum is taken over the elements in P_n of rank k and mu is the Moebius mu incidence function of P_n.

To obtain the inverse, we regard the triangle as a lower triangular matrix, but then ignore the part above the diagonal.

			 Triangle begins
         1;
        -1,       1;
         5,      -6,        1;
      -113,     140,      -28,     1;
     10879,  -13560,     2800,  -120,    1;
  -4324129, 5395984, -1120960, 49600, -496, 1;
  ...

Cf. A296548, A002884.

nn = 6; B[n_] = Product[q^n - q^i, {i, 0, n - 1}] /. q -> 2;e[x_] := Sum[x^n/B[n], {n, 0, nn}];Table[B[n], {n, 0, nn}]*CoefficientList[Series[ e[y x]/e[x], {x, 0, nn}], {x, y}] // Grid

Sum_{n>=0} Sum_{k=0..n} T(n,k)*y^k*x^n/A002884(n) = e(y*x)/e(x) where e(x) = Sum_{n>=0} x^n/A002884(n).

A132186 Number of idempotent n X n matrices over GF(2); also number of diagonalizable n X n matrices over GF(2).

Original entry on oeis.org

1, 2, 8, 58, 802, 20834, 1051586, 102233986, 19614424834, 7355623374338, 5494866505497602, 8087844439442585602, 23834930674299549249538, 138978138716920276085366786, 1626809921636911219317749563394, 37757678575184051755732304668884994

Offset: 0

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 19 2003 and Vladeta Jovovic, Nov 04 2007

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..81
Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A002884, A081080.

Row sums of A296548.

T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, T(n-1, k-1)+2^k*T(n-1, k)))
    end:
a:= n-> add(2^(k*(n-k))*T(n, k), k=0...n):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 06 2017

nn = 10; g[n_] := (q - 1)^n  q^Binomial[n, 2] FunctionExpand[
QFactorial[n, q]] /. q -> 2; G[z_] := Sum[z^k/g[k], {k, 0, nn}];Table[g[n], {n, 0, nn}] CoefficientList[Series[G[z]^2, {z, 0, nn}], z] (* Geoffrey Critzer, Aug 04 2017 *)
a[n_] := Block[{m}, Length@ Select[ Range[2^(n^2)], (m = Partition[ IntegerDigits[ #-1, 2, n^2], n]; Mod[m.m, 2] == m) &]]; a /@ Range[4] (* Giovanni Resta, Apr 09 2017 *)

a(n) = sum(k=0...n, 2^(k(n-k))*[n,k]2), where [n,k]_2 is the Gaussian binomial for q=2. - _Marc van Leeuwen, May 22 2013
a(n)/A002884(n) is the coefficient of x^n in (Sum_{n>=0} x^n/A002884(n))^2. - Geoffrey Critzer, Aug 04 2017
a(n) ~ c * 2^(n^2/2), where c = EllipticTheta(3, 0, 1/4) / QPochhammer(1/2) = 5.221199057419682876170323638731707664618893... if n is even and c = EllipticTheta(2, 0, 1/4) / QPochhammer(1/2) = 5.2043255482837364968664526298606149440286... if n is odd. - Vaclav Kotesovec, Jun 09 2025

This is the result of merging two independently submitted but identical sequences. Thanks to Geoffrey Critzer for suggesting this. - N. J. A. Sloane, Dec 26 2017

A378666 Triangular array read by rows: T(n,k) is the number of n X n idempotent matrices over GF(3) having rank k, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 1, 12, 1, 1, 117, 117, 1, 1, 1080, 10530, 1080, 1, 1, 9801, 882090, 882090, 9801, 1, 1, 88452, 72243171, 666860040, 72243171, 88452, 1, 1, 796797, 5873190687, 491992666011, 491992666011, 5873190687, 796797, 1, 1, 7173360, 476309310660, 360089838858960, 3267815287645062, 360089838858960, 476309310660, 7173360, 1

Offset: 0

Geoffrey Critzer, Dec 02 2024

A matrix M is idempotent if M^2 = M.

			Triangle T(n,k) begins:
  1;
  1,    1;
  1,   12,      1;
  1,  117,    117,      1;
  1, 1080,  10530,   1080,    1;
  1, 9801, 882090, 882090, 9801, 1;
  ...

Cf. A296548, A053846 (row sums).

Cf. A022167, A118180.

b:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, b(n-1, k-1)+3^k*b(n-1, k)))
    end:
T:= (n,k)-> 3^(k*(n-k))*b(n, k):
seq(seq(T(n,k), k=0..n), n=0..8);  # Alois P. Heinz, Dec 02 2024

nn = 8; \[Gamma][n_, q_] := Product[q^n - q^i, {i, 0, n - 1}]; B[n_, q_] := \[Gamma][n, q]/(q - 1)^n; \[Zeta][x_] := Sum[x^n/B[n, 3], {n, 0, nn}];Map[Select[#, # > 0 &] &, Table[B[n, 3], {n,0,nn}]*CoefficientList[Series[\[Zeta][x] \[Zeta][y x], {x, 0, nn}], {x, y}]] // Flatten

Sum_{n>=0} Sum_{k=0..n} T(n,k)*y^k*x^n/B(n) = e(x)*e(y*x) where e(x) = Sum_{n>=0} x^n/B(n) and B(n) = A053290(n)/2^n.

T(n,k) = A022167(n,k) * A118180(n,k). - Alois P. Heinz, Dec 02 2024

A358649 Number of convergent n X n matrices over GF(2).

Original entry on oeis.org

1, 2, 11, 205, 14137, 3755249, 3916674017, 16190352314305, 266479066904477569, 17503939768635307654913, 4593798697440979773283368449, 4819699338906053452395454422580225, 20221058158328101246044232181365184919553

Offset: 0

Geoffrey Critzer, Nov 26 2022

nonn

A matrix A over a finite field is convergent if A^j=A^(j+1) for some j>=1. Every convergent matrix converges to an idempotent matrix. Every idempotent matrix is convergent to itself. Every nilpotent matrix is convergent to the zero matrix.

Cf. A296548, A053763, A132186, A379778.

nn = 12; q = 2;g[n_] := Product[q^n - q^i, {i, 0, n - 1}]; Table[Sum[g[n]/(g[k] g[n - k]) q^((n - k) (n - k - 1)), {k, 0, n}], {n, 0, nn}]

a(n) = Sum_{k=0..n} A296548(n,k)*A053763(n-k).

Sum_{n>=0} a(n)*x^n/B(n) = f(x)*e(x) where f(x)=Sum_{n>=0} q^(n^2-n)*x^n/B(n), e(x)=Sum_{n>=0} 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

A359313 Triangular array read by rows. T(n,k) is the number of Green's H-classes contained in the D-class of rank k matrices in the semigroup Mat_n(F_2) of n X n matrices over the field F_2. n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 1, 9, 1, 1, 49, 49, 1, 1, 225, 1225, 225, 1, 1, 961, 24025, 24025, 961, 1, 1, 3969, 423801, 1946025, 423801, 3969, 1, 1, 16129, 7112889, 139499721, 139499721, 7112889, 16129, 1, 1, 65025, 116532025, 9439094025, 40315419369, 9439094025, 116532025, 65025, 1

Offset: 0

Geoffrey Critzer, Dec 25 2022

For all a,b in the semigroup Mat_n(F_2), aDb if and only if rank(a)=rank(b). Also, aHb if and only if the row(a)=row(b) and col(a)=col(b). So the H classes correspond to ordered pairs (U,W) of subspaces of F_2^n with dim(U) = dim(W). Let a in Mat_n(F_2) be such that col(a) = U and row(a)=W. The size of H_a, the H-class containing a is |GL_d(F_2)| where d=dim(U). H_a contains an idempotent if and only if col(a) + perp(row(a)) is a direct sum decomposition of F_2^n where perp(X)={v in F_2^n: v*x = 0 for all x in X}.

Let H_a,H_b be H-classes in Mat_n(F_2). Let H_a ~ H_b if and only if col(a) is contained in col(b) and row(a) is contained in row(b). Then ~ is a partial order relation on the set of all H-classes in Mat_n(F_q). The poset is isomorphic to a typical n-interval in the binomial poset L*L where L is the binomial poset of all finite dimensional subspaces over a countably infinite dimensional subspace and * is the Segre product (see Stanley reference). T(n,k) is the number of elements at rank k in an n-interval of L*L.

			 1
 1,   1
 1,   9,     1
 1,  49,    49,     1
 1, 225,  1225,   225,   1
 1, 961, 24025, 24025, 961, 1

R. P. Stanley, Enumerative Combinatorics, Volume I, Second Edition, section 3.18.

Wikipedia, Green's relations

Cf. A243950 (row sums), A022166, A005329, A002884, A002416, A296548 (a subposet of L*L).

nn = 8; B[n_, q_] := QFactorial[n, q]^2; e[x_] := Sum[x^n/B[n, 2], {n, 0, nn}]; Map[Select[#, # > 0 &] &, Table[QFactorial[n, 2]^2, {n, 0, nn}] CoefficientList[
   Series[e[x] e[y x], {x, 0, nn}], {x, y}]]

T(n,k) = A022166(n,k)^2.
Sum_{k=0..n} T(n,k)*A002884(k) = A002416(n).
Let B(n) = A005329(n)^2.  Let E(x)=Sum_{n>=0}x^n/B(n).  Then Sum{n>=0} Sum{k=0..n} T(n,k)*y^k*x^n/B(n) = E(x)*E(y*x).

A297892 Triangle read by rows. T(n,k) is the number of n X n diagonalizable matrices over GF(3) that have rank k, 0 <= k <= n, n >= 0.

Original entry on oeis.org

1, 1, 2, 1, 24, 14, 1, 234, 1638, 236, 1, 2160, 147420, 254880, 12692, 1, 19602, 12349260, 208173240, 124394292, 1783784, 1, 176904, 1011404394, 157378969440, 916910326332, 157779262368, 811523288

Offset: 0

Geoffrey Critzer, Jan 07 2018

			Triangle begins
  1;
  1,     2;
  1,    24,       14;
  1,   234,     1638,       236;
  1,  2160,   147420,    254880,     12692;
  1, 19602, 12349260, 208173240, 124394292, 1783784;

Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A296548, A053846 (main diagonal), A290516 (row sums).

nn = 5; g[n_] := (q - 1)^n  q^Binomial[n, 2] FunctionExpand[QFactorial[n, q]] /. q -> 3;G[n] := Sum[u z^r/g[r], {r, 0, nn}]; Grid[Map[Select[#, # > 0 &] &,Table[g[n], {n, 0, nn}] CoefficientList[Series[Sum[(u z)^r/g[r] , {r, 0, nn}]^2 Sum[
       z^r/g[r], {r, 0, nn}], {z, 0, nn}], {z, u}]]]

T(n,k)/A053290(n) is the coefficient of y^k*x^n in the expansion of Sum_{n>=0} x^n\A053290(n) * (Sum_{n>=0} y*x^n\A053290(n))^2.

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

A373396 Matrix inverse of triangle A296548, read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A132186 Number of idempotent n X n matrices over GF(2); also number of diagonalizable n X n matrices over GF(2).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A378666 Triangular array read by rows: T(n,k) is the number of n X n idempotent matrices over GF(3) having rank k, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A358649 Number of convergent n X n matrices over GF(2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A359313 Triangular array read by rows. T(n,k) is the number of Green's H-classes contained in the D-class of rank k matrices in the semigroup Mat_n(F_2) of n X n matrices over the field F_2. n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A297892 Triangle read by rows. T(n,k) is the number of n X n diagonalizable matrices over GF(3) that have rank k, 0 <= k <= n, n >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula