Find the generator matrix

Question

Given the parity check matrix $$H=$$ \begin{bmatrix} 4&1&4&2&0&4\\2&1&1&4&2&0\end{bmatrix}

find its generator matrix

I know generator matrix $G$ and $H$ satisfies $GH^T=0$

Also if $H$ is in standard form $H=[P|I^T]\implies G=[I|-P^T]$

But I dont get how to put $H$ in standard for

Answer 1

Hint: If you work over the field ${\Bbb F}_5$, then multiply the first row of $H$ with the inverse of $2$ and the second row with the inverse of $4$. Then exchange the rows of $H$. This gives you the desired form $H = (A\mid I)$ from which you can easily obtain the corresponding generator matrix.

More concretely, in $\left(\begin{array}{ccccc} 4&1&4&2&0&4\\2&1&1&4&2&0 \end{array}\right)$ multiply the first row by $4$ and the second row by $3$ giving $\left(\begin{array}{ccccc} 1&4&1&3&0&1\\1&3&3&2&1&0 \end{array}\right)$. Swapping rows gives $\left(\begin{array}{ccccc} 1&3&3&2&1&0\\1&4&1&3&0&1 \end{array}\right)$ as required.

Answer 2

But I dont get how to put H in standard form

You should understand that

performing elementary row operations on the generator matrix of a linear code does not change the code.

You should spend some time convincing yourself of this (and/or proving it concretely.) It is a very basic idea.

This allows you to put your matrix into the form you described. After that, you can apply the trick you mentioned to produce $H$. The parity check matrix will work with both the modified generator and the original.

---

In your case, row operations suffice to put the matrix into the "standard form." It could actually be the case that all the rows were $0$ on the last column, and then you might not know what to do.

In that case, you'd need to understand what column equivalent codes are and how you can use them to proceed. The idea is that performing elementary column operations on the generator matrix does change the code, but the resulting code has all the same parameters (weight, length, distance) and that you can change it back when you're done by undoing the column operations.

So in that case, you'd perform column operations on the generator to get the last two columns to be a linearly independent set, then perform row operations to get standard form generator matrix (for the column equivalent code) then extract the parity check matrix (for the column equivalent code) and then undo the column permutation of the parity matrix (to arrive at a parity check for the original code.)