Resilience of the rank of random matrices. (28th March 2021) - Ferber, Asaf; Luh, Kyle; McKinley, Gweneth
Abstract: Let M be an n × m matrix of independent Rademacher (±1) random variables. It is well known that if n ≤ 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 n + n^1 - ε /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 ].