1
$\begingroup$

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

Most notably this one: https://www.semanticscholar.org/paper/The-Number-of-Linearly-Independent-Binary-Vectors-Damelin-Michalski/15630b8ad6de8f245e5ea9c52a3a757bd98d701e

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – Anthony Quas
    Commented Jun 13, 2019 at 4:48
  • 1
    $\begingroup$ 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}$ $\endgroup$
    – Kevin P. Costello
    Commented Jun 13, 2019 at 6:19
  • $\begingroup$ @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... $\endgroup$
    – BenB
    Commented Jun 14, 2019 at 6:17
  • 1
    $\begingroup$ 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}$$ $\endgroup$
    – Kevin P. Costello
    Commented Jun 15, 2019 at 20:09
  • $\begingroup$ @KevinP.Costello Excellent thanks. I now understand completely. $\endgroup$
    – BenB
    Commented Jun 15, 2019 at 21:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .