Linear Binary Codes - Show that no such vectors exist...

Question

I have a question that involves showing there do not exist vectors $v_1,v_2,v_3 \in \mathbb{Z}_2^6$ such that:

$wt(v_i)\geq4$ for $i \in \{1,2,3\}$

$wt(v_i+v_j)\geq3$ for $i \in \{1,2,3\}$

$wt(v_1+v_2+v_3)\geq2$

where $\mathbb{Z}_2^6$ is the set of binary words of length 6 ($\mathbb{Z}_2$ can be considered as the set of residue classes mod 2, and addition as residue class addition).

and $wt(v)$ is the weight function (the number of 1's in the vector v).

---

I originally tried finding vectors in $\mathbb{Z}_2^6$ that did satisfy the three conditions above, and couldn't, only to give up and look at the mark scheme, which mentions that the above should be simple to show.

Any hint would be appreciated.

Thanks in advance :)

Answer 1

As I was commenting above, the three hypotheses imply that the three vectors are linearly independent, and span a (6,3,2) code, one which doesn't include the weight 6 word.

Switching to the dual code, $d=2$ this all means that the parity check matrix has to have 6 distinct nonzero columns from $\mathbb{F}_2^3$ whose sum is nonzero.

There are only 7 such columns possible, so I think this is an excellent angle of attack for the problem.

Answer 2

The words $0,v_1,v_2,v_3,v_1+v_2,v_1+v_3,v_2+v_3,v_1+v_2+v_3$ form a group $C$ under addition. As observed by rschwieb, the given conditions imply that all the 8 vectors are distinct. We get six homomorphisms $f_i$ from $C$ to $\mathbb{Z}_2$ by mapping each vector to its bit at position $i$, $i=1,2,\ldots,6$. Because $|f_i(C)|$ is either 1 (if all the words have a zero at position $i$) or 2 (if both 1 and 0 occur at that position, we get that $|\mathrm{ker}(f_i)|$ is either 4 or 8. Therefore at each of the six bit positions we have a zero in either exactly 4 of the vectors of $C$, or in all 8 of them. Consequently, at each of the six bit positions we have a 1 in exactly four words, or a 0 in all 8 words.

Therefore the sum of the weights of the words of $C$ is divisible by four, and also $\le 4\cdot6=24$. OTOH the given inequalities imply that the sum of the weights is at least 23, so it must be exactly 24. Therefore the total "slack" (= the amount by which the inequality fails to be an equality) in these inequalities is exactly one.

We get a contradiction as follows. If all the vectors $v_i$ have an even weight, then so do the pairwise sums $v_i+v_j,i\neq j$. But the second set of inequalities then produce a total slack of three, which we showed to be impossible. So at least one of the vectors $v_i$ must have odd weight. In order for the first set of inequalities not to produce too much slack, exactly one of the vectors $v_i$, say $v_1$ must be of odd weight, and the other two must have weight four. But in this case $v_2+v_3$ has an even weight, and thus it will produce some slack in the second group of inequalities. Therefore the total slack would be at least two, which is also impossible.