Resilience of the Rank of Random Matrices

Abstract

Let $M$ be an $n\times m$ matrix of independent Rademacher ($\pm 1$) random variables. It is well known that if $n\le 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-\epsilon /6}$, then even after changing the sign of $(1-\epsilon )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.

15 pages

References in corpus (2)

• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices

Cited by in corpus (2)

• Sparse recovery properties of discrete random matrices
• Counting matrices over finite rank multiplicative groups