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

$D(X) = \sum_{k=-\infty}^{\infty} (-1)^k X^{p_k}$
where $p_k = \frac{k\cdot(3k-1)}{2}$
$D(X) = 1 - X - X^2 + X^5 + X^7 - X^{12} - X^{15} + X^{22} + X^{26} - \ldots$
$\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$