Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$.
We call ${\cal A}$ a (n,k)-covering, if for every subset of columns $I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in {\cal A}$ such that the columns $(i_1,\ldots,i_k)$ in $A$ are linearly independent.
It is known that when choosing a random $k\times k$ matrix over ${\mathbb F}_2$ the probability that it is non-singular is at least half.
This means that if we pick at random a set of $r$ such matrices, the probability that for some $I=(i_1,\ldots,i_k)\subseteq [n]$ won't be covered (by any matrix $A \in {\cal A}$) is at most $2^{-r}$.
Since there are $n \choose k$ such $I$'s, the probability that one of them will not be covered is at most (union bound):
$${n \choose k} \cdot 2^{-r}.$$
If we force this probability to be strictly lower than 1 (which ensures such family of size $r$ exists), we get:
$${n \choose k} \cdot 2^{-r}<1 \Rightarrow r > k \log n.$$
Is there a deterministic build of such family of size $O(k \log n)$, or at least of size $\text{poly}(k,\log n)$?
Motivation for this problem:
I have an algorithm that searches for subgraphs of a given graph $G$ which are similar to a smaller graph $H$ on $k$ vertices. As part of the algorithm it gets a $k\times n$ matrix (each vertex in the graph is associated with a binary vector of length k) and then it checks that all of the vertices which are matched to $H$ are different by checking that the induced $k \times k$ matrix is not singular.
On the one hand, if two vertices of $H$ were mapped to the same vertex, their vectors are the same and the matrix's rank will surely be less than $k$. On the other, I'm not guaranteed that if the vertices were distinct the resulting matrix will be of full rank, so I run the algorithm for every matrix in my $(n,k)$-covering family.
Currently I can draw random matrices and get the result with high probability, but an explicit build will allow me to derandomize the algorithm.
