Linear codes : why has the parity check matrix dimensions $(n-k)*k$?

Question

I am studying Quantum error correction that is based on some aspects on classical error correction.

I am reading some very basics around linear error correcting codes.

I consider a linear code [n,k]: thus it encodes k bits of information into n bits.

My question: I don't understand why the parity check matrix has $n-k$ lines.

---

What I understand from the topic.

If I call $x$ the column vector of the information bits I want to encode in the n-bits, I define $G$ the generator matrix such that:

$$ y = G x $$

Where $y$ is my encoded information.

The $H$ matrix is built such that its kernel is the code space. Thus, its kernel must be composed of the column vectors of $G$ as the code space is spanned by the column vectors of $G$.

All this means that the line vectors of $H$ must be orthogonal to the column vectors of $G$.

But why do we have to take $n-k$ lines in $H$, why not $n$ lines, or $2$ lines ? I guess it is a way to ensure us that the Kernel of $H$ is exactly the code space but I don't understand why this number of lines ensure this.

Answer 1

You can have as many rows in $H$ as you like, but they will be linearly dependent after you reach $n-k$ independent rows. You can apply the rank-nullity theorem. If you like, think of the rank of $H$ as the number of pivots you get, when you row reduce. It is the same number you get when you column reduce. Now for $H$ is a $s\times n$-matrix with kernel of dimension $k$. That means by the rank-nullity theorem that $\mathrm{rank}~H+k=n$. So $\mathrm{rank}~H=n-k$ but rank is just the number of pivots (either from row or column reducing). Said another way, $s\geq n-k$ and if $s>n-k$ then after row reducing you get just $n-k$ nonzero rows. So the most compact $H$ is $(n-k)\times k$.

Usually one thinks of generator and parity check matrices as having been row/column reduced with 0 rows serving no purpose so omitted. That forces your dimensions. But yes in principal you could repeat yourself, it just wouldn't help or be what anyone expects. But no, you can't choose just 2 that will make for a larger kernel in general.

Answer 2

If you have k input bits and n output bits, you need to compute only n-k extra bits, so the matrix should be k * (n-k). You multiply the input vector by the matrix and get the extra bits vector.