The rank of sparse random matrices
Loading...
Date
2022-04-23
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We determine the asymptotic normalized rank of a random matrix 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.
Description
Table of contents
Keywords
Finite field, Random constraint satisfaction, Random matrices, Rank, Sparse matrices