[Math] Finding parity check matrix for linear code

coding-theorylinear algebramatrices

I have a generator matrix:

0 2 1 2 0
2 1 1 0 1
2 2 0 1 1

V is a linear code over GF(3) determined by this matrix. I'm trying to find a parity check matrix for V. Now, n = 5. I then row reduced to reduced echelon form and got:

1 0 1 1 0
0 1 2 1 0
0 0 0 0 1

So Dim k = 3. The code I have right now is V = (5, 3).

I'm confused on what to do next. Normally the matrix I have would be in this form:

1 0 0|other numbers here 
0 1 0|
0 0 1|

and I could just do the -P^T | In-k

I know I should have a 2 x 5 matrix. But the identity matrix isn't there, did I do something wrong?

EDIT: Wait, you can swap columns can't you? In that case I can swap the 3rd and 5th column to put the generator matrix in standard form.

Best Answer

You can modify the $$ G=(I|P)\quad \implies \quad H=(-P^T|I) $$ process as follows, when putting $G$ into reduced row echelon form fails to produce a leading identity block.

  1. Put an identity matrix block into those columns that won't have a leading one.
  2. Spread that $-P^T$-block into the remaining columns.

From your generator matrix $$ G=\left(\begin{array}{ccccc}1& 0& 1& 1& 0\\ 0& 1& 2& 1& 0\\ 0& 0& 0& 0& 1 \end{array}\right) $$ the process gives $$ H=\left(\begin{array}{ccccc} -1&-2&1&0&-0\\ -1&-1&0&1&-0 \end{array}\right)=\left(\begin{array}{ccccc} 2&1&1&0&0\\ 2&2&0&1&0 \end{array}\right). $$ The form of $H$ on the left has those minus signs in place, but of course we get rid of them in the final answer.

By all means check that the equation $GH^T=0$ holds when you are done.

Related Question