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
    @Martin: $q$ is the order of $F$?2011-01-17
  • 0
    @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}$.2011-01-17
  • 0
    @Trevor: I do not understand your comment. For example, $l$ might be larger than $q$.2011-01-17
  • 0
    For a lower bound, consider what happens when you apply some invertible matrix to your collection.2011-01-17
  • 0
    @Yuval: Any invertible matrix or a specific one?2011-01-17
  • 0
    @Martin: Any invertible matrix. You will get another collection (most of the time). Now you have to count in how many ways you can get any given collection, and a lower bound will follow (hopefully).2011-01-18
  • 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
    Thank you. That is interesting. I will ask the instructor if he really meant to ask that question as posed.2011-01-17
  • 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.$$