Row/Column operations of a parity check/generator matrix for a linear code

Question

Given a linear code C with generator matrix G and parity matrix H. Would permuting rows and/or columns of these matricies produce a different linear code? I am under the impression that the resulting linear code would be equivalent to the original linear code. However when using Sage Maths, the set of codewords generated by the generator matrix seem to be different. Could anyone explain what is going?

Answer 1

Some of this is going to depend on what definitions you are using. Hill, A First Course in Coding Theory, page 49, says a generator matrix for a linear code is a matrix whose rows form a basis for the code. With that definition, if you permute the rows of a generator matrix, you do not affect the code, but if you permute the columns then in general you will get a different code.

But you also use the word, "equivalent," in your question. Two codes can be different, but still be equivalent. Indeed, on the next page of Hill, Theorem 5.4 asserts that whether you permute the rows or the columns, you still get an equivalent code.

Answer 2

Consider the (rather silly) generator matrix $G=\pmatrix{ 1 &0 &0 \\ 0 & 1 & 0}$. This corresponds to a $(3,2)$ linear code, which has 4 codewords of length 3. These codewords correspond to all the posible 2-binary tuples, plus a trailing zero.

If you permute the rows (or, also, make a linear combination), the resulting code is the same? Well, the mapping of raw inputs to codewords is not the same (in this same, it's not the same code), but the set of codewords (the codebook) is the same (in this sense, it's the same code: usually these are called "equivalent" codes).

What if you permute the columnsof $G$? This reflects on a permutation of the bits positions in the codewords. So the codebooks are different, and the codes are not "equivalent". However, many properties of the code (eg, distance) are the same, the permutation is like a relabelling of the coordinates axis. For a channel without memory (the time index does not matter), the codes could still be consider equivalent. In general, they are not considered equivalent. (For example, column permutation would not preserve cyclically; and burst errors detection would be altered)