Lean, informalized

Nielsen & Chuang · Chapter 10, Quantum error-correction · p. 447

Exercise 10.19 - The code a parity check matrix in standard form defines, and the generator matrix that spans it

The generator matrix for a parity check matrix in standard form.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Exercise

Fix a commutative ring RR, the field ℤ2\mathbb{Z}_2 for a binary code. A classical linear code CC of length nn is a subspace of RnR^n, the space of words of nn symbols from RR. Its codewords carry messages of kk symbols.

Two kinds of matrix over RR describe CC. A generator matrix of CC is an n×kn \times k matrix whose columns are linearly independent and whose range is CC; multiplying a message by it gives the codeword that carries the message. A parity check matrix of CC is an (n−k)×n(n-k) \times n matrix whose kernel is CC.

The exercise starts from a parity check matrix in standard form. For an (n−k)×k(n-k) \times k matrix AA over RR, the parity check matrix in standard form is the (n−k)×n(n-k) \times n matrix HH that sets AA beside the identity of size n−kn-k: H=[AIn−k].H = \begin{bmatrix} A & I_{n-k} \end{bmatrix}.(1)✦ The exercise asks for a generator matrix, written in terms of AA, of the code whose parity check matrix is HH.

The Claim

The generator matrix in standard form of AA is the n×kn \times k matrix GG that stacks the identity of size kk above −A-A: G=[Ik−A].G = \begin{bmatrix} I_k \\ -A \end{bmatrix}.(2)✦

Theorem 1. Let RR be a commutative ring and AA an (n−k)×k(n-k) \times k matrix over RR, with generator matrix GG and parity check matrix HH in standard form, as in (2) and (1). Then range⁡G=ker⁡H\operatorname{range} G = \ker H(3)✦ and ker⁡G={0}.\ker G = \{0\}.(4)✦

With (3) and (4), GG is a generator matrix of the code whose parity check matrix is HH, which is the exercise.

What Is Checked

The claim is stated over the two standard forms of one (n−k)×k(n-k) \times k matrix AA: the parity check matrix HH of (1) and the generator matrix GG of (2). What the library proves about these two matrices is the theorem, both (3) and (4).