Maths Olympiad Prep

Library / /8 of 64

Algebra Difficulty 7.6 National olympiad, round 2 Find the answer

Let AA be a 2n×2n2n \times 2n matrix, with entries chosen independently at random. Every entry is chosen to be 0 or 1, each with probability 1/21/2. Find the expected value of det(AAt)\det(A-A^t) (as a function of nn), where AtA^t is the transpose of AA.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The expected value equals (2n)!4nn!. \frac{(2n)!}{4^n n!}. Write the determinant of AAtA-A^t as the sum over permutations σ\sigma of {1,,2n}\{1,\dots,2n\} of the product \sgn(σ)i=12n(AAt)iσ(i)=\sgn(σ)i=12n(Aiσ(i)Aσ(i)i); \sgn(\sigma) \prod_{i=1}^{2n} (A-A^t)_{i \sigma(i)} = \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σE_\sigma. Note that if we partition {1,,2n}\{1,\dots,2n\} into orbits for the action of σ\sigma, then partition the factors of the product accordingly, then no entry of AA appears in more than one of these factors; consequently, these factors are independent random variables. This means that we can compute Eσ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 m3m \geq 3, the corresponding factor contains 2m2m 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 Aiσ(i)Aσ(i)iA_{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σ=0E_\sigma = 0 unless σ\sigma acts with nn orbits of size 2. To compute EσE_\sigma in this case, assume without loss of generality that the orbits of σ\sigma are {1,2},,{2n1,2n}\{1,2\}, \dots, \{2n-1,2n\}; note that \sgn(σ)=(1)n\sgn(\sigma) = (-1)^n. Then EσE_\sigma is the expected value of i=1n(A(2i1)2iA2i(2i1))2\prod_{i=1}^n -(A_{(2i-1)2i} - A_{2i(2i-1)})^2, which is (1)n(-1)^n times the nn-th power of the expected value of (A12A21)2(A_{12} - A_{21})^2. Since A12A21A_{12} - A_{21} takes the values 1,0,1-1, 0, 1 with probabilities 14,12,14\frac{1}{4}, \frac{1}{2}, \frac{1}{4}, its square takes the values 0,10,1 with probabilities 12,12\frac{1}{2}, \frac{1}{2}; we conclude that Eσ=2n. E_\sigma = 2^{-n}. The permutations σ\sigma of this form correspond to unordered partitions of {1,,2n}\{1,\dots,2n\} into nn sets of size 2, so there are (2n)!n!(2!)n \frac{(2n)!}{n!(2!)^n} such permutations. Putting this all together yields the claimed result.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.