Timeline for Linear Independence of random binary vectors
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2019 at 21:02 | comment | added | BenB | @KevinP.Costello Excellent thanks. I now understand completely. | |
| Jun 15, 2019 at 20:09 | comment | added | Kevin P. Costello | 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}$$ | |
| Jun 14, 2019 at 6:17 | comment | added | BenB | @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... | |
| Jun 13, 2019 at 6:19 | comment | added | Kevin P. Costello | 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}$ | |
| Jun 13, 2019 at 4:48 | comment | added | Anthony Quas | 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$. | |
| Jun 13, 2019 at 3:21 | history | edited | user64494 | CC BY-SA 4.0 |
The title is improved.
|
| Jun 13, 2019 at 0:01 | history | edited | BenB | CC BY-SA 4.0 |
added 80 characters in body
|
| Jun 12, 2019 at 23:50 | review | First posts | |||
| Jun 13, 2019 at 1:09 | |||||
| Jun 12, 2019 at 23:46 | history | asked | BenB | CC BY-SA 4.0 |