Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The expected mean determinant of random $n\times n$ matrices of $0$'s and $1$'s is $0$. What is the expected root mean square determinant? e.g. $\frac{\sqrt{3}}{2\sqrt{2}}$ for a $2\times 2$

share|cite|improve this question
1  
Actually rotating a matrix by $90$ degrees does not always change its sign. Works if the size is $2$ or $3$, but not if the size is $1$, $4$, $5$ (or even $0$), in general not for sizes $0$ or $1$ modulo $4$. – Marc van Leeuwen Feb 6 '12 at 10:19
    
$\frac38$ is the mean square determinant, not the root mean square determinant for $2\times2$. – joriki Feb 6 '12 at 23:29
up vote 10 down vote accepted

As you say, the expected mean determinant is zero:

$$ \def\expect#1{\left\langle#1\right\rangle} \begin{eqnarray} \expect{\det A} &=& \expect{\sum_\pi\sigma(\pi)\prod_iA_{i\pi(i)}} \\ &=& \sum_\pi\sigma(\pi)\expect{\prod_iA_{i\pi(i)}} \\ &=& \sum_\pi\sigma(\pi)\expect{\prod_iA_{ii}} \\ &=& \expect{\prod_iA_{ii}}\sum_\pi\sigma(\pi) \\ &=& 0\;. \end{eqnarray} $$

The expected mean squared determinant of an $n\times n$ matrix can be calculated similarly:

$$ \begin{eqnarray} \expect{(\det A)^2} &=& \expect{\left(\sum_\pi\sigma(\pi)\prod_iA_{i\pi(i)}\right)^2} \\ &=& \expect{\left(\sum_\pi\sigma(\pi)\prod_iA_{i\pi(i)}\right)\left(\sum_\rho\sigma(\rho)\prod_iA_{i\rho(i)}\right)} \\ &=& \expect{\sum_{\pi,\rho}\sigma(\pi)\sigma(\rho)\prod_iA_{i\pi(i)}\prod_iA_{i\rho(i)}} \\ &=& \expect{\sum_{\pi,\rho}\sigma(\pi^{-1}\rho)\prod_iA_{ii}\prod_iA_{i(\pi^{-1}\rho)(i)}} \\ &=& n!\expect{\sum_{\pi}\sigma(\pi)\prod_iA_{ii}\prod_iA_{i\pi(i)}}\;. \\ &=& n!\sum_{\pi}\sigma(\pi)\expect{\prod_iA_{ii}\prod_iA_{i\pi(i)}}\;. \end{eqnarray} $$

The expectation value in the last line has $n$ factors of $1/2$ from the diagonal elements and another factor of $1/2$ for each $i$ that is not a fixed point of $\pi$. Thus we have

$$ \begin{eqnarray} \expect{(\det A)^2} &=& \frac{n!}{2^n}\sum_\pi\sigma(\pi)M_{i\pi(i)} \\ &=& \frac{n!}{2^n}\det M \end{eqnarray} $$

with

$$M_{ij}=\begin{cases}\vphantom{\frac12}1&i=j\;,\\\frac12&i\ne j\;.\end{cases}$$

This matrix has $n-1$ eigenvalues of $1/2$ and one eigenvalue of $(n+1)/2$, and so

$$ \begin{eqnarray} \expect{(\det A)^2} &=& \frac{n!}{2^n}\frac{n+1}{2^n} \\ &=& \frac{(n+1)!}{2^{2n}} \end{eqnarray} $$

and

$$\sqrt{\expect{(\det A)^2}}=\frac{\sqrt{(n+1)!}}{2^n}\;,$$

in agreement with your result for $n=2$.

See also OEIS sequence A055137 for more on the connection to fixed points of permutations.

The calculation doesn't rely on the distribution of the matrix elements up to the point where we plug in the factors of $1/2$; evaluating the result for matrix elements uniformly chosen as $\pm1$ instead and noting that in this case any unpaired matrix element causes the expectation value to vanish, we obtain a mean squared determinant of $n!$ for a random matrix of $\pm1$s.

P.S.: Another way to evaluate

$$ \expect{(\det A)^2}=n!\sum_{\pi}\sigma(\pi)\expect{\prod_iA_{ii}\prod_iA_{i\pi(i)}} $$

just occurred to me. There are $\binom nk$ ways to choose $n-k$ fixed points for a permutation. The rest of the permutation is a derangement of $k$ objects, and in the inclusion-exclusion sum for the number of derangements,

$$ k! \sum_{i=0}^k \frac{(-1)^i}{i!} $$

(see the Wikipedia article), all terms except the last two count the same number of even and odd permutations, whereas the last two only count even permutations, so the excess of even over odd permutations in this sum is

$$ (-1)^k+(-1)^{k-1}k\;. $$

Thus

\begin{align} \expect{(\det A)^2}&=n!\sum_{\pi}\sigma(\pi)\expect{\prod_iA_{ii}\prod_iA_{i\pi(i)}}\\ &=\frac{n!}{2^n}\sum_{k=0}^n\binom nk\left((-1)^k+(-1)^{k-1}k\right)\left(\frac12\right)^k\\ &=\frac{n!}{2^n}\left(\left(\frac12\right)^n+n\left(\frac12\right)^n\right)\\ &=\frac{(n+1)!}{2^{2n}}\;, \end{align}

in agreement with the result obtained using the determinant.

share|cite|improve this answer
    
That the mean determinant is zero is perhaps even easier to see by symmetry. Let $A'$ be the matrix $A$ with the first two rows swapped. Then $\det A' = - \det A$. On the other hand, $A$ and $A'$ are identically distributed, so $\mathbb{E} \det A = \mathbb{E} \det A' = - \mathbb{E} \det A$. – Nate Eldredge Feb 7 '12 at 23:40
    
@Nate: Good point. As you can still see from Marc's comment, the question had originally contained a claim of proof by symmetry that turned out to be wrong. Yours is right, of course. My purpose in that first part wasn't so much to give the most elegant proof of the result for the mean determinant but to introduce the relabeling technique in a simpler setting with a known result before applying it to the question. – joriki Feb 8 '12 at 4:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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