# How many ways to choose $l$ vectors in $n$-dimensional space such that every $k$-subset is independent

Working in $F_q^n$. How many different ways do we have to choose $l$ vectors such that every subset of size $k$ of them is linearly independent. (Assume n is large)

My Progress: For the first k vectors, just keep out of the subspace spanned so far, so for $1 \leq i \leq k$ we have $q^n-q^{i-1}$ ways to choose the $i^{th}$ vector. But the next ones are harder.

Edit: Although the assignment asks me to find the exact number, a good lower bound can be helpful.

-
@Martin: $q$ is the order of $F$? –  PEV Jan 17 '11 at 16:57
@Martin: You first choose the $l$ vectors. So I think this is $\binom{q}{l}$. So perhaps the answer is $\binom{q}{l} \sum_{i=1}^{k} q^{n}-q^{i-1}$. –  PEV Jan 17 '11 at 17:01
@Trevor: I do not understand your comment. For example, $l$ might be larger than $q$. –  Jonas Meyer Jan 17 '11 at 19:04
For a lower bound, consider what happens when you apply some invertible matrix to your collection. –  Yuval Filmus Jan 17 '11 at 21:36
@Yuval: Any invertible matrix or a specific one? –  Martin Jan 17 '11 at 22:12

Note the proviso: "Assume n is large", so existence is not in doubt. A set of $l$ linearly independent vectors will have every $k$-subset of them linearly independent as well. –  hardmath Jan 18 '11 at 15:28
Consider some collection of vectors satisfying the requirements. If we apply any regular linear transformation, we get another collection satisfying the requirements. There are $$(q^n-1)\cdots(q^n-q^{n-1}) = q^{n^2} (1-q^{-n}) \cdots (1-q^{-1}) \geq c_q q^{n^2}$$ of these. However, we might get the same collection. Let us call two collections equivalent if there's a regular linear transformation mapping one to the other. This is an equivalence relation, so if we upper bound the size of an equivalence class, we will get a lower bound on the number of collections.
How many regular linear transformations can take a collection into itself? Choose some arbitrary $k$ vectors from the collection. These are mapped into some other $k$ vectors from the collections (less than $l^k$ possibilities). How many regular matrices map the former to the latter? Assuming that the first $k$ vectors where $e_1,\ldots,e_k$, the first $k$ rows of the matrix are forced, and for the rest we have $$(q^n-q^k)\cdots(q^n-q^{n-1}) \leq q^{n(n-k)}$$ possibilities. Thus an equivalence classes consists of at most $q^{n(n-k)} l^k$ regular matrices, and the resulting lower bound on the number of collections is $$\frac{c_q q^{n^2}}{q^{n(n-k)} l^k} = c_q \left(\frac{q^n}{l}\right)^k.$$