Zyklenzeiger linearer Gruppen und Abzählung linearer Codes

Harald Fripertinger

Vortrag im Rahmen des 33. Séminaire Lotharingien de Combinatoire in der TU Bergakademie Freiberg vom 11. bis 17. September 1994

Abstract Verfahren zur Berechnung der Zyklenzeiger der natürlichen Aktionen von linearen und projektiven Gruppen werden vorgeführt und bei der Bestimmung der Anzahl von Isometrieklassen linearer Codes angewendet.

Die Berechnung der Zyklenzeiger linearer Gruppen über dem endlichen Körper F_{2} (bestehend aus zwei Elementen) und die Bestimmung der Anzahl von Klassen binärer linearer (n, k)-Codes erfolgte bereits Ende der 50-ger Jahre; siehe [10]; nun ist es interessant, Verallgemeinerungen davon auf beliebige endliche Körper F_{q} (mit q = p_{0}^{r}, p_{0} eine Primzahl (die Charakteristik von F_{q}), q die Mächtigkeit des Körpers) zu untersuchen. Notation und Sprechweisen sind an [6] angepaßt.

1 Zyklenzeiger linearer Gruppen

Die Gruppe GL(k, F_{q}): = {A ∈ M_{k}(F_{q})|A^{−1} existiert} (die Gruppe aller regulären k × k-Matrizen, bzw. aller Matrizen A mit det(A) ∈ F_{q}^{∗}: = F_{q} \ {0}) operiert auf dem Vektorraum F_{q}^{k}

GL(k, F_{q}) × F_{q}^{k} → F_{q}^{k}, (A, v) ↦ Av

auf natürliche Weise. Nach Definition berechnet sich der Zyklenzeiger dieser Gruppenaktion als

Z(GL(k, F_{q}), F_{q}^{k}) = \frac{1}{|GL(k, F_{q})|} ∑_{A∈GL(k,F_{q})} ∏_{i=1}^{q^{k}} x_{i}^{a_{i}(A)} ∈ IQ[x_{1}, x_{2}, …],

wobei (a_{1}(A), a_{2}(A), …) der Zykeltyp der von A induzierten Permutation ist, d.h. diese Permutation zerfällt in a_{i}(A) disjunkte Zykel der Länge i. Zur rationellen Bestimmung dieses Zyklenzeigers gehe man wie folgt vor:

1. Bestimmung der Konjugiertenklassen in GL(k, F_{q}).

2. Bestimmung der Mächtigkeit der Konjugiertenklassen.

3. Bestimmung des Zykeltyps eines Repräsentanten jeder Konjugiertenklasse. (Es ist bekannt, daß konjugierte Elemente vom gleichen Zykeltyp sind.)

1.1 Bestimmung der Konjugiertenklassen in GL(k, F_{q})

Die dafür benötigte Theorie ist die Theorie der Normalformen von Matrizen bzw. Vektorraumendomorphismen A, welche auf der Zerlegung eines Vektorraums in bezüglich A zyklische Unterräume aufbaut. Man spricht dann von klassischen kanonischen Normalformen oder rational kanonischen Normalformen. Diese sollen kurz erläutert werden: Sei p(x) = ∑_{i=0}^{d} a_{i}x^{i} mit a_{d} = 1 ein normiertes Polynom in F_{q}[x], dann ist die Begleitmatrix B(p) von p(x) definiert als folgende d × d-Matrix:

B(p): = ( \begin{matrix}0 & 0 & … & 0 & 0 & −a_{0} \\ 1 & 0 & … & 0 & 0 & −a_{1} \\ 0 & 1 & … & 0 & 0 & −a_{2} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & … & 1 & 0 & −a_{d−2} \\ 0 & 0 & … & 0 & 1 & −a_{d−1} \end{matrix} ) .

Weiters ist die Hyperbegleitmatrix von p^{j}(x) folgende Blockmatrix

H(p^{j}): = ( \begin{matrix}B(p) & 0 & 0 & … & 0 & 0 \\ E_{1d} & B(p) & 0 & … & 0 & 0 \\ 0 & E_{1d} & B(p) & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & … & B(p) & 0 \\ 0 & 0 & 0 & … & E_{1d} & B(p) \end{matrix} )\} j-mal.

Dabei ist

E_{1d} = (e_{ij})_{1≤i,j≤d} mit e_{ij} = \{ \begin{matrix}1 & falls (i, j) = (1, d), \\ 0 & sonst. \end{matrix}

Falls λ = (λ_{1}, λ_{2}, …) einen Zykeltyp einer Zahl c ∈ IN bezeichne, d.h. c = ∑_{i} iλ_{i}, so sei D(p, λ) jene Blockdiagonalmatrix bestehend aus λ_{1} Begleitmatrizen B(p), λ_{2} Hyperbegleitmatrizen H(p^{2}) usw.

D(p, λ) = diag(\underbrace{B(p), …, B(p)}_{λ_{1}}, \underbrace{H(p^{2}), …, H(p^{2})}_{λ_{2}}, …).

Als Teiler des charakteristischen Polynoms von einem Vektorraumisomorphismus A ∈ GL(k, F_{q}) können alle über F_{q}[x] irreduziblen normierten Polynome p(x) ∈ F_{q}[x] vom Grad kleiner gleich k auftreten mit Ausnahme des Polynoms p(x) = x. Man bestimme alle diese Polynome, bezeichne sie mit p_{1}, p_{2}, … und bestimme deren Grade d_{1}, d_{2}, . . .. Um alle Konjugiertenklassen von GL(k, F_{q}) zu bestimmen, berechne man alle Lösungen c = (c_{1}, c_{2}, …) von

∑_{i} c_{i}d_{i} = k,

und zu jeder Lösung bestimme man alle möglichen Zykeltypen

λ^{(i)} = (λ_{1}^{(i)}, λ_{2}^{(i)}, …)

von c_{i}. Dann bilde man alle möglichen Blockdiagonalmatrizen der Form

diag (D(p_{1}, λ^{(1)}), D(p_{2}, λ^{(2)}), …) .

In jeder Konjugiertenklasse liegt dann genau so eine Blockdiagonalmatrix. Im weiteren werden wir feststellen, daß man für die Berechnung des Zyklenzeigers von GL(k, F_{q}) nicht die genaue Gestalt der einzelnen Konjugiertenklassen kennen muß. Insbesondere muß man nicht die einzelnen über F_{q} irreduziblen Polynome bestimmen.

1.2 Bestimmung der Mächtigkeit der Konjugiertenklassen

Untersuchungen dieser Art gehen bereits auf Dickson [2] zurück. Es ist dabei üblich aus der Mächtigkeit des Zentralisators von A ∈ GL(k, F_{q}) die Mächtigkeit der Konjugiertenklasse zu bestimmen. Bei Kung [7] findet man folgendes Ergebnis: Sei p(x) ∈ F_{q}[x] ein irreduzibles normiertes Polynom vom Grad d, und sei λ ein Zykeltyp von c ∈ IN, so kann die Anzahl der regulären Matrizen, die mit der Matrix D(p, λ) kommutieren, als

b(d, λ): = ∏_{i=1}^{c} ∏_{j=1}^{λ_{i}}(q^{dμ_{i}} − q^{d(μ_{i}−j)})

berechnet werden, wobei

μ_{i}: = ∑_{k=1}^{i} kλ_{k} + ∑_{k=i+1}^{c} iλ_{k}.

Diese Zahl hängt nur von λ und vom Grad d des Polynoms, nicht jedoch von der speziellen Gestalt von p(x) ab. Die Anzahl der mit

diag(D(p_{1}, λ^{(1)}), D(p_{2}, λ^{(2)}), …)

kommutierenden Matrizen ist dann

∏_{i} b(d_{i}, λ^{(i)}).

1.3 Bestimmung des Zykeltyps eines Repräsentanten jeder Konjugiertenklasse

In jeder Konjugiertenklasse gibt es genau eine Matrix, die Blockdiagonalmatrix von Hyperbegleitmatrizen von über F_{q} irreduziblen Polynomen ist. Die Operation von diag(D(p_{1}, λ^{(1)}), D(p_{2}, λ^{(2)}), …) auf F_{q}^{k} entspricht dem direkten Produkt der Operationen der einzelnen Diagonalblöcke auf gewissen Unterräumen von

F_{q}^{k}, d.h. das direkte Produkt ×_{i} ×_{j} ×_{k=1}^{λ_{j}^{(i)}} H(p_{i}^{j}) operiert auf ×_{i} ×_{j} ×_{k=1}^{λ_{j}^{(i)}} F_{q}^{jd_{i}}. Kennt man die Zykelstruktur von H(p_{i}^{j}) auf F_{q}^{jd_{i}}, so kann man mit Hilfe einer bekannten Operation für Zykeltypen den Zykeltyp des direkten Produktes bestimmen. Diese Operation ist die in beiden Komponenten multiplikative und lineare Fortsetzung von

x_{i_{1}}^{j_{1}} × x_{i_{2}}^{j_{2}}: = x_{kgV(i_{1},i_{2})}^{j_{1}j_{2} ggT(i_{1},i_{2})}

auf IQ[x_{1}, x_{2}, …]. Für die Berechnung des Zykeltyps von H(p^{j}) auf F_{q}^{jd} zeigt es sich, daß man den Exponenten, die Periode bzw. die Ordnung von p(x) bestimmen muß. Dieser Exponent ist für Polynome mit p(0) ≠ 0 durch

exp(p): = min {n ∈ IN|p(x) | x^{n} − 1}

definiert. Der Zykeltyp von H(p^{j}) auf F_{q}^{jd}, wobei p(x) ein irreduzibles, normiertes Polynom in F_{q}[x] ist, ist dann gleich

x_{1} ∏_{i=1}^{j} x_{e_{i}}^{(q^{id}−q^{(i−1)d})/e_{i}}

mit e_{i}: = exp(p^{i}) = exp(p)p^{t_{i}}, wobei t_{i} = min {n ∈ IN_{0}|p_{0}^{n} ≥ i} und p_{0} die Charakteristik von F_{q} ist.

Weiters kann man berechen, welche Zahlen als Exponenten von über F_{q} irreduziblen, normierten Polynomen vom Grad d auftreten können, und zu gegebenem Exponenten die Anzahl dieser Polynome bestimmen. Im Fall d = e = 1 gibt es 2 normierte Polynome vom Grad d mit Exponent e, nämlich p(x) = x und p(x) = x − 1. Sonst gilt: Ist e ein Teiler von q^{d} − 1 und e teilt nicht q^{r} − 1 für 1 ≤ r < d, so gibt es φ(e)/d irreduzible, normierte Polynome vom Grad d mit Exponent e in F_{q}[x], wobei φ die Eulersche φ-Funktion ist. Dies zeigt nun, daß man nicht die einzelnen irreduziblen Polynome vom Grad kleiner gleich k bestimmen muß, um den Zyklenzeiger von GL(k, F_{q}) zu bestimmen.

Nun komme ich zum 2. Abschnitt meines Vortrags:

2 Abzählung linearer (n, k)-Codes

Ein linearer (n, k)-Code über dem Körper F_{q} ist ein k-dimensionaler Unterraum des Vektorraums F_{q}^{n}. Wie üblich schreibe ich die Codewörter x ∈ F_{q}^{n} als Zeilenvektoren x = (x_{1}, …, x_{n}). Oft wird ein (n, k)-Code C durch seine Generatormatrix gegeben. Diese ist eine k × n-Matrix Γ, deren Zeilen eine Basis von C bilden, und es gilt dann

C = {x · Γ|x ∈ F_{q}^{k}} .

Zwei lineare (n, k)-Codes C_{1}, C_{2} heißen äquivalent, falls es eine lineare Isometrie (bezüglich der Hamming Distanz) gibt, die C_{1} auf C_{2} abbildet. Dies kann mit Hilfe von Gruppenaktionen wie folgt formuliert werden: Es existiert (ψ, π) ∈ F_{q}^{∗} ≀ S\underline{n} mit (ψ, π)(C_{1}) = C_{2}. In dieser Situation ist es sinnvoll F_{q}^{n} mit der Menge F \underline{n} ; q, der Menge aller Abbildungen von \underline{n}: = \{1, 2, …, n\} nach F_{q}, zu identifizieren. Das Kranzprodukt F_{q}^{∗} ≀ S\underline{n} operiert auf folgende Weise auf F \underline{n} ; q:

F_{q}^{∗} ≀ S\underline{n} × F \underline{n} ; q → F \underline{n} ; q, ((ψ, π), f) ↦ ψ(·)f(π^{−1}·).

Dieser Äquivalenzbegriff von Codes überträgt sich zu einem Äquivalenzbegriff für Generatormatrizen. Dazu seien Generatormatrizen Γ ∈ M_{k,n}(F_{q}) als Funktionen

Γ: \underline{n} → F_{q}^{k} \ \{0\}

aufgefaßt, wobei Γ(i) die i-te Spalte von Γ ist. (Ich untersuche nur Matrizen ohne 0-Spalten.) Obige Gruppenaktion schreibt sich nun zu folgender Gruppenaktion auf der Menge aller k × n-Matrizen (unabhängig von deren Rang) um:

(GL(k, F_{q}) × F_{q}^{∗} ≀ S\underline{n}) × (F_{q}^{k} \ \{0\})\underline{n} → (F_{q}^{k} \ \{0\})\underline{n}
((A, (ψ, π)), Γ) ↦ Aψ(·)Γ(π^{−1}·).

Dem Konzept von Slepian folgend, sei S_{nkq} die Anzahl der Äquivalenzklassen von linearen (n, k)-Codes über F_{q}, die keine 0-Spalten enthalten, das heißt für jedes i ∈ \underline{n} gibt es ein Codewort x, sodaß x_{i} ≠ 0. Die Anzahl der Äquivalenzklassen injektiver Codes sei mit S̄_{nkq} bezeichnet. Ein Code heißt injektiv, falls es für alle i, j ∈ \underline{n} mit i ≠ j und für alle α ∈ F_{q}^{∗} ein Codewort x gibt, sodaß x_{i} ≠ αx_{j}. Weiters sei T_{nkq} die Anzahl der Bahnen von k × n-Matrizen ohne 0-Spalten über F_{q} und T̄_{nkq} die Anzahl der Bahnen von k × n-Matrizen Γ mit der Eigenschaft, daß für alle i, j ∈ \underline{n} mit i ≠ j und für alle α ∈ F_{q}^{∗} der Vektor Γ(i) verschieden ist von αΓ(j). Von den Matrizen, die zur Berechnung von T_{nkq} bzw. T̄_{nkq} herangezogen werden, wird aber nicht verlangt, daß ihr Rang gleich k ist. Es gilt

S_{nkq} = T_{nkq} − T_{n,k−1,q}
S̄_{nkq} = T̄_{nkq} − T̄_{n,k−1,q}

mit den Anfangsbedingungen S_{n1q} = 1 für n ∈ IN, S̄_{11q} = 1 und S̄_{n1q} = 0 für n > 1.

Im Fall q = 2 wird aus dem Kranzprodukt F_{q}^{∗} ≀ S\underline{n} die Gruppe S\underline{n}, es bleibt somit genau eine Gruppe übrig, die auf F_{q}^{k} \{0} operiert und genau eine Gruppe, die auf \underline{n} operiert. Da auf dem Definitionsbereich die symmetrische Gruppe operiert, erhält man durch geeignete Substitution in dem Zyklenzeiger von GL(k, F_{2}) auf F_{2}^{k} \ \{0\} die Anzahl der S\underline{n} × GL(k, F_{2})-Bahnen solcher Funktionen Γ (siehe [1]). Man erhält

∑_{n=0}^{∞} T_{nk2}x^{n} = Z (GL(k, F_{2}), F_{2}^{k} \ {0} |x_{i} = ∑_{j=0}^{∞} x^{ij}) =

= Z (GL(k, F_{2}), F_{2}^{k} \ \{0\} |x_{i} = \frac{1}{1 − x^{i}} )

und

∑_{n=0}^{∞} T̄_{nk2}x^{n} = Z (GL(k, F_{2}), F_{2}^{k} \ {0} |x_{i} = 1 + x^{i}) .

Im Fall q ≠ 2 operiert das Kranzprodukt F_{q}^{∗} ≀ S\underline{n} sowohl von rechts, als auch von links auf der Menge aller Abbildungen (F_{q}^{k} \ \{0\})\underline{n}. Auf Lehmann [8, 9] geht die folgende Bijektion Φ zurück:

Φ: F_{q}^{∗} ≀ S\underline{n}\\(F_{q}^{k} \ \{0\})\underline{n} → S\underline{n}\\ (F_{q}^{∗}\\(F_{q}^{k} \ \{0\}))\underline{n}
Φ(F_{q}^{∗} ≀ S\underline{n}(Γ)) = S\underline{n}(Γ̄),

wobei

Γ̄: \underline{n} → F_{q}^{∗}\\(F_{q}^{k} \ \{0\}), i ↦ F_{q}^{∗}(Γ(i))

und wobei S\underline{n} auf F_{q}^{∗}\\(F_{q}^{k}\\{0\})\underline{n} nach der Definition (π, Γ̄) ↦ Γ̄∘π^{−1} operiert. Diese Bijektion erlaubt das Problem wie folgt umzuformulieren:

(S\underline{n} × GL(k, F_{q})) × (F_{q}^{∗}\\(F_{q}^{k} \ \{0\}))\underline{n} → (F_{q}^{∗}\\(F_{q}^{k} \ \{0\}))\underline{n}
((π, A), Γ̄) ↦ AΓ̄π^{−1},

wobei die Gruppe GL(k, F_{q}) auf F_{q}^{∗}\\(F_{q}^{k} \ {0}) nach folgender Definition operiert:

(A, F_{q}^{∗}(v)) ↦ F_{q}^{∗}(Av).

Die Menge der F_{q}^{∗}-Orbiten F_{q}^{∗}\\(F_{q}^{k}\{0}) ist der (k−1)-dimensionale projektive Raum PG(k − 1, F_{q}) und die Permutationsdarstellung von GL(k, F_{q}) ist die projektive lineare Gruppe PGL(k, F_{q}). Kennt man also den Zyklenzeiger von PGL(k, F_{q}), so kann man wie im Fall q = 2 vorgehen und die Anzahl der Klassen linearer (n, k)-Codes bestimmen. Für die Bestimmung der T_{nkq} bzw. T̄_{nkq} erhält man folgende Formeln:

∑_{n=0}^{∞} T_{nkq}x^{n} = Z (PGL(k, F_{q}), PG(k − 1, F_{q})|x_{i} = ∑_{j=0}^{∞} x^{ij}) =

= Z (PGL(k, F_{q}), PG(k − 1, F_{q})|x_{i} = \frac{1}{1 − x^{i}} ) ,

∑_{n=0}^{∞} T̄_{nkq}x^{n} = Z (PGL(k, F_{q}), PG(k − 1, F_{q})|x_{i} = 1 + x^{i}) .

Zur Berechnung dieses Zyklenzeigers geht man analog wie bei der Berechnung des Zyklenzeigers von GL(k, F_{q}) vor. Nur die Berechnung des Zykeltyps muß abgeändert werden. Man berechnet den sogenannten Subzykeltyp von A ∈ GL(k, F_{q}). Ein Vektor v ∈ F_{q}^{k} \ {0} liegt in einem Subzykel der Länge j, falls j die kleinste natürliche Zahl ist, für die ein α ∈ F_{q}^{∗} existiert, sodaß A^{n}v = αv. Für die Berechnung von Subzykellängen benötigt man den Subexponenten bzw. die integrale Ordnung eines Polynoms p(x) ∈ F_{q}[x] mit p(0) ≠ 0. Dieser ist definiert durch

subexp(p): = min {t ∈ IN|∃α_{0} ∈ F_{q} sodaß p(x) | x^{t} − α_{0}} .

Das Element α_{0} heißt auch integrales Element von p(x) (und ist für Polynome mit p(0) ≠ 0 eindeutig bestimmt). Sei p(x) ein irreduzibles, normiertes Polynom vom Grad d mit Subexponent e und integralem Element α_{0} ∈ F_{q}^{∗}, dann hat die Matrix H(p^{j}) den Subzykeltyp

∏_{i=1}^{j} x_{e_{i},α_{0}^{e_{i}/e}}^{(q^{id}−q^{(i−1)d})/e_{i}},

wobei e_{i} = subexp(p^{i}) = ep^{t_{i}} mit t_{i} = min {n ∈ IN_{0}|p_{0}^{n} ≥ i}. Wie vorne bezeichnet p_{0} die Charakteristik von F_{q}. Die Unbestimmten sind mit 2 Indizes versehen: der erste beinhaltet die Subzykellänge, der zweite ist das zugehörige integrale Element. Überdies ist der Exponent von x_{i,α} stets durch q −1 teilbar.

In einem zweiten Schritt muß man eine Verallgemeinerung des direkten Produktes von Zyklenzeigern zu einem direkten Produkt von Subzyklenzeigern angeben. Dies erfolgt durch

x_{i_{1},β^{r_{1}}}^{j_{1}} ⊗ x_{i_{2},β^{r_{2}}}^{j_{2}}: = x_{i_{1},β^{r_{1}}}^{j_{1}}x_{i_{2},β^{r_{2}}}^{j_{2}}x_{i_{3},β^{r_{3}}}^{j_{3}}.

Dabei ist F_{q}^{∗} = ⟨β⟩ und

i_{3} = kgV(i_{1}, i_{2})\frac{q − 1}{ggT (q − 1, kgV(i_{1}, i_{2})r_{1}/i_{1} − kgV(i_{1}, i_{2})r_{2}/i_{2})}

r_{3} ≡ \frac{r_{1}i_{3}}{i_{1}} ≡ \frac{r_{2}i_{3}}{i_{2}} mod q − 1

und

j_{3} = \frac{i_{1}j_{1}i_{2}j_{2}}{i_{3}} .

Setzt man ⊗ linear und multiplikativ in beiden Komponenten fort, so berechnet man den Subzykeltyp von diag(A_{1}, A_{2}) als ⊗-Verknüpfung der Subzykeltypen von A_{1} und A_{2}. Auf diese Weise bestimmt man den Subzyklenzeiger von GL(k, F_{q}) auf F_{q}^{k} \ {0} als Summe der Subzykeltypen aller Elemente von GL(k, F_{q}) geteilt durch die Gruppenordnung. Streicht man dann die Indizes α in x_{i,α} und teilt man die Exponenten von x_{i} durch q − 1 (d.h. man faßt jeweils q − 1 Vektoren {v, βv, …, β^{q−2}v} = ⟨β⟩(v) = F_{q}^{∗}(v) zu einem Element von PG(k − 1, F_{q}) zusammen), so erhält man den Zyklenzeiger von PGL(k, F_{q}). Zur Bestimmung der Subexponenten und integralen Elemente von über F_{q} irreduziblen, normierten Polynomen sei noch folgendes erwähnt: Sei e > 1 ein Teiler von q^{d} − 1 und e teile nicht q^{r} − 1 für 1 ≤ r < d. Sei weiters h: = ggT(q − 1, e), dann gilt: Für jedes α ∈ F_{q}^{∗} mit multiplikativer Ordnung h gibt es genau

\frac{φ(e)}{dφ(h)}

verschiedene irreduzible, normierte Polynome p(x) ∈ F_{q}[x] vom Grad d mit Exponent e und Subexponent e/h und integralem Element α.

Damit ist es möglich wie vorne beschrieben den Zyklenzeiger von PGL(k, F_{q}) zu bestimmen und somit auch die Anzahl der Klassen linearer (n, k)-Codes über beliebigen endlichen Körpern F_{q} zu ermitteln. Die hier vorgeführten Verfahren wurden bereits in SYMMETRICA (einem Computer Algebra System zur Darstellungstheorie und Kombinatorik der symmetrischen Gruppen und anderer Gruppen) programmiert und zur Abzählung linearer Codes verwendet. Als kleine Illustration der Leistungsfähigkeit der in [4] vorgestellten Algorithmen seien die Zahlen der Isometrie Klassen linearer (n, k)-Codes über F_{q} für q = 3 und 4 angegeben.

Eine genauere Darstellung der hier vorgetragenen Themen sind in [3] und [5] geplant.

References

[1] N.G. De Bruijn. Pólya’s Theory of Counting. In E.F. Beckenbach, Editor, Applied Combinatorial Mathematics, Kapitel 5, Seiten 144 – 184. Wiley, New York, 1964.

[2] L.E. Dickson. Linear Groups. Dover Publications, Inc., New York, 1958.

[3] H. Fripertinger. Cycle indices of linear, affine and projective groups. Nicht veröffentlicht.

[4] H. Fripertinger. Enumeration of isometry classes of linear (n, k)-codes over GF (q) in SYMMETRICA. Bayreuther Mathematische Schriften, 49:215 – 223, 1995. ISSN 0172-1062.

[5] H. Fripertinger und A. Kerber. Isometry classes of indecomposable codes. G.Cohen,M.Giusti,T.Mora (eds.),Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS 948, 1995, pp.194-202.

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

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

[8] H. Lehmann. Das Abzähltheorem der Exponentialgruppe in gewichteter Form. Mitteilungen aus dem Mathem. Seminar Giessen, 112:19 – 33, 1974.

[9] H. Lehmann. Ein vereinheitlichender Ansatz für die REDFIELD – PÓLYA – de BRUIJNSCHE Abzähltheorie. Dissertation, Universität Giessen, 1976.

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

Table 1: Number of isometry classes of linear (n, k)-codes over F_{3}, where columns of zeros are not allowed.

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 4 & 3 & 1 & 0 & 0 & 0 \\ 5 & 1 & 5 & 8 & 4 & 1 & 0 & 0 \\ 6 & 1 & 8 & 19 & 15 & 5 & 1 & 0 \\ 7 & 1 & 10 & 39 & 50 & 24 & 6 & 1 \\ 8 & 1 & 14 & 78 & 168 & 118 & 37 & 7 \\ 9 & 1 & 17 & 151 & 538 & 628 & 255 & 53 \\ 10 & 1 & 22 & 280 & 1789 & 3759 & 2266 & 518 \\ 11 & 1 & 26 & 506 & 5981 & 26131 & 28101 & 7967 \\ 12 & 1 & 33 & 904 & 20502 & 208045 & 500237 & 230165 \\ 13 & 1 & 38 & 1571 & 70440 & 1.788149 & 11.165000 & 11.457192 \\ 14 & 1 & 46 & 2687 & 241252 & 15.675051 & 269.959051 & 734.810177 \\ 15 & 1 & 53 & 4520 & 812381 & 135.088306 & 6509.617382 & 50106.349550 \\ 16 & 1 & 63 & 7474 & 2.674456 & 1123.937633 & 151407.115499 & 3.365565.864529 \\ 17 & 1 & 71 & 12156 & 8.562016 & 8961.374245 & 3.358439.044687 & 216.942933.517425 \\ 18 & 1 & 83 & 19491 & 26.612531 & 68333.073432 & 70.853158.173793 & 13315.081085.011815 \\ 19 & 1 & 93 & 30763 & 80.233923 & 498519.876882 & 1422.491253.596747 & 777125.587904.335661 \end{matrix}

10 H. Fripertinger

Table 2: Number of isometry classes of injective linear (n, k)-codes over F_{3}, where columns of zeros are not allowed.

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 4 & 0 & 1 & 2 & 1 & 0 & 0 & 0 \\ 5 & 0 & 0 & 3 & 3 & 1 & 0 & 0 \\ 6 & 0 & 0 & 4 & 8 & 4 & 1 & 0 \\ 7 & 0 & 0 & 4 & 19 & 15 & 5 & 1 \\ 8 & 0 & 0 & 3 & 44 & 61 & 26 & 6 \\ 9 & 0 & 0 & 3 & 91 & 277 & 162 & 40 \\ 10 & 0 & 0 & 2 & 199 & 1439 & 1381 & 375 \\ 11 & 0 & 0 & 1 & 401 & 8858 & 17200 & 5923 \\ 12 & 0 & 0 & 1 & 806 & 62311 & 311580 & 182059 \\ 13 & 0 & 0 & 1 & 1504 & 459828 & 6.876068 & 9.427034 \\ 14 & 0 & 0 & 0 & 2659 & 3.346151 & 159.373844 & 608.045192 \\ 15 & 0 & 0 & 0 & 4304 & 23.246482 & 3609.085016 & 40932.394177 \\ 16 & 0 & 0 & 0 & 6472 & 152.150717 & 77820.525594 & 2.689924.561256 \\ 17 & 0 & 0 & 0 & 8846 & 934.417218 & 1.585853.806095 & 168.808656.255926 \\ 18 & 0 & 0 & 0 & 11127 & 5384.092498 & 30.517085.050170 & 10054.654260.189282 \\ 19 & 0 & 0 & 0 & 12723 & 29148.064514 & 555.334469.037874 & 568100.206087.336919 \end{matrix}

Table 3: Number of isometry classes of linear (n, k)-codes over F_{4}, where columns of zeros are not allowed.

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 4 & 3 & 1 & 0 & 0 & 0 \\ 5 & 1 & 6 & 9 & 4 & 1 & 0 & 0 \\ 6 & 1 & 9 & 24 & 17 & 5 & 1 & 0 \\ 7 & 1 & 12 & 55 & 70 & 28 & 6 & 1 \\ 8 & 1 & 17 & 131 & 323 & 189 & 44 & 7 \\ 9 & 1 & 22 & 318 & 1784 & 1976 & 490 & 65 \\ 10 & 1 & 30 & 772 & 12094 & 36477 & 13752 & 1240 \\ 11 & 1 & 37 & 1881 & 89437 & 923978 & 948361 & 102417 \\ 12 & 1 & 48 & 4568 & 668922 & 25.124571 & 91.149571 & 25.983495 \\ 13 & 1 & 59 & 10857 & 4.843901 & 665.246650 & 9163.203790 & 9229.228790 \\ 14 & 1 & 74 & 25276 & 33.456545 & 16677.221922 & 887802.519854 & 3.433862.618525 \\ 15 & 1 & 90 & 57340 & 219.445013 & 393513.820272 & 81.226850.913333 & 1235.275542.789440 \\ 16 & 1 & 110 & 126546 & 1367.508687 & 8.746404.847560 & 6995.509895.858546 & 420983.966000.848855 \\ 17 & 1 & 131 & 271821 & 8112.982336 & 183.604673.384799 & 568026.309364.649897 & 135.464277.950330.542478 \\ 18 & 1 & 158 & 568714 & 45940.917668 & 3651.189061.424972 & 43.605786.853186.808968 & 41211.648695.055403.242662 \\ 19 & 1 & 186 & 1.159878 & 248958.221585 & 68984.762728.576459 & 3173.908501.513177.711047 & 11.882925.353489.748367.899821 \end{matrix}

Table 4: Number of isometry classes of injective linear (n, k)-codes over F_{4}, where columns of zeros are not allowed.

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 4 & 0 & 1 & 2 & 1 & 0 & 0 & 0 \\ 5 & 0 & 1 & 4 & 3 & 1 & 0 & 0 \\ 6 & 0 & 0 & 8 & 10 & 4 & 1 & 0 \\ 7 & 0 & 0 & 10 & 35 & 19 & 5 & 1 \\ 8 & 0 & 0 & 13 & 136 & 122 & 33 & 6 \\ 9 & 0 & 0 & 17 & 657 & 1320 & 376 & 52 \\ 10 & 0 & 0 & 19 & 3849 & 25619 & 11632 & 1057 \\ 11 & 0 & 0 & 19 & 23456 & 645751 & 845949 & 95960 \\ 12 & 0 & 0 & 17 & 138200 & 16.822798 & 81.806606 & 25.058580 \\ 13 & 0 & 0 & 13 & 761039 & 418.686704 & 8140.667601 & 8935.079862 \\ 14 & 0 & 0 & 10 & 3.880522 & 9757.619492 & 775867.907732 & 3.317031.738218 \\ 15 & 0 & 0 & 8 & 18.294487 & 212356.023661 & 69.608988.504682 & 1188.156545.352085 \\ 16 & 0 & 0 & 5 & 79.884393 & 4.324364.325987 & 5866.545477.361639 & 402824.242293.156876 \\ 17 & 0 & 0 & 3 & 323.922715 & 82.656563.598884 & 465371.337968.846503 & 128.876144.128834.834992 \\ 18 & 0 & 0 & 2 & 1223.091788 & 1487.726907.561588 & 34.847717.443512.158622 & 38965.296608.277082.280167 \\ 19 & 0 & 0 & 1 & 4311.839430 & 25290.829421.058624 & 2470.448907.990450.018140 & 11.161512.263255.300041.612255 \end{matrix}

Adresse: Harald Fripertinger

Institut für Mathematik Karl-Franzens-Universität Graz Heinrichstr. 36/4 A–8010 Graz Austria

e-mail: harald.fripertinger@balu.kfunigraz.ac.at