$Gx$ is distributed uniformly in the set $\Bbb Z_2 ^n$.

Question

I read the probabilistic proof of the Gilbert Varshamov bound in Coding Theory, and I came across the following argument, which I would like to discuss:

Suppose that $G$ is a random matrix in $M_ {n×k} (\Bbb Z_2) $. We fix a non zero element $x=(x_1,\dots,x_n)\in \Bbb Z_2^k$.

Then, the element $Gx$ is distributed uniformly in the set $\Bbb Z_2 ^n$.

My intuition says that as all the elements $a_{ij}$ of $G=(a_{ij}) \in M_{n×k} (\Bbb Z_2)$ are picked at random, any element has the form $y=Gx=(a_{11} x_1+\dotsb +a_{ 1k} x_k,\dots, a_{n1}x_1+\dotsb +a_{nk} x_k)$ is just a random element of $\Bbb Z_2^n$ and thus has equal probability of occurrence $1/2^n$.

Update: The proof uses that a random generator matrix $G$ of size ${\displaystyle k×n}$ contains ${\displaystyle kn}$ elements which are chosen independently and uniformly over the field $\mathbb {Z} _{2}$.

Is that correct? How could we show this more formally?

Answer 1

Since $(x_1,\ldots,x_n)$ is nonzero we can assume that at least one component, say $x_1$, is equal to $1.$

Clearly $x_1 U$ is equidistributed in $\mathbb{Z}_2$ if the random variable $U$ is equidistributed. Think of this $U$ as any random entry $a_{i,j}$ of the matrix.

Also clearly $x_1 U+c$ for any $c\in \mathbb{Z}_2$ is equidistributed. This is regardless of whether $c$ is deterministic or random with any distribution over $\mathbb{Z}_2$ since $x_1 U=U$ just flips the quantity $c$ between $0$ and $1$.

Finally any entry of $G x$ is of the form $x_1 U+c=U+c.$

Answer 2

Please feel free to judge my justification:

Let $G\in M_{k\times n}$ be a uniformly random full-rank $k \times n$ matrix. For all $m\in \Bbb F_q^k\setminus \{0\}$ the random variable $mG$ is uniformly distributed in $\Bbb F_q^n\setminus \{0\}$.

Let $y,y'\in \Bbb F_q^n\setminus \{0\}$. We show that $\Pr(mG=y)=\Pr(mG=y')$. Indeed, there exists an invertible matrix $M\in GL_k(\Bbb F_q)$ such that $y=My'$. Then, $$\Pr(mG=y)=\Pr(mGM=yM)=\Pr(mGM=y').$$ Moreover, since the map $A\overset{f}{\longmapsto} AM$ is a bijection from the set of full rank $k\times n$ matrices onto itself. So, $GM$ is a uniformly random full rank $k\times n$ matrix. Therefore, the probability that $mGM$ is equal to $y'$ is the same with the probability that $mG$ is equal to $y'$. Hence, $$\Pr(mGM=y')=\Pr(mG=y'),$$ so using the first lines $\Pr(mG=y')=\Pr(mGM=y')=\Pr(mG=y)$, as wanted.