Random matrices and pentagonal numbers

Here is a clever problem:

Let us fix n. Take at random, with uniform probability, a n \times n binary matrix (call it A).
Let: \gamma_n = P[\det_{Z_2}(A)=1].
(You can think of it as taking determinant of matrix normally and asking for a probability that it is odd number.)
Find the value of: \gamma = \lim_{n\to\infty} \gamma_n

(It’s not that gamma! Although, it is still related to Euler!)

Let’s clarify it by looking into some examples.

\gamma_1 = \frac{1}{2}
because
\begin{vmatrix} 1 \end{vmatrix} = 1
and
\gamma_2 = \frac{6}{16}
because
\begin{vmatrix} 1 & 0 \\ 0 & 1 \end{vmatrix} = \begin{vmatrix} 0 & 1 \\ 1 & 0 \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 0 & 1 \end{vmatrix} = \begin{vmatrix} 1 & 0 \\ 1 & 1 \end{vmatrix} = \begin{vmatrix} 0 & 1 \\ 1 & 1 \end{vmatrix} = 1

A few consecutive values are:
\gamma_1 = \frac{1}{2} = 0.5
\gamma_2 = \frac{3}{8} = 0.375
\gamma_3 = \frac{21}{64} = 0.328125
\gamma_4 = \frac{315}{1024} = 0.3076171875

Looks converging, doesn’t it?
For me, it is surprising that such a limit can be nontrivial, I would rather expect it to be either 1 or 0.

If we treat columns of matrix as binary vectors: A = (A_1 A_2 \ldots A_n) = \left( \begin{bmatrix} a_{1,1} \\ a_{2,1} \\ \vdots \\ a_{n,1} \end{bmatrix} \begin{bmatrix} a_{1,2} \\ a_{2,2} \\ \vdots \\ a_{n,2} \end{bmatrix} \dots \begin{bmatrix} a_{1,n} \\ a_{2,n} \\ \vdots \\ a_{n,n} \end{bmatrix}\right),

then \det_{Z_2}(A_1, A_2, \ldots A_n) = 1 iff the column vectors A_i are linearly independent (in a Z_2 world). So maybe we can look at this as we were taking at random n binary vectors?

But, (A_1,\ldots, A_{i+1}) are linearly independent, iff (A_1,\ldots,A_i) are, and A_{i+1} is not in the linear space spanned by (A_1,\ldots,A_i).
So by adding another vector, we can only break independence. If after i steps the vectors are still independent,
the linear space they span is of size 2^i, so we have 1 - \frac{1}{2^{n-i}} probability of success at next step.
(Why?)
That gives us:
\gamma_n = \prod_{i=1}^{n} \left(1-\frac{1}{2^i}\right) = \frac{1}{2} \cdot \frac{3}{4} \cdot \ldots \cdot \frac{2^n-1}{2^n}
\gamma = \prod_{i=1}^{\infty} \left(1-\frac{1}{2^i}\right) = \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{7}{8} \cdot \frac{15}{16} \ldots

So.. we are sure that the limit exists (decreasing sequence bounded from below is always converging), but we have no guarantee that the constant is non-trivial. And here starts the fun part!

Lets look at the function:

D(X) = \prod_{i=1}^{\infty} \left(1-X^i\right)

(if we skip some boring first terms)

D_3(X) = 1-X-X^2+X^4+X^5-X^6
D_4(X) = 1-X-X^2+2X^5-X^8-X^9+X^{10}
D_5(X) = 1 - X - X^2 + X^5 + X^6 + X^7 - X^8 - X^9 - X^{10} + X^{13} + X^{14} - X^{15}
D_6(X) = 1 - X - X^2 + X^5 + 2 X^7 - X^9 - X^{10} - X^{11} - X^{12} + 2 X^{14} + X^{16} - X^{19} - X^{20} + X^{21}

If we continue to multiply additional term (from now on), we’re unable to modify the terms earlier than X^7. So we know, that starting terms are:
D(X) = 1 - X - X^2 + X^5 + \ldots

Another observation states is that most of the terms vanish to 0, and rest are 1 and -1. (There happen to be 2, but it is in the are that haven’t stabilized yet.)

The function Q(X) = (1+X)(1+X^2)(1+X^3)\ldots = \prod_{i=1}^{\infty} (1+X^i),
as we recall from combinatorics course, is a generating function of a number of partitions without repetitions:
Q(X) = 1 + X + X^2 + X^3 + X\cdot X^2 + X^4 + X^5 + X^2\cdot X^3 + X\cdot X^4 + \ldots =
= 1 + X + X^2 + 2X^3 + X^4 + 3X^5 + \ldots

Our D(X) is also a generating function of a sequence of partitions without repetitions, but the one where we count partitions into even number of terms as +1, and into odd number of terms as -1. So for example:
12 = 1+2+3+6 = 1+2+4+5 = 1+2+9 = 1+3+8 = 1+4+7 = 1+5+6 = 1+11 = 2+3+7 = 2+4+6 = 2+10 = 3+4+5 = 3+9 = 4+8 = 5+7 = 12, so d_{12} = 1 + 1 - 1 - 1 -1 -1 + 1 - 1 - 1 + 1 - 1 + 1 + 1 + 1 - 1 = -1

And here real magic starts.
According to pentagonal number theorem, for almost every natural number, the number of odd and even partition is identical, so our term is 0. The proof is constructive one, shows a bijection (please click the link for pretty pictures, they enough to see the bijection). The proof fails for numbers known as pentagonal numbers.

Long story short (please, look at the proof at wikipedia page), we get:
D(X) = \sum_{k=-\infty}^{\infty} (-1)^k X^{p_k}
where p_k = \frac{k\cdot(3k-1)}{2}
is k-th pentagonal number (defined for both positive and negative k).So we can enumerate some more terms:
D(X) = 1 - X - X^2 + X^5 + X^7 - X^{12} - X^{15} + X^{22} + X^{26} - \ldots
And our magic constant can be written as:
\gamma = 1 - \frac{1}{2} - \frac{1}{4} + \frac{1}{32} + \frac{1}{128} - \frac{1}{4096} - \frac{1}{32768} + \frac{1}{4194304} + \frac{1}{67108864} - \ldots \approx 0.28878809511

Magic!

Advertisements

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 )

Google+ photo

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

Connecting to %s