The rank of sparse random matrices
Amin Coja‐Oghlan, Alperen A. Ergür, Pu Gao, Samuel Hetterich, Maurice Rolvien · Society for Industrial and Applied Mathematics eBooks · 2019
We determine the rank of a random matrix A over an arbitrary field with prescribed numbers of non-zero 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 [Proc. IEEE Information Theory Workshop 2013]. The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that likely diminishes the number of short linear relations.