Enumeration of Linear Codes by Applying Methods from Algebraic Combinatorics

Harald Fripertinger¹

IX. Mathematikertreffen Zagreb-Graz, Motovun, June 22 - 25, 1995.

At first let me draw your attention to the enumeration of linear codes. Let p be a prime and let q be a power of p then GF(q) denotes the finite field of q elements. A linear (n,k)-code over the Galois field GF(q) is a k-dimensional subspace of the vector space GF(q)ⁿ. As usual codewords will be written as rows x=(x₁,...,x_n). 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}. The Hamming distance d(x,y) := |{i∈ n | x_i ≠ y_i}| is a metric on GF(q)ⁿ. (The set of integers from 1 to n will be indicated as n.) The minimal distance d(C) of a code C is given by

d(C) := min(x,y)∈ C2, x ≠ y d(x,y)...

In coding theory 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₂. This means there is a linear isomorphism φ: C₁→ C₂ such that d(x,y)=d(φ(x),φ(y)) for all x,y∈ C₁. It can be shown that such a linear isometry between two linear (n,k)-codes can always be extended to an isometry of GF(q)ⁿ. (See [10].) Let's investigate the structure of the group of all linear isometries of GF(q)ⁿ. It is enough to consider an isometry φ acting on the standard basis {e₁,..., e_n} where e_i=(δ_i,j)_{j∈ n}. Since φ is a homomorphism, φ(e_i)=∑_j=1ⁿα_i,je_j, where α_i,j∈ GF(q). Since φ is an isometry, for each i there is exactly one j such that α_i,j ≠ 0. This defines a function π: n→ n such that α_i,π(i) ≠ 0 and φ(e_i)=α_i,π(i) e_π(i). Since φ is an isomorphism, π must be a permutation, i.e. π∈ S_n. Let's define ψ(i) := α_i,π(i), then ψ is a mapping from n to GF(q)^* (where GF(q)^* denotes the multiplicative group of the Galois field), and φ can be identified with the pair (ψ,π). Then the group of all isometries corresponds to the wreath product

GF(q)*≀ Sn = {(ψ,π) | ψ∈ GF(q)*n, π∈ Sn},..

(ψ,π)(ψ',π') = (ψψπ',ππ'),..

GF(q)*≀ Sn × GF(q)n→ GF(q)n,    ((ψ,π),(x1,...,xn))↦ (ψ(1)xπ-11,..., ψ(n)xπ-1n)...

Let me start with the basic concept of a finite group action. (More details can be found in [11].) Let G denote a multiplicative finite group and X a nonempty set. A finite group action _GX of G on X is described by a mapping

G × X → X,         (g,x) ↦ gx, ..

δ: G→ SX, g ↦ δ(g) =: g, where g(x) := gx. ..

x ∼G x'  iff ∃ g ∈ G : x'=gx. ..

G(x) := {gx | g ∈ G }. ..

G\\X := {G(x) | x∈ X}...

Gx := { g | gx=x } ..

|G(x) | = |G |/ |Gx |. ..

Xg := { x | gx=x }. ..

|G\\X | = ..

1 |G |

..

∑ g ∈ G

|Xg |. ..

Proof:

..

∑ g∈ G

|Xg| = ..

∑ g∈ G

..

∑ x ∈ Xg

1 = ..

∑ x∈ X

..

∑ g ∈ Gx

1 = ..

∑ x∈ X

|Gx| = ..

∑ x∈ X

..

|G| |G(x)|

..

= |G|..

∑ ω∈ G\\X

..

∑ x∈ ω

..

1 |G(x)|

= |G|..

∑ ω∈ G\\X

..

∑ x∈ ω

..

1 |ω|

= |G|..

∑ ω∈ G\\X

1 = |G||G\\X|...

1. Let _GX be a finite group action, then G acts on Y^X by the definition

   G × YX→ YX,        (g,f)↦ f o g-1, ..

   and the number of G-orbits on Y^X is given by

   |G\\YX| = ..

   1 |G|

   ..

   ∑ g∈ G

   |Y|c(g),..

   where c(g) is the number of cycles of the permutation g=δ(g)∈ S_X.

   Proof: A function f∈ Y^X is a fixed point of g, if and only if f(g^-1x)=f(x) for all x∈ X, i.e. f is constant on each g-orbit (i.e. cycle of g) on X, and c(g) is the number of all these cycles.

2. Let _HY be a finite group action, then H acts on Y^X by the definition

   H × YX→ YX,        (h,f)↦ h o f, ..

   and the number of H-orbits on Y^X is given by

   |H\\YX| = ..

   1 |H|

   ..

   ∑ h∈ H

   |Yh||X|...

3. Let _GX and _HY be finite group actions, then the direct product G × H acts on Y^X by the definition

   (G × H) × YX→ YX,        ((g,h),f)↦ h o f o g-1, ..

   and the number of G × H-orbits on Y^X is given by

   |G × H\\YX| = ..

   1 |G||H|

   ..

   ∑ (g,h)∈ G × H

   ..

   |X| ∏ i=1

   |Yhi|ai(g),..

   where (a₁(g),...,a_|X|(g)) the cycle type of the permutation g∈ S_X is. (I.e. g decomposes into a product of a_i(g) pairwise disjoint cycles of length i for i=1,...,|X|.) Furthermore there is a bijection

   (G × H)\\YX → G\\(H\\YX),    (G × H)(f)↦ G(H(f)),..

   where G acts on H\\Y^X by g(H(f)) := H(f o g^-1). This bijection is due to de Bruijn.
4. Let _GX and _GY be finite group actions, then G acts on Y^X by the definition

   G × YX→ YX,        (g,f)↦ g o f o g-1, ..

   and the number of G-orbits on Y^X is given by

   |G\\YX| = ..

   1 |G|

   ..

   ∑ g∈ G

   ..

   |X| ∏ i=1

   |Ygi|ai(g),..

   where g is the permutation representation of G on X. The group actions mentioned above can be considered as special cases of this group action. All the group actions mentioned so far can be restricted to group actions on the sets of all injective, surjective or bijective mappings from X to Y.
5. Let _GX and _HY be finite group actions, then the wreath product H≀_XG acts in form of the exponentiation on Y^X

   (H≀XG) × YX→ YX,        ((ψ,g),f)↦ f̃ , ..

   where f̃(x)=ψ(x)f(π^-1x). There is a bijection due to Lehmann ([12][13]) which reduces the action of a wreath product to the action of the group G on the set of all functions from X into the set of all orbits of H on Y:

   Φ: H≀XG\\YX→ G\\(H\\Y)X,    (H≀XG(f)) ↦ G(F), ..

   where F∈ (H\\Y)^X is given by F(x)=H(f(x)), and G acts on (H\\Y)^X by g(F) := F o g^-1. So the number of H≀_XG-orbits on Y^X is given by

   |(H≀XG)\\YX| = ..

   1 |G|

   ..

   ∑ g∈ G

   |H\\Y|c(g)...

   All the group actions above are special cases of this group action.

..

∑ ω∈ G\\X

W(ω) = ..

1 |G|

..

∑ g∈ G

..

∑ x∈ Xg

w(x)...

Another concept is the enumeration of orbits of given stabilizer type. We have already seen that the stabilizer type of an orbit G(x) is the conjugacy class of the stabilizer G_x. Having detailed information on the subgroup lattice of the acting group it is possible to determine the number of orbits of stabilizer type Ũ , where Ũ is the conjugacy class of U≤ G. In my PhD thesis [7] all the enumeration formulae are given for group actions of the form 1,2,3 and 4 on Y^X.

Finally let me introduce the cycle index of a finite group action. Let _GX be a finite group action, then the cycle index of G acting on X is the following polynomial in the indeterminates x₁,...,x_|X| over Q.

Z(G,X) := ..

1 |G|

..

∑ g∈ G

..

|X| ∏ i=1

xiai(g),..

1. Let _HY be a finite group action, then S_n × H acts on Yⁿ according to (*) and H-orbits on Yⁿ is given by

   ..

   ∞ ∑ n=0

   |(Sn × H)\\Yn|xn = Z(H,Y)|xi=∑j=0∞ xij =Z(H,Y)|xi=(1)/(1-xi). ..

2. The group action of above can be restricted to the set of all injective mappings from n to Y. The corresponding generating function is

   ..

   ∞ ∑ n=0

   |(Sn × H)\\Yninj| xn = Z(H,Y)|xi=1+xi, ..

   which is a polynomial.

Returning to the enumeration of linear codes, we translate the equivalence relation for linear (n,k)-codes 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 [15], we use the following notation:

T_nkq :=

the number of orbits of functions Γ: n→ GF(q)^k \ {0} under the group action of Theorem *, i.e. T_nkq=|(GL_k(q) × GF(q)^*≀ S_n)\\(GF(q)^k \ {0})ⁿ|.

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

Snkq = Tnkq-Tn, 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.

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

GF(q)*\\GF(q)k \ {0} =: PGk-1(q)..

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) equation (*) can be applied for computing T_nkq. When restricting the group action of PGL_k(q) × S_n to an action on the set of all injective functions Γ: n → GF(q)^*\\(GF(q)^k \ {0}) one can derive the number of classes of injective codes, which are codes without proportional columns.

In [15] Slepian explained how the cycle index of GL_k(2) can be computed using results of Elspas [5]. In [6] the author 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. These cycle indices are now available in the computer algebra package SYMMETRICA [16]. (See [8] for more details on the implementation.) They were applied for computing the tables of linear codes over GF(9), which can be found on the next pages.

(

Γ1 0 0 Γ2

)

In [15] Slepian proves that every decomposable linear (n,k)-code is equivalent to a direct sum of indecomposable codes, and that this decomposition is unique up to equivalence and order of the summands. Slepian used a generating function scheme for computing the numbers R_nk2. However after constructing these codes the author realized that in some situations this formula doesn't work correctly. For that reason we are giving another formula to determine R_nkq. For the rest of this article let n≥ 2.

Theorem: The number R_nkq is equal to

Snkq - ..

∑ a

..

∑ b

..

n-1 ∏ j=1    aj ≠ 0

( ..

∑ c=(c1,...,caj)∈  ℕaj    j≥ c1≥ ...≥ caj≥ 1, ∑ci=bj

U(j,a,c)),..

where

U(j,a,c) = ..

j ∏ i=1

Z( Sν(i,aj,c),ν(i,aj,c)) | xℓ=Rjiq,    ν(i,aj,c) = |{1≤ l≤ aj | cl=i}|,..

and where the first sum is taken over the cycle types a=(a₁,...,a_n-1) of n, (which means that a_i∈ ℕ₀ and ∑ia_i=n) such that ∑a_i≤ k, while the second sum is over the (n-1)-tuples b=(b₁,...,b_n-1)∈ ℕ^n-1₀, for which a_i≤ b_i≤ i a_i, and ∑b_i=k. The numerical results show that for fixed q and n the sequence of R_nkq is unimodal and symmetric. (It is easy to prove that this sequence must be symmetric, but the proof of the unimodality is still open.)

The numbers of classes of indecomposable linear codes over GF(9) are given in the next two tables.

• References
• Footnotes