3
$\begingroup$

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.)

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chris Godsil
    Commented Apr 5, 2013 at 14:36
  • 1
    $\begingroup$ 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 :-) $\endgroup$
    – Jyrki Lahtonen
    Commented Apr 7, 2013 at 20:44
  • $\begingroup$ 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). $\endgroup$
    – Jyrki Lahtonen
    Commented Apr 7, 2013 at 20:46
  • $\begingroup$ @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.. $\endgroup$
    – aelguindy
    Commented Apr 8, 2013 at 12:12
  • 1
    $\begingroup$ 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$ $\endgroup$
    – Jyrki Lahtonen
    Commented Apr 9, 2013 at 10:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .