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.

Let $V$ be an $n$-dimensional $\mathbb F_2$ vector space. Note that $V$ has $2^n$ elements and $\mathcal P(V)$ has $2^{2^n}$.

I'm interested in the probability (under a uniform distribution) that an element of $\mathcal P(V)$ is a spanning set for $V$. Equivalently a closed form formula (or at least one who's asymptotics as $n\rightarrow \infty$ are easy to work out) for the number of spanning sets or non-spanning sets.

It's not hard to show that the probability is greater than or equal to $1/2$. Since any subset of size greater than $2^{n-1}$ must span the space. I calculated the proportion of spanning sets of size $n$ for $n$ up to $200$ which seem to be going to a number starting with $.2887$. This leads me to believe that the probability exceeds $1/2$. I couldn't nail down a formula for arbitrary sized subsets though to continue experimental calculations.

I feel like this is something that's been done before, but googling I've mostly found things concerning counting points on varieties over finite fields or counting subspaces of finite fields. Any references would be appreciated.

share|improve this question
    
I think it would be sufficient to count how many different bases you can have in V. Then multiply that number by all possibilities of adding elements to it, since that does not perturb the spanning property of the set. –  Raskolnikov Jul 17 '12 at 15:31
1  
@Raskolnikov The issue with that is avoiding duplicates. –  JSchlather Jul 17 '12 at 15:32
    
Indeed, you're right. –  Raskolnikov Jul 17 '12 at 15:33
add comment

2 Answers 2

up vote 13 down vote accepted

A random subset of $V$ is owerwhelmingly likely to span $V$.

Let's look at how hard it is for a random subset not to span $V$. In order not to span $V$, there must be an $(n-1)$-dimensional subspace that contains the entire subset. There are exactly $2^n-1$ such subspaces, since they are in bijective correspondence with the nontrivial linear maps $V\to\mathbb F_2$ (each subspace is the kernel of exactly one map).

For each fixed $(n-1)$ dimensional subspace, the probability for a random subset to stay within that subspace is $2^{-2^{n-1}}$, since the $2^{n-1}$ vectors outside the subspace must all randomly decide not to be in the subset.

So the probability for a random set not to span is at most $(2^n-1)2^{-2^{n-1}} < 2^{-(2^{n-1}-n)}$ (and this is slightly too high, because there are a few non-spanning subsets that have more than one proper subspace they fit into and so are counted twice here). Everything else spans.

Even for $n$ as small as $5$ the probability for a random subset to span $V$ is above 99.9%, and the number of 9's increases exponentially with larger $n$s.

share|improve this answer
1  
There are indeed $2^n - 1$ subspaces of dimension $n - 1$. There is a bijection with subspaces of dimension $1$, though not via the inner product. –  Zhen Lin Jul 17 '12 at 15:57
2  
I think the problem is that the probability that some set $S$ is not contained in some subspace $U$ is not independent of the probability that $S$ is not contained in some other subspace $U'$. –  Zhen Lin Jul 17 '12 at 16:01
2  
That works, and it's certainly enough to get the conclusion that the probability goes to $1$ as $n \to \infty$. –  Zhen Lin Jul 17 '12 at 16:08
3  
(+1 to Henning) @ZhenLin: A non-degenerate bilinear form gives that correspondence (as you probably noticed) between $(2^n-1)$ non-zero vectors (=1-dim. subspaces) and $(n-1)$-dimensional subspaces. IMHO the word orthogonal might still be used - with the caveat that a vector or a subspace may be orthogonal to itself. –  Jyrki Lahtonen Jul 17 '12 at 16:23
2  
@Jyrki: I think it is cleaner to speak of nonzero vectors in $V$ and $(n-1)$-dimensional subspaces in $V^{\ast}$ (their annihilators) as this correspondence is functorial and doesn't require the addition of extra structure. –  Qiaochu Yuan Jul 17 '12 at 20:18
show 5 more comments

It's worth mentioning that there is an explicit formula for the probability that $N$ random vectors drawn from $\mathbb{F}_q^n$ span. (Note: I am doing sampling with replacement. If you want to require the $N$ vectors to be distinct, you can do this using inclusion-exclusion, but the result will be much messier.) Of course, the answer is $0$ if $N<n$, so assume $N \geq n$.

Write down an $n \times N$ matrix whose columns are the vectors in question. Note that the following are equivalent:

  1. The columns span $\mathbb{F}_q^n$.
  2. The matrix has rank $n$.
  3. The rows are linearly independent.

Thinking in terms of rows, we have the new question: If we draw $n$ vectors at random from $\mathbb{F}_q^N$, what is the probability that they are linearly independent?

The probability that the first vector is nonzero is $1-q^{-N}$. Given that, the probability that the second vector is not in the span of the first is $1-q^{-N+1}$. Given that, the probability that the third vector is not in the span of the first two is $1-q^{-N+2}$. Continuing in this manner, the probability that $n$ vectors in $\mathbb{F}_q^n$ are independent is $$(1-q^{-N}) (1-q^{-N+1}) \cdots (1-q^{-N+n-1}).$$ And, by the above argument, this is also the probability that $N$ random vectors will span $\mathbb{F}_q^n$.

In particular, as Henning says, once $N-n$ is of any significant size, this is extremely close to $1$.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.