5
$\begingroup$

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.

  • 0
    @Yuval: If q=2, then I can get ${i \choose 0} + {i \choose 1} + ... + {i \choose k-1}$ as an upper bound for the number of "forbidden vectors" when choosing the $(i+1)^{th}$ vector. Is this the kind of bound you meant? Is this expression less than ${i \choose k}$ for large i? (trying to simplify)2011-01-18

2 Answers 2

0

This is an open question in general, I think even asymptotically speaking. The question "is the number of ways zero or not" is equivalent to the linear coding question, since the distance of a linear code is equal to the minimal number of linearly dependent columns in the parity check matrix. See the Wikipedia entry for linear codes for more.

  • 0
    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.2011-01-18
0

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