Probability of sampling linearly independent vectors Let $q$ be a prime so that $\mathbb{Z}_q$  is a field. I would like to sample $n$ vectors independently and uniformly from $\mathbb{Z}^n_q$, to get a set $V = \{ v_i \}_{i=1}^n$.
What is the probability that $V$ is a basis for $\mathbb{Z}^n_q$? I had the following proof idea, by induction. The problem reduces to what is the probability of sampling $n$ linearly independent vectors, and as such, we proceed by induction on the number of sampled vectors $k$. For $k = 1$, we only require that we are not sampling the zero vector, and as such we have that $\Pr[\{v_1\} \text{is LI} ] = 1 - q^{-n}$. Now let us suppose that we have $k$ linearly independent vectors $\{ v_i \}_{i=1}^k$. We sample a new vector $v_{k+1}$. In order for it to be linearly independent, it must be that it is not a linear combination of the others, and as such there are at most $q^k$ possible 'forbidden' values. Namely these correspond to the possible coefficients $\alpha_i$ of the   linear combinations $\sum_{i=1}^k \alpha_i v_i$. So we have that $\Pr[\{v_i\}_{i=1}^{k+1} \text{is LI} \, | \, \{v_i\}_{i=1}^{k} \text{is LI}] \geq 1 - q^{k - n}$. As such we should have that
$$\Pr[\{v_i\}_{i=1}^n \text{is LI}] = \Pr[\{v_i\}_{i=1}^n \text{is LI} | \{v_i\}_{i=1}^{n-1} \text{is LI}] \Pr[\{v_i\}_{i=1}^{n-1} \text{is LI}] \geq \prod_{i=1}^n (1 - q^{i - n})$$
Do you think this analysis is correct? What I am also interested in is the following generalizations, on which I, unfortunately, had less success.

*

*Suppose we set $n=3k$ and that instead of sampling the vectors independently we sample three matrices $M, M_0, M_1 \in \mathbb{Z}^{3k\times k}_q$ such that each matrix is of full rank. What would be an upper bound on the probability of the columns of said matrices spanning $\mathbb{Z}_q^{3k}$? I have found in the literature (Lemma 8) a claim that it should be at least $1 - \frac{2k}{q}$ but have not found any good argument

*Let us relax the very first statement, and admit that $q$ could be composite. Does this change the argument significantly? I am interested in this result both in the vector case and in the three matrices sample case.

Thank you, I hope the formatting is clear enough :)
For context, I am investigating whether the construction in the linked paper would hold in nonprime order groups.
 A: Your analysis is correct. There is possibly a typo: $i$ should be $k$. Moreover, I think it is equality. More precisely, $\{v_i\}_{i=1}^{k+1} \text{is LI} \, | \, \{v_i\}_{i=1}^{k} \text{is LI}$ if and only if $v_{k+1}$ is not a linear combination of $v_1,\ldots,v_k$. The only thing that you need to make sure is that two different linear combinations of $\{v_i\}_{i=1}^{k}$ give rise to two different vectors, which would be true since $\{v_i\}_{i=1}^{k}$ is LI. Thus $\Pr[\{v_i\}_{i=1}^{k+1} \text{is LI} \, | \, \{v_i\}_{i=1}^{k} \text{is LI}] = \frac{q^n-q^k}{q^n}$.
If it is not a field (that is $q$ is composite) then the equality may not hold as two different linear combinations can give you the same vector. To see this take $q=6$, then $v_1=(1,0,0,0,0,0)', v_2=(5,2,0,0,0,0)$, note that here $v_1+v_2 = 4v_1+4v_2=(0,2,0,0,0,0)$.
The inequality that you wrote still holds (after the typo correction:)).
Matrix Case: write $M_0|M_1|M_2$ for the augmented $3k\times 3k$ matrix.
Now $M_0|M_1|M_2 \text{ is LD}$ if one of the columns in $M_1$ is linear combination of columns in $M_0$ or one of the column in $M_2$ is linear combination of columns in $M_0$ and $M_1$. Now probability that a fixed column in $M_1$ is linear combination of columns in $M_0$ is at most $\frac{q^k}{q^{3k}}\leq \frac{1}{q}$, and probability that a fixed column in $M_2$ is linear combination of columns in $M_0$ and $M_1$ is at most $\frac{q^{2k}}{q^{3k}}\leq \frac{1}{q}$. Therefore using union bound
$$
\mathbb{P}(M_0|M_1|M_2 \text{ is LD}) \leq  \frac{2k}{q}.
$$
You can see that this bound holds even if $q$ is not a prime.
A: If I am not mistaken, when $q$ is composite without squares, i.e., $q = \prod_{i = 1}^\kappa p_i$ for distinct primes $p_i$, you can use the Chinese Remainder Theorem to establish the probability that $n$ vectors of $\mathbb{Z}_q^n$ are linearly independent over $\mathbb{Z}_q$.
The reasoning is as follows. I denote by $\theta$ the CRT isomorphism from $\mathbb{Z}_q$ to the direct sum $\oplus_{i = 1}^\kappa \mathbb{Z}_{p_i}$ defined by  $\theta: x\mapsto (x \bmod p_1, \ldots, x \bmod p_{\kappa})$ . We can extend it to vectors coordinate-wise. I denote by $\mathbf{v}_1, \ldots, \mathbf{v}_n$ the vectors over $\mathbb{Z}_q^n$ and $\mathbf{v}_1^i, \ldots, \mathbf{v}_n^i$ their CRT residues over $\mathbb{Z}_{p_i}^n$, i.e, $\theta(\mathbf{v}_j) = (\mathbf{v}_j^1, \ldots, \mathbf{v}_j^\kappa)$. Since $\theta$ is an isomorphism we can prove the following result.
$$(\mathbf{v}_1, \ldots, \mathbf{v}_n) \text{ are }\mathbb{Z}_q\text{-linearly independent} \Leftrightarrow \forall i \in \{1, \ldots, \kappa\}, (\mathbf{v}_1^i, \ldots, \mathbf{v}_n^i) \text{ are }\mathbb{Z}_{p_i}\text{-linearly independent} $$

Proof: First assume that $(\mathbf{v}_1, \ldots, \mathbf{v}_n) \text{ are }\mathbb{Z}_q\text{-linearly independent}$. Let $i \in \{1, \ldots, \kappa\}$. Let $\mu_1, \ldots, \mu_n \in \mathbb{Z}_{p_i}^n$ such that $\sum_{j = 1}^n \mu_j \mathbf{v}_j^i = \mathbf{0} \bmod p_i$. For each $j \in \{1, \ldots, n\}$, define $\lambda_j = \theta^{-1}(0, \ldots, 0, \mu_j, 0, \ldots, 0)$ where $\mu_j$ is at position $i$. Then, we have
$$ \theta\left(\sum_{j = 1}^n \lambda_j \mathbf{v}_j\right) = \left(\mathbf{0}, \ldots, \mathbf{0}, \sum_{j = 1}^n \mu_j \mathbf{v}_j^i, \mathbf{0}, \ldots, \mathbf{0}\right) = (\mathbf{0}, \ldots, \mathbf{0})$$
and thus $\sum_{j = 1}^n \lambda_j \mathbf{v}_j = \mathbf{0} \bmod q$ as $\theta$ is injective. By assumption, we have that each $\lambda_j = 0 \bmod q$ and therefore $\mu_j = 0 \bmod p_i$. This proves the first implication. Reciprocally, assume that for each $i \in \{1, \ldots, \kappa\}$, the $(\mathbf{v}_1^i, \ldots, \mathbf{v}_n^i)$ are $\mathbb{Z}_{p_i}$-linearly independent. Let $\lambda_1, \ldots, \lambda_n \in \mathbb{Z}_q^n$ be such that $\sum_{j = 1}^n \lambda_j \mathbf{v}_j = \mathbf{0} \bmod q$. By applying $\theta$, we get that for all $i$,
$$ \sum_{j = 1}^n (\lambda_j \bmod p_i) \mathbf{v}_j^i = \mathbf{0} \bmod p_i$$
By assumption, it yields that for all $j$ and all $i$, $\lambda_j \bmod p_i = 0$.
Then, for all $j \in \{1, \ldots, n\}$,
$$\lambda_j = \theta^{-1}(\lambda_j \bmod p_1, \ldots, \lambda_j \bmod p_\kappa) = \theta^{-1}(0, \ldots, 0) = 0$$

Then, what you need before concluding is the fact that the CRT residues are independent and random over $\mathbb{Z}_{p_i}$. More precisely, you have that
if $x$ is a random variable is uniformly distributed over $\mathbb{Z}_q$, then the random variables $x \bmod p_1, \ldots, x \bmod p_\kappa$ are independent and uniformly distributed over their respective support $\mathbb{Z}_{p_i}$.

Proof: Take the random variable $x$ that is uniformly distributed over $\mathbb{Z}_q$. Denote by $\mathbf{x} = \theta(x)$ the random vector composed of the $x \bmod p_i$. Since $\theta$ is an isomorphism, it holds that $\mathbf{x}$ is uniformly distributed over $\oplus_{i = 1}^\kappa \mathbb{Z}_{p_i}$. Let $\mathbf{y}$ be the random vector over $\oplus_{i = 1}^\kappa \mathbb{Z}_{p_i}$ such that the coordinates are independent and uniform over each $\mathbf{Z}_{p_i}$ respectively. Let $\mathbf{z} \in \oplus_{i = 1}^\kappa$. It holds that
$$ \mathbb{P}_{\mathbf{x}}[\mathbf{x} = \mathbf{z}] = q^{-1} = \prod_{i = 1}^{\kappa} p_i^{-1} = \prod_{i = 1}^{\kappa} \mathbb{P}_{y_i}[y_i = z_i] = \mathbb{P}_{\mathbf{y}}[\mathbf{y} = \mathbf{z}]$$
Then, $\mathbf{x}$ and $\mathbf{y}$ are identical random vectors, which yields that the coordinates of $\mathbf{x}$ are independent and uniform over each $\mathbb{Z}_{p_i}$.

The second result generalizes to vectors coordinate-wise as well. Now, you can conclude:
\begin{align*}
&\mathbb{P}_{(\mathbf{v}_j)_{1\leq j \leq n}}[(\mathbf{v}_j)_{1\leq j \leq n} \text{ are }\mathbb{Z}_q\text{-linearly independent}] &\\
&= \mathbb{P}_{(\mathbf{v}_j)_{1\leq j \leq n}}[\forall i \in \{1, \ldots, \kappa\}, (\mathbf{v}_j^i)_{1\leq j \leq n} \text{ are }\mathbb{Z}_{p_i}\text{-linearly independent}] &\text{ (first result)}\\
&= \prod_{i = 1}^\kappa \mathbb{P}_{(\mathbf{v}_j^i)_{1\leq j \leq n}}[(\mathbf{v}_j^i)_{1\leq j \leq n} \text{ are }\mathbb{Z}_{p_i}\text{-linearly independent}] &\text{ (second result)} \\
&= \prod_{i = 1}^\kappa \prod_{j = 0}^{n-1} \left(1 - \frac{1}{p_i^{n - j}}\right) &\text{ (result for prime }p_i\text{)}
\end{align*}
This proves the result you want but only for $q$ composite without squares. If you have $q = \prod_{i = 1}^\kappa p_i^{\alpha_i}$, both of the results I used still work but with the residues in $\mathbb{Z}_{p_i^{\alpha_i}}$ which are no longer fields. So if you have the result for any prime power, you can use the same reasoning I did to get the result for all composite $q$.
