Suppose that $C$ is an binary linear code of length $n$ and dimension $k$ (i.e. it's a $k$-dimensional linear subspace of $\mathbb{F}_2^n$). As usual, the automorphism group of $C$ is the subgroup of all permutations of the coordinates whose induced linear map maps $C$ into $C$. Another way of describing the automorphism group of $C$ is in terms of generator matrices. Let $M$ be a $k \times n$ matrix over $\mathbb{F}_2$ whose rows are a basis for $C$. Then the automorphism group of $C$ is $\{ (U,P) | U^t M P = M\}$, where $U$ is an invertible $k \times k$ matrix, and $P$ is an $n \times n$ permutation matrix. Suppose that we're interested in the subgroup in which $U$ is also a permutation matrix. How big can this subgroup be? In particular, I started out with $M$ as a systematic generator matrix for the Golay code (i.e. it's left hand $k \times k$ submatrix is the identity) and calculated the above subgroup. I tried randomly permuting the columns of $M$ and then putting in in reduced row echelon form, and calculated the same subgroup for it. I found, in 20 trials, that almost all the time the subgroup was of order 20 (a semidirect product of the cyclic groups of order 4 and 5), but in two cases it was as large as having 660 elements. But the automorphism group of the Golay code is $M_{23}$ which is much larger.

Here are some questions

  1. How big is the largest subgroup of the automorphism group that can occur in this way?

  2. If one starts with a generator matrix $M$ and chooses column permutations at random, and then reduces to row echelon form, what is the distribution of the orders of the groups that one produces? In particular, what is the expected value?

  • $\begingroup$ I'm a little bit curious as to how you got interested in this problem. The subgroup you describe depends heavily on the choice of generator matrix, so it is not really an invariant of the code $C$. Were you just toying with the idea, or is there a coding theoretical motivation behind this? $\endgroup$ – Jyrki Lahtonen Jun 18 '14 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.