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

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

Offset: 0

Author

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

Keywords

• nonn

Links

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

Crossrefs

Cf. A002884, A081080.

Row sums of A296548.

Programs

Maple

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

Mathematica

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

Formula

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

Extensions

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