A pretty well-known theorem regarding linear $(n,k,d)$ codes is that every $n-d+1$ coordinate positions contain an information set, but not all $n-d$ coordinate positions do. This is equivalent to a codeword always being able to handle $d-1$ erasures, but only sometimes more than that.

If any choice of $k$ coordinates is an information set, then the code is MDS. I've been searching pretty vigorously for results on the maximum number of information sets for a linear code but I've not found much. I'm guessing an exact answer is NP-complete, but even bounds are hard to find.

For a given linear $(n,k)$ code, the number of possible size $k$ subsets is $\binom{n}{k}$. I'd like to know how many of these can possibly be information sets.

References or reductions to equivalent problems would also be nice - notice that this problem is equivalent to finding the number of invertible $k \times k$ submatrices of a binary $k \times n$ matrix. This may be a well known problem in the CS community but my searches have turned up nothing...


migrated from math.stackexchange.com Mar 30 '16 at 2:29

This question came from our site for people studying math at any level and professionals in related fields.

  • $\begingroup$ Is this perhaps better suited for MathOverflow...? $\endgroup$ – Benjamin Lindqvist Mar 29 '16 at 9:55
  • 1
    $\begingroup$ Some elementary related discussion. Probably you know all that - in particular the connection to the dual code. The probability for a random set of $k$ column vectors being linearly independent is known. That might give you a ball park figure? $\endgroup$ – Jyrki Lahtonen Mar 29 '16 at 13:55
  • $\begingroup$ That's a nice link, but the problem is that I want a bound rather than an approximation. Maybe I could massage the problem statement so that I can use an approximation instead, but I'm not sure... $\endgroup$ – Benjamin Lindqvist Mar 29 '16 at 14:14

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.