The Exercise

A classical linear code on $n$ symbols can be described by a parity check matrix $H$ , and different matrices can describe the same code. The exercise asks to show that adding one row of $H$ to another leaves the code unchanged^✦, and that a parity check matrix with linearly independent rows can be brought, without changing its code, to a standard form in which some of its columns make up the identity matrix.^✦

The Code of a Parity Check Matrix

Codes are taken over a field $K$ , which is $\mathbb{Z}_2$ for codes on bits. A parity check matrix $H$ is an $r \times n$ matrix over $K$ , each of its rows one check on a string of $n$ symbols. The code $C(H)$ of $H$ is its kernel, a linear code of length $n$ : $C(H) = \{\, x \in K^n : Hx = 0 \,\}.$ (1)^✦

The Claim

Theorem 1. Let $H$ be an $r \times n$ parity check matrix over $K$ , let $a \ne b$ be two of its rows, and let $H'$ be the matrix obtained from $H$ by adding row $a$ to row $b$ , the other rows left as they are. Then $C(H') = C(H).$ (2)^✦

Theorem 2. Let $H$ be an $r \times n$ parity check matrix over $K$ of full row rank: the map $x \mapsto Hx$ takes $K^n$ onto $K^r$ . Then there are an invertible $r \times r$ matrix $E$ and distinct column indices $c_1, \dots, c_r$ among $1, \dots, n$ such that $(EH)_{i\,c_j} = \delta_{ij} \quad (1 \le i, j \le r), \qquad C(EH) = C(H).$ (3)^✦

What Is Checked

Both theorems are stated over one construction, the code (1) of a parity check matrix. What the library proves about it are the invariances (2) and (3), equalities between codes, as sets of code words, and not between the matrices that define them.