MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have, say, $n$ $2n$-dimensional linearly independent vectors over $\mathbb{F}_2$. We do a projection on a random $d$-dimensional subspace. We are interested in probability that images of our vectors will be linearly independent (over $\mathbb{F}_2$) too.

The question is as follows: how large $d - n$ should be if we want this probability to be, say, $1 - 1 / \mathrm{poly}(n)$?

share|cite|improve this question
Ilya, is this your homework in probability? Sounds like an advanced problem for serious students at MSU. – Wadim Zudilin May 4 '10 at 13:17
No. This fact would be useful for my research. Our course in probability is not that advanced. – ilyaraz May 4 '10 at 13:22
Then please clarify whether all objects (vectors, random $d$-dimensional subspaces) are with respect to ground field $\mathbb F_2$, or the 2-element field is needed to express the independence property. Even the latter option sounds strange, a better formulation of the problem would be helpful. – Wadim Zudilin May 4 '10 at 13:41
We consider linear dependence over $F_2$ of course. – ilyaraz May 4 '10 at 13:54
This is clear. Are the vectors from $\mathbb F_2^{2n}$? Is the subspace viewed as a subspace of $\mathbb F_2^{2n}$? – Wadim Zudilin May 4 '10 at 14:14
up vote 10 down vote accepted

Suppose the vectors are $e_1,\dots,e_n$. The kernel of projection onto a random subspace of dimension $n+r$ is a random subspace of dimension $n-r$, so you want the probability that such a subspace has trivial intersection with the span of $e_1,\dots, e_n$. Now just count the number of choices for a basis $v_1,\dots, v_{n-r}$ of such a space: $2^{2n} - 2^n$ for the first vector, then $2^{2n} - 2^{n+1}$ for the second, and so on. This is to be compared with $2^{2n} - 1$ choices for the first vector if one doesn't have an restriction, $2^{2n}-2$ for the second and so on.

So the probability of this happening is the ratio of these two quantities, which you need to find a good approximation for; a very brief back-of-an-envelope calculation suggested it's about $1 - c2^{-r}$, at least if $r$ is largeish. For your specific needs, then, $d - n$ should be about $C\log n$.

share|cite|improve this answer

Your Answer


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.