Expected determinant of a random NxN matrix

Question

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 1

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 }u)}$$

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 2

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

Answer 3

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.

Answer 4

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.

5.64. a. [2+] Let $\mathcal D_n$ be the set of all $n\times n$ matrices of $+1$'s and $-1$'s. For $k\in\mathbb P$ let \begin{align*} f_k(n)&= 2^{-n^2} \sum_{M\in\mathcal D_n} (\det M)^k \\ g_k(n)&= 2^{-n^2} \sum_{M\in\mathcal D_n} (\operatorname{per} M)^k, \end{align*} where $\operatorname{per}$ denotes the permanent function defined by $$\operatorname{per}(m_{ij})= \sum_{n\in\mathfrak{S}_n} m_{1,\pi(1)} m_{2,\pi(2)} \dots m_{n,\pi(n)}.$$ Find $f_k(n)$ and $g_k(n)$ explicitly when $k$ is odd or $k=2$.
b. [3-] Show that $f_4(n)=g_4(n)$, and show that $$\sum_{n\ge 0} f_4(n) \frac{x^n}{n!} = (1-x)^{-3} e^{-2x}. \tag{5.120}$$ HINT. We have $$\sum_m (\det M)^4 = \sum_M \left(\sum_{\pi\in\mathfrak S_n} \pm m_{1,\pi(1)}\dots m_{n,\pi(n)}\right)^4.$$ Interchange the order of summation and use Exercise 5.63.
c. [2+] Show that $f_{2k}(n)<g_{2k}(n)$ if $k\ge 3$ and $n\ge 3$.
d. [3-] Let $\mathcal D'_n$ be the set of all $n\times n$ 0-1 matrices. Let $f'_k(n)$ and $g'_k(n)$ be defined analogously to $f_k(n)$ and $g_k(n)$. Show that $f'_k(n)=2^{-kn} f_k(n+1)$. Show also that \begin{align*} g'_1(n) &= 2^{-n} n!\\ g'_2(n) &= 4^n n!^2 \left(1+\frac1{1!}+\frac1{2!}+\dots+\frac1{n!}\right) \end{align*}

Answer 5

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 6

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 7

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