20
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ What ring or field do the entries come from? What distribution on the entries are you assuming? $\endgroup$
    – Ben Weiss
    Jan 26, 2010 at 4:22
  • 1
    $\begingroup$ @Ben: The field is probably the reals. The OP specified the distribution: i.i.d. uniform on 0 and 1. $\endgroup$
    – aorq
    Jan 26, 2010 at 4:27
  • $\begingroup$ Thanks Charles, what's OP? $\endgroup$
    – Ben Weiss
    Jan 26, 2010 at 4:29
  • 1
    $\begingroup$ OP stands for Original Poster. $\endgroup$ Jan 26, 2010 at 4:48
  • 1
    $\begingroup$ I assume that is what Charles means by "on 0 and 1." Anyway, as for the original question it might be more interesting to compute the variance. $\endgroup$ Jan 26, 2010 at 5:26

7 Answers 7

32
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Previous version had many sign errors, I think they are fixed now. $\endgroup$ Jan 26, 2010 at 15:40
  • 5
    $\begingroup$ There is another simple proof based on Cauchy Binet theorem. Turan published (in Chinese) a formula for the sum of the 4th power. (I think there are simpler proof but I dont know a reference). I am not aware of a formula for higher powers. $\endgroup$
    – Gil Kalai
    Jan 26, 2010 at 16:15
  • $\begingroup$ see (mathoverflow.net/q/210666) $\endgroup$ Nov 9, 2017 at 8:04
  • $\begingroup$ I don't know what $\ell(v)$ stands for. I don't know what $i$ stands for in the sum over $u$. $\endgroup$ Feb 19, 2018 at 1:41
  • $\begingroup$ $\ell(v)$ is the length of the permutation $v$. In this case, it only appears in exponents: $(-1)^{\ell(v)}$ is the sign of $v$. $\endgroup$ Feb 19, 2018 at 2:58
45
$\begingroup$

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

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Update: the central limit theorem for the log-determinant was worked out carefully by Nguyen and Vu, arxiv.org/abs/1112.0752 $\endgroup$
    – Terry Tao
    Jul 2, 2015 at 15:46
  • $\begingroup$ How exactly was the Gaussian elimination carried over? I mean how can one get from (-1,+1) ran. matrix to another (0,1) ran. matrix $\endgroup$
    – Machinato
    Jun 12 at 23:36
  • 1
    $\begingroup$ By multiplying rows and columns by signs, one can normalise the first row and column to be all 1s. If one then subtracts the first row from all the others to make the first column (1,0,...,0), the bottom right n-1 x n-1 minor is now a random matrix of 0s and -2s, whose determinant is $(-2)^{n-1}$ times that of a random 0-1 matrix. The various sign factors one incurs in this process can then be removed by interchanging some rows (assuming $n>2$). $\endgroup$
    – Terry Tao
    Jun 13 at 15:56
11
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ The permanent isn't multiplicative. $\endgroup$ Jan 26, 2010 at 4:41
  • 1
    $\begingroup$ That's somewhat of a Freudian slip (since I typically use permanents rather than determinants). Thanks, I fixed it. $\endgroup$ Jan 26, 2010 at 4:54
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.