Let $C$ be a binary linear code and $\neg C := \{\neg c$ $|$ $ c$ $ \epsilon$ $ C\ \}$. $\neg c$ is the complement of $c$. So for $c = c_1,...,c_n $ with $c_i \ \epsilon \ \{0,1\}$ the complement is $\neg c_i \ = c_i \oplus1 $.
Tasks:
- Proof that:
If $1^n \ \epsilon \ C$ then $ C = \neg C $.
- Proof or disproof:
If $C$ is linear, then $\neg C$ is linear.
- Proof or disproof:
If $C$ is linear, then $C \cap \neg C $ is linear.
- Proof or disproof:
If $C$ is linear, then $C \cup \neg C $ is linear.
My question: How to do this proof? The wiki article about linear codes isn't very helpful for me.
This is homework, so i would like to get hints (e.g. a way to do the proof) rather then a full solution to work it out myself.
Since $C$ is a binary linear code, for any $c_1,c_2\in C$ we have $c_1+c_2\in C$. Since $1^n\in C$ therefore for any $c\in C$ also $c+1^n\in C$ where $\neg c=c+1^n\in C$ and this holds for all $c\in C$ so $\neg C=C$.
This one doesn't hold e.g. take $C=\{(0,0),(0,1)\}$ as a linear codebook, therefore $\neg C=\{(1,1),(1,0)\}$ which is not linear since $(1,1)+(1,0)=(0,1)\notin \neg C$.
this is true only if $\neg C$ is a linear codebook. In that case, for $c_1,c_2\in C\cap \neg C$ we have $c_1,c_2\in C$ and $c_1,c_2\in\neg C$. Since both $C$ and $\neg C$ are linear we have $c_1+c_2\in C$ and $c_1+c_2\in\neg C$ or $c_1+c_2\in C\cap\neg C$. Therefore $C\cap\neg C$ is linear.
$C\cup \neg C$ is linear only if $\neg C$ is linear (why?)