# How do I check if two linear binary codes are equivalent?

Suppose I have a list of generator matrices $$G_i$$, $$i=1,\ldots N$$, of the same size (each defines an $$n$$-bit linear binary code encoding $$k$$ logical bits).

I consider two codes to be equivalent if they contain the same codewords, or if they differ by permutation of the physical bits. This means that, if $$G'$$ is a generator matrix obtained from $$G$$ by permutation of columns, or elementary row operations (adding and subtracting rows), then $$G'$$ defines a code equivalent to the code defined by $$G$$. I believe this is the standard notion of equivalence.

I want to prune my list of generator matrices to contain only inequivalent codes. One way to partially prune is to put each matrix in reduced row echelon form, and then just delete duplicates, but that doesn't take into account column swaps. Is there a simple way to also take into account column swaps?

If the best solution is exponential time, that is also OK, but I'd like to know what it is.

• I would have thought that the (or at least a) standard notion of equivalence is that the code subspaces are the same. In this case you could just combine pairs of matrices and compute ranks, and compare to the ranks of individual matrices. – Steve Huntsman Jan 8 at 13:44
• Can you clarify what you mean? – guest17 Jan 14 at 9:38