# Minimal spanning set of binary vectors

For a fixed integer $m$, does there exist a set of $a=\Theta(m)$ vectors $\mathcal{V}= \{v_1, v_2, \dots, v_a\}$ in binary Field (i.e $v_i \in \mathbb{F}_2^m$) with Hamming distance of at least $d$ for some $d \ge 4$ such that for any subset $\mathcal{A} \subset \mathcal{V}$ of cardinality $b$ for some fixed $b < a$, none of the base vectors $e_i \in \mathbb{F}_2^m$ exists in the span of the vectors in $\mathcal{A}$ but $\mathcal{V}$ spans the whole space of $\mathbb{F}_2^m$? If so, how can we construct such a set of vectors? For what values of $b$ as a function of $m$ and $d$ does such a set exist? Does such a set exist for $b=a-1$?

• If $m$ is a power of two, doesn't the Walsh basis give what you want with even the best possible estimates? Dec 26 '16 at 19:58
• I need a solution for general m as m is not a power of two in my problem. Dec 26 '16 at 20:15

If $\mathcal V$ spans $\mathbb F_2^m$, it should contain a basis of $\mathbb F_2^m$; so we may assume that $\mathcal V$ contains ony this basis, and $a=m$.
In this case, if $e_i$ is not expressible via $m-1$ vectors from $\mathcal V$, this means exactly that $e_i=v_1+\dots+v_m$. This may happen only for one of the $e_i$; so $b=a-1$ is impossible for $m>1$.
On the other hand, $b=a-2$ is always realizable (if $m>1$, surely). Indeed, set $$A=\begin{pmatrix} 0& 1& 1& \cdots& 1& 1\\ 1& 0& 1& \cdots& 1& 1\\ 1& 1& 0& \cdots& 1& 1\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ 1& 1& 1& \cdots& 0& 1\\ 1& 1& 1& \cdots& 1& 1 \end{pmatrix}$$ (the last row looks a bit different). It is easily seen that $A$ is non-degenerate; so we may find a basis $\{v_1,\dots,v_m\}$ such that $$(e_1,\dots,e_m)=(v_1,\dots,v_m)A.$$ This basis constitutes the required set.
• Thank you for your answer @Ilya . In my problem, I actually need the vectors to have a minimum Hamming distance of $d$. Sorry, I did not mention this earlier in my problem. I have edited the problem now to include this concern. Can we tweak your response to accommodate this concern? Dec 26 '16 at 19:31