First we want to introduce the dual code $C^{\perp}$ of a linear code $C$. To this end we have to introduce an inner product. For words $v, w \in \mathbb{Z}{2}^{n}$ we define the inner product $$ =\sum{i=1}^{n} v_{i} w_{i}
$$
Let $C$ be a linear binary code of length $n$ and dimension $k$. The dual code $C^{\perp}$ is defined as
$$
C^{\perp}=\left{v \in \mathbb{Z}_{2}^{n}:=0 \text { for all } u \in C\right}
$$
Show that $C^{\perp}$ defines indeed a linear binary code of length $n$, provided $\left|C^{\perp}\right| \geq 2 .$
The next theorem gives the relationship between a code and its dual in terms of the generator and parity check matrices.
Let $C$ be a linear binary code of length $n$ and dimension $k<n$. Then $C^{\perp}$ is a linear binary code of length $n$ and dimension $n-k$. Moreover, $H$ is a parity check matrix for $C$ if and only if $H$ is a generator matrix for $C^{\perp}$.
As a reminder of Theorem $14.3$, if $C$ has a generator matrix $G$ in standard form $G=$ $\left(I_{k} \quad A\right)$ then
$$
\left(\begin{array}{ll}
A^{t r} & I_{n-k}
\end{array}\right)
$$
is a parity check matrix for $C$.
Show that $\left(C^{\perp}\right)^{\perp}=C$. (Hint: Clearly $C \subset\left(C^{\perp}\right)^{\perp}$, for the other inclusion compare dimensions.) Conlcude that $H$ is a parity check matrix for $C^{\perp}$ if and only if $H$ is a generator matrix for $C$.
For example, if $G=\left(I_{k} \quad A\right)$ is the standard form generator matrix for the square code, then applying Theorem $14.3$ to $G$, we get the parity check matrix already found in Example $14.2(2)$
Example 16.5. Let $C_{\text {ext }}$ be as in (1). Then
$$
C_{\text {ext }}^{\perp}={00000,11111}
$$
is the binary repetition code of length 5 , and
$$
{00000,11111}^{\perp}=C_{\text {ext }}
$$
