Dual Codes

Orthogonal complement of a code, and the generator/parity-check duality.

The idea

The dual code of a linear code is the set of vectors orthogonal to all of its codewords, and it explains how a generator matrix and a parity-check matrix describe the same code from two sides.

Give $\mathbb{F}_q^{n}$ the standard inner product $\langle x, y \rangle = \sum_{i=1}^{n} x_i y_i$, the sum computed in $\mathbb{F}_q$. Over a finite field this product measures no lengths — over $\mathbb{F}_2$ the vector $(1,1)$ is orthogonal to itself — but it is bilinear, and bilinearity is the only property the theory needs.

Definition (Dual code).

For a linear code $C \subseteq \mathbb{F}_q^{n}$, the dual code is $C^{\perp} = \{\, x \in \mathbb{F}_q^{n} : \langle x, c \rangle = 0 \text{ for all } c \in C \,\}.$

Theorem (Dimension of the dual).

If $C \subseteq \mathbb{F}_q^{n}$ is a linear code of dimension $k$, then $C^{\perp}$ is a linear code of dimension $n - k$: $\dim C + \dim C^{\perp} = n.$

By bilinearity, a vector orthogonal to the rows of a generator matrix $G$ of $C$ is orthogonal to all of $C$, so $x$ lies in $C^{\perp}$ exactly when $G x^{\top} = 0$. That is $k$ independent linear conditions on $n$ coordinates, and their solution space has dimension $n - k$.

Those conditions are parity checks: a generator matrix of $C$ is a parity-check matrix of $C^{\perp}$, and in the same way a parity-check matrix $H$ of $C$ is a generator matrix of $C^{\perp}$. The identity $G H^{\top} = 0$ records both statements, and it is why we can present a code either by listing generators of its codewords or by listing the conditions they satisfy.

Ways to work on it

• Walkthrough. How the dual of a linear code is built, and how its dimension and matrices mirror the original's.
• Practice. Test whether a vector lies in the dual of a small code.
• Hardest. Identify the dual of the Hamming code and read off its parameters.

Not sure where to start? Take the ten-question placement test.