Isometry classes of linear codes

Isometry classes of linear codes

The complete monomial group GF(q)^* wr 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 wr _XG on Y^X:

  (y,p)(f)(x)= y(x)f(p^-1x).

Theorem  The matrices corresponding to the two functions G₁ and G₂ from n to GF(q)^k \ {0} are generator matrices of two equivalent codes, if and only if G₁ and G₂ lie in the same orbit of the following action of GL_k(q)´GF(q)^* wr S_n as permutation group on (GF(q)^k \ {0} )ⁿ:

(A,(y,p))(G)=Ay(·)G(p^-1·),

Following Slepian, we use the following notation:

T_nkq:=

the number of orbits of functions G:n -> GF(q)^k \ {0} under the group action of *, i.e. T_nkq=|(GL_k(q) ´GF(q)^* wr S_n)\\(GF(q)^k \ {0} )ⁿ|.

bar (T)_nkq:=

the number of orbits of functions G:n -> GF(q)^k \ {0} under the group action of *, such that for all i,jÎn, i¹j and all aÎGF(q)^* the value of G(i) is different from aG(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.)

bar (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 aÎGF(q)^* there is some codeword x such that x_i¹ax_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.)

bar (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.

  W_nkq=å_i=kⁿS_ikq, S_nkq=T_nkq-T_{n, k-1, q}, bar (S)_nkq=bar (T)_nkq-bar (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 G of the same orbit have the same rank.
• The number of orbits of functions G which induce matrices of rank less or equal k-1 is T_n,k-1,q. (This proposition holds for bar (T)_nkq as well.)

In the case q=2 the wreath product GF(q)^* wr 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)) | _{xi=åj=0^¥x^ij}= Z(GL_k(2)) | _{xi=(1)/(1-xⁱ)}

  å_n=0^¥bar (T)_nk2xⁿ= Z(GL_k(2)) | _xi=1+xⁱ.

F:GF(q)^* wr S_n\\(GF(q)^k \ {0} )ⁿ -> S_n\\(GF(q)^*\\(GF(q)^k \ {0} ))ⁿ ,

GF(q)^* wr S_n(G) -> S_n(bar (G))

bar (G):n -> GF(q)^*\\(GF(q)^k \ {0} ), i -> GF(q)^*(G(i))

(p,A)(bar (G))=Abar (G)p^-1,

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)ⁿ. 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:

1. 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.
2. Determination of the order of the conjugacy classes, which can be found in Dickson, Green or Kung [2][5][8].
3. 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ÎN | f(x) | xⁿ-1}

   and the subexponent is

   subexp(f(x)):=min{nÎN | $aÎGF(q)^*:f(x) | xⁿ-a} .

   This element aÎ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.
4. Determination of the cycle index by applying formula (*).

Isometry classes of linear codes