Parity Check Matrix

Let be a Linear Code
A parity check matrix is a Generator Matrix for
It is a matrix
Note that

Lemma

An Linear Code with Generator Matrix
has parity check matrix

Proof

Since
So rows of generate a subcode of
But
Thus the rows of are a basis for as required.

Lemma

Let be a Linear Code with parity check matrix .
Then if and only if:

1. any columns of are linearly independent
2. a set of columns of are linearly dependent.

Proof

Suppose has length
Then
If has columns
Then if and only if