Bayreuther Mathematische Schriften 49 (1995), 215-223

Enumeration of isometry-classes of linear (n, k)-codes over GF (q) in SYMMETRICA

Fripertinger Harald

February 4, 1995

Abstract Isometry classes of linear codes can be described as orbits of generator matrices, as it was shown by Slepian. The author demonstrates how they can be enumerated using cycle index polynomials and the tools already incorporated in SYMMETRICA, a computer algebra package devoted to representation theory and combinatorics of symmetric groups and of related classes of groups.

1 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)^{n}, where n denotes the set {0, 1, …, n − 1}. As usual codewords will be written as rows x = (x_{0}, …, x_{n−1}). A k × nmatrix Γ 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_{1}, C_{2} are called equivalent, if and only if there is an isometry (with respect to the Hamming metric) which maps C_{1} onto C_{2}. Using the notion of finite group actions (see [8]) one can easily express equivalence of codes in terms of the wreath product action: C_{1} and C_{2} are equivalent, if and only if there exist (ψ, π) ∈ GF (q)^{∗} ≀ S_{n} = {(ψ, π)|ψ ∈ (GF (q)^{∗})^{n}, π ∈ S_{n}} (where GF (q)^{∗} denotes the multiplicative group of the Galois field) such that (ψ, π)(C_{1}) = C_{2}. The complete monomial group GF (q)^{∗} ≀ S_{n} of degree n over GF (q)^{∗} acts on GF (q)^{n} by the following definition:

GF (q)^{∗} ≀ S_{n} × GF (q)^{n} → GF (q)^{n} (ψ, π) ((x_{i})_{i∈n}) = (ψ(i)x_{π^{−1}(i)})_{i∈n} .

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 ith column of the generator matrix Γ. (We exclude 0-columns for obvious reasons.)

1.1 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 GL_{k}(q) × GF (q)^{∗} ≀ S_{n} as permutation group on (GF (q)^{k} \ {0})^{n}:

(A, (ψ, π))(Γ) = Aψ(·)Γ(π^{−1}·),

or, more explicitly,

(A, (ψ, π))(Γ)(i) := Aψ(i)Γ(π^{−1}(i)).

As a generalization of Slepian’s article [11] we show in [5] that, by using Lehmann’s Lemma about actions of the wreath product, the generating function for the numbers

T_{nkq} := |(GL_{k}(q) × GF (q)^{∗} ≀ S_{n})\\(GF (q)^{k} \ {0})^{n}|

can be computed by the following substitution into the cycle index of the projective group P GL_{k}(q) acting on the k − 1-dimensional projective space P G_{k−1}(q):

∑_{n=0}^{∞} T_{nkq}x^{n} = Z(P GL_{k}(q))|_{x_{i}=∑_{j=0}^{∞} x^{ij}} = Z(P GL_{k}(q))|_{x_{i}= \frac{1}{1−x^{i}}} . (1)

Since the T_{nkq} can be interpreted as numbers of classes of k × n-matrices of rank ≤ k the numbers S_{nkq}, which are the numbers of isometry classes of linear (n, k)-codes with no columns of zeros, satisfy

S_{nkq} = T_{nkq} − T_{n,k−1,q}.  (2)

Restricting our attention to codes with generator matrices Γ, such that Γ̄ : n → P G_{k−1}(q), Γ̄(i): = GF (q)^{∗}(Γ(i)) is injective, we can derive the numbers of isometry classes of ”injective” linear codes, obtaining

S̄_{nkq} = T̄_{nkq} − T̄_{n,k−1,q},  (3)

where the T̄_{nkq} are computed by:

∑_{n=0}^{∞} T̄_{nkq}x^{n} = Z(P GL_{k}(q))|_{x_{i}=1+x^{i}}.  (4)

In [3] it is shown how the cycle index of P GL_{k}(q) acting on P G_{k−1}(q) can be computed. This paper is a generalization of [11] and of Harrison [7, 6], where the cycle indices of GL_{k}(2) are computed. The idea for computing these cycle indices is the following: First determine the conjugacy classes in GL_{k}(q), which can be done by using the theory of normal forms of matrices. Then determine the number of elements in these conjugacy classes, for instance by applying a very nice formula of Kung [9]. Finally compute the cycle type of one representative of each class. (It is well known that all elements in one conjugacy class are of the same cycle type.) These formulae have been implemented into SYMMETRICA, so a C-program for computing S_{ikq} for i = k, …, n can be written in the following way:

INT S_nkq_maxgrad(n,k,q,f)
OP n,k,q,f;
{
OP c,d;
INT erg=OK;
c=callocobject();
d=callocobject();
erg+=T_nkq_maxgrad(n,k,q,c);
if (gt(k,cons_eins))
{
  erg+=dec(k);
  erg+=T_nkq_maxgrad(n,k,q,d);
  erg+=inc(k);
  erg+=sub(c,d,f);
}
else erg+=copy(c,f);
erg+=freeall(c);
erg+=freeall(d);
if (erg!=OK) return error(" in computation of S_nkq_maxgrad");
return erg;
}

The program for the computation of the T_{ikq} for i ≤ n is the following:

INT T_nkq_maxgrad(n,k,q,f)
OP k,q,n,f;
{
OP c,d;
INT erg=OK;
c=callocobject();
d=callocobject();
erg+=zykelind_pglkq(k,q,c);
erg+=numberofvariables(c,d);
erg+=co_polya3_sub(c,d,n,f);
erg+=freeall(c);
erg+=freeall(d);
if (erg!=OK) return error(" in computation of T_nkq_maxgrad");
return erg;
}

With the routine zykelind_pglkq(k,q,c) one can compute the cycle index of P GL_{k−1}(q) acting on the projective space P G_{k−1}(q), and the routine co_polya3_sub(c,d,n,f) computes the first part of degree ≤ n of the substitution x_{i} ↦ ∑_{j=0}^{∞} x^{ij} in the polynomial c. Both these routines can be found in the source file zykelind.c.

2 Indecomposable codes

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 C_{1} be a linear (n_{1}, k_{1})-code over GF (q) with generator matrix Γ_{1} and let C_{2} be a linear (n_{2}, k_{2})-code over GF (q) with generator matrix Γ_{2}, then the code C with generator matrix

Γ: = ( \begin{matrix}Γ_{1} & 0 \\ 0 & Γ_{2} \end{matrix} )

is called the direct sum of the codes C_{1} and C_{2}, and it will be denoted by C = C_{1} ⊕C_{2}. 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.

Since there are some errors in Slepian’s table of the numbers of isometry classes of indecomposable (n, k)-codes, denoted by R_{nkq} or R̄_{nkq}, the following theorem is proved in [5]:

2.1 Theorem The number R_{nkq} is equal to

S_{nkq} − ∑_{a} ∑_{b} ∏_{{j=1 \atop a_{j} ≠0}}^{n−1} (  ∑_{{c=(c_{1},...,ca_{j} )∈IN^{a_{j}} \atop j≥c_{1}≥...≥ca_{j} ≥1, ∑ c_{i}=b_{j}}} U(j, a, c)) ,  (5)

where

U(j, a, c) = ∏_{i=1}^{j} Z(S_{ν(i,a_{j},c)})|_{x_{ℓ}=R_{jiq}}, ν(i, a_{j}, c) = |{1 ≤ l ≤ a_{j}|c_{l} = i}| ,

and where the first sum is taken over the cycle types a = (a_{1}, …, a_{n−1}) of n, (which means that a_{i} ∈ IN_{0} and ∑ ia_{i} = n) such that ∑ a_{i} ≤ k, while the second sum is over the (n − 1)-tuples b = (b_{1}, …, b_{n−1}) ∈ IN_{0}^{n−1}, for which a_{i} ≤ b_{i} ≤ ia_{i}, and ∑ b_{i} = k. In the same way the R̄_{nkq} can be computed from the S̄_{nkq}. 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.)

This formula is implemented in SYMMETRICA as well. For instance for computing the tables of S_{nkq} and R_{nkq} one can use the next program:

INT co_all_codes()
{
OP n,k,q,R,S;
INT i,j;
INT erg=OK;
n=callocobject();
k=callocobject();
q=callocobject();
S=callocobject();
R=callocobject();
erg+=printeingabe("maximum value of n=? ");
erg+=scan(INTEGER,n);

erg+=printeingabe("maximum value of k=? ");
erg+=scan(INTEGER,k);
erg+=printeingabe("q=? ");
erg+=scan(INTEGER,q);
erg+=all_codes(n,k,q,S,R);
erg+=println(S);
erg+=println(R);
erg+=freeall(n); erg+=freeall(k); erg+=freeall(q);
erg+=freeall(S); erg+=freeall(R);
if (erg!=OK) return error(" in computation of co_all_codes");
return erg;
}

The routine all_codes(n,k,q,S,R) first computes the numbers T_{ijq} for 1 ≤ i ≤ n and 1 ≤ j ≤ k by (1), then the S_{ijq} by (2) and finally the R_{ijq} by (5). For computing the numbers of classes of injective linear (n, k)-codes by (3), (4) and (5) there is the routine all_inj_codes(n,k,q,S,R). The following tables for q = 8, n ≤ 15 and k ≤ 4 were computed using these two routines:

Table 1: Number of isometry classes of linear (n, k)-codes over GF (8)

\begin{matrix}n\k & 1 & 2 & 3 & 4 \\ 1 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 \\ 3 & 1 & 2 & 1 & 0 \\ 4 & 1 & 4 & 3 & 1 \\ 5 & 1 & 6 & 9 & 4 \\ 6 & 1 & 13 & 43 & 21 \\ 7 & 1 & 20 & 252 & 282 \\ 8 & 1 & 38 & 1995 & 11897 \\ 9 & 1 & 63 & 16604 & 697905 \\ 10 & 1 & 108 & 132128 & 40.614006 \\ 11 & 1 & 172 & 986280 & 2187.942319 \\ 12 & 1 & 285 & 6.875894 & 108580.294923 \\ 13 & 1 & 438 & 44.880497 & 4.985498.095659 \\ 14 & 1 & 685 & 275.497100 & 212.944334.871779 \\ 15 & 1 & 1027 & 1597.384440 & 8503.509808.998891 \end{matrix}

Table 2: Number of isometry classes of indecomposable linear (n, k)-codes over GF (8)

\begin{matrix}n\k & 1 & 2 & 3 & 4 \\ 1 & 1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 \\ 4 & 1 & 2 & 1 & 0 \\ 5 & 1 & 4 & 4 & 1 \\ 6 & 1 & 10 & 33 & 10 \\ 7 & 1 & 17 & 231 & 231 \\ 8 & 1 & 34 & 1956 & 11596 \\ 9 & 1 & 59 & 16529 & 695614 \\ 10 & 1 & 103 & 131993 & 40.595108 \\ 11 & 1 & 167 & 986040 & 2187.791284 \\ 12 & 1 & 279 & 6.875485 & 108579.157553 \\ 13 & 1 & 432 & 44.879807 & 4.985490.082276 \\ 14 & 1 & 678 & 275.495976 & 212.944281.977581 \\ 15 & 1 & 1020 & 1597.382635 & 8503.509480.606942 \end{matrix}

Table 3: Number of isometry classes of injective linear (n, k)-codes over GF (8)

\begin{matrix}n\k & 1 & 2 & 3 & 4 \\ 1 & 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 \\ 3 & 0 & 1 & 1 & 0 \\ 4 & 0 & 1 & 2 & 1 \\ 5 & 0 & 1 & 4 & 3 \\ 6 & 0 & 1 & 24 & 14 \\ 7 & 0 & 1 & 131 & 232 \\ 8 & 0 & 1 & 900 & 10507 \\ 9 & 0 & 1 & 6154 & 613247 \\ 10 & 0 & 0 & 38344 & 34.772483 \\ 11 & 0 & 0 & 217432 & 1812.280847 \\ 12 & 0 & 0 & 1119290 & 86639.601001 \\ 13 & 0 & 0 & 5.242484 & 3.818387.464701 \\ 14 & 0 & 0 & 22.449375 & 156.004956.091612 \\ 15 & 0 & 0 & 88.267837 & 5938.561168.433472 \end{matrix}

Table 4: Number of isometry classes of injective indecomposable linear (n, k)-codes over GF (8)

\begin{matrix}n\k & 1 & 2 & 3 & 4 \\ 1 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 \\ 3 & 0 & 1 & 0 & 0 \\ 4 & 0 & 1 & 1 & 0 \\ 5 & 0 & 1 & 3 & 1 \\ 6 & 0 & 1 & 23 & 9 \\ 7 & 0 & 1 & 130 & 207 \\ 8 & 0 & 1 & 899 & 10374 \\ 9 & 0 & 1 & 6153 & 612345 \\ 10 & 0 & 0 & 38343 & 34.766326 \\ 11 & 0 & 0 & 217432 & 1812.242500 \\ 12 & 0 & 0 & 1119290 & 86639.383565 \\ 13 & 0 & 0 & 5.242484 & 3.818386.345408 \\ 14 & 0 & 0 & 22.449375 & 156.004950.849125 \\ 15 & 0 & 0 & 88.267837 & 5938.561145.984095 \end{matrix}

In [5] there are tables of R_{nkq} and R̄_{nkq} for q = 2, 3, 4, 5, 7. Tables of S_{nkq} can be found in [3, 4] and in the article of Wild [12], when interpreting matroids as linear codes. Extensions of the tables given in [11] for the binary case were evaluated by Lattermann in [10]. In her thesis [1], Arnold evaluated transversals of isometry classes of linear codes. Another implementation, due to Betten allowed to evaluate representatives of all the isometry classes of indecomposable binary (n, k)- codes for n ≤ 12 except for the case of n = 12 and k = 6. Use was made of orderly generation in connection with isomorphism checking [2]. Details will be given elsewhere.

References

[1] E. Arnold. Äquivalenzklassen linearer Codes. Master’s thesis, Universität Bayreuth, 1993.

[2] A. Betten. Gruppenaktionen auf Verbänden und die Konstruktion kombinatorischer Objekte. Master’s thesis, Universität Bayreuth. To appear.

[3] H. Fripertinger. Cycle indices of linear, affine and projective groups. To be published.

[4] H. Fripertinger. Zyklenzeiger linearer Gruppen und Abzählung linearer Codes. Submitted paper.

[5] H. Fripertinger and A. Kerber. Isometry classes of indecomposable codes. Submitted paper.

[6] M.A. Harrison. On the classification of Boolean functions by the general linear and affine groups. J. Soc. Appl. Ind. Math., 12:285 – 299, 1964.

[7] M.A. Harrison. Counting Theorems and their Applications to Switching Theory. In A. Mukhopadyay, editor, Recent Developments in Switching Functions, chapter 4, pages 85 – 120. Academic Press, 1971.

[8] A. Kerber. Algebraic Combinatorics via Finite Group Actions. B. I. Wissenschaftsverlag, Mannheim, Wien, Zürich, 1991. ISBN 3-411-14521-8.

[9] J.P.S. Kung. The Cycle Structure of a Linear Transformation over a Finite Field. Linear Algebra and its Applications, 36:141 – 155, 1981.

[10] D. Lattermann. Computerunterstützte Abzählung von Codes. Master’s thesis, Universität Bayreuth, 1994.

[11] D. Slepian. Some Further Theory of Group Codes. The Bell System Technical Journal, 39:1219 – 1252, 1960.

[12] M. Wild. Enumeration of binary and ternary matroids and other applications of the Brylawski–Lucas–Theorem. Preprint 1693, Technische Hochschule Darmstadt, November 1994.

Address of the author: Harald Fripertinger Institut für Mathematik Karl-Franzens-Universität Graz Heinrichstr. 36/4 A–8010 Graz

harald.fripertinger@balu.kfunigraz.ac.at