login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A046747 Number of n X n rational {0,1}-matrices of determinant 0. 16
1, 10, 338, 42976, 21040112, 39882864736, 292604283435872, 8286284310367538176 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

REFERENCES

J. Bourgain, V. Vu and P. M. Wood, On the Singularity Probability of Discrete Random Matrices, Journal of Functional Analysis, 258 (2010), 559-603.

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.

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

LINKS

Table of n, a(n) for n=1..8.

R. P. Brent and J. H. Osborn, Bounds on minors of binary matrices, arXiv preprint arXiv:1208.3330, 2012.

Eric Weisstein's World of Mathematics, Singular Matrix.

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

Index entries for sequences related to binary matrices

FORMULA

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

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

CROSSREFS

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

Cf. A000409, A002884, A056990, A056989, A046747, A055165, A002416.

Also a(n) + A055165(n) = 2^(n^2) = total number of n X n (0, 1) matrices, sequence A002416.

Sequence in context: A218996 A113082 A288684 * A006426 A029698 A197598

Adjacent sequences:  A046744 A046745 A046746 * A046748 A046749 A046750

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 06:06 EST 2018. Contains 317385 sequences. (Running on oeis4.)