login
A046747
Number of n X n rational {0,1}-matrices of determinant 0.
17
1, 10, 338, 42976, 21040112, 39882864736, 292604283435872, 8286284310367538176
OFFSET
1,2
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.
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]
EXAMPLE
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.
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 *)
PROG
(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
KEYWORD
hard,nonn,nice
AUTHOR
Günter M. Ziegler (ziegler(AT)math.tu-berlin.de)
EXTENSIONS
a(8) from Vladeta Jovovic, Mar 28 2006
STATUS
approved