×

On sparse parity check matrices. (English) Zbl 0902.94018

Summary: We consider the extremal problem to determine the maximal number \(N(m,k,r)\) of columns of a 0-1 matrix with \(m\) rows and at most \(r\) ones in each column such that each \(k\) columns are linearly independent modulo 2. For fixed integers \(k\geq 1\) and \(r\geq 1\), we shall prove the probabilistic lower bound \(N(m,k,r)= \Omega(m^{kr/2(k-1)}\)): for \(k\) a power of 2, we prove the upper bound \(N(m,k,r) =O(m^{\lceil kr/(k-1) \rceil/2})\), which matches the lower bound for infinitely many values of \(r\). We give some explicit constructions.

MSC:

94B05 Linear codes (general theory)
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI