Isometry
classes of linear codes |

The *complete monomial group*
GF(q)^{*}≀S_{n} of
degree n over GF(q)^{*} acts on GF(q)^{n} as it was
described above (see equation (*)) in the more general case of H≀_{X}G on Y^{X}:

In order to apply the results of the theory of finite group actions, this equivalence relation for linear (n,k)-codes is translated into an equivalence relation for generator matrices of linear codes, and these generator matrices are considered to be functions Γ: n→ GF(q)

(ψ,π)(f)(x)= ψ(x)f(π ^{-1}x).^{.}_{.}

**Theorem** *The matrices
corresponding to the two functions Γ _{1} and
Γ_{2} from n to GF(q)^{k} \ {0} are
generator matrices of two equivalent codes, if and only if
Γ_{1} and Γ_{2} lie in the same orbit
of the following action of GL_{k}(q) ×
GF(q)^{*}≀S_{n} as
permutation group on
(GF(q)^{k} \ {0})^{n}:*

(A,(ψ,π))(Γ)=Aψ(⋅)Γ(π ^{-1}⋅),^{.}_{.}

(A,(ψ,π))(Γ)(i):=Aψ(i)Γ(π ^{-1}(i) ).^{.}_{.}

Following Slepian, we use the following notation:

**T**_{nkq}:=- the number of orbits of functions Γ: n→
GF(q)
^{k}\ {0} under the group action of *, i.e. T_{nkq}=|(GL_{k}(q) × GF(q)^{*}≀S_{n})\\(GF(q)^{k}\ {0})^{n}|. **T**_{nkq}:=- the number of orbits of functions Γ: n→
GF(q)
^{k}\ {0} under the group action of *, such that for all i,j∈ n, i ≠ j and all α∈ GF(q)^{*}the value of Γ(i) is different from αΓ(j). (In the case q=2, this is the number of injective functions G.) **S**_{nkq}:=- the number of equivalence classes of linear (n,k)-codes over
GF(q) with no columns of zeros. (A linear (n,k)-code has columns of
zeros, if and only if there is some i∈ n such that
x
_{i}=0 for all codewords x, and so we should exclude such columns.) **S**_{nkq}:=- the number of classes of injective linear (n,k)-codes over
GF(q) with no columns of zeros. (A linear (n,k)-code is called
injective, if and only if for all i,j∈ n, i ≠ j and
α∈ GF(q)
^{*}there is some codeword x such that x_{i}≠ αx_{j}.) **R**_{nkq}:=- the number of classes of indecomposable linear (n,k)-codes over GF(q) with no columns of zeros. (The definition of an indecomposable code will be given later.)
**R**_{nkq}:=- the number of classes of indecomposable, injective linear (n,k)-codes over GF(q) with no columns of zeros.
**W**_{nkq}:=- be the number of classes of linear (n,k)-codes over GF(q) with columns of zeros allowed.

As initial values we have S

W _{nkq}=^{.}_{.}n

∑

i=kS _{ikq}, S_{nkq}=T_{nkq}-T_{n,k-1,q}, S_{nkq}=T_{nkq}-T_{n,k-1,q}.^{.}_{.}

- T
_{nkq}is the number of orbits of functions from n to GF(q)^{k}\ {0} without any restrictions on the rank of the induced matrix. - All matrices which are induced from functions Γ of the same orbit have the same rank.
- The number of orbits of functions Γ which induce matrices
of rank less or equal k-1 is T
_{n,k-1,q}. (This proposition holds for T_{nkq}as well.)

In the case q=2 the wreath product GF(q)^{*}≀S_{n} becomes the group S_{n},
and so there is the group GL_{k}(2) acting on
GF(2)^{k} \ {0} and the symmetric group
S_{n} acting on n. Applying the formulae (*) and (*)
we get

and

^{.}_{.}∞

∑

n=0T _{nk2}x^{n}= Z(GL_{k}(2))|_{xi=∑j=0∞ xij}= Z(GL_{k}(2))|_{xi=(1)/(1-xi)}^{.}_{.}

In the case q ≠ 2 the wreath product GF(q)

^{.}_{.}∞

∑

n=0T _{nk2}x^{n}= Z(GL_{k}(2))|_{xi=1+xi}.^{.}_{.}

Φ: GF(q) ^{*}≀S_{n}\\(GF(q)^{k}\ {0})^{n}→ S_{n}\\(GF(q)^{*}\\(GF(q)^{k}\ {0}))^{n},^{.}_{.}

where

GF(q) ^{*}≀S_{n}(Γ)↦ S_{n}(Γ)^{.}_{.}

and S

Γ: n→ GF(q) ^{*}\\(GF(q)^{k}\ {0}), i↦ GF(q)^{*}(Γ(i))^{.}_{.}

where GL

(π,A)(Γ)=AΓπ ^{-1},^{.}_{.}

and the representation of GL

GF(q) ^{*}\\GF(q)^{k}=PG_{k-1}(q)^{.}_{.}

This proves in fact the following to be true:

**Theorem** *The isometry classes of linear (n,k)-codes
over GF(q) are the orbits of GL _{k}(q) × S_{n} on
the set of mappings PG_{k-1}(q)^{n}. This set of
orbits is equal to the set of orbits of GL_{k}(q) on the
set S_{n}\\PG_{k-1}(q)^{n}, which can be
represented by a complete set of mappings of different content, if
the content of f∈ PG_{k-1}(q)^{n} is defined
to be the sequence of orders of inverse images
|f^{-1}(x)|.*

*Thus the set of isometry classes of linear (n,k)-codes over
GF(q) is equal to the set of orbits of GL _{k}(q) on the set
of mappings f∈ PG_{k-1}(q) of different content that
form k × n-matrices of rank k.*

*The particular classes of elements with orders of inverse
images |f ^{-1}(x)|≤ 1 are the classes consisting of
Hamming codes.*

Knowing the cycle index of PGL_{k}(q) acting on
PG_{k-1}(q) the equations (*)
and (*) can be applied again.

In [13] Slepian explained
how the cycle index of GL_{k}(2) can be computed using
results of Elspas [3]. The first
author [4] generalized this
concept for computing the cycle indices of GL_{k}(q) and
PGL_{k}(q) acting on GF(q)^{k} or
PG_{k-1}(q) respectively. The steps of the method used were
the following ones:

- Determination of the conjugacy classes of GL
_{k}(q) by applying the theory of normal forms of matrices (or vector space endomorphisms). This theory can be found in many textbooks of algebra. - Determination of the order of the conjugacy classes, which can be found in Dickson, Green or Kung [2][5][8].
- Determination of the cycle type of a linear map or of a
projectivity respectively. Since normal forms of regular matrices
are strongly connected with companion and hypercompanion matrices
(see [6]) of monic,
irreducible polynomials over GF(q) it is important to know the
*exponent*or*subexponent*of such polynomials (see [11][6]). The exponent of such a polynomial f(x)∈ GF(q)[x] is defined to beexp(f(x)) := min{n∈ ℕ | f(x) | x ^{n}-1}^{.}_{.}subexp(f(x)) := min{n∈ ℕ | ∃ α∈ GF(q) ^{*}:f(x) | x^{n}-α}.^{.}_{.}_{q}^{*}is uniquely defined, and it is called the*integral element*of f(x). The exponent of f(x) can be used to compute the cycle type of the companion or hypercompanion matrices of a monic, irreducible polynomial f(x), and by a direct product formula for cycle indices the cycle types of the normal forms in GL(k,F_{q}) can be derived. Using the subexponent of f(x) and defining a formula similar to the direct product formula of cycle indices, which depends on the integral element of f(x) as well, the cycle type of a projectivity can be computed. - Determination of the cycle index by applying formula (*).

harald.fripertinger "at" uni-graz.at, May 10, 2016

Isometry
classes of linear codes |