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

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

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

References

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

Links

• 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

Crossrefs

Cf. A002884.

Column k=0 of A346201 and of A346381.

Programs

Maple

# (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)];

Mathematica

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

Formula

Reference gives a recurrence.

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

Extensions

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