Introduction
The methods and results presented in this paper are interesting in
the framework of classification of discrete structures
[10][11]. Very often discrete structures
can be described as equivalence classes of certain objects. In such
cases when these equivalence classes can be expressed as orbits
under a group G acting on a set X -- i. e. there is a
mapping G × X→ X, (g,x)↦ gx such that
g1(g2x)=(g1g2)x and
1x=x for all g1,g2∈ G, x∈ X, where
1 is the unit element of G -- then there exist some combinatorial
and algebraic methods for the classification of these structures.
We will apply these methods for the classification of linear codes.
Let n and k≤ n be two positive integers. A linear
(n,k)-code C over the finite field GF(q), where q is
the power of a prime p, is a k-dimensional subspace of
GF(q)n. The error correcting properties of C can be
described by using the minimum distance d(C) of C,
| d(C) := min{d(c,c') | c,c'∈
C, c ≠ c'}, |
where d(c,c') is the Hamming distance of the two code
words, which is the number of different coordinates of c and c';
| d(c,c')=|{1≤ i≤ n |
ci ≠ ci'}|. |
Applying a Maximum-Likelihood decoder, which decodes a
received message into one of the nearest code words in C with
respect to the Hamming distance, it is possible to correct at most
⌊(d(C)-1)/2 ⌋ transmission errors and detect d(C)-1
errors.
If there is a vector space isomorphism ι:C→ C' which
preserves the Hamming distance then C and C' are called isometric.
The isomorphism ι is called an isometry between C and
C' as well. Isometric codes have the same structure with respect to
the Hamming metric, so they have the same error correcting
properties, and we collect them all to one isometry class.
For that reason we are interested rather in the classification of
isometry classes of codes than in the classification of all codes.
Each isometry can be described as a permutation of the coordinates
together with a simultaneous multiplication in each coordinate with
elements of GF(q)* (cf. [9]). To be more precise,
the group of all isometries can be described as the wreath
product GF(q)* ≀Sn of the
multiplicative group GF(q)* and the symmetric group
Sn. Its underlying set is
| {(ψ,π) | ψ∈
GF(q)*n, π∈ Sn}, |
where GF(q)*n is the set of all functions
ψ: n := {1,...,n}→ GF(q)*, and the
multiplication is defined by
| (ψ,π)(ψ',π') :=
(ψψ'π,ππ'), |
together with
| ψψ'π(i) :=
ψ(i)ψ'π(i) :=
ψ(i)ψ'(π-1 i). |
Each element of this group can also be described as an n × n-matrix
M over GF(q) which has in each row and in each column exactly one
entry different from zero. The action of this monomial group on
GF(q)n is given by
| GF(q)*
≀Sn × GF(q)n→
GF(q)n |
| ((ψ,π),v :=
(κ1,...,κn))↦
(ψ(1)κπ-1(1),...,
ψ(n)κπ-1(n)), |
or
It induces a group action on U(n,k,q), the set of all k-dimensional
subspaces of GF(q)n. Usually it is more convenient to
represent an (n,k)-code C by a generator matrix Γ
which is an n × k-matrix over GF(q), the rows of which form a basis
of the code C. Obviously each code has many different generator
matrices; the set of all generator matrices of C is the
orbit3
GLk(q)(Γ) under the following action of the
general linear group GLk(q) on the set
GF(q)n × kk of all n × k-matrices over GF(q)
of rank k.
| GLk(q) × GF(q)n
× kk→ GF(q)n × kk:
(A,Γ)↦ A⋅ Γ. |
For technical reasons, we will drop the condition on the rank of
these matrices Γ, and we will write them as functions from
the set n to GF(q)k \ {0}, since it is obvious
that we can restrict our investigations to generator matrices
having no 0-columns. (A 0-column in a generator matrix causes that
the corresponding coordinate in all code words is 0, so this
coordinate cannot carry any information.) Finally we end up with
the following group action describing the isometry classes of
linear (n,l)-codes for l≤ k as orbits under the particular
action:
| (GLk(q) ×
GF(q)* ≀Sn) ×
(GF(q)k \ {0})n→
(GF(q)k \ {0})n |
This can be made more clear when applying Lehmann's Lemma
[13][14] which reduces the action of the
wreath product GF(q)* ≀Sn on
GF(q)k \ {0} to an action of Sn on
the set of GF(q)*-orbits on
GF(q)k \ {0}. Since each of these orbits
collects all nonzero vectors of a one-dimensional vector space of
GF(q), each of these orbits can be identified with an element of
the projective geometry PGk-1(q).
In our final description the isometry classes of linear
(n,l)-codes for l≤ k correspond to GLk(q) ×
Sn-orbits of functions Γ:n→
PGk-1(q), where Sn operates by permuting the
coordinates, and GLk(q) acts by multiplication from the
left. Since GLk(q) acts on elements of
PGk-1(q) we can consider this action as an action of the
projective linear group PGLk(q).
| (PGLk(q) × Sn) ×
(PGk-1(q))n→
(PGk-1(q))n |
After having described the isometry classes in a suitable way as
orbits under a group action, we were able to compute the number of
these classes for many parameters n, k and q using methods from
Pólya theory (cf. [8][5][4][6]). The main point in all these
calculations was the computation of the cycle index of the
action of PGLk(q) acting on PGk-1(q)
(cf. [7]).
Some further efforts were done, for computing complete lists of
representatives of these isometry classes (cf. [1]). Even though we were applying a
mixture of algebraic and combinatorial algorithms together with
very skilled programming techniques this approach works only for
small parameter values n, k and q. Soon the size of the operating
group together with the number of representatives to be computed
are getting too large. In such situations it is useful, helpful and
makes sense to apply probabilistic methods which allow the
construction of linear codes distributed over all isometry classes
uniformly at random. This way we are able to produce huge sets of
representatives, to check hypotheses on them and afterwards we can
try to prove the valid ones.
harald.fripertinger "at" uni-graz.at, November 17,
2011
