Putnam 2016, Problem B-4

Let \( A \) be a \( 2n \times 2n \) matrix, with entries chosen independently at random. Every 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 \)), where \( A^T \) is the transpose of \( A \).

Solution:
The expected value equals

$$\frac{(2n)!}{4^n n!}.$$

**First solution:**

Write the determinant of $A - A^t$ as the sum over permutations $\sigma$ of $\{1,\ldots,2n\}$ of the product

$$\operatorname{sgn}(\sigma) \prod_{i=1}^{2n} (A - A^t)_{i\sigma(i)} = \operatorname{sgn}(\sigma) \prod_{i=1}^{2n} (A_{i\sigma(i)} - A_{\sigma(i)i});$$

then the expected value of the determinant is the sum over $\sigma$ of the expected value of this product, which we denote by $E_\sigma$.

Note that if we partition $\{1,\ldots,2n\}$ into orbits for the action of $\sigma$, then partition the factors of the product accordingly, then no entry of $A$ appears in more than one of these factors; consequently, these factors are independent random variables. This means that we can compute $E_\sigma$ as the product of the expected values of the individual factors.

It is obvious that any orbit of size 1 gives rise to the zero product, and hence the expected value of the corresponding factor is zero. For an orbit of size $m \geq 3$, the corresponding factor contains $2m$ distinct matrix entries, so again we may compute the expected value of the factor as the product of the expected values of the individual terms $A_{i\sigma(i)} - A_{\sigma(i)i}$. However, the distribution of this term is symmetric about 0, so its expected value is 0.

We conclude that $E_\sigma = 0$ unless $\sigma$ acts with $n$ orbits of size 2. To compute $E_\sigma$ in this case, assume without loss of generality that the orbits of $\sigma$ are $\{1,2\},\ldots,\{2n-1,2n\}$; note that $\operatorname{sgn}(\sigma) = (-1)^n$. Then $E_\sigma$ is the expected value of $\prod_{i=1}^n -(A_{2i-1,2i} - A_{2i,2i-1})^2$, which is $(-1)^n$ times the $n$-th power of the expected value of $(A_{12} - A_{21})^2$. Since $A_{12} - A_{21}$ takes the values $-1,0,1$ with probabilities $\frac{1}{4},\frac{1}{2},\frac{1}{4}$, its square takes the values $0,1$ with probabilities $\frac{1}{2},\frac{1}{2}$; we conclude that

$$E_\sigma = 2^{-n}.$$

The permutations $\sigma$ of this form correspond to unordered partitions of $\{1,\ldots,2n\}$ into $n$ sets of size 2, so there are

$$\frac{(2n)!}{n!(2!)^n}$$

such permutations. Putting this all together yields the claimed result.

**Second solution:** (by Manjul Bhargava) Note that the matrix $A - A^t$ is skew-symmetric:

$$(A - A^t)^t = A^t - A = -(A - A^t).$$

The determinant of a $2n \times 2n$ skew-symmetric matrix $M$ is the square of the Pfaffian of $M$, which is a polynomial of degree $n$ in the entries of $M$ defined as follows. Define a perfect matching of $\{1,\ldots,2n\}$ to be a permutation of $\{1,\ldots,2n\}$ that is the product of $n$ disjoint transpositions. Then the Pfaffian of $M$ is given by

$$\sum_{\alpha} \operatorname{sgn}(\alpha) M_{i_1,j_1} \cdots M_{i_n,j_n} \quad (1)$$

where the sum is over perfect matchings $\alpha = (i_1,j_1)\cdots(i_n,j_n)$, and $\operatorname{sgn}(\alpha)$ denotes the sign of the permutation $\binom{1\ 2\ 3\ 4\ \cdots\ (2n-1)\ 2n}{i_1\ j_1\ i_2\ j_2\ \cdots\ i_n\ j_n}$. The determinant of $M$ is then the square of (1), i.e.,

$$\det(M) = \sum_{\alpha,\beta} \operatorname{sgn}(\alpha) \operatorname{sgn}(\beta) M_{i_1,j_1} \cdots M_{i_n,j_n} M_{i'_1,j'_1} \cdots M_{i'_n,j'_n} \quad (2)$$

where the sum is now over ordered pairs $(\alpha = (i_1,j_1)\cdots(i_n,j_n), \beta = (i'_1,j'_1)\cdots(i'_n,j'_n))$ of perfect matchings.

Taking $M = A - A^t$, so that $M_{ij} = A_{ij} - A_{ji}$, we wish to find the expected value of (2); again, this is the sum of the expected values of each summand in (2). Note that each $M_{ij}$ with $i < j$ is an independent random variable taking the values $-1,0,1$ with probabilities $\frac{1}{4},\frac{1}{2},\frac{1}{4}$, respectively.

Consider first a summand in (2) with $\alpha \neq \beta$. Then some factor $M_{ij}$ occurs with exponent 1; since the distribution of $M_{ij}$ is symmetric about 0, any such summand has expected value 0.

Consider next a summand in (2) with $\alpha = \beta$. This summand is a product of distinct factors of the form $M_{ij}^2$; from the distributions of the $M_{ij}$, we see that the expected value of each of these terms is $1/2^n$.

Since the total number of perfect matchings $\alpha$ is $(2n)!/(2^n n!)$, the expected value of (2) is therefore $(2n)!/(2^n n!) \cdot 1/2^n = (2n)!/(4^n n!)$, as desired.