Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am looking for a class of matrices $M(n(m), m, k(m), \phi)$ with the following properties:

  1. M is $n \times m$ where $n(m) > m$.
  2. Every subset of rows of size $k$ has (maximal) rank $m$.
  3. $n(m)$ grows slowly.
  4. $m \leq k(m) \leq (1 - \phi) n(m)$ and $k(m)$ is as close as possible to $m$.

and preferably, the matrix is binary.

Has this been studied before? I appreciate any pointers.

I know that a random uniform binary matrix with $n(m) \approx \frac{2}{1-\phi}(m + log 1/\delta)$ and $k(m) = m$ satisfies the properties above with probability $1 - \delta$ (for large enough $m$).

Also, any probabilistic suggestions that perform better than the uniform random binary matrix are welcome.

(I apologize if my question turns out to be elementary, I also appreciate any help with properly tagging the question.)

share|cite|improve this question
I think I'd look for information on so-called MDS codes. (MDS = maximum distance separable.) I do not think these are the same thing, but they should lead you closer to what you want. – Chris Godsil Apr 5 '13 at 14:36
Something very similar is happening with so called fountain codes. IIRC they have results of the type: in a carefully designed matrix any $k(m)=(1+\varepsilon)*m$ rows will work with a high probability. Some constructions are known. Not exactly what you want, but may be worth checking out (in coding theory the roles of the rows and columns would be opposite to yours, but I'm sure you'll manage :-) – Jyrki Lahtonen Apr 7 '13 at 20:44
MDS codes would be nice, but there aren't any non-trivial binary ones. Furthermore, then $n(m)$ could never exceed the size of the field (+1). – Jyrki Lahtonen Apr 7 '13 at 20:46
@ChrisGodsil Thanks! I am looking into MDS codes, and while it seems that they are not exactly what I want they are giving pointers to some useful leads.. @JyrkiLahtonen if I am not mistaken, fountain codes are using random matrices. What I refer to in the question is in fact one simplistic form of fountain codes (simplified Luby transform). I am primarily looking for something deterministic. Better fountain codes use different distributions to improve encoding/decoding efficiency.. – aelguindy Apr 8 '13 at 12:12
If the problem with MDS-codes is that there maximum length is $q+1$ ($q=|F|$), and you need to be able to make them longer, then an option is algebraic-geometry codes (aka Goppa codes). If you use a maximal curve of genus $g$, then the resulting codes are "within (the constant) $g$ of being MDS". The maximal attainable length (when $q$ is a square) is $q+1+2g\sqrt{q}$. Several families of such curves are known. But here typically $q$ is a bit larger, $q=16, 64, 256,\ldots$ – Jyrki Lahtonen Apr 9 '13 at 10:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.