Binary linear codes and weights Let $C$ be a binary $[n,k]$ linear code. If $C$ has a codeword of odd weight
then the codewords of even weightin $C$ form an $[n,k-1]$ binary linear code. Can you prove that?
 A: Hint: Consider the linear mapping $f$ from $C$ to $GF(2)$ defined by 
$$
f:(a_1,a_2,\ldots,a_n)\mapsto a_1+a_2+\cdots+a_n.
$$ 
Show that this is onto. Apply the rank-nullity theorem (familiar from linear algebra) to it.
A: Let $E \subset C$ be the code containing all the codewords of even weight in $C$. In order to show that the code is linear, we only need to show that it is closed under addition. In other words, we need to show that if $a, b \in E$, then $a + b \in E$.
Note that $a + b$ surely is in the original code $C$, because $C$ is linear. This means that it is sufficient to show that $a + b$ is of even weight.
Suppose that $a$ is of weight $2m_1$, $b$ is of weight $2m_2$, and the $1$s in $a$ and $b$ overlap at $r$ places. Then, the weight of $a + b$ is $2m_1 + 2m_2 - 2r$, which surely is even. Thus, $E$ is closed under addition and is a linear code!
You can show that the dimension of $E$ is precisely $1$ less than that of $C$ (i.e. that half of the codewords in $C$ are of even weight) by showing that there are equally many codewords of odd weight and even weight in $C$.
Using similar reasoning as before, it can be shown that the sum of two codewords of odd weights is of even weight and that the sum of codewords of weights of different parities is of odd weight.
Let $c \in C$ be a codeword of odd weight. All the sums obtained by adding $c$ and a codeword of odd weight are thus of even weight. Furthermore, they are all distinct, because $C$ is a group. This means that there are at least as many words of even weight as of odd weight in $C$.
Similarly, the sums obtained by adding $c$ and the codewords of even weight indicate that there are at least as many codewords of odd weight as of even weight in $C$.
Therefore, the amount of even codewords in $C$ must be precisely the same as the amount of odd codewords in $C$. In other words, half of the codewords in $C$ is of even weight, which means that the dimension of the code $E$ of even-weighted codewords is $1$ less than that of $C$.
A: Let $D$ be the subcode of $C$ spanned (as a vector space) by all words of $C$ having even weight. Let $w \in C$ be an odd weight word.
One can begin by showing that, given two words $w_1$ and $w_2\in C$, the word $w_1+w_2$ has even weight iff the weights of $w_1$ and $w_2$ are of the same evenness.
The claim follows from a couple of remarks. First, each word in the subcode $D$ has even weight and the coset $w+D$ consists of odd weight words only. Second, $C$ is the disjoint union $D \cup (w+D)$. As the sets $D$ and $w+D$ have the same cardinality, $D$ contains exactly half of all words of $C$, i.e. $2^{k-1}$ ones. Thus, the subcode $D$ has codimension $1$.
Also, as $D$ can be described as the kerner of the (augmentation) homomorphism
$$
\phi\colon C \to \mathbb{F}_2, \quad (x_1,\ldots,x_n) \stackrel{\phi}{\mapsto} x_1+\ldots + x_n,
$$
the claim can be proven (by means of linear algebra) using the isomorphism between $C/\ker{\phi}$ and $\textrm{im}{\,\phi}$. Notice that in this context $D$ and $w + D$ are the two classes in the quotient vector space $C/D$.
A: Let x be an odd codeword so that the cosets x+E and E are distinct. Given any coset y+E we must have y+E=E if y is even. Otherwise y is odd while x+y is even implying x+E = y+E. Therefore, C/E has size 2 and dimension 1. Therefore dim(E) = dim(C) - 1.
