# Constructing a small (n,k)-Covering Matrices family

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.