Probability of a matrix that is not full rank over the finite field

Question

The probability of a matrix that is not full rank over the finite field can be calculated as follows. \begin{equation} \Pr\left(\text{rank}(\mathbf{G})<k\right)=\sum_{\mathbf{w}\in\mathbb{F}^k_p,\mathbf{w}\neq0}\Pr\left({\mathbf{G}\mathbf{w}=\mathbf{0}}\right)=\frac{p^k-1}{p^n} \end{equation} where $\mathbf{G}\in \mathbb{F}^{n\times k}_p$, $k<n$

But I don't know why $\sum_{\mathbf{w}\in\mathbb{F}^k_p,\mathbf{w}\neq0}\Pr\left({\mathbf{G}\mathbf{w}=\mathbf{0}}\right)=\frac{p^k-1}{p^n}$. Can anybody show me the reason?

Answer 1

For any fixed $\mathbf{w}$, a uniformly random matrix $\mathbf{G}$ will by definition be such that the vector $\mathbf{G}\mathbf{w}$ is uniformly distributed in $\mathbb{F}_p^n$. Therefore, the probability that it is equal to any fixed vector $\mathbf{v}\in \mathbb{F}_p^n$ (and, in particular, to the zero vector $\mathbf{0}_n$ is $1/|\mathbb{F}_p^n|=1/p^n$.

Therefore, $$ \sum_{\mathbf{w}\in\mathbb{F}_p^k\setminus \{\mathbf{0}_k\}} \mathbb{P}\{\mathbf{G}\mathbf{w}=\mathbf{0}\} = \sum_{\mathbf{w}\in\mathbb{F}_p^k\setminus \{\mathbf{0}_k\}} \frac{1}{p^n} = \frac{p^k-1}{p^n} $$ as claimed, since $\lvert \mathbb{F}_p^k\setminus \{\mathbf{0}_k\}\rvert = p^k -1$.

Answer 2

This formula does not seem to be correct. According to the first formula of Section 3 in [1] it should be $$ \mathbb{P}(\mathrm{rank}(G)<k) = 1 - \prod_{j=0}^{k-1}\left(1-\frac{1}{2^{n-j}}\right). $$ E.g., in the special case of random $3 \times 2$ matrices over $\mathbb{F}_2$ ($n = 3$, $k = 2$ and $p = 2$), this is approximately 0.343, whereas your estimate gives $(2^{n-1}-1)/2^n = 0.375$.

[1] Blake, Ian F., and Chris Studholme. "Properties of random matrices and applications." Unpublished report available at http://www. cs. toronto. edu/~ cvs/coding (2006).