The Exercise

A classical linear code is often given by a parity check matrix $H$ rather than by a list of its codewords. The exercise asks for the number $d$ such that any $d-1$ columns of $H$ are linearly independent but some $d$ of them are linearly dependent, and how that number shows in the distance of the code.

Linear Codes

Let $K$ be a field. A linear code $C$ over $K$ with $n$ positions is a subspace of $K^n$ , and its elements are its codewords. A parity check matrix $H$ over $K$ has one column for each of the $n$ positions and one row for each parity check. The code $C$ defined by $H$ is the kernel of $H$ , the set of words that pass every check: $C = \{\, x \in K^n : Hx = 0 \,\}.$ (1)

The Hamming weight $\mathrm{wt}(x)$ of a word $x \in K^n$ is the number of its nonzero entries. The minimum distance $d(C)$ of a linear code $C$ over $K$ is the least Hamming weight of a nonzero codeword, $d(C) = \min\{\, \mathrm{wt}(x) : x \in C,\ x \neq 0 \,\},$ (2)^✦ and it is infinite when $C$ has no nonzero codeword.

The Claim

Theorem 1. Let $H$ be a parity check matrix over a field $K$ , let $C$ be the code it defines, and let $d$ be a natural number. Suppose every set of fewer than $d$ columns of $H$ is linearly independent, and some set of $d$ columns of $H$ is linearly dependent. Then the minimum distance of $C$ is $d$ : $d(C) = d.$ (3)^✦

What Is Checked

The claim is stated over the minimum distance (2) of the code (1), for any field $K$ and any parity check matrix $H$ over it. What the library proves about these constructions is the equality (3) under the two conditions on the columns of $H$ .