Application: The automorphism group of a code

Let $C\subset \mathbb{F}_q^n$ be a code. It is not necessary at this point for $C$ to be linear. Let

$$Aut(C)=\{A\in GL(n,\mathbb{F}_q)\ \vert\ Ac\in C,\ {\rm for\ all}\ c\in C\}.$$

This is called the automorphism group of $C$

Proposition 5.5.1   $Aut(C)$ is a group under ordinary matrix multiplication.

proof: The identity matrix is in $Aut(C)$. Associativity is an inherited property from $GL(n,\mathbb{F}_q)$. The set $Aut(C)$ is closed under multiplication since the defining property is preserved. The existence of inverses is inherited from $GL(n,\mathbb{F}_q)$. $\Box$

Example 5.5.2   Let $C$ be the $[7,4,3]$ Hamming code over $\mathbb{F}_2$ having generator matrix

$$G=\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0... ... 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right).$$

The elements of $C$ are

$$\begin{array}{cc} (0, 0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 0... ... (1, 1, 0, 0, 1, 0, 1), (1, 1, 1, 1, 1, 1, 1) \end{array}$$

The automorphism group is a group of order $168$ generated by

$$\left( \begin{array}{ccccccc} 1& 0& 0& 0& 0& 0& 0\\ 0& ... ... 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 1 \end{array} \right),\ \ \$$

$$\left( \begin{array}{ccccccc} 1& 0& 0& 0& 0& 0& 0\\ 0& ... ...0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 0 \end{array} \right).$$

These are the permutation matrices associated with the coordinate permutations $(3, 5)(6, 7)$, $(1, 3)(4, 5)$, $(2, 3)(4, 7)$, and $(3, 7)(5, 6)$.

Let $Mon(n,\mathbb{F}_q)$ denote the group of of $n\times n$ monomial matrices with entries in $\mathbb{F}_q^\times$. These are the matrices which have exactly one non-zero element in each row and column. Let $C,C'\subset \mathbb{F}_q^n$ be two linear codes. We say that $g\in Mon(n,\mathbb{F}_q)$ is an isometry between $C$ and $C'$ if

• $g:C\rightarrow C'$ is an isomorphism of vector spaces,
• for all $c_1,c_2\in C$,
  $$d(c_1,c_2)=d(g(c_1),g(c_2)).$$

In this case, we say $C,C'$ are isometric (with respect to the Hamming metric).

Exercise 5.5.3   Show that two codes are isometric if and only if they are equivalent.

Exercise 5.5.4   Find the automorphism group of the binary repetition code of length $3$,

$$C=\{(0,0,0),(1,1,1)\}.$$