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

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.

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$$.
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.