4
$\begingroup$

There are only two entries, $0$ and $1$, over $\mathbb{Z}_2$. Thus, only $16$ possible $2\times2$ matrices over $\mathbb{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?

$\endgroup$
  • $\begingroup$ the probability as a function of $n$ the size of the matrix stabilizes very quickly with the increase of $n$. For $n=11$ you already get the correct $3$ digits $\endgroup$ – Orest Bucicovschi May 28 '18 at 8:50
4
$\begingroup$

The general linear group $GL(n,q)$ is the group of invertible $n\times n$ matrices over a field with $q$ elements (note $q=p^k$ for some prime $p$).

The order of $$|GL(n,q)|=\prod_{k=0}^{n-1}(q^n-q^k)$$

So the probability is $$\dfrac{1}{q^{n^2}}\prod_{k=0}^{n-1}(q^n-q^k)$$

For $n=2$ $q=2$ you get $\frac{1}{2^4}(2^2-2)(2^2-1)=\frac{6}{16}$

$\endgroup$
  • 1
    $\begingroup$ My major is not math, and I am courious with two points. (1) Does the group $GL(n,q)$ include all invertible $n\times n$ matrices over $GF(p^k)$ ? (2) The conclusion of the order of $GL(n,q)$ can be found in an ordinary textbook of group theory? $\endgroup$ – foool May 28 '18 at 7:10
  • 1
    $\begingroup$ Yes GL(n,q) is all nxn invertible matrices over GF(q). It depends on the book, but usually. It's not actually that hard it's a basis counting argument over GF(q)^n. The number of nonzero vectors is (q^n-1). Then take a subspace spanned by the first vector you picked it has size q. So the number of vectors linearly independent from the first subspace is q^n-q. Now pick a vector from that set and then the subspace spanned by the first 2 vectors has size q^2. You can continue doing this till you have a basis. The total number of bases is the product and equal to the number of invertible matrices $\endgroup$ – N8tron May 28 '18 at 7:18
5
$\begingroup$

The probability that a random $n$-by-$n$ matrix over a field of $q$ elements is non-singular is $$P(n,q)=\prod_{k=1}^n\left(1-\frac1{q^k}\right).$$ To prove this, prove that the probability that the $k$-th row is linearly independent of the previous rows, conditional on those previous rows being linearly independent, is $1-1/q^{n+1-k}$.

As $n\to\infty$ for fixed $q$, $P(n,q)$ tends to a positive limit. Indeed $$\prod_{k=1}^\infty\left(1-\frac1{q^k}\right) =1-\frac1{q}-\frac1{q^2}+\frac1{q^5}+\frac1{q^7}-\cdots =1+\sum_{m=1}^\infty(-1)^m(q^{-m(3m-1)/2}+q^{{-m(3m+1)/2}})$$ by Euler's pentagonal number theorem. For large $n$, a few terms of this will give a good approximation to $P(n,q)$.

$\endgroup$
  • 1
    $\begingroup$ You can also prove $P(n,q)$ through reference to the size of $GL(n,q)$ through a tricky reverse reindexing: $$|GL(n,q)|=q^{n^2}\prod_{j=0}^{n-1}\left(1-q^{j-n}\right)=q^{n^2}\left(1-q^{-n}\right)\left(1-q^{1-n}\right)\cdots\left(1-q^{-1}\right)=q^{n^2}\prod_{k=1}^{n-1}\left(1-q^{-k}\right)$$ Thanks for the proof that $P(n,q)$ converges for a fixed $q$ I'd noticed that but had not proved it :) $\endgroup$ – N8tron May 28 '18 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.