4
$\begingroup$

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 :)

  • 0
    (cont.) taking that permutations idea a bit further. Let us look at the common 1s shared by $v_1$ and $v_2$. By permuting, we can put these into the beginning, so $v_1$ will be one of $111100$, $111110$, $111111$ (actually rschwieb already explained, why the last cannot occur). Then $v_2$ will also begin with at least two ones (because it will necessarily overlap with those of $v_1$ at at least 2 positions), and after its first zero, it can have any further 1s only at positions, where $v_1$ has 0s. There are not too many cases remaining, me thinks.2012-05-09

2 Answers 2

2

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.

  • 0
    You're right, I shouldn't have said "distinct". The above post was not meant as a complete solution, just an angle of attack.2012-05-09
0

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.

  • 0
    But to be honest, a solution based on case-by-case study (using permutations to reduce the number of cases) is probably better. I was just having fun with the sum of weights. Hopefully you don't mind.2012-05-10