Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@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

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer
    
Thank you. That is interesting. I will ask the instructor if he really meant to ask that question as posed. –  Martin Jan 17 '11 at 22:07
    
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.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.