Expected determinant of a random NxN matrix. - MathOverflow

Expected determinant of a random NxN matrix.

2010-01-26T04:14:17Z

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?

Answer by Bjorn Poonen for Expected determinant of a random NxN matrix.

2010-01-26T04:32:37Z

If $N \ge 2$, then the expected value is $0$ since interchanging two rows preserves the distribution but negates the determinant.

Answer by Douglas S. Stones for Expected determinant of a random NxN matrix.

2010-01-26T04:33:43Z

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$.

Answer by Mike Picollelli for Expected determinant of a random NxN matrix.

2010-01-26T04:55:25Z

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

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)$.

Answer by David Speyer for Expected determinant of a random NxN matrix.

2010-01-26T13:26:04Z

As everyone above has pointed out, the expected value is $0$.

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.

Now, $(\det A)^2$ is the sum over all pairs $v$ and $w$ of permutations in $S_n$ of $$(-1)^{\ell(v) + \ell(w)} (1/2)^{2n-\# \{ i : v(i) = w(i) \}}$$

Group together pairs $(v,w)$ according to $u := w^{-1} v$. We want to compute $$(n!) \sum_{u \in S_n} (-1)^{\ell(u)} (1/2)^{2n-\# (\mbox{Fixed points of }i)}$$

This is $(n!)^2/2^{2n}$ times the coefficient of $x^n$ in $$e^{2x-x^2/2+x^3/3 - x^4/4 + \cdots} = e^x (1+x).$$

So $\sqrt{E((\det A)^2)}$ is $$\sqrt{(n!)^2/2^{2n} \left(1/n! + 1/(n-1)! \right)} = \sqrt{(n+1)!}/ 2^n$$

Answer by Richard Stanley for Expected determinant of a random NxN matrix.

2010-01-26T22:48:21Z

For some further results of this nature, see Exercise 5.64 of Enumerative Combinatorics, 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.

Answer by Gerhard Paseman for Expected determinant of a random NxN matrix.

2010-01-27T00:42:00Z

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 http://arxiv.org/abs/math.CO/0511636 .

Gerhard "Ask Me About System Design" Paseman, 2010.01.26

Answer by Terry Tao for Expected determinant of a random NxN matrix.

2010-06-09T21:03:14Z

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

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 this paper of Vu and myself. 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 claimed by Girko; the proof is unfortunately not quite complete, but the result is still likely to be true.