A046747 -id:A046747 - cp's OEIS frontend

A002884 Number of nonsingular n X n matrices over GF(2) (order of the group GL(n,2)); order of Chevalley group A_n (2); order of projective special linear group PSL_n(2).

1, 1, 6, 168, 20160, 9999360, 20158709760, 163849992929280, 5348063769211699200, 699612310033197642547200, 366440137299948128422802227200, 768105432118265670534631586896281600, 6441762292785762141878919881400879415296000, 216123289355092695876117433338079655078664339456000

Offset: 0

N. J. A. Sloane

Also number of bases for GF(2^n) over GF(2).
Also (apparently) number of n X n matrices over GF(2) having permanent = 1. - Hugo Pfoertner, Nov 14 2003
The previous comment is true because over GF(2) permanents and determinants are the same. - Joerg Arndt, Mar 07 2008
The number of automorphisms of (Z_2)^n (the direct product of n copies of Z_2). - Peter Eastwood, Apr 06 2015
Note that n! divides a(n) since the subgroup of GL(n,2) consisting of all permutation matrices is isomorphic to S_n (the n-th symmetric group). - Jianing Song, Oct 29 2022
The number of boolean operations on n bits, or quantum operations on n qubits, that can be constructed using only CNOT (controlled NOT) gates. - David Radcliffe, Jul 06 2025

			PSL_2(2) is isomorphic to the symmetric group S_3 of order 6.

Roger W. Carter, Simple groups of Lie type. Pure and Applied Mathematics, Vol. 28, John Wiley & Sons, London-New York-Sydney, 1972. viii+331pp. MR0407163 (53 #10946). See page 2.
J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker and R. A. Wilson, ATLAS of Finite Groups. Oxford Univ. Press, 1985 [for best online version see https://oeis.org/wiki/Welcome#Links_to_Other_Sites], p. xvi.
H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, 4th ed., Springer-Verlag, NY, reprinted 1984, p. 131.
K. J. Horadam, Hadamard matrices and their applications. Princeton University Press, Princeton, NJ, 2007. xiv+263 pp. See p. 132.
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).

Seiichi Manyama, Table of n, a(n) for n = 0..57 (first 30 terms from T. D. Noe)
Marcus Brinkmann, Extended Affine and CCZ Equivalence up to Dimension 4, Ruhr University Bochum (2019).
Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
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.
Nataša Ilievska and Danilo Gligoroski , Error-Detecting Code Using Linear Quasigroups, ICT Innovations 2014, Advances in Intelligent Systems and Computing Volume 311, 2015, pp 309-318.
Aaron Meyerowitz & N. J. A. Sloane, Correspondence 1979.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
Jeffrey Overbey, William Traves, and Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol. 29, Iss. 1 (2005), pp. 59-72; author's copy.
I. Strazdins, Universal affine classification of Boolean functions, Acta Applic. Math. 46 (1997), 147-167.
Index entries for sequences related to binary matrices.
Index entries for sequences related to groups.
Index to divisibility sequences.

Column k=2 of A316622 and A316623.
Cf. A000409, A000410, A002820, A005329, A006125, A028365, A046747.
Cf. A006516, A048651, A203303. Row sums of A381854.

[1] cat [(&*[2^n -2^k: k in [0..n-1]]): n in [1..15]]; // G. C. Greubel, Aug 31 2023

# First program
A002884:= n-> mul(2^n - 2^i, i=0..n-1);
seq(A002884(n), n = 0..12);
# Second program
A002884:= n-> 2^(n*(n-1)/2) * mul( 2^i - 1, i=1..n);
seq(A002884(n), n=0..12);

Table[Product[2^n-2^i,{i,0,n-1}],{n,0,13}] (* Harvey P. Dale, Aug 07 2011 *)
Table[2^(n*(n-1)/2) QPochhammer[2, 2, n] // Abs, {n, 0, 11}] (* Jean-François Alcover, Jul 15 2017 *)

a(n)=prod(i=2,n,2^i-1)<Charles R Greathouse IV, Jan 13 2012

[product(2^n -2^j for j in range(n)) for n in range(16)] # G. C. Greubel, Aug 31 2023

a(n) = Product_{i=0..n-1} (2^n-2^i).
a(n) = 2^(n*(n-1)/2) * Product_{i=1..n} (2^i - 1).
a(n) = A203303(n+1)/A203303(n). - R. J. Mathar, Jan 06 2012
a(n) = (6*a(n-1)^2*a(n-3) - 8*a(n-1)*a(n-2)^2) / (a(n-2)*a(n-3)) for n > 2. - Seiichi Manyama, Oct 20 2016
a(n) ~ A048651 * 2^(n^2). - Vaclav Kotesovec, May 19 2020
a(n) = A006125(n) * A005329(n). - John Keith, Jun 30 2021
a(n) = Product_{k=1..n} A006516(k). - Amiram Eldar, Jul 06 2025

A055165 Number of invertible n X n matrices with entries equal to 0 or 1.

Original entry on oeis.org

1, 1, 6, 174, 22560, 12514320, 28836612000, 270345669985440, 10160459763342013440

Offset: 0

Ulrich Hermisson (uhermiss(AT)server1.rz.uni-leipzig.de), Jun 18 2000

All eigenvalues are nonzero.

			For n=2 the 6 matrices are {{{0, 1}, {1, 0}}, {{0, 1}, {1, 1}}, {{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}, {{1, 1}, {1, 0}}}.

Eric Weisstein's World of Mathematics, Nonsingular Matrix.
Chai Wah Wu, Can machine learning identify interesting mathematics? An exploration using empirically observed laws, arXiv:1805.07431 [cs.LG], 2018.
Miodrag Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005; Linear Algebra and its Applications, 414 (2006), 310-346.
Miodrag Zivkovic, Classification of (0,1) matrices of order not exceeding 8.
Index entries for sequences related to binary matrices

Cf. A056990, A056989, A046747, A055165, A002416, A003024 (positive definite matrices).
A046747(n) + a(n) = 2^(n^2) = total number of n X n (0, 1) matrices = sequence A002416.
Main diagonal of A064230.

a(n)=sum(t=0,2^n^2-1,!!matdet(matrix(n,n,i,j,(t>>(i*n+j-n-1))%2))) \\ Charles R Greathouse IV, Feb 09 2016

from itertools import product
from sympy import Matrix
def A055165(n): return sum(1 for s in product([0,1],repeat=n**2) if Matrix(n,n,s).det() != 0) # Chai Wah Wu, Sep 24 2021

For an asymptotic estimate see A046747. A002884 is a lower bound. A002416 is an upper bound.

a(n) = n! * A088389(n). - Gerald McGarvey, Oct 20 2007

More terms from Miodrag Zivkovic (ezivkovm(AT)matf.bg.ac.rs), Feb 28 2006
Description improved by Jeffrey Shallit, Feb 17 2016
a(0)=1 prepended by Alois P. Heinz, Jun 18 2022

A000410 Number of singular n X n rational (0,1)-matrices.

Original entry on oeis.org

0, 0, 6, 425, 65625, 27894671, 35716401889, 144866174953833

Offset: 1

N. J. A. Sloane

Number of all n X n (0,1)-matrices having distinct, nonzero ordered rows and determinant 0 - compare A000409.

a(n) is the number of singular n X n rational {0,1}-matrices with no zero rows and with all rows distinct, up to permutation of rows and so a(n) = binomial(2^n-1,n) - A088389(n). Cf. A116506, A116507, A116527, A116532. - Vladeta Jovovic, Apr 03 2006

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

N. Metropolis and P. R. Stein, On a class of (0,1) matrices with vanishing determinants, J. Combin. Theory, 3 (1967), 191-198.
Miodrag Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.
Miodrag Zivkovic, Classification of small (0,1) matrices, Linear Algebra and its Applications, 414 (2006), 310-346.
Index entries for sequences related to binary matrices

Cf. A000409, A046747, A064230, A064231.

n! * a(n) = A046747(n) - 2^(n^2) + n! * binomial(2^n -1, n).

n=7 term from Guenter M. Ziegler (ziegler(AT)math.TU-Berlin.DE)

a(8) from Vladeta Jovovic, Mar 28 2006

A000409 Singular n X n (0,1)-matrices: the number of n X n (0,1)-matrices having distinct, nonzero ordered rows, but having at least two equal columns or at least one zero column.

Original entry on oeis.org

0, 6, 350, 43260, 14591171, 14657461469, 46173502811223, 474928141312623525, 16489412944755088235117, 1985178211854071817861662307, 846428472480689964807653763864449, 1299141117072945982773752362381072143359, 7268140170419155675761326840423792818571154945, 149650282980396792665043455999899697765782372693740287

Offset: 2

N. J. A. Sloane

This is a lower bound for the set of all n X n (0,1)-matrices having distinct, nonzero ordered rows and determinant 0 (compare A000410).
Here ordered means that we take only one representative from the n! matrices obtained by all permutations of the distinct rows of an n X n matrix.
a(n) is also the number of sets of n distinct nonzero (0,1)-vectors in R^n that do not span R^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).

J. Kahn, J. Komlos and E. Szemeredi, On the probability that a random ±1-matrix is singular, J. AMS 8 (1995), 223-240.
Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
J. Komlos, On the determinant of (0,1)-matrices, Studia Math. Hungarica 2 (1967), 7-21.
N. Metropolis and P. R. Stein, On a class of (0,1) matrices with vanishing determinants, J. Combin. Theory, 3 (1967), 191-198.
Index entries for sequences related to binary matrices

Cf. A000410, A002884, A046747.

[ -(&+[StirlingFirst(n+1,k+1)*Binomial(2^k-1,n): k in [0..n-1]]): n in [2..15]]; // G. C. Greubel, Jun 05 2020

with(combinat): T := proc(n) -sum(stirling1(n+1,k+1)*binomial(2^k-1,n),k=0..n-1); end proc:

a[n_] := -Sum[ StirlingS1[n+1, k+1]*Binomial[2^k-1, n], {k, 0, n-1}]; Table[a[n], {n, 2, 15}] (* Jean-François Alcover, Nov 21 2012, from formula *)

a(n) = -sum(k=0, n-1, stirling(n+1, k+1, 1)*binomial(2^k-1, n)); \\ Michel Marcus, Jun 05 2020

[sum((-1)^(n+k+1)*stirling_number1(n+1,k+1)*binomial(2^k-1,n) for k in (0..n-1)) for n in (2..15)] # G. C. Greubel, Jun 05 2020

a(n) = (-1)*Sum_{k=0..n-1} Stirling1(n+1, k+1)*binomial(2^k-1, n).

a(n) = binomial(2^n-1, n) - A094000(n). - Vladeta Jovovic, Nov 27 2005

Edited by W. Edwin Clark, Nov 02 2003

A056989 Number of nonsingular n X n (-1,0,1)-matrices (over the reals).

Original entry on oeis.org

1, 2, 48, 11808, 27947520, 609653621760, 119288919620689920

Offset: 0

Eric W. Weisstein

It would be nice to have an estimate for the asymptotic rate of growth.

			a(1) = 2: [1], [ -1].
a(2) = 48: There are 8 choices for the first column, u (say) and then the 2nd column can be anything except 0, u, -u, so 6 choices, giving a total of 8*6 = 48.

Minfeng Wang, C++ program to calculate A056989
Eric Weisstein's World of Mathematics, Nonsingular Matrix
Index entries for sequences related to binary matrices

Cf. A055165, A053290, A056990, A055165, A002884, A046747, A057981, A060722.

(* A brute force solution up to n = 4 *) a[n_] := a[n] = (m = Array[x, {n, n}]; cnt = 0; iter = {#, -1, 1}& /@ Flatten[m]; Do[ If[ Det[m] != 0, cnt++], Evaluate[ Sequence @@ iter]]; cnt); Table[ Print[a[n]]; a[n], {n, 1, 4}] (* Jean-François Alcover, Oct 11 2012 *)

a(n) = A060722(n) - A057981(n). - Alois P. Heinz, Dec 02 2019

a(4) from Winston C. Yang (winston(AT)cs.wisc.edu), Aug 27 2000
Entry revised by N. J. A. Sloane, Jan 02 2007
a(5) from Giovanni Resta, Feb 20 2009
a(0)=1 prepended by Alois P. Heinz, Dec 02 2019
a(0)-a(5) confirmed and a(6) added by Minfeng Wang, May 01 2024

A064230 Triangle T(n,k) = number of rational (0,1) matrices of rank k (n >= 0, 0 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 9, 6, 1, 49, 288, 174, 1, 225, 6750, 36000, 22560, 1, 961, 118800, 3159750, 17760600, 12514320, 1, 3969, 1807806, 190071000, 5295204600, 34395777360, 28836612000, 1, 16129, 25316928, 9271660734, 1001080231200, 32307576315840

Offset: 0

N. J. A. Sloane, Sep 23 2001

Rows add to 2^(n^2).
Komlos and later Kahn, Komlos and Szemeredi show that almost all such matrices are invertible.
Table 3 from M. Zivkovic, Classification of small (0,1) matrices (see link). - Vladeta Jovovic, Mar 28 2006

			Triangle T(n,k) begins:
  1;
  1,   1;
  1,   9,      6;
  1,  49,    288,     174;
  1, 225,   6750,   36000,    22560;
  1, 961, 118800, 3159750, 17760600, 12514320;
  ...

J. Kahn, J. Komlos and E. Szemeredi: On the probability that a random +-1 matrix is singular, J. AMS 8 (1995), 223-240.
J. Komlos, On the determinants of random matrices, Studia Sci. Math. Hungar., 3 (1968), 387-399.

M. Zivkovic, Classification of small (0,1) matrices, Linear Algebra and its Applications, 414 (2006), 310-346.

Cf. A064231, A000409, A000410, A046747, A086875.

Main diagonal gives A055165.

T=matrix(5,5); { for(n=0,4, mm=matrix(n,n); for(k=0,n,T[1+n,1+k]=0); forvec(x=vector(n*n,i,[0,1]), for(i=1,n, for(j=1,n,mm[i,j]=x[i+n*(j-1)])); T[1+n,1+matrank(mm)]++); for(k=0,n,print1(T[1+n,1+k], if(k

Sum_{k=1..n} k * T(n,k) = A086875(n). - Alois P. Heinz, Jun 18 2022

More terms and PARI code from Michael Somos, Sep 25 2001
6 more terms from Lambert Klasen (Lambert.Klasen(AT)gmx.net), Dec 17 2004
More terms from Vladeta Jovovic, Mar 28 2006

A086906 Number of symmetric singular n X n (0,1) matrices over the reals.

Original entry on oeis.org

1, 4, 32, 496, 14172, 816684, 87982904, 18748545824, 7565600671504, 5940152086634096

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 19 2003

Cf. A046747, A086899, A086879, A086900, A118989, A118990, A118991, A118996, A119008, A119010.

Cf. A006125.

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

W. Edwin Clark computed the first entries.
a(6)-a(7) from Giovanni Resta, May 08 2006
a(8)-a(10) from Max Alekseyev, Jun 17 2025

A051752 Number of n X n (real) {0,1}-matrices having determinant A003432(n).

Original entry on oeis.org

1, 1, 3, 3, 60, 3600, 529200, 75600, 195955200, 13716864000

Offset: 0

Eric W. Weisstein

Eric Weisstein's World of Mathematics, Hadamard's Maximum Determinant Problem.
Eric Weisstein's World of Mathematics, (0, 1)-Matrix
Luke Zeng, Shawn Xin, Avadesian Xu, Thomas Pang, Tim Yang, Maolin Zheng, Seele's New Anti-ASIC Consensus Algorithm with Emphasis on Matrix Computation, arXiv:1905.04565 [cs.CR], 2019.
Miodrag Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.
Miodrag Zivkovic, Classification of small (0,1) matrices, Linear Algebra and its Applications, 414 (2006), 310-346.

Cf. A003432, A046747, A086264, A089478, A188895.

a(5) = 3600 from Daniel P. Corson (danl(AT)MIT.EDU), Jan 09 2000
a(6) = 529200, a(7) = 75600 from Ulrich Hermisson (uhermiss(AT)rz.uni-leipzig.de), Feb 25 2003
More terms from Miodrag Zivkovic (ezivkovm(AT)matf.bg.ac.yu), Feb 28 2006
a(0)=1 prepended by Alois P. Heinz, Dec 20 2023

A064231 Triangle read by rows: T(n,k) = number of rational (+1,-1) matrices of rank k (n >= 1, 1 <= k <= n).

Original entry on oeis.org

2, 8, 8, 32, 288, 192, 128, 6272, 36864, 22272, 512, 115200, 3456000, 18432000, 11550720, 2048, 1968128, 243302400, 6471168000, 36373708800, 25629327360, 8192, 32514048, 14809546752, 1557061632000, 43378316083200, 281770208133120

Offset: 1

N. J. A. Sloane, Sep 23 2001

Rows add to 2^(n^2) = A002416. - Jonathan Vos Post, Feb 27 2011

Komlos and later Kahn, Komlos and Szemeredi show that almost all such matrices are invertible.

			2; 8,8; 32,288,192; 128,6272,36864,22272; ...

J. Kahn, J. Komlos and E. Szemeredi: On the probability that a random +-1 matrix is singular, J. AMS 8 (1995), 223-240.
J. Komlos, On the determinants of random matrices, Studia Sci. Math. Hungar., 3 (1968), 387-399.

Cf. A064230, A000409, A000410, A046747.

T=matrix(4,4); { for(n=1,4, mm=matrix(n,n); for(k=1,n, T[n,k]=0); forvec(x=vector(n*n,i,[0,1]), for(i=1,n, for(j=1,n,mm[i,j]=(-1)^x[i+n*(j-1)])); T[n,matrank(mm)]++); for(k=1,n,print1(T[n,k], if(k

More terms and PARI code from Michael Somos, Sep 25 2001
More terms from Vladeta Jovovic, Apr 02 2006
Offset changed to 1 by T. D. Noe, Mar 02 2011

A086264 Number of real {0,1} n X n matrices having determinant=1.

Original entry on oeis.org

1, 1, 3, 84, 10020, 4851360, 9240051240, 67745781734400, 1883481284085791040

Offset: 0

Hugo Pfoertner, Oct 05 2003

Hugo Pfoertner, Determinants of (0,1)-matrices. FORTRAN program.
Minfeng Wang, C++ program
Eric Weisstein's World of Mathematics, (0,1)-Matrix.
Index entries for sequences related to binary matrices

Cf. A003024, A003432, A051752, A055165.

Cf. A046747.

a[n_] := Module[{M, iter, cnt = 0}, M = Table[a[i, j], {i, 1, n}, {j, 1, n}]; iter = Thread[{Flatten[M], 0, 1}]; Do[If[Det[M] == 1, cnt++], Evaluate[Sequence @@ iter]]; cnt];
Do[Print[n, " ", a[n]], {n, 1, 4}] (* Jean-François Alcover, Dec 09 2018 *)

a(0)=1 prepended by Alois P. Heinz, Jun 18 2022
a(7) from Minfeng Wang, Feb 09 2023
a(8) from Minfeng Wang, Apr 26 2024

cp's OEIS Frontend

A002884 Number of nonsingular n X n matrices over GF(2) (order of the group GL(n,2)); order of Chevalley group A_n (2); order of projective special linear group PSL_n(2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A055165 Number of invertible n X n matrices with entries equal to 0 or 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A000410 Number of singular n X n rational (0,1)-matrices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A000409 Singular n X n (0,1)-matrices: the number of n X n (0,1)-matrices having distinct, nonzero ordered rows, but having at least two equal columns or at least one zero column.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A056989 Number of nonsingular n X n (-1,0,1)-matrices (over the reals).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A064230 Triangle T(n,k) = number of rational (0,1) matrices of rank k (n >= 0, 0 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula