The beautiful blending between linear algebra and probability

#Putnam 2016:http://www.artofproblemsolving.com/community/c375980_2016_putnam

As usual, I would write about a math contest that I took part (and passionate about). However now I would hand-pick one problem that I thought beautiful, mainly because it mixes both the concept of determinant/permutation and probability/expectation in an exquisite manner:

One big square, named A, is divided into identical smaller squares, such that there are equal number of squares each column and each row. Moreover, the number of squares in each row is even (so for example we have 2 times 2, 4 times 4, 6 times 6, and so on).  For every smaller square in A (henceforth named cell), we write either 0 or 1 onto it, such that there’s equal chance of we writing 0 or 1 in that square. Consider A’ as another big square, same size as A, formed by reflecting each cell across the diagonal joining the cell in the first row, first column and the last cell, last column (henceforth called main diagonal), and let B be the matrix formed by subtracting numbers in each cell of A by the number in corresponding cell of A’ (i.e. same coordinate). Considering all such possible B, what is the average value of determinant of B?

My approach examines each term in counting the determinant of B (valid because of linearity of expectations), with these observations:
-each number written in the main diagonal is 0
-for each number written in other cells, it has half of the chance of being 0, quarter of chance being 1 and quarter of chance being -1. Implication: the average number written is 0.
-for a cell C and its image C’ across the main diagonal, the number written on C is the negative of that of C’ (i.e. the sum of these two numbers is 0).
-for any two cells X and Y such that neither of them lies on main diagonal and such that X and Y are not the image of each other in the reflection across the main diagonal, the number written in X and that in Y has no impact on each other (we call these numbers independent).

(Terminology: term means the product of entries such that exactly one entry is picked from each row and each column. Factor means the individual cells in each term).

Here’s an illustration how the numbers in cells will look like when we have 4 times 4 squares:

a,b,c,d,e,f can be -1, 0, 1 with chances 1/4, 1/2, 1/4 respectively

In view of the first observation, we can omit those terms that involve any of the cells on the main diagonal. If, for some cell, its image is not in the equation (i.e. we picked a, d, f, -c as inside the diagram) then the every other cell chosen as the term are independent of this cell. Due to this independence we have:

Average of the term =average of the entry * average of the product of the rest of factor in this term.

Also the average value of each entry is 0, so average of this term is 0. We can then disregard this case.

Which terms do we need to care? The case when we choose nobody from the main diagonal and for each cell we choose, its image across the main diagonal is also chosen. Say, in the picture, we choose a, -a, f, -f. In this case, we are examining the average value of (-a^2)(-f^2). Now -a^2 and -f^2 each has half chance to be 0 and half chance to be -1, so af has quarter chance to be 1 (and the rest of chance 0). In general if we have 2n*2n grid then the term chosen has 1/2^n chance to be 1 for n even, or -1 for n odd, so the average is 1/2^n * (-1)^n. Also the permutation of the term has the same parity with n: n swaps from the identity permutation are involved (e.g. in the grid we have 4*4 grids so n=2, and the permutation a, -a, f, -f is definitely even since two swaps from the identity permutation are involved). So the expected value of this term in counting the determinant is actually 1/2^n.

Finally, how many such useful terms we have? It’s (2n Choose 2)*(2n-2 Choose 2)*…*(2 Choose 2)/n!. Reason: in terms of ordered pairs we have (2n Choose 2) ways to choose the first pair, then (2n-2 Choose 2) ways to choose the second pair, and the list goes on. Of course, each pair has been counted n! times (hence the division by n!) Summing up, the expected value, or the average, is (2n Choose 2)*(2n-2 Choose 2)*…*(2 Choose 2)/n! times 1/2^n which is (2n!)/(4^n).

Aside: this can never pass the eyes of a professional mathematician (at least I didn’t write in this manner during the contest) but I intend to make my wordings more accessible to general public (which also explains why I reword the problem).

1 thought on “The beautiful blending between linear algebra and probability

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s