Combinatorial constructions -- Matroids and linear codes

Matroids and linear codes

Matroids and linear codes

In general a matroid is a set X together with a closure operator on its power set bar ():2^X -> 2^X such that the following two axioms are fulfilled:

x not Îbar (A) and xÎbar (AÈ{y} ) then yÎbar (AÈ{x} ) " x,yÎX, AÍX A1)

" AÍX$BÍX such that |B|<¥ and bar (B)=bar (A) A2)

Two matroids X and Y are called isomorphic if and only if there is a bijection f:X -> Y such that all xÎX and all AÌX fulfill

xÎbar (A)Ûf(x)Îbar (f(A)).

Matroids which are representable over a field F are called F-linear. We are especially interested in binary matroids (these are GF(2)-linear matroids) and in regular matroids, which are representable over any field F. For GF(2)- and GF(3)-linear matroids the so called Brylawski-Lucas-Theorem [7] holds. It describes the isomorphism classes of n´k matrix matroids of rank k over GF(2) or GF(3) as orbits of these matrices under group actions of direct products of linear groups and symmetric or full monomial groups of the form GL₂(k)´S_n or GL₃(k)´GF(3)^* wr S_n. The isometry classes of linear (n,k)-codes over GF(q) were already described by the same group action [43][29][23][18][21]. To be more precise the isometry classes of linear (n,k)-codes over GF(q) correspond to the orbits of n´k generator matrices of rank k under the following action:

(GL_k(q)´GF(q)^* wr S_n)´(GF(q)^k)ⁿ -> (GF(q)^k)ⁿ

((A,M),G) -> A·G·M,

where the monomial matrix M represents the elements of GF(q)^* wr S_n, and the generator matrices G are written as n-tuples of elements in GF(q)^k. We realized that when using Lehmann's Lemma [35][36] (which describes how this action of the wreath product can be replaced by two group actions which can be handled more easily) it is possible to generalize Slepian's approach [43] for binary codes to arbitrary q. In the general case we have to compute cycle indices of projective linear groups acting on projective spaces [12] from which it is possible to compute the numbers of isometry classes of linear codes [18]. Furthermore we have to mention that we proved a formula for computing the numbers of classes of indecomposable (or connected) linear codes, which generalizes and corrects [23] a formula by Slepian [43]. The main results on enumeration of isometry classes of linear codes were presented at the AAECC-11 in Paris in July 1995.

For many parameter values n, k and q the numbers of isometry classes of linear codes (with additional properties as "no repeated columns", "no zero-columns" or "indecomposability") have been computed [2][34] and in many cases there are complete lists of representatives of these isometry classes available [5]. See for instance

/home/home_codes.html.

All these new results will be published in a forthcoming book [6] together with A. Kerber and other co-authors of Bayreuth and of Hamburg-Harburg. This book will be published by Springer (most of the details are already settled) and it will probably be the first text-book on coding theory describing how to get a complete overview over the isometry classes of linear codes. In other words in one part of this book we will describe all the details needed for enumerating these classes (combinatorics under finite group actions, Pólya theory, cycle index methods, especially the cycle indices of projective groups, ...) and for constructing complete lists of these codes (Sims chains, orderly generation combined with learning techniques, canonical forms, ...). Other parts of the book will give an introduction to error correcting codes and describe interesting connections between representation theory of groups and coding theory. In addition to this our software developed for the classification of linear codes will be made available by ftp.

There are many interesting characterizations of regular matroids [1] and together with M. Wild [45][46] we designed and implemented a regularity test for binary matrix matroids in the computer algebra system SYMMETRICA [44]. This test takes as an input a binary matrix matroid and decides whether this matroid is regular or not. Since we have complete lists of the isomorphism classes of binary matrices we can produce complete lists of regular matrix matroids. This test seems to be the first regularity test for matroids which is completely implemented in a computer algebra system. When applying this regularity test on a matrix matroid we get some further information about it. For instance the sets of all hyperplanes co-lines and co-planes are computed or we can get an overview over all flats (closed sets) of a matroid.

Now it would be interesting to investigate the properties of these regular matroids. Determine whether there are connections between coding theoretic properties and matroidal properties. For instance indecomposable codes correspond to connected matroids, codes without repeated columns correspond to simple matroids, codes with no zero-columns correspond to loopless matroids. Since we have representatives of the isomorphism classes of regular matroids we really can put our hands on each of these objects and test them for certain prescribed properties.

For larger values of n and k we will use probabilistic methods like the Dixon-Wilf-Algorithm [11] in order to construct binary or regular matrix matroids distributed over all isomorphism classes uniformly at random, which allows to produce huge sets of representatives and to check hypotheses on them and afterwards try to prove the valid ones.

harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001

Matroids and linear codes