probability of having linearly independent sparse vectors over finite fields

Question

Suppose that there are $i< N$ linearly independent $N$-dimensional vectors $\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i$ over a finite field $\mathbb{F}_q$, whose elements are denoted as $\{0,1,2,\ldots,q-1\}$. Each vector consists of exactly $m$ nonzero elements uniformly randomly chosen from $\{1,2,\ldots,q-1\}$, $m\ll N$. The nonzero coordinates of each vector are randomly located.

Now the question is, given a new such random $N$-dimensional vector $\mathbf{v}_{i+1}$, what is the probability that it is linearly independent with the previous $i$ vectors?

Best Regards.

Answer 1

These are some preliminary thoughts that are too long for a comment.

An equivalent question is: How many vectors with exactly $m$ nonzero entries are in the subspace generated by the first $i$ vectors? Then one just divides by $(q-1)^m\left(\begin{array}{c}N \\ m \end{array}\right)$ to get the probability. A naive guess is $\frac{(q-1)^m}{q^{N-i}} \left(\begin{array}{c}N \\ m \end{array}\right)$. A trivial lower bound is $i (q-1)$. A trivial upper bound is $q^i-1$.

I would guess that, as long as $m$ is reasonably large, for small $i$ the trivial lower bound is approximately correct, and for larger $i$ the naive guess is correct. All in all, the problem behaves very differently depending on the relative sizes of $i$, $m$, $N$, and, to a lesser extent, $q$. What regimes are you most interested in?

When $m$ is very small, we get some interesting behavior. For $m=1$, we can exactly compute the probability of linear independence - it is $(1-1/N)^{i}$. For $m=2$, we can see the $N$ elements as vertices of a graph and the $i$ vectors as edges. Then our new vector can be linearly dependent only if the two nonzero coordinates are connected to each other, or both connected to cycles. I think one can get accurate formulas without too much difficulty this way.

When the probability of a linear dependence among the $i$ vectors is sufficiently small, a good upper bound is provided by counting the expected number of ways to write a new vector as the sum of old vectors. One can write this a a sum over different ways to write a new vector as a sum of old ones, and try to find the largest terms. In particular for small $i$ I think only a couple of ways of writing a new vector as a sum of old ones will be dominant - most vectors of length $m$ that are sums of vectors of length $m$ will be sums of only $1$ or $2$ or $3$ vectors of length $m$. Then you would get a sequence of increasingly exact formulas.

The most important question is really how $i,m,$ and $N$ relate to each other. The problem is really very different for different values of that.

Answer 2

You might wanna take a look at the following papers by Calkin:

1. Dependent sets of constant weight binary vectors
2. Dependent sets of constant weight vectors in GF(q)