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$?
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$– Bill JohnsonDec 26, 2016 at 19:58
-
$\begingroup$ I need a solution for general m as m is not a power of two in my problem. $\endgroup$– mhsnkDec 26, 2016 at 20:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
1$\begingroup$ I wrote the exact same thing, but you beat me to it by 2 seconds. +1. $\endgroup$ Dec 26, 2016 at 9:17
-
1$\begingroup$ Nice argument! +1 for beating Tony Huynh... :) $\endgroup$– ShahroozDec 26, 2016 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$– mhsnkDec 26, 2016 at 19:31