# A $k \times n$ matrix with a lot of invertible $k \times k$ submatrices over $\mathbb{F}_2$

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.

• 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. Oct 21 '15 at 14:24
• 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. Oct 27 '15 at 16:58
• That's a valid point. I should have checked before commenting. Oct 27 '15 at 20:38
• Your best bet is generator or parity check matrix of dual of BCH code or anything related to BCH code. Aug 10 '17 at 13:36