Proving that only the linear codes pass parity check

Question

An exercise in my book goes as follows:

Let $C$ be a binary $(n,k)$ linear code with parity-check matrix $H$. We know $Hc=0$ for all $c\in C$. Show that $Hw=0$ implies $w\in C$.

---

My idea: Let $w\in\mathbb B^n$ be given with $Hw=0$. Define $v\in\mathbb B^k$ by $v=(w_1,w_2,...,w_k)$. Then $u=v^\mathrm TG\in C$ where $G$ is the generator matrix for $C$. Assume for contradiction that $u_{k+i}\neq w_{k+i}$ for some $i\leq n-k$. Then we must have $0=(Hu)_i\neq (Hw)_i$ contradicting that $Hw=0$. It follows that $w=u\in C$.

Is this a reasonable approach and does it make sense?

---

EDIT: I work with the definition that $G=[I_k\mid P]$ and $H=[P^\mathrm T\mid I_{(n-k)}]$ so the parity bits are always in the last $n-k$ positions of $v^\mathrm TG$.

Answer 1

Given the definitions in your question, your proof is fine. You may want to clarify why $(Hu)_i = 0$. (Hint: It's because $HG^T = 0$.)

---

Note that the definition you gave for a parity check matrix is special case (for systematic codes) of the general definition: Typically the parity check matrix of a code $C$ is defined as the generator matrix of the dual code $C^\perp$. With that definition, we have $c \in C \iff Hc = 0$, of which your exercise is the $\impliedby$ direction.

Answer 2

The general way to proof can be based on:

$ wH^T=0 \Leftrightarrow \exists v \in \mathbb B^k: w=vG \Leftrightarrow w \in C $

(used here writing vectors as rows).

Really, $ C= \lbrace w \in E_q^n: \exists v \in \mathbb B^k: w=vG \rbrace . $

Let $ C_1 =\lbrace w \in E_q^n: wH^t=0 \rbrace . $

We know, that $ C \subseteq C_1 $ (code is linea), $ \mid C_1 \mid =q^k, \mid C \mid =q^k, $ so $ C= C_1 $.