2

There are only two entries, $0$ and $1$, over $\mathbb{Z}_2$. Thus, only $16$ possible $2\times 2$ matrices over $Z_2$, and $6$ of them have full rank:

$\begin{pmatrix}0&1\\ 1&0\end{pmatrix} \quad \begin{pmatrix}1&1\\ > 1&0\end{pmatrix} \quad \begin{pmatrix}0&1\\ 1&0\end{pmatrix} \quad > \begin{pmatrix}0&1\\ 1&1\end{pmatrix} \quad \begin{pmatrix}1&1\\ > 0&1\end{pmatrix} \quad \begin{pmatrix}1&0\\ 0&1\end{pmatrix}$

Randomly generate a $n\times n$ matrix over $\mathbb {Z}_2$ (where n is big, say, $1000$). What's the probability that the matrix has full rank?

I'd want to talk something regarding to this question.

I found the probability is equal to:

$\dfrac{(2^n-1)(2^n-2)(2^n-2^2)...(2^n-2^{n-1})}{2^n} \tag{1}$

On other hand, what's difference between $2^n$ and $2^{n^2}$?

$\dfrac{(2^n-1)(2^n-2)(2^n-2^2)...(2^n-2^{n-1})}{2^{n^2}} \tag{2}$

Can you tell whether or not I'm wrong?

Regards!

Busi
  • 572

1 Answers1

0

The second formula seems correct to me. The rows of the matrix must be linearly independent. The first row can be any vector but the zero vector, so there are $2^n-1$ choices. Suppose that $k$ linearly independent rows have been added. The next row can be any vector not in the linear span of the the first $k$ rows. Since these form a $k-$dimensional vector space over GF(2), there are $2^n-2^k$ choices for row $k+1.$

Since there are $2^{n^2}$ possible $n\times n$ matrices, the denominator should be $2^{n^2}$.

saulspatz
  • 53,131