Project topics and materials
Get Complete Project Material File(s) Now! »
MacWilliams Extension Theorem
Consider the context of classical linear codes with a nite eld alphabet A. A map h : An ! An that acts by permutation of coordinates and by multiplication of coordinates by nonzero scalars in A is called monomial. A monomial map is a linear Hamming isometry of the Hamming space. An essential question is whether all the linear code isometries act as monomial maps. The MacWilliams Extension Theorem describes all the linear isometries of linear codes in An. Theorem 2.1.1 (MacWilliams Extension Theorem, see [48] and [49]). Let C Fnq be an Fq-linear code. Each Fq-linear Hamming isometry f : C ! Fnq extends to a monomial map, i.e., there exist a permutation 2 Sn and scalars c1; : : : ; cn 2 Fq n f0g such that, for all a 2 C, f (a1; : : : ; an) = (c1a (1); : : : ; cna (n)):
The proof of the theorem appeared in the Ph.D. thesis of F. J. MacWilliams. The original proof was later re ned by other researchers in [8] and [58] using di erent approaches. We give a de nition of a monomial map for the contexts of a module al-phabet observed in Section 1.4. Let R be a ring with identity and let A be a nite R-module alphabet. Let AutR(A) denote the group of all R-module automorphisms of A. De nition 2.1.1. A map h : An ! An is called monomial if there exist a permutation 2 Sn and automorphisms g1; : : : ; gn 2 AutR(A) such that, for any a 2 An, h ((a1; : : : ; an)) = g1(a (1)); : : : ; gn(a (n)) :
The given de nition generalizes the de nition of a classical monomial map for linear codes. Indeed, for a nite eld Fq, the group AutFq (Fq) consists of multiplications by nonzero elements of the eld. Remark 2.1.1. Note that the group AutFq (Fq) of module automorphisms of a nite eld and the group Gal(Fq) of automorphisms of a nite eld are di erent. In the rst case we consider the bijections Fq ! Fq that preserve addition and multiplication by scalars and in the second case we consider the bijections that preserve addition and multiplication. It is known that the group Gal(Fq) consists of the Frobenius automorphisms, see [47, p. 113].
The set of monomial maps forms a group, isomorphic to the semi-direct product (AutR(A))n o Sn, which is equal, by de nition, to the wreath product Sn o AutR(A), see [17, Section 2.6]. The de nition of the monomial map for the contexts of group codes and combinatorial codes can be obtained from De nition 2.1.1 by replacing AutR(A) with the corresponding automorphism group: the group Aut(A) of group auto-morphisms of A for group codes, and the group S(A) of permutations of A for combinatorial codes. For the combinatorial codes, a full description of the Hamming isometries of An is given. Theorem 2.1.2 (see [9, 13]). Let A be a nite set alphabet and let n be a positive integer. A map h : An ! An is a Hamming isometry if and only if h is a monomial map. An analogue of this theorem holds for the Hamming isometries of An in all the contexts. We formulate the statement and give the proof for the context of module alphabets. The same statement with a similar proof holds for group codes. Proposition 2.1.1. Let A be a nite R-module alphabet and let n be a positive integer. A map h 2 EndR(An) is a Hamming isometry if and only if h is a monomial map.
Proof. It is easy to see that a monomial map is R-linear and preserves the Hamming distance. Conversely, if h preserves the Hamming distance, then, considering A as a set, from Theorem 2.1.2, the map h acts by permutation of columns 2 Sn and by permutation of coordinates 1; : : : ; n 2 S(A). Since h is R-linear, each map i : A ! A is an R-linear automorphism of A. Hence, i 2 AutR(A). Therefore, h is a monomial map.
Except for the case of classical linear codes, a general analogue of the MacWilliams Extension Theorem does not exist for other contexts. That is, there exists a code and there exists a Hamming isometry of this code that does not extend to a monomial map. The following example of an unextendable code isometry for combinatorial codes can be found in [4].
Example 2.1.1. Let A = f0; 1g. The two codes in A4 C = f(0; 0; 0; 0); (1; 1; 0; 0); (1; 0; 1; 0); (0; 1; 1; 0)g.
Module alphabets over PIDs
A nonzero commutative ring in which a product of every two nonzero elements is nonzero is called an integral domain (or entire ring). A commutative ring R is called a principal ideal ring if every ideal I R is of the form Rx for some x 2 R. Combining these two de nition, a ring R is called a PID (principal integral domain) if it is an integral domain and a principal ideal ring.
Examples of PIDs include elds, the ring of integers Z and the ring of poly-nomials in one variable with coe cients in a eld. The ring of polynomials with integer coe cients or the ring of multi-variable polynomials with coe cients in a eld are not PIDs. Let R be a PID. To prove the extension theorem for R-module alphabets we need the following two lemmas. Lemma 2.5.1. A nite R-module M is cyclic if and only if soc(M) is cyclic. Proof. Since R is PID, if M is cyclic, then soc(M) M is cyclic, so prove the converse. Let M be a nite R-module with a cyclic socle. For a prime p 2 R, let M(p) denote the set of those elements x in M such that there exists a positive integer t with ptx = 0. The R-module M is isomorphic to the sum p M(p) over all primes p 2 R with M(p) 6= 0 (see [43, p. 149]). From [60, p. 175], the socle of a direct sum of L modules equals to the direct sum of socles of summands, soc(M) M soc(M(p)): = p Thus, soc(M) is cyclic if and only if each summand soc(M(p)) is cyclic. For a prime p 2 R, the R-module M(p) is isomorphic to a product of cyclic R-modules R=(pt1 ) R=(ptr ), where t1; : : : ; tr are positive integers, (see [43, R=(p), for i 2 f 1; : : : ; r g . Calculate the socle, p. 149]). Note that soc(R=(pti )) = R=(p); soc(M(p)) = R=(p) | {zr } t that is cyclic if and only if r = 1, i.e., M(p) R=(p ) for some integer t. = Therefore M is cyclic. Lemma 2.5.2. A nite cyclic R-module M is pseudo-injective.
Codes over a module alphabet
Consider the general module alphabet context and recall the notations of Sec-tion 2.3. Before using the properties of MDS codes, one general property of the n-tuple V of the code C is the following. Since the encoding map is injective, ker = Tni=1 ker i = f0g. Hence, n \ Vi = f0g: i=1.
Lemma 4.1.1. Let C be an R-linear (n; k)A MDS code. For each k-element subset I f1; : : : ; ng, the equality of right R-modules hold, M Vi? = Mc: i2I Moreover, jVi?j = jAj, for all i 2 f1; : : : ; ng.
Proof. It is a well-known fact that deleting any n k coordinates of C we get a code of the same cardinality, see for example the proof for classical linear codes, [47, p. 319].
Let I f1; : : : ; ng be a subset with k elements. Let C0 be a code obtained from C by keeping only coordinates from I. Since C is MDS, the map 0 = ( i)i2I , 0 : M ! Ak is an encoding map of C0 and thus i2I Vi = f0g. Calculating the annihilators of both sides, we get i2I Vi? = M. T k c All the modules M, C and C0 are isomorphic to Ak. Thus the dual modules P M and A are isomorphic as right R-modules. Since for all i 2 f1; : : : ; ng, inequalities,cibi (see eq. (2.3)), we have j i j = j im ij j j . Consider the following V ? = im V ?
Therefore there are equalities everywhere in the expression above. We get j V i j = j bj j j and the equality of the statement. ? A = A
Next lemma shows that for an MDS code the condition of pseudo-injectivity of the alphabet in Proposition 2.3.1 can be omitted. Lemma 4.1.2. Let C be an R-linear (n; k)A MDS code and let f : C ! An be an R-linear map. If V = U, then f extends to a monomial map.
Table of contents :
1. Preliminaries
1.1 Rings and modules
1.2 Characters and the Fourier transform
1.3 Hamming space and codes
1.4 Categories of codes
1.5 Additive codes
2. Extension criterion
2.1 MacWilliams Extension Theorem
2.2 Pseudo-injective modules
2.3 Extension criterion
2.4 General extension theorem
2.5 Module alphabets over PIDs
3. Short codes
3.1 Matrix modules
3.2 Codes over a matrix module alphabet
4. MDS codes
4.1 Codes over a module alphabet
4.2 Additive codes
4.2.1 Multi-fold partitions of vector spaces
4.2.2 Additive isometries of classical linear codes
4.2.3 MDS codes of dimension two
4.3 Group codes
5. Symmetrized weight composition and general weights
5.1 Closure of a group
5.2 Extension criterion
5.3 G-pseudo-injective modules
5.4 Posets and Mobius function
5.5 Code construction
5.6 Proof of the main results
5.7 Additive codes
6. G-pseudo-injectivity of vector spaces
6.1 General properties
6.2 Poset of orbit partitions
6.3 Proof of the main result
6.3.1 Spaces of dimension that diers from 3
6.3.2 Three-dimensional spaces
7. Extension properties of other codes
7.1 Stabilizer quantum codes
7.2 Gabidulin codes
8. Isometry groups of combinatorial codes
8.1 Preliminaries
8.2 Main result
8.3 Auxiliary results
8.3.1 Multiplicity function
8.3.2 Extension criterion and stabilizers
8.3.3 Two matrices
8.3.4 Properties of the map W
8.4 Proof of the main result
8.5 Codes with 4 elements
9. Conclusion
9.1 Weight preserving maps of the full space
9.2 MDS combinatorial codes
9.3 Other problems
Appendix
