A046747 Number of n X n rational {0,1}-matrices of determinant 0.
1, 10, 338, 42976, 21040112, 39882864736, 292604283435872, 8286284310367538176
Offset: 1
Examples
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.
Links
- 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
Programs
-
Mathematica
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 *) -
PARI
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
-
PARI
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
Formula
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]
Extensions
a(8) from Vladeta Jovovic, Mar 28 2006