Resilience of the rank of random matrices. (28th March 2021)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Luh, Kyle; McKinley, Gweneth
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 2(2021)
• Page Start: 163
• Page End: 174
• Publication Date: 2021-03-28
• Subjects: 60B20, -- 05, -- 60; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000413
• Languages: English
• ISSNs: 0963-5483

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 ].