# 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.

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)$$.
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.
• In fact, I just noticed that the reasoning for the inequality will not necessarily hold in the composite case. This can happen since $v_k$ not in span of LI $v_1, ... v_{k-1}$ is not enough for linear independence. For example, take (0, 2) mod 6 which is linearly dependent by itself. Jun 20 at 18:19