3
$\begingroup$

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$?

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

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.

$\endgroup$
3
  • 1
    $\begingroup$ I wrote the exact same thing, but you beat me to it by 2 seconds. +1. $\endgroup$
    – Tony Huynh
    Dec 26 '16 at 9:17
  • 1
    $\begingroup$ Nice argument! +1 for beating Tony Huynh... :) $\endgroup$
    – Shah Rooz
    Dec 26 '16 at 11:28
  • $\begingroup$ 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? $\endgroup$
    – mhsnk
    Dec 26 '16 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.