3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ I have taken the liberty to propose a less "neutral" title. This will attract more readers. I wish you don't object. $\endgroup$ – Jean Marie Nov 3 '19 at 11:26
  • $\begingroup$ Could you say if you have found a different way to solve this issue ? $\endgroup$ – Jean Marie Nov 14 '19 at 23:58
  • $\begingroup$ @JeanMarie I approached a postdoc at my university, he presented virtually the same proof as the accepted answer by achille. $\endgroup$ – PhysMath Nov 20 '19 at 23:04
  • $\begingroup$ Thanks. I thought at first that using the Pfaffian was useful but I am now convinced that achille hui's answer is the good one... $\endgroup$ – Jean Marie Dec 4 '19 at 8:15
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ [+1] Moreover, I just posted your result as a conjecture ! $\endgroup$ – Jean Marie Nov 3 '19 at 18:38
  • 1
    $\begingroup$ @JeanMarie I just saw that, I already upvoted your answer before your new data come in :-) $\endgroup$ – achille hui Nov 3 '19 at 18:42
  • $\begingroup$ I just found the Putnam 2016 "official" solution, very close to yours :( math.caltech.edu/~2016-17/1term/ma017/exams/…) $\endgroup$ – Jean Marie Nov 16 '19 at 9:02
2
$\begingroup$

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

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