A000410 -id:A000410 - cp's OEIS frontend

A173760 Partials sums of A000410.

0, 0, 6, 431, 66056, 27960727, 35744362616, 144901919316449

Offset: 1

Jonathan Vos Post, Feb 23 2010

Partials sums of number of singular n X n rational (0,1)-matrices. The subsequence of primes in this partial sum begins: 431.

			a(8) = 0 + 0 + 6 + 425 + 65625 + 27894671 + 35716401889 + 144866174953833.

Cf. A000409, A000410, A046747, A064230, A064231.

a(n) = SUM[i=0..n] A000410(i).

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

Original entry on oeis.org

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

A046747 Number of n X n rational {0,1}-matrices of determinant 0.

Original entry on oeis.org

1, 10, 338, 42976, 21040112, 39882864736, 292604283435872, 8286284310367538176

Offset: 1

Günter M. Ziegler (ziegler(AT)math.tu-berlin.de)

			a(2)=10: the matrix of all 0's, 4 matrices with 2 zeros in the same row or column, 4 matrices with 3 zeros and the all-1 matrix.

J. Bourgain, V. Vu and P. M. Wood, On the Singularity Probability of Discrete Random Matrices, Journal of Functional Analysis, 258 (2010), 559-603.
R. P. Brent and J. H. Osborn, Bounds on minors of binary matrices, arXiv preprint arXiv:1208.3330 [math.CO], 2012.
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 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.
Eric Weisstein's World of Mathematics, Singular Matrix.
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, A000410, A002416, A002884, A046747, A055165, A056989, A056990.

Sum[KroneckerDelta[Det[Array[Mod[Floor[k/(2^(n*(#1-1)+#2-1))],2]&,{n,n}]],0],{k,0,(2^(n^2))-1}] (* John M. Campbell, Jun 24 2011 *)
Count[Det /@ Tuples[{0, 1}, {n, n}], 0] (* David Trimas, Sep 23 2024 *)

A046747(n) = m=matrix(n,n); ct=0; for(x=0,2^(n*n)-1,a=binary(x+2^(n*n)); for(i=1,n, for(j=1,n,m[i,j]=a[n*i+j+1-n])); if(matdet(m)==0,ct=ct+1,); ); ct \\ Randall L Rathbun

a(n)=sum(i=0,2^n^2-1,matdet(matrix(n,n,x,y,(i>>(n*x+y-n-1))%2))==0) \\ Charles R Greathouse IV, Feb 21 2015

a(n) = 2^(n^2) - n! * binomial(2^n -1, n) + n! * A000410(n).
a(n) + A055165(n) = 2^(n^2) = total number of n X n (0, 1) matrices.
The probability that a random n X n {0,1}-matrix is singular is conjectured to be asymptotic to C(n+1, 2)*(1/2)^(n-1). [Corrected by N. J. A. Sloane, Jan 02 2007]

a(8) from Vladeta Jovovic, Mar 28 2006

A116532 Number of singular n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

Original entry on oeis.org

0, 0, 3, 285, 50820, 23551920, 31898503077, 134251404794199

Offset: 1

Vladeta Jovovic, Apr 03 2006

Cf. A000410, A116506, A116527.

Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763

a(n) = A054780(n) - A088389(n).

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

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

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

A116506 Number of singular n X n rational {0,1}-matrices with no zero rows.

Original entry on oeis.org

0, 3, 169, 28065, 16114831, 33686890209, 262530190180063, 7717643584470877185

Offset: 1

Vladeta Jovovic, Apr 03 2006

Cf. A000410, A116507, A116527, A116532.

a(n) = A055601(n) - A055165(n).

A116527 Number of singular n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct and all columns distinct, up to permutation of rows.

Original entry on oeis.org

0, 0, 0, 75, 22365, 13303500, 21058940420, 98692672142610

Offset: 1

Vladeta Jovovic, Apr 03 2006

Cf. A000409, A000410, A116506, A116507, A116532.

a(n) = A094000(n) - A088389(n).

Conjecture: a(n) = A000410(n) - A000409(n-1) for n>1. - Jean-François Alcover, Jan 08 2020

A116507 Number of singular n X n rational {0,1}-matrices with no zero rows or columns.

Original entry on oeis.org

0, 1, 91, 18943, 12483601, 28530385447, 235529139302185, 7183142489571818623

Offset: 1

Vladeta Jovovic, Apr 03 2006

Cf. A000410, A116506, A116527, A116532.

a(n) = A048291(n) - A055165(n).

cp's OEIS Frontend

A173760 Partials sums of A000410.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A046747 Number of n X n rational {0,1}-matrices of determinant 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A116532 Number of singular n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

Views

Author

Keywords

Crossrefs

Formula

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

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

Extensions

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

Views

Author

Keywords

Comments

Examples

References