KAIST POW 2012-21 : Determinant of a random 0-1 matrix

Determinant of a random 0-1 matrix

 Let $n$ be a fixed positive integer and let $p\in(0,1)$. Let $D_n$ be the determinant of a random $n \times n$ 0-1 matrix whose entries are independent identical random variables, each of which is 1 with the probability $p$ and 0 with the probability $1-p$. Find the expected value and variance of $D_n$.

 

Proof. If $x$ is such a random variable, $E(x)=E(x^2)=p$.

If $n=1$, $D_n=x$. So $E(D_n)=E(x)=p$, $Var(D_n)=E(x^2)-E(x)^2 = p-p^2$.

Suppose $n\geq 2$. Then $D_n =\sum_{\sigma\in S_n} s(\sigma) a_{1\sigma(1)}\cdots a_{n\sigma(n)}=\sum_{\sigma\in S_n}A_\sigma$ where $A_\sigma=s(\sigma) a_{1\sigma(1)}\cdots a_{n\sigma(n)}$ and $s(\sigma)$ is a sign of $\sigma$.
Since entries are independent, $E(A_\sigma)=s(\sigma)p^n$, and $$E(D_n)=p^n \sum_{\sigma \in S_n}s(\sigma)=0$$
Note that $E(A_\sigma A_\tau)=s({\tau}^{-1}\sigma)p^{2n-i}$ where $i=|\{j|\sigma(j)=\tau(j)\}|$. If we take $\phi={\tau}^{-1}{\sigma} \in S_n$, this becomes $s(\phi)p^{2n-i_{\phi}}$ where $i_{\phi} = |\{j|\phi(j)=j\}|$ and there are $n!$ pair of $\sigma$, $\tau$ for each $\phi$.
Then $Var(D_n) = E(D_n^2)-E(D_n)^2 = E(D_n^2)=\sum_{\sigma, \tau \in S_n}E(A_\sigma A_\tau)=n!\sum_{\phi\in S_n}s(\phi)p^{2n-i_{\phi}}=n! p^{2n} \sum_{\phi \in S_n}s(\phi)p^{-i_{\phi}}$.
The summation term is clearly the determinant of a matrix with 1/p for all diagonals and 1 for others.
To compute this, subtracting 1st row to other rows,
$$ \left| \begin{array}{ccccc}\frac{1}{p} & 1 & 1 & \ldots & 1\\ 1-\frac{1}{p} & \frac{1}{p}-1 & 0 & \ldots & 0\\1-\frac{1}{p} & 0 & \frac{1}{p}-1 & \ldots & 0\\ \vdots & \vdots & & \ddots & 0 \\ 1-\frac{1}{p} & 0 & \vdots & & \frac{1}{p}-1 \\ \end{array} \right| $$
Pulling out $\frac{1}{p}-1$, and subtracting other rows to 1st row, it becomes
$$\left(\frac{1}{p}-1\right)^{n-1}\left| \begin{array}{ccccc} \frac{1}{p} + n-1 & 0 & 0 & \ldots & 0\\ -1 & 1 & 0 & \ldots & 0\\ -1 & 0 & 1 & \ldots & 0\\ \vdots & \vdots & & \ddots & 0 \\ -1 & 0 & \vdots & & 1 \\ \end{array} \right| =n\left(\frac{1}{p}-1\right)^{n-1}+\left(\frac{1}{p}-1\right)^n$$
Therefore, $Var(D_n)=n!p^{2n}\left[n\left(\frac{1}{p}-1\right)^{n-1}+\left(\frac{1}{p}-1\right)^n\right]$.