# How to prove randomly-generated high-dimensional $0$-$1$ vectors are probably independent?

Today our teacher told us that if you randomly generated ten 100-dimensional $0$-$1$ vectors, it's very unlikely that they are dependent in $\mathbb{R} ^ {100}$. To be specific, every entry has equal chance to be $0$ or $1$.

I have thought about this, but I can't get a nice upper bound for the probability that they are dependent. Can someone help me?

-
If you work over $\Bbb F_2$, the field with $2$ elements, the exact answer just follows from a straightforward combinatorial/linear algebra argument. I wonder if there is any "obvius" relation between the 2 situations. – Andrea Mori Jan 2 '13 at 11:36
It might at least work as an upper bound; you should write up the argument as an answer. – Eric Stucky Jan 2 '13 at 11:39

I assume stochastic independence.

Using determinants, we easily see that if the vectors are dependent over $\mathbb{R}$, then they (in fact, their projections) also are dependent over $\mathbb{F_2}=\mathbb{Z}/2\mathbb{Z}$. But the probability that 10 independent randomly choosen (with uniform probability) vectors of $(\mathbb{F}_2)^{100}$ are dependent over $\mathbb{F_2}$ is $$1 - \frac{(2^{100}-1)(2^{100} - 2)\times(2^{100}-2^9)}{(2^{100})^{10}}= 1 - \prod_{i=91}^{100} (1-2^{-i}) \leq 1 - (1-2^{-91})^{10} \leq 10\times 2^{-91}$$

(where we used Bernoulli's inequality $(1-p)^n \geq 1 - np$).

Note that this bound is very crude.

The passage from $\mathbb{R}$ to $\mathbb{F}_2$ is a special case of the following lemma:

Let $A$ be a $n\times m$ matrix with coefficients in $\mathbb{Z}$, and $p$ be a prime number. Note $\overline{A}$ the $n\times m$ matrix with coefficients in $\mathbb{F}_p$ given by $\overline{A}_{i,j} = A_{i,j} \bmod p$. We have, $\mathrm{rank}_\mathbb{R}\,A \geq \mathrm{rank}_{\mathbb{F}_p}\,\overline{A}$.

Proof. Remember that the rank of a matrix is the size of the largest non-vanishing minor. Furthermore, notice that for every square matrix $B$ with coefficients in $\mathbb{Z}$, we have $\det_\mathbb{R} B \in \mathbb{Z}$ and $$\det_{\mathbb{F_p}} (\overline{B}) = \det_{\mathbb{R}} (B) \bmod p$$ since the determinant is a polynomial function of the coefficients.

-
I'm sorry, I don't understand why they are also dependent over $\mathbb{F}_2$, could you give me an example?Thanks!! – cloudygoose Jan 2 '13 at 13:13
I made my answer more precise regarding this point. – Siméon Jan 2 '13 at 14:39
@cloudygoose: Being dependent over $\mathbb R$ requires that the sum be zero in each component. Being dependent over $\mathbb F_2$ just requires the sum to be even. So $(1,1)$ and $(1,-1)$ are dependent over $\mathbb F_2$, but not over $\mathbb R$ – Ross Millikan Jan 2 '13 at 14:56
While in principle, the coefficients of a nontrivial linear combination could be arbitrary reals, it is quite(?) clear that they can be chosen to be rational, hence also integer and relatively prime, i.e. at least one odd. Thus yo obtain also a nontrivial combination over $\mathbb F_2$ – Hagen von Eitzen Jan 2 '13 at 15:23

This is a thought. Let us stack all this vectors in the matrix $X$ whose size is $10 \times 100$. Your question is equivalent to asking if $X$ is a full-rank matrix. When is it full rank? One way is to look at its singular values, if the lowest singular value is non-zero, then it is full rank. What is the probability for this? Thus, you are looking at the distribution of the lowest singular value of a given random binary rectangular matrix. It is a continuous random variable. To see this, note that the lowest singular value of $X$ is the square root of the smallest eigenvalue of $X^TX$. Eigenvalues are a continuous function of the entries of the matrix.
So the probability that it will take a discrete point $0$ is zero. So the matrix should be full rank with probability one.
For $\{0,1\}$-valued matrices, I would need some convincing to believe that the singular value is continuously distributed. – Eric Stucky Jan 2 '13 at 11:02
"Eigenvalues are a continuous function of the entries of the matrix." Agreed. But the possibilities for the entries of the matrix are $0$ and $1$, which is a discrete set (in the subspace topology), and thus the domain of the function is discrete so a continuous function does not have a connected range. – Eric Stucky Jan 2 '13 at 11:25
There are $N=2^{100}-1$ such available vectors. After the first choice, your random generator will produce the same first vector with probability $1/N$. So it's hard to believe that the probability for a linearly independent set is $1$. – Andrea Mori Jan 2 '13 at 11:27