Resilience of the rank of random matrices

DOI10.1017/S0963548320000413MaRDI QIDQ4993256zbMATH OpenOpenAlexFDO

Authors Asaf Ferber, Kyle Luh, Gweneth McKinley

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.03619

zbMATH Keywords

asymptotic solutionRademacher random variables

Mathematics Subject Classification ID

Matrices of integers (15B36) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: Let $M$ be an $nimesm$ matrix of independent Rademacher ($pm1$) random variables. It is well known that if $nleqm$, then $M$ is of full rank with high probability. We show that this property is resilient to adversarial changes to $M$. More precisely, if $mgeqn+n^{1-varepsilon/6}$, then even after changing the sign of $(1-varepsilon)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.

Recommendations

• scientific article; zbMATH DE number 1436005
• Singularity of random Bernoulli matrices
• The rank of a random matrix
• On the permanent of a random symmetric matrix
• Random matrices: probability of normality

Cites work

• Estimates for the concentration function of combinatorial number theory and probability
• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Invertibility of symmetric random matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Singularity of random Bernoulli matrices
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• The Littlewood-Offord problem and invertibility of random matrices

Cited in

(6)

• Recent progress in combinatorial random matrix theory
• Rank deficiency of random matrices
• Probabilistic rank and matrix rigidity
• Sparse recovery properties of discrete random matrices
• Counting matrices over finite rank multiplicative groups
• Eigenvalue gaps of random perturbations of large matrices

This page was built for publication: Resilience of the rank of random matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993256)