## Random projection and finite fields

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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)$?

-

Ilya, is this your homework in probability? Sounds like an advanced problem for serious students at MSU. – Wadim Zudilin May 4 2010 at 13:17
No. This fact would be useful for my research.  Our course in probability is not that advanced. – ilyaraz May 4 2010 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 2010 at 13:41
We consider linear dependence over $F_2$ of course. – ilyaraz May 4 2010 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 2010 at 14:14
show 1 more comment

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 25, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9236832857131958, "perplexity_flag": "head"}