# Enumeration of Linear Codes by Applying Methods from Algebraic Combinatorics

## Harald Fripertinger1

### Abstract

It is demonstrated how classes of linear (n,k)-codes can be enumerated using cycle index polynomials and other methods from algebraic combinatorics.

Some results of joined work [9] with Prof. Kerber from the University of Bayreuth on the enumeration of linear codes over GF(q) are presented. Furthermore I will give an introduction to enumeration under finite group actions.

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)n. As usual codewords will be written as rows x=(x1,...,xn). 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 | xi ≠ yi}| is a metric on GF(q)n. (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)...
It can be used to express the quality of a code. A maximum likelihood decoding algorithm for instance corrects (d-1)/2 errors and detects d-1 errors, when d is the minimal distance of the code.

In coding theory two linear (n,k)-codes C1,C2 are called equivalent, if and only if there is an isometry (with respect to the Hamming metric) which maps C1 onto C2. This means there is a linear isomorphism φ: C1→ C2 such that d(x,y)=d(φ(x),φ(y)) for all x,y∈ C1. 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)n. (See [10].) Let's investigate the structure of the group of all linear isometries of GF(q)n. It is enough to consider an isometry φ acting on the standard basis {e1,..., en} where ei=(δi,j)j∈ n. Since φ is a homomorphism, φ(ei)=j=1nαi,jej, 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 π: nn such that αi,π(i) ≠ 0 and φ(ei)=αi,π(i) eπ(i). Since φ is an isomorphism, π must be a permutation, i.e. π∈ Sn. 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},..
which is the semidirect product of GF(q)*n and Sn, where the multiplication is given by
 (ψ,π)(ψ',π') = (ψψπ',ππ'),..
where ψψπ'(i)=ψ(i)ψπ'(i) and ψπ'(i)=ψ'(π-1i). (From now on GF(q)n will be identified with GF(q)n, the set of all mappings from n to GF(q).) The complete monomial group GF(q)* Sn of degree n over GF(q)* acts on GF(q)n in the form of the exponentiation, i.e.
 GF(q)*≀ Sn × GF(q)n→ GF(q)n,    ((ψ,π),(x1,...,xn))↦ (ψ(1)xπ-11,..., ψ(n)xπ-1n)...
For computing the number of isometry classes of linear (n,k)-codes we use methods from algebraic combinatorics, which shall be described now.

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, ..
such that g(g'x)=(gg')x, and 1x=x. In other words, there is a group homomorphism δ from G into the symmetric group SX on X (i.e. the set of all permutations of X) which is called a permutation representation of G on X:
 δ: G→ SX, g ↦ δ(g) =: g, where g(x) := gx. ..
A group action GX defines the following equivalence relation on X:
 x ∼G x'  iff ∃ g ∈ G : x'=gx. ..
The equivalence classes are called orbits, and the orbit of x ∈ X will be indicated as
 G(x) := {gx | g ∈ G }. ..
The set of all orbits will be denoted by
 G\\X := {G(x) | x∈ X}...
For each x ∈ X the stabilizer Gx of x
 Gx := { g | gx=x } ..
is a subgroup of G. The stabilizer of y=gx is given by Gy=gGxg-1, so the stabilizers of all elements in the orbit of x form the conjugacy class of the subgroup Gx of G. The mapping G(x) → G/Gx, gx ↦ gGx is a bijection. So we conclude that
 |G(x) | = |G |/ |Gx |. ..
Finally the set of all fixed points of g∈ G is denoted by
 Xg := { x | gx=x }. ..
The main lemma in the theory of enumeration under finite group actions is the so called Lemma of Cauchy Frobenius. It says that the number of orbits of a finite group G acting on a finite set X is equal to the average number of fixed points:
 |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|...
Interesting examples for group actions can be found as actions on the set YX of all functions from X to Y, where the group action on YX is induced from actions on X or Y.
1. Let GX be a finite group action, then G acts on YX by the definition
 G × YX→ YX,        (g,f)↦ f o g-1, ..
and the number of G-orbits on YX 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)∈ SX.
Proof: A function f∈ YX 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 YX by the definition
 H × YX→ YX,        (h,f)↦ h o f, ..
and the number of H-orbits on YX 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 YX by the definition
 (G × H) × YX→ YX,        ((g,h),f)↦ h o f o g-1, ..
and the number of G × H-orbits on YX is given by
 |G × H\\YX| = .. 1 |G||H| .. ∑(g,h)∈ G × H .. |X| ∏i=1 |Yhi|ai(g),..
where (a1(g),...,a|X|(g)) the cycle type of the permutation g∈ SX is. (I.e. g decomposes into a product of ai(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\\YX 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 YX by the definition
 G × YX→ YX,        (g,f)↦ g o f o g-1, ..
and the number of G-orbits on YX 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 HXG acts in form of the exponentiation on YX
 (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 HXG-orbits on YX 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.
These enumeration methods can be generalized by introducing weights, which are constant on each orbit. Let R be a commutative ring such that Q is a subring of R and let w: X→R be a weight function which is constant on each G-orbit, then the weight of the orbit G(x) can be defined by W(G(x)) := w(x) and from the Cauchy Frobenius Lemma we derive
 .. ∑ω∈ 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 Gx. Having detailed information on the subgroup lattice of the acting group it is possible to determine the number of orbits of stabilizer type Ũ , where Ũ 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 YX.

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 x1,...,x|X| over Q.

 Z(G,X) := .. 1 |G| .. ∑g∈ G .. |X| ∏i=1 xiai(g),..
where (a1(g),...,a|X|(g)) is the cycle type of the permutation g∈ SX. Most of the enumerative formulae for group actions on YX induced from actions on X or Y can be expressed by using the cycle index notion. Let me just give two examples (see [4]):
1. Let HY be a finite group action, then Sn × H acts on Yn according to (*) and H-orbits on Yn 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 Γ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 GLk(q) × GF(q)* Sn as permutation group on (GF(q)k \ {0})n:
 (A,(ψ,π))(Γ) = Aψ(⋅)Γ(π-1⋅), ..
or, more explicitly,
 (A,(ψ,π))(Γ)(i) := Aψ(i)Γ(π-1(i) ). ..

Following Slepian [15], we use the following notation:

Tnkq :=
the number of orbits of functions Γ: n→ GF(q)k \ {0} under the group action of Theorem *, i.e. Tnkq=|(GLk(q) × GF(q)* Sn)\\(GF(q)k \ {0})n|.
Snkq :=
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 xi=0 for all codewords x, and so we should exclude such columns.)
The Snkq can be computed from the Tnkq by
 Snkq = Tnkq-Tn, k-1, q. ..
As initial values we have Sn1q=1 for n∈ ℕ. It is important to realize that
• Tnkq 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 Tn,k-1,q.
Applying Lehmann's bijection for the action of the wreath product GF(q)* Sn we realize that Tnkq is the number of orbits under the following action of Sn × GLk(q) on the set of all functions Γ from n to GF(q)*\\GF(q)k \ {0}:
 (π,A)(Γ) = AΓπ-1,..
where Γ∈ (GF(q)k \ {0})n defines Γ by Γ(i)=GF(q)*(Γ(i)) and Sn acts on the set of the functions (GF(q)*\\(GF(q)k \ {0}))n by π(Γ)=Γ o π-1. Furthermore GLk(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 \ {0} =: PGk-1(q)..
and the representation of GLk(q) as a permutation group is the projective linear group PGLk(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 GLk(q) × Sn on the set of mappings PGk-1(q)n. This set of orbits is equal to the set of orbits of GLk(q) on the set Sn\\PGk-1(q)n, which can be represented by a complete set of mappings of different content, if the content of f∈ PGk-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 GLk(q) on the set of mappings f∈ PGk-1(q)n 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 PGLk(q) acting on PGk-1(q) equation (*) can be applied for computing Tnkq. When restricting the group action of PGLk(q) × Sn 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 GLk(2) can be computed using results of Elspas [5]. In [6] the author generalized this concept for computing the cycle indices of GLk(q) and PGLk(q) acting on GF(q)k or PGk-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.

Isometry classes of linear (n,k)-codes over GF(9)
 n\k 1 2 3 4 1 1 0 0 0 2 1 1 0 0 3 1 2 1 0 4 1 5 3 1 5 1 8 12 4 6 1 17 62 28 7 1 27 430 475 8 1 54 4150 28856 9 1 91 42401 2.417364 10 1 168 413259 197.609449 11 1 275 3.76216 14874.498092 12 1 477 31.8816 1.029632.967128 13 1 764 252.307 65.891528.575554 14 1 1247 1873.44 3920.491447.510867 15 1 1937 13111.7 217978.744960.455289
Isometry classes of injective linear (n,k)-codes over GF(9)
 n\k 1 2 3 4 1 1 0 0 0 2 0 1 0 0 3 0 1 1 0 4 0 2 2 1 5 0 2 7 3 6 0 2 38 21 7 0 1 250 409 8 0 1 2178 26436 9 0 1 19067 2.206042 10 0 1 153106 176.938649 11 0 0 1.11949e+06 13005.200885 12 0 0 7.44464 876508.494146 13 0 0 45.193 54.475570.780948 14 0 0 251.682 3140.099483.972559 15 0 0 1291.73 168727.736939.110698
In order to minimize the number of orbits that must be enumerated or represented, and following Slepian again, we can restrict attention to indecomposable linear (n,k)-codes. Let C1 be a linear (n1,k1)-code over GF(q) with generator matrix Γ1 and let C2 be a linear (n2,k2)-code over GF(q) with generator matrix Γ2, then the code C with generator matrix
(
 Γ1 0 0 Γ2
)
is called the direct sum of the codes C1 and C2, and it will be denoted by C=C1 ⊕ C2. A code C is called decomposable, if and only if it is equivalent to a code which is the direct sum of two or more linear codes. Otherwise it is called indecomposable. The number of all indecomposable linear (n,k)-codes over GF(q) will be denoted by Rnkq.

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 Rnk2. 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 Rnkq. For the rest of this article let n≥ 2.

Theorem: The number Rnkq 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=(a1,...,an-1) of n, (which means that ai∈ ℕ0 and iai=n) such that ai≤ k, while the second sum is over the (n-1)-tuples b=(b1,...,bn-1)∈ ℕn-10, for which ai≤ bi≤ i ai, and bi=k. The numerical results show that for fixed q and n the sequence of Rnkq 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.

Isometry classes of indecomposable linear (n,k)-codes over GF(9)
 n\k 1 2 3 4 1 1 0 0 0 2 1 0 0 0 3 1 1 0 0 4 1 3 1 0 5 1 6 6 1 6 1 14 49 14 7 1 24 402 402 8 1 50 4097 28353 9 1 87 42296 2412712 10 1 163 413066 197.562376 11 1 270 3.7618 14874.037714 12 1 471 31.881 1.029628.744436 13 1 758 252.306 65.891492.470922 14 1 1240 1873.44 3920.491159.098191 15 1 1930 13111.7 217978.742798.601836
Isometry classes of indecomposable injective linear (n,k)-codes over GF(9)
 n\k 1 2 3 4 1 1 0 0 0 2 0 0 0 0 3 0 1 0 0 4 0 2 1 0 5 0 2 5 1 6 0 2 36 13 7 0 1 248 369 8 0 1 2177 26181 9 0 1 19066 2203858 10 0 1 153105 176.919574 11 0 0 1.11949e+06 13005.047772 12 0 0 7.44464 876507.374648 13 0 0 45.193 54.475563.336302 14 0 0 251.682 3140.099438.779534 15 0 0 1291.73 168727.736687.428860
Using double coset methods and the combinatorial method of orderly generation [14][3] we got a complete overview of indecomposable linear (n,k)-codes over GF(q) for quite a number of parameter triples (n,k,q) by constructing lists of representatives of the isometry classes of indecomposable linear codes. (See for instance [1][2][17].)
harald.fripertinger "at" uni-graz.at, May 10, 2016