A346381 -id:A346381 - cp's OEIS frontend

A002820 Number of n X n invertible binary matrices A such that A+I is invertible.

1, 0, 2, 48, 5824, 2887680, 5821595648, 47317927329792, 1544457148312846336, 202039706313624586813440, 105823549214125066767168438272, 221819704567105547916502447159246848, 1860304261534304703934696550224148083769344, 62413833036707798343389591015829588620560344023040

Offset: 0

N. J. A. Sloane

Also number of linear orthomorphisms of GF(2)^n.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..55
Zong Duo Dai, Solomon W. Golomb, and Guang Gong, Generating all linear orthomorphisms without repetition, Discrete Math. 205 (1999), 47-55.
P. F. Duvall, Jr. and P. W. Harley, III, A note on counting matrices, SIAM J. Appl. Math., 20 (1971), 374-377.
Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow, arXiv:2012.13570 [math.CO], 2020.
Kent Morrison, Matrices over F_q with no eigenvalues of 0 or 1
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
Index entries for sequences related to binary matrices

Cf. A002884.

Column k=0 of A346201 and of A346381.

# (Maple program based on Dai et al. from N. J. A. Sloane, Aug 10 2011)
N:=proc(n,i) option remember; if i = 1 then 1 else (2^n-2^(i-1))*N(n,i-1); fi; end;
Oh:=proc(n) option remember; local r; global N;
if n=0 then RETURN(1) elif n=1 then RETURN(0) else
add( 2^(r-2)*N(n,r)*2^(r*(n-r))*Oh(n-r), r=2..n); fi; end;
[seq(Oh(n),n=0..15)];

ni[n_, i_] := ni[n, i] = If[i == 1, 1, (2^n - 2^(i-1))*ni[n, i-1]]; a[0] = 1; a[1] = 0; a[n_] := a[n] = Sum[ 2^(r-2)*ni[n, r]*2^(r*(n-r))*a[n-r], {r, 2, n}]; Table[a[n], {n, 1, 11}] (* Jean-François Alcover, Jan 19 2012, after Maple *)

Reference gives a recurrence.

a(n) = 2^(n(n-1)/2) * A005327(n+1).

More terms from Vladeta Jovovic, Mar 17 2000
Entry revised by N. J. A. Sloane, Aug 10 2011
a(0)=1 prepended by Alois P. Heinz, Jan 10 2025

A379105 Triangular array read by rows. T(n,k) is the number of n X n matrices T over GF(2) such that there are exactly 2^k vectors v in GF(2)^n with Tv=v, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 6, 9, 1, 168, 294, 49, 1, 20160, 37800, 7350, 225, 1, 9999360, 19373760, 4036200, 144150, 961, 1, 20158709760, 39687459840, 8543828160, 326932200, 2542806, 3969, 1, 163849992929280, 325139829719040, 71124337751040, 2812314375360, 23435953128, 42677334, 16129, 1

Offset: 0

Geoffrey Critzer, Dec 15 2024

Sum_{k=0..n} T(n,k)*2^k = (2^(n+1)-1)*2^(n^2-n) so that as n->oo the average number of fixed points is 2.

T(n,k) is also the number of n X n matrices over GF(2) with nullity k. As n->oo, the probability that a random n X n matrix over GF(q) has nullity k is 1/|GL_k(F_q)|*Product_{i>=k+1} (1 - 1/q^i). - Geoffrey Critzer, Dec 31 2024

			Triangle T(n,k) begins:
        1;
        1,        1;
        6,        9,       1;
      168,      294,      49,      1;
    20160,    37800,    7350,    225,   1;
  9999360, 19373760, 4036200, 144150, 961, 1;
  ...

Cf. A060867 (T(n,n-1)), A002884 (column k=0), A086699 (column k=1), A346381, A286331.

Row sums give A002416.

nn = 5; 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]}]; \[Nu] = Table[1/n Sum[MoebiusMu[n/d] q^d, {d, Divisors[n]}], {n, 1, nn}]; L=Level[Table[IntegerPartitions[n], {n, 0, nn}], {2}]; g[u_, v_, deg_] :=  Total[Map[v^Length[#] u^(deg Total[#])/aut[deg, #] &, L]]; Map[Select[#, # > 0 &] &,  Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0,nn}] CoefficientList[Series[g[u, 1, 1] g[u, v, 1] Product[g[u, 1, deg]^\[Nu][[deg]], {deg, 2, nn}], {u, 0, nn}], {u,v}]] // Grid

T(n,k)=Product_{j=0..n-k-1} (2^n - 2^j)^2/(2^(n-k)-2^j). - Geoffrey Critzer, Dec 31 2024

cp's OEIS Frontend

A002820 Number of n X n invertible binary matrices A such that A+I is invertible.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions