Does a random matrix over $\mathbb{Z}_q$ map linearly independent vectors to statistically independent vectors?

Question

Suppose $A \in \mathbb{Z}_q^{n \times m}$ is a random $n \times m$ matrix whose entries are i.i.d. uniform over $\mathbb{Z}_q=\mathbb{Z}/q\mathbb{Z}$, where $q\geq2$. Let $\mathbf{x}_1, \ldots, \mathbf{x}_r \in \mathbb{Z}_q^m$ be fixed linearly independent vectors (meaning that there exist no $\alpha_1, \ldots, \alpha_r \in \mathbb{Z}_q$ such that at least one them is nonzero and $\sum_{i=1}^r\alpha_i \mathbf{x}_i = \mathbf{0}$), and consider the random vectors $A\mathbf{x}_1, \ldots, A\mathbf{x}_r \in \mathbb{Z}_q^n$.

Question: Are $A\mathbf{x}_1, \ldots, A\mathbf{x}_r$ statistically independent, i.e., is it true that $\operatorname{Pr}\left[A\mathbf{x}_1=\mathbf{y}_1, \ldots, A\mathbf{x}_r=\mathbf{y}_r\right] = \prod_{i=1}^r \operatorname{Pr}\left[A\mathbf{x}_i=\mathbf{y}_i\right]$ for every $\mathbf{y}_1, \ldots, \mathbf{y}_r \in \mathbb{Z}_q^n$? If so, how does one prove this formally?

Motivation: Say $q$ is a prime, and so $\mathbb{Z}_q$ is a field. If $\mathbf{x}_1, \ldots, \mathbf{x}_r$ are not linearly independent, then $A\mathbf{x}_1, \ldots, A\mathbf{x}_r$ are certainly not statistically independent. For example, if $\mathbf{x}_2 = \alpha \mathbf{x}_1$, then $\operatorname{Pr}\left[A\mathbf{x}_2 \neq \alpha\mathbf{y} | A\mathbf{x}_1 =\mathbf{y} \right] = 0$. I was wondering if the opposite statement is also true. And also, if it is true when $\mathbb{Z}_q$ is not a field (I don't know if something weird can happen when $\mathbb{Z}_q$ has zero divisors).

Answer 1

This is basically the argument in Sean Eberhard’s comment posted while I was writing this answer.

Note that the condition on $A$ is exactly the same as: $A$ follows a uniform distribution on $\mathcal{M}_{n,m}(\mathbb{Z}/q\mathbb{Z})$.

By your assumptions, there is a matrix $X \in GL_m(\mathbb{Z}/q\mathbb{Z})$ such that $Xe_i=x_i$ for each $1 \leq i \leq r$, where $(e_1,\ldots,e_m)$ is the canonical basis for $(\mathbb{Z}/q\mathbb{Z})^{\oplus m}$.

So the question you are asking is: are the random vectors $AXe_i$ for $1 \leq i \leq r$ independent?

Since $X$ is invertible, $B=AX$ also follows a uniform distribution on $\mathcal{M}_{n,m}(\mathbb{Z}/q\mathbb{Z})$, so that its entries are iid uniformly in $\mathbb{Z}/q\mathbb{Z}$.

But the vector $Be_i$ only depends on the entries $B_{\ast,i}$ for each $i$, so that the vectors $Be_i$ are independent random variables.