Let $A$ be a $2n \times 2n$ matrix with entries chosen independently at random. Each entry is chosen to be $0$ or $1$, each with probability $1/2$. Find the expected value of $\det(A - A^T)$ as a function of $n$.
Appeared in a class that prepares students for the Putnam exam, but we did not get to it.
On
Two partial results :
$$\text{for } \ n=2 : \mathbb{E}(\det(A-A^T))=\tfrac{3}{4}\tag{1a}$$
$$\text{for } \ n=3 : \mathbb{E}(\det(A-A^T))=\tfrac{15}{8}\tag{1b}$$
and a conjecture : on the basis of numerical simulations, the sequence of mathematical expectations looks to be :
$$e_2=\tfrac{3}{2^2}, e_3=\tfrac{3 \times 5}{2^3}, e_4=\tfrac{3 \times 5 \times 7}{2^4}, e_5=\tfrac{3 \times 5 \times 7 \times 9}{2^5}, \cdots$$
Proof of relationship (1a): (the method developed here can be extended to any - reasonably small - value of $n$).
$$B:=A-A^T=\begin{pmatrix}0&a&b&c\\-a&0&d&e\\-b&-d&0&f\\-c&-e&-f&0\end{pmatrix}\tag{2}$$
$$\det(B)=(\text{Pfaff}(B))^2 \ \ \text{where Pfaff}(B)=af-be+cd\tag{3}$$
(Pfaff denotes the Pfaffian : see https://en.wikipedia.org/wiki/Pfaffian where it is explained that the determinant of a skew-symmetric matrix of even order is always the square of a polynomial in the entries of the upper part of this matrix).
Let us determine step by step the distributions (i.e., probability density functions, abbreviated as pdf) of the different Random Variables (RV).
First of all, RVs $a,b,c,d,e,f$ are independent identically distributed (iid) with common distribution :
$$\begin{array}{|c|c|c|c|}\hline a&-1&0&1\\ \hline \mathbb{P}(a)&\tfrac14&\tfrac12&\tfrac14\\ \hline\end{array}\tag{4}$$
(belonging to the family of binomial distributions).
Now, the three RVs that one finds in (3), i.e., af, be and dc are iid with distribution given by (exercise !) :
$$\begin{array}{|c|c|c|c|}\hline af&-1&0&1\\ \hline \mathbb{P}(af)&\tfrac18&\tfrac68&\tfrac18\\ \hline\end{array}\tag{5}$$
Now we come to the RV $p:=af-be+dc$ ; being a sum of 3 iid RV, its pdf is obtained by convolving (at the power 3) the pdf of table (5), giving :
$$\begin{array}{|c|c|c|c|c|c|c|c|}\hline p&-3&-2&-1&0&1&2&3\\ \hline \mathbb{P}(p)&\tfrac{1}{512}&\tfrac{18}{512}&\tfrac{111}{512}&\tfrac{252}{512}&\tfrac{111}{512}&\tfrac{18}{512}&\tfrac{1}{512}\\ \hline\end{array}\tag{6}$$
The final pdf is for RV $p^2$ ; it is obtained from table (6):
$$\begin{array}{|c|c|c|c|c|}\hline p^2&0&1&2^2&3^2\\ \hline \mathbb{P}(p^2)&\tfrac{252}{512}&\tfrac{222}{512}&\tfrac{36}{512}&\tfrac{2}{512}\\ \hline\end{array}\tag{7}$$
And the result follows :
$$0 \times \tfrac{252}{512}+1 \times \tfrac{222}{512}+4 \times \tfrac{36}{512}+9 \times \tfrac{2}{512}=\tfrac{3}{4}\tag{8}$$
as announced in (1a).
Remark 1 : One can give a rule for obtaining the coefficients of the pfaffian. For example $(af-be+cd)$ in relationship (3) can be written under the form :
$$B_{12}B_{34}-B_{13}B_{24}+B_{14}B_{23}$$
where $(12)(34)$, $(13)(24)$ and $(14)(23)$ are the different permutations that can be written as products of permutations with disjoint support. This establishes a connection with the other solution by Achille Hui.
Remark 2 : We don't give a proof of (1b). But we would like to stress a point. If
$$B:=A-A^T=\begin{pmatrix}0&a&b&c&d&e\\-a&0&f&g&h&k\\-b&-f&0&l&m&n\\-c&-g&-l&0&o&p\\-d&-h&-m&-o&0&q\\-e&-k&-n&-p&-q&0\end{pmatrix}\tag{8},$$
its determinant is the square of this (Pfaffian) polynomial :
$$dgn - chn - egm + ehl - bgq + bhp + cfq - dfp + efo + ckm - dkl - bko + alq - amp + ano$$
with $15$ terms, precisely the numerator in relationship (1b), just as there were 3 terms in the first Pfaffian, ... not accidentaly (see remark 1, this time with permutations of the form $(..)(..)(..)$).
For a better understanding of the connection of these kind of permutations with double factorial generating sequence ($3,3\times 5 = 15, 3\times 5 \times 7 = 105,$ etc.), see this reference : (https://oeis.org/A001147).
We haven't attempted to reproduce the next Pfaffian, which has not less than... 105 terms...
Let $B = A - A^T$, we have $$\verb/E/[\det B] = \sum_{\sigma \in S_{2n}}(-1)^{\sigma}\verb/E/\left[\prod_{k=1}^{2n} B_{k\sigma(k)}\right]$$ where the sum on RHS is over $S_{2n}$, the collection of permutation $\sigma$ over $2n$ symbols.
By definition, the diagonal entries of $B$ are zero. Since the entries of $A$ are i.i.d., any two off-diagonal entries of $B$, $B_{ij}$ and $B_{k\ell}$, will be independent unless $(i,j) = (k,\ell)$ or $(\ell,k)$.
For any $\sigma \in S_{2n}$ such that $\sigma(\sigma(1)) \ne 1$, $B_{1\sigma(1)}$ will be independent of all entries appear in $\prod\limits_{k=2}^{2n} B_{k\sigma(k)}$. This implies
$$ \verb/E/\left[\prod_{k=1}^{2n} B_{k\sigma(k)}\right] = \verb/E/[B_{1\sigma(1)}]\cdot\verb/E/\left[\prod_{k=2}^{2n} B_{k\sigma(k)}\right] = 0\cdot \verb/E/\left[\prod_{k=2}^{2n} B_{k\sigma(k)}\right] = 0 $$
Apply similar argument to other $B_{k\sigma(k)}$ in the product $\prod\limits_{k=1}^{2n} B_{k\sigma(k)}$, we find the expectation value of the product is zero unless $\sigma$ is a product of $n$ transpositions.
There are $(2n-1)!!$ such permutations. It is easy to see all of them contribute same value to the determinant. One of such permutation $\sigma_0 = (12)(34)(56)\cdots(2n-1,n)$. We have
$$\verb/E/[B] = (-1)^{\sigma_0} (2n-1)!!\;\verb/E/\left[\prod_{k=1}^{2n}B_{k\sigma_0(k)}\right] = (-1)^n (2n-1)!!\; \verb/E/[B_{12}B_{21}]^n$$
Since $$\begin{align} \verb/E/[B_{12}B_{21}] &= \verb/E/[(A_{12}-A_{21})(A_{21}-A_{12})] = 2\left(\verb/E/[A_{12}]^2 - \verb/E/[A_{12}^2]\right)\\ &= 2\left(\frac1{2^2} - \frac12\right) = -\frac12\end{align}$$ We obtain $$\verb/E/[B] = \frac{(2n-1)!!}{2^n} = \frac{(2n)!}{4^nn!}$$ In particular, for $n = 2$ and $3$, this reduces to $\verb/E/[B] = \frac34$ and $\frac{15}{8}$, reproducing the result in another answer.