Timeline for Probability a random matrix contains a short integer vector in its kernel
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 7, 2015 at 2:01 | history | edited | Igor Rivin | CC BY-SA 3.0 |
fixed bug
|
| Jul 6, 2015 at 21:44 | history | edited | Igor Rivin | CC BY-SA 3.0 |
added a comment on $m<n.$
|
| Jul 5, 2015 at 1:46 | comment | added | Igor Rivin | @dorothy well, if the matrix is nonsingular, it has no vectors in the kernel, so Tao-Vu gives an upper bound for the probability of having such a vector. I don't know how close their bound is to the truth, but it is certainly a NONTRIVIAL bound. Of course, it is only relevant for $m=n,$ since otherwise there is always a non-trivial kernel, but again, the OP did ask for $m\leq n,$ so this is relevant. | |
| Jul 4, 2015 at 19:13 | comment | added | Simd | The OP seems to be interested in non square matrices as well as vectors in the kernel with only integer components. Is the result if tao and vu relevant to that? | |
| Jul 4, 2015 at 3:06 | history | answered | Igor Rivin | CC BY-SA 3.0 |