Resilience of the rank of random matrices

Abstract

Abstract Let M be an n × m matrix of independent Rademacher (±1) random variables. It is well known that if $n \leq m$ , then M is of full rank with high probability. We show that this property is resilient to adversarial changes to M . More precisely, if $m \ge n + {n^{1 - \varepsilon /6}}$ , then even after changing the sign of (1 – ε ) m /2 entries, M is still of full rank with high probability. Note that this is asymptotically best possible as one can easily make any two rows proportional with at most m /2 changes. Moreover, this theorem gives an asymptotic solution to a slightly weakened version of a conjecture made by Van Vu in [17].

Locations

• arXiv (Cornell University) - View - PDF
• DataCite API - View
• Combinatorics Probability Computing - View