# Linear Independence of random binary vectors

Suppose we have $$Y_1, \ldots, Y_n \in \mathbb{R}^m$$, $$n$$ independent random vectors ($$m \geq n$$), where the entries of each $$Y_i$$ are i.i.d. Bernoulli random variables taking the values $$\{0, 1\}$$ with equal probability. I am interested in estimates for the probability that the $$Y_i$$'s are linearly independent over $$\mathbb{R}$$. Or more generally, for $$k \leq n$$, what is the probability that for all subsets $$S \subset [n]$$ of size $$k$$, that $$\{ Y_i : i \in S\}$$ are linearly independent.

I have found some references that answer related questions. This post has references that speak on the asymptotic probability of a random square $$\{0, 1\}$$ matrix being invertible: Number of invertible {0,1} real matrices?

Most notably it includes this reference ( https://arxiv.org/abs/0905.0461 ) that shows the probability that a $$n \times n$$ random $$\{0,1\}$$ matrix is singular is $$\mathcal{O}\left((\sqrt{\frac{1}{2}} + o(1))^n \right)$$. Using this I can get some crude asymptotic estimates, but I am searching for a non-asymptotic result ideally.

Similar problems have been investigated where the independence is instead over $$\mathbb{F}^2$$: Expected number of random binary vectors so that the form a basis

I am interested in any references that offer any tools that might help with this problem. I am most interested in the case when $$m$$ is a large constant multiple of $$n$$. Thank you.

• Nice fact: if $K$ is a subfield of $L$ and $S$ is a collection of vectors in $K^n$. Then $S$ is linearly independent over $K$ if and only if $S$ is independent over $L$. (Proof: consider the system of linear equations $\sum a_sx_s=0$ and write it as $Xa=0$ where $A$ is a $n\times |S|$ matrix with entries in $K$. Then the rank of $A$ over $K$ may be obtained by row reduction, but one obtains the same matrix if one row reduces over $L$). Hence you can just ask about independence over $\mathbb Q$. – Anthony Quas Jun 13 '19 at 4:48
• If $m$ is large relative to $n$ then the $\mathbb{F}^2$ answer is already quite small (should be on the order of $2^{n-m}$), and is also an upper bound for the answer over $\mathbb{R}$ – Kevin P. Costello Jun 13 '19 at 6:19
• @KevinP.Costello thank you; that would be great. I thought I was able to prove such a bound for a second, but I made a mistake. Do you have a reference or a sketch of an argument? I am probably missing something simple... – BenB Jun 14 '19 at 6:17
• If $v_1, \dots, v_k$ are independent, the probability that $v_{k+1}$ lies in their span is $2^{k-m}$. (This is the observation used by Douglas Zare in the linked answer; if your existing vectors form a $k$ dimensional space, there's $k$ coordinates that parameterize it, so $2^k$ vectors in the space out of $2^m$ total). Adding up over all $k$ and using the union bound, the probability that your vectors fail to be independent is at most $$\sum_{k=0}^{n-1} 2^{k-m} < 2^{n-m}$$ – Kevin P. Costello Jun 15 '19 at 20:09
• @KevinP.Costello Excellent thanks. I now understand completely. – BenB Jun 15 '19 at 21:02