Parity check matrices and product representations of squares (Q949791): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1007/s00493-008-2195-2 / rank | |||
Property / DOI | |||
Property / DOI: 10.1007/S00493-008-2195-2 / rank | |||
Normal rank |
Latest revision as of 09:32, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parity check matrices and product representations of squares |
scientific article |
Statements
Parity check matrices and product representations of squares (English)
0 references
21 October 2008
0 references
Let \(N_{F}(n,k,r)\) denote the maximum number of columns in an \(n\)-row matrix with entries in a finite field \(F\) in which each column has at most \(r\) nonzero entries and every \(k\) columns are linearly independent over \(F\). In this paper it is shown that \(N_{F}(n,k,r)\ll n^{r/2+cr/k}\) where \(c\approx 4/3\) for large \(k\) and \(a_n\ll b_n\) means that there exists a constant \(C>0\) such that for all \(n\), \(a_n\leq Cb_n\). The proof of this result is based on a novel reduction of the problem to the following Turán type problem: What is the maximum number of edges in an \(n\)-vertex graph which does not contain an even cycle of length \(2k\)? and the method yields a fast algorithm for finding short linear dependencies. Some applications of this method to a problem on hypergraphs which do not contain an even cover of a given size and a problem on product representations of squares in combinatorial number theory are presented.
0 references
finite field
0 references
parity check matrix
0 references
linear dependency
0 references
even hypergraph cover
0 references
forbidden cycle
0 references
product representations of squares
0 references
Turan type problem
0 references
0 references