Probability of Degenerate Random Matrix in Z(2)

The problem reduces to computing the number of ordered bases of \( V = F_2^n \). This can be done by choosing

• a vector \( b_1 \in V - span(0) \)
• a vector \( b_2 \in V - span(b_1) \)
• a vector \( b_3 \in V - span(b_1,b_2) \)
• and so on.

Considering that the number of \( n\times n \) matrices over \( F_2 \) is \( 2^{n^2} = (2^n)^n,\) we obtain

$\displaystyle \frac{\displaystyle \prod^{n-1} _{i=0}(2^n - 2^i)}{(2^n)^n} = \prod^{n-1} _{i=0}\left(1 - 2^{i-n}\right) = \prod _{j=1}^n\left(1 - \frac{1}{2^j}\right)$

as the probability of the random matrix to be nondegenerate.

The probability of a random matrix being degenerate is therefore

$\displaystyle 1 - \prod_{j=1}^n\left(1 - \frac{1}{2^j}\right).$

A non-degenerate matrix is a full rank matrix where none of the columns (or rows) can be written as a linear combination of the other columns (or rows).

Suppose there are $k$ non-zero linearly-independent vectors in a vector space defined over the modulo 2 field. There are $2^k-1$ distinct non-zero linear combinations of the $k$ vectors (A vector is either included or excluded in the linear combination and the pathological case of all vectors being excluded is removed).

Every column of the $n\times n$ matrix is a vector in this space. Let us first calculate the probability of constructing a non-degenerate matrix. Any column vector can be chosen in $2^n-1$ (the case of a null vector is excluded). Starting from the second vector, sequentially choose the remaining column vectors such that every new column vector is not a linear combination of the column vectors that have already been chosen. Thus, if the $k^{th}$ column (assuming zero based indexing) is being chosen, we have to exclude $2^k-1$ from $2^n-1$ possible vectors. Thus, the zeroth column can be chosen in $2^n-1$ ways, first in $2^n-2^1$ ways, second in $2^n-2^2$ ways and so on. Thus the probability of choosing a degenerate matrix is

$\displaystyle \begin{align} P&=1-\left(\frac{2^n-1}{2^n}\right)\left(\frac{2^n-2}{2^n}\right)... \left(\frac{2^n-2^{n-1}}{2^n}\right) \\ &=1-\left(1-\frac{1}{2}\right)\left(1-\frac{1}{2^2}\right)...\left(1-\frac{1}{2^n}\right) \end{align}$

This a problem from the 1976 student math competition at the Moscow State University. Solution 1 is by @erugli; Solution 2 is by Amit Itagi; Solution 3 is by N. N. Taleb.