The rank of random matrices over finite fields
arXiv:1810.07390
Abstract
We determine the rank of a random matrix A over a finite 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 verifies a conjecture of Lelarge [Proc. IEEE Information Theory Workshop 2013]. The proofs are based on coupling arguments and the interpolation method from mathematical physics.
arXiv comment37 pages
References in corpus (8)
- Statistical physics of inference: Thresholds and algorithms
- An Extended Variational Principle for the SK Spin-Glass Model
- Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
- Information-theoretic thresholds from the cavity method
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Spin glass models from the point of view of spin distributions
- The k-core and branching processes
- The stripping process can be slow: part I