5
$\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, 2019 at 11:26
  • $\begingroup$ Could you say if you have found a different way to solve this issue ? $\endgroup$
    – Jean Marie
    Nov 14, 2019 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$
    – SescoMath
    Nov 20, 2019 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, 2019 at 8:15

2 Answers 2

4
$\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, 2019 at 18:38
  • 1
    $\begingroup$ @JeanMarie I just saw that, I already upvoted your answer before your new data come in :-) $\endgroup$ Nov 3, 2019 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, 2019 at 9:02
3
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .