most recent 30 from http://mathoverflow.net 2013-05-22T06:55:27Z http://mathoverflow.net/feeds/question/18636 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices Tony Huynh 2010-03-18T18:49:59Z 2012-03-23T11:28:07Z

<p>This question is inspired from <a href="http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix" rel="nofollow">here</a>, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$. </p> <p>My question is: how many such matrices have non-zero determinant? </p> <p>If we instead view the matrix as over $\mathbb{F}_2$ instead of $\mathbb{R}$, then the answer is </p> <p>$(2^n-1)(2^n-2)(2^n-2^2) \dots (2^n-2^{n-1}).$</p> <p>This formula generalizes to all finite fields $\mathbb{F}_q$, which leads us to the more general question of how many $n \times n$ matrices with entries in { $0, \dots, q-1$ } have non-zero determinant over $\mathbb{R}$? </p>

http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices/18639#18639 Michael Lugo 2010-03-18T19:04:41Z 2010-03-18T19:04:41Z

<p>See <a href="http://www.research.att.com/~njas/sequences/A046747" rel="nofollow">Sloane, A046747</a> for the number of singular (0,1)-matrices. It doesn't seem like there's an exact formula, but it's conjectured that the probability that a random (0,1)-matrix is singular is asymptotic to $n^2/2^n$.</p> <p>Over $F_2$ the probability that a random matrix is nonsingular, as $n \to \infty$, approaches the product $(1/2)(3/4)(7/8)\cdots = 0.2887880951$, and so the probability that a random large matrix is singular is only around 71 percent. I should note that a matrix is singular over $F_2$ if its real determinant is even, so this tells us that determinants of 0-1 matrices are more likely to be even than odd. </p>

http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices/18676#18676 Kevin P. Costello 2010-03-18T22:49:07Z 2010-03-18T22:49:07Z

<p>As Michael noted, the conjectured bound for the probability a random $(0,1)$ matrix is singular is conjectured to be $(1+o(1)) n^2 2^{-n} $. This corresponds to the natural lower bound coming from the observation that if a matrix has two equal rows or columns it is automatically singular. </p> <p>The best bound currently known for this problem is $(\frac{1}{\sqrt{2}} + o(1) )^n$, and is due to <a href="http://arxiv.org/abs/0905.0461" rel="nofollow">Bourgain, Vu, and Wood</a>. Corollary 3.3 in their paper also gives a bound of $(\frac{1}{\sqrt{q}}+o(1))^n$ in the case where entries are uniformly chosen from ${0, 1, \dots, q-1}$ (here the conjectured bound would be around $n^2 q^{-n})$</p> <p>Even showing that the determinant is almost surely non-zero is not easy (this was first proven by Komlos in 1967, and the reference is given in Michael's Sloane link). </p>

http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices/91999#91999 Tony Huynh 2012-03-23T11:28:07Z 2012-03-23T11:28:07Z

<p>Lurking around MO, I found a question which is related to the second part of my question. Namely, Greg Martin and Erick B. Wong prove that assuming that the entries of an $n \times n$ matrix are chosen randomly with respect to a uniform distribution from the set {$-k, -k + 1 \cdots, -1, 0, 1, \cdots, k-1, k$}, then the probability that the resulting matrix will be singular is $\ll k^{-2 + \epsilon}$. </p> <p>See this <a href="http://mathoverflow.net/questions/90591/singular-matrices-with-integer-entries" rel="nofollow">MO question</a> (where the above paragraph is plagarized from) and also <a href="http://www.math.ubc.ca/~gerg/papers/downloads/AAIMHNIE.pdf" rel="nofollow">here</a> for the link to the Martin, Wong paper. </p>