Expected determinant of a random NxN matrix. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T12:20:50Z http://mathoverflow.net/feeds/question/13008 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix Expected determinant of a random NxN matrix. Jason Knight 2010-01-26T04:14:17Z 2010-06-09T21:03:14Z <p>What is the expected value of the determinant over the uniform distribution of all possible 1-0 NxN matrices? What does this expected value tend to as the matrix size N approaches infinity?</p> http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix/13010#13010 Answer by Bjorn Poonen for Expected determinant of a random NxN matrix. Bjorn Poonen 2010-01-26T04:32:37Z 2010-01-26T04:32:37Z <p>If $N \ge 2$, then the expected value is $0$ since interchanging two rows preserves the distribution but negates the determinant.</p> http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix/13012#13012 Answer by Douglas S. Stones for Expected determinant of a random NxN matrix. Douglas S. Stones 2010-01-26T04:33:43Z 2010-01-26T04:53:54Z <p>Is it not zero whenever $n \geq 2$? Let $A$ be a $n \times n$ permutation matrix with determinant $-1$ (which requires $n \geq 2$). Then the uniform distribution of a random $n \times n$ $(0,1)$-matrix $X$ is the same as the distribution of $AX$. The determinant is multiplicative, hence Det$(AX)=$Det$(A)$Det$(X)=-$Det$(X)$. Hence the probability of Det$(X)=x$ is the same as the probability of Det$(X)=-x$.</p> http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix/13014#13014 Answer by Mike Picollelli for Expected determinant of a random NxN matrix. Mike Picollelli 2010-01-26T04:55:25Z 2010-01-26T04:55:25Z <p>Unless I'm missing something, this also follows immediately from linearity and multiplicativity of expectation, treating each entry as independently $0-1$ with probability $1/2$. Every permutation yields the same expected value in the sum, $\pm (1/2)^n$ depending on sign, and the number of even and odd permutations is identical (for $n \ge 2$, as noted above).</p> <p>It's probably worth mentioning that an old result of Komlos shows that despite this, the probability the determinant is actually 0 is $o(1)$. </p> http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix/13040#13040 Answer by David Speyer for Expected determinant of a random NxN matrix. David Speyer 2010-01-26T13:26:04Z 2010-01-26T15:38:26Z <p>As everyone above has pointed out, the expected value is $0$.</p> <p>I expect that the original poster might have wanted to know about how big the determinant is. A good way to approach this is to compute $\sqrt{E((\det A)^2)}$, so there will be no cancellation.</p> <p>Now, $(\det A)^2$ is the sum over all pairs $v$ and $w$ of permutations in $S_n$ of <code>$$(-1)^{\ell(v) + \ell(w)} (1/2)^{2n-\# \{ i : v(i) = w(i) \}}$$</code></p> <p>Group together pairs $(v,w)$ according to $u := w^{-1} v$. We want to compute <code>$$(n!) \sum_{u \in S_n} (-1)^{\ell(u)} (1/2)^{2n-\# (\mbox{Fixed points of }i)}$$</code></p> <p>This is $(n!)^2/2^{2n}$ times the coefficient of $x^n$ in <code>$$e^{2x-x^2/2+x^3/3 - x^4/4 + \cdots} = e^x (1+x).$$</code></p> <p>So $\sqrt{E((\det A)^2)}$ is <code>$$\sqrt{(n!)^2/2^{2n} \left(1/n! + 1/(n-1)! \right)} = \sqrt{(n+1)!}/ 2^n$$</code> </p> http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix/13079#13079 Answer by Richard Stanley for Expected determinant of a random NxN matrix. Richard Stanley 2010-01-26T22:48:21Z 2010-01-26T22:48:21Z <p>For some further results of this nature, see Exercise 5.64 of <em>Enumerative Combinatorics</em>, vol. 2. This exercise deals with the uniform distribution on (0,1)-matrices or $(-1,1)$-matrices, but the arguments can be carried over to other distributions where the matrix entries are i.i.d. The proofs are similar to the argument in David Speyer's comment. </p> http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix/13087#13087 Answer by Gerhard Paseman for Expected determinant of a random NxN matrix. Gerhard Paseman 2010-01-27T00:42:00Z 2010-01-27T00:42:00Z <p>Miodrag Zivkovic has actually done a classification on small orders of 0-1 matrices by rank and absolute determinant value. You may be interested in the tables in his Arxiv paper <a href="http://arxiv.org/abs/math.CO/0511636" rel="nofollow">http://arxiv.org/abs/math.CO/0511636</a> .</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.01.26</p> http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix/27616#27616 Answer by Terry Tao for Expected determinant of a random NxN matrix. Terry Tao 2010-06-09T21:03:14Z 2010-06-09T21:03:14Z <p>It is a little more convenient to work with random (-1,+1) matrices. A little bit of Gaussian elimination shows that the determinant of a random n x n (-1,+1) matrix is $2^{n-1}$ times the determinant of a random n-1 x n-1 (0,1) matrix. (Note, for instance, that Turan's calculation of the second moment ${\bf E} \det(A_n)^2$ is simpler for (-1,+1) matrices than for (0,1) matrices, it's just n!. It is also clearer why the determinant is distributed symmetrically around the origin.)</p> <p>The log $\log |\det(A_n)|$ of a (-1,+1) matrix is known to asymptotically be $\log \sqrt{n!} + O( \sqrt{n \log n} )$ with probability $1-o(1)$; see <a href="http://www.ams.org/mathscinet-getitem?mr=2187480" rel="nofollow">this paper of Vu and myself</a>. A more precise result should be that the logarithm is asymptotically normally distributed with mean $\log \sqrt{(n-1)!}$ and variance $2 \log n$. This result was <a href="http://www.ams.org/mathscinet-getitem?mr=1453330" rel="nofollow">claimed by Girko</a>; the proof is unfortunately not quite complete, but the result is still likely to be true.</p>