Isometry classes of linear codes

Isometry classes of linear codes

A linear (n,k)-code over the Galois field GF(q) is a k-dimensional subspace of the vector space Y^X:=GF(q)ⁿ. As usual codewords will be written as rows x=(x₀,...,x_n-1). A k × n-matrix Γ over GF(q) is called a generator matrix of the linear (n,k)-code C, if and only if the rows of Γ form a basis of C, so that C={x⋅ Γ | x∈ GF(q)^k}. Two linear (n,k)-codes C₁,C₂ are called equivalent, if and only if there is an isometry (with respect to the Hamming metric) which maps C₁ onto C₂. Using the notion of finite group actions one can easily express equivalence of codes in terms of the wreath product action introduced above: C₁ and C₂ are equivalent, if and only if there exist (ψ, π)∈ GF(q)^*≀S_n (where GF(q)^* denotes the multiplicative group of the Galois field) such that (ψ,π)(C₁)=C₂.

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

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

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)^k \ {0} where Γ(i) is the i-th column of the generator matrix Γ. (We exclude 0-columns for obvious reasons.)

Theorem The matrices corresponding to the two functions Γ₁ and Γ₂ from n to GF(q)^k \ {0} are generator matrices of two equivalent codes, if and only if Γ₁ and Γ₂ 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})ⁿ:

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

or, more explicitly,

(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})ⁿ|.
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.

The following formulae hold:

W_nkq=^._. n
∑
i=k S_ikq, S_nkq=T_nkq-T_n,k-1,q, S_nkq=T_nkq-T_n,k-1,q. ^._.

As initial values we have S_n1q=1 for n∈ ℕ, S_11q=1 and S_n1q=0 for n>1. It is important to realize that

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 next section we will show that the R_nkq or R_nkq can be computed from the S_nkq or S_nkq respectively, so the main problem is the computation of the T_nkq or T_nkq.

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

^._. ∞
∑
n=0 T_nk2xⁿ= Z(GL_k(2))| _{x_i=∑_j=0^∞
x^ij}= Z(GL_k(2))| _{x_i=(1)/(1-xⁱ)} ^._.

and

^._. ∞
∑
n=0 T_nk2xⁿ= Z(GL_k(2))| _{x_i=1+xⁱ}. ^._.

In the case q ≠ 2 the wreath product GF(q)^*≀S_n acts both on range and domain of the functions Γ. Applying Lehmann's Lemma * there is the bijection

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

GF(q)^*≀S_n(Γ)↦ S_n(Γ)^._.

where

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

and S_n acts on (GF(q)^*\\(GF(q)^k \ {0}))ⁿ by π(Γ)=Γ o π^-1. Using this bijection we have to investigate the following action of S_n × GL_k(q):

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

where GL_k(q) acts on GF(q)^*\\(GF(q)^k \ {0}) by A(GF(q)^*(v))=GF(q)^*(Av). The set of the GF(q)^*-orbits GF(q)^*\\(GF(q)^k \ {0}) is the (k-1)-dimensional projective space:

GF(q)^*\\GF(q)^k=PG_k-1(q)^._.

and the representation of GL_k(q) as a permutation group is the projective linear group PGL_k(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)ⁿ. This set of orbits is equal to the set of orbits of GL_k(q) on the set S_n\\PG_k-1(q)ⁿ, which can be represented by a complete set of mappings of different content, if the content of f∈ PG_k-1(q)ⁿ 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 be

exp(f(x)) := min{n∈ ℕ | f(x) | xⁿ-1}^._.

and the subexponent is

subexp(f(x)) := min{n∈ ℕ | ∃ α∈ GF(q)^*:f(x) | xⁿ-α}.^._.

This element α∈ F_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 (*).

These cycle indices are now available in the computer algebra package SYMMETRICA. Tables obtained this way are shown lower down.

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

Isometry classes of linear codes