In the appendix of the paper by Tolhuizen ( http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=841182) there is a very fast and easy probabilistic proof that for $k=cn$ where $c \in [0,1]$ is fixed, there is a matrix $A$ over $\mathbb{F}_2$ of size $k \times n$ such that the number of invertble $k \times k$ submatrices is at least $0.28 \binom{n}{k}$.

Question: Is there an explicit construction for any $c\in [0,1]$ of a $k \times n$ matrix $A$ over $\mathbb{F}_2$ where $k=cn$ such that there are at least $$\frac{1}{Poly(n)}\binom{n}{k} $$ invertible $k \times k$ submatrices of $A$? (here $Poly(n)$ denotes a fixed polynomial)

Motivation: This paper settles the maximal asymptotic size of a cancellative set system. I am studying set systems that are very similar to cancellative ones so I would like to build them from cancellative ones.

  • 2
    $\begingroup$ You might want to look at some families of MDS codes. There all n choose k submatrices of a generator matrix are invertible, so Poly(n) = 1. May be such a family, or a possibly modified family of such codes will solve your problem. $\endgroup$
    – Anurag
    Oct 21 '15 at 14:24
  • 2
    $\begingroup$ Thank you for the comment. I looked at MDS codes, but there are only trivial MDS codes over the field with two elements. I am not yet sure whether MDS codes over larger fields could be used somehow in this case. $\endgroup$ Oct 27 '15 at 16:58
  • $\begingroup$ That's a valid point. I should have checked before commenting. $\endgroup$
    – Anurag
    Oct 27 '15 at 20:38
  • $\begingroup$ Your best bet is generator or parity check matrix of dual of BCH code or anything related to BCH code. $\endgroup$
    – Balaji sb
    Aug 10 '17 at 13:36

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.