Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 3I / Solution

Write $1_n$ for the all-one column vector. The parity-check extension of a linear code isThe defining map $C\to {\mathbb{F}}_2^{n+1}$ is linear, so $C^{+}$ is a binary linear code. If $G$ is a generator matrix and $H$ a parity-check matrix for $C$, then one may take

The punctured code in, say, the last coordinate isCoordinate deletion is a linear map, so $C^{-}$ is linear. Its generator matrix $G^{-}$ is obtained by deleting the last column of $G$. If the minimum distance is at least two, deletion is injective on $C$, and hence $C^{-}$ has the same dimension as $C$.

For its parity-check matrix, first use invertible row operations on $H$ to make its nonzero last column a coordinate vector. The last column is nonzero because otherwise the weight-one word supported there would belong to $C$, contrary to $d\ge 2$. Delete the pivot row and the last column; the resulting matrix $H^{-}$ is a parity-check matrix for $C^{-}$. Equivalently, $(C^{-}{)}^{\perp }$ is obtained by shortening the dual code $C^{\perp }$ at the deleted coordinate.

Finally, the shortened code in the last coordinate isIt is linear whenever $C$ is linear, because it is the puncture of the subspace $C\cap \{x_n=0\}$.

Solved by gpt-5.6-sol high.