The rank of sparse random matrices. Issue 1 (23rd April 2022)

• Record Type: Journal Article
• Authors: Coja‐Oghlan, Amin; Ergür, Alperen A.; Gao, Pu; Hetterich, Samuel; Rolvien, Maurice
• Is Part Of: Random structures & algorithms. Volume 62:Issue 1(2023)
• Page Start: 68
• Page End: 130
• Publication Date: 2022-04-23
• Subjects: finite field -- random constraint satisfaction -- random matrices -- rank -- sparse matrices; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21085
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We determine the asymptotic normalized rank of a random matrix A $$ \boldsymbol{A} $$ over an arbitrary field with prescribed numbers of nonzero entries in each row and column. As an application we obtain a formula for the rate of low‐density parity check codes. This formula vindicates a conjecture of Lelarge (2013). The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that diminishes the number of short linear relations.