Double and bordered alpha-circulant self-dual codes over finite commutative chain rings

Double and bordered α-circulant self-dual codes over finite commutative chain rings Michael Kiermaier and Alfred Wassermann ABSTRACT. In this paper we investigate codes over finite commutative rings R, whose generator matrices are built from α-circulant matrices. For a non-trivial ideal I < R we give a method to lift such codes over R/I to codes over R, such that some isomorphic copies are avoided. For the case where Iis the minimal ideal of a finite chain ring we refine this lifting method: We impose the additional restriction that lifting preserves self-duality. It will be shown that this can be achieved by solving a linear system of equations over a finite field. Finally we apply this technique to Z4-linear double nega-circulant and bordered circulant self-dual codes. We determine the best minimum Lee distance of these codes up to length 64. 1. α-circulant matrices In this section, we give some basic facts on α-circulant matrices, compare with [4, chapter 16], where some theory of circulant matrices is given, and with [1, page 84], where α-circulant matrices are called {k}-circulant. DEFINITION 1.1. Let Rbe a commutative ring, ka natural number and α∈R. A (k×k)- matrix Ais called α-circulant, if Ahas the form       a0a1a2. . . ak−2ak−1 αak−1a0a1. . . ak−3ak−2 αak−2αak−1a0. . . ak−4ak−3 . . .. . .. . .. . .. . . αa1αa2αa3. . . αak−1a0       with ai∈Rfor i∈ {0, . . . , k −1}. For α= 1,Ais called circulant, for α=−1,Ais called nega-circulant or skew-circulant, and for α= 0,Ais called semi-circulant. An α-circulant matrix Ais completely determined by its first row v= (a0, a1, . . . , ak−1)∈Rk. We denote Aby circα(v)and say that Ais the α-circulant matrix generated by v. In the following, αusually will be a unit or even α2= 1. We define Tα= circα(0,1,0,...,0), that is Tα=       1 1 ... 1 α       Key words and phrases. linear code over rings, self-dual code, circulant matrix, finite chain ring. 1 Using Tα, there is another characterization of an α-circulant matrix: A matrix A∈Rk×kis α-circulant iff ATα=TαA. This is seen directly by comparing the components of the two matrix products. In the following it will be useful to identify the generating vectors (a0, a1, . . . , ak−1)∈Rn with the polynomials Pk−1 i=0 aixi∈R[x]of degree at most k−1, which again can be seen as a set of representatives of the R-algebra R[x]/(xk−α). Thus, we get an injective mapping circα:R[x]/(xk−α)→Rk×k. Obviously circα(1) = Ik, which denotes the (k×k)-unit matrix, circα(λf) = λcircα(f)and circα(f+g) = circα(f) + circα(g)for all scalars λ∈Rand all fand gin R[x]/(xk−α). Furthermore, it holds circα(ei) = circα(xi) = Ti αfor all i∈ {0, . . . , k −1}and circα(xk) = circα(α) = αIk=Tk α, where eidenotes the ith1unit vector. So we have circα(xixj) = circα(xi) circα(xj)for all {i, j} ⊂ N. By linear extension it follows that circαis a monomorphism of R-algebras. Hence the image of circα, which is the set of the α-circulant (k×k)- matrices over R, forms a commutative subalgebra of the R-algebra Rk×kand it is isomorphic to the R-algebra R[x]/(xk−α). Especially, we get circα(a0, . . . , ak−1) = Pk−1 i=0 aiTi α. 2. Double α-circulant and bordered α-circulant codes DEFINITION 2.1. Let Rbe a commutative ring and α∈R. Let Abe an α-circulant matrix. A code generated by a generator matrix (Ik|A) is called double α-circulant code. A code generated by a generator matrix     Ik β γ · · · γ δ . . . δ A     with {β, γ, δ} ⊂ R}is called bordered α-circulant code. The number of rows of such a generator matrix is denoted by k, and the number of columns is denoted by n= 2k. As usual, two codes C1and C2are called equivalent or isomorphic, if there is a monomial transformation that maps C1to C2. DEFINITION 2.2. Let Rbe a commutative ring and k∈N. The symmetric group over the set {0, . . . , k −1}is denoted by Sk. For a permutation σ∈Skthe permutation matrix S(σ)is defined as Sij =δi,σ(j), where δis the Kronecker delta. An invertible matrix M∈GL(k, R)is called monomial, if M=S(σ)Dfor a permutation σ∈Skand an invertible diagonal matrix D. The decomposition of a monomial matrix into the permutational and the diagonal matrix part is unique. Let M=M(k, R, α)be the set of all pairs (N, M)of monomial (k×k)-matrices Mand Nover R, such that for each α-circulant matrix A∈Rk×k, the matrix N−1AM is again α-circulant. An element (N, M)of Mcan be interpreted as a mapping Rk×k→Rk×k,A7→ N−1AM. The composition of mappings implies a group structure on M, and Moperates on the set of all α-circulant matrices. Now let (N, M)∈M. The codes generated by (I|A)and by (I|N−1AM)are equivalent, since N−1(I|A)N0 0M= (I|N−1AM) 1Throughout this article, counting starts at 0. Accordingly, N={0,1,2, . . .} 2 and the matrix N0 0Mis monomial. Thus, Malso operates on the set of all double αcirculant generator matrices. In general M-equivalence is weaker than the code equivalence: For example the vectors v= (1111101011011010) ∈Z16 2and w= (1110010011100000) ∈Z16 2generate two equivalent binary double circulant self-dual [32,16]-codes. But since the number of zeros in vand wis different, the two circulant matrices generated by vand wcannot be in the same M-orbit. 3. Monomial transformations of α-circulant matrices Let Rbe a commutative ring, k∈Nand α∈Ra unit. In this section we give some elements (N, M)of the group M=M(R, k, α)defined in the last section. In part they can be deduced from [4, chapter 16, §6, problem 7]. Quite obvious elements of Mare (Ik, Tα),(Tα, Ik),(Ik, D)and (D, Ik), where Ddenotes an invertible scalar matrix. For certain αfurther elements of Mare given by the following lemma, which is checked by a calculation: LEMMA 3.1. Let α∈Rwith α2= 1 and s∈ {0, . . . , k −1}with gcd(s, k) = 1. Let σ= (i7→ si mod k)∈Sk. We define Das the diagonal matrix which has α(s+1)i+bsi/kcas i-th diagonal entry, and we define the monomial matrix M=S(σ)D. Then (M, M)∈M More specifically: Let f∈R[x]/(xk−α). It holds: M−1circα(f)M= circα(f((αx)s)) Finally, there is an invertible transformation A7→ M−1AM that converts an α-circulant matrix into a β-circulant matrix for certain pairs (α, β): LEMMA 3.2. Let Rbe a commutative ring, α∈Ra unit and {i, j} ⊂ N. Let Abe an αi-circulant (k×k)-matrix over Rand Mthe diagonal matrix with the diagonal vector (1, αj, α2j, . . . , α(k−1)j). Then M−1AM is an αi−kj-circulant matrix. For α2= 1 the matrix Mis orthogonal. 4. The lift of an α-circulant matrix If we want to construct all equivalence classes of double α-circulant codes over a commutative ring R, it is enough to consider orbit representatives of the group action of Mon the set of all double α-circulant generator matrices, or equivalently, on the set of all α-circulant matrices. Furthermore, we can benefit from non-trivial ideals of R: Let Ibe an ideal of Rwith {0} 6= I6=R, and¯ : R→R/I the canonical projection of Ronto R/I. We set M=M(k, R, α)and ¯ M={(¯ N, ¯ M):(N, M)∈M}. It holds ¯ M⊆M(k, R/I, ¯α). Let e:R/I →Rbe a mapping that maps each element r+Iof R/I to a representative element r∈R. DEFINITION 4.1. Let A= circ¯α(v)be an ¯α-circulant matrix with generating vector v∈R/I. An α-circulant matrix Bover Ris called lift of A, if ¯ B=A. In this case we also say that the code generated by (Ik|B)is a lift of the code generated by (Ik|A). The lifts of Aare exactly the matrices of the form circα(e(v))+circα(w)with w∈Ik.2The vector wis called lift vector. 2To avoid confusion, we point out that Ikdenotes the k-fold Cartesian product I×. . . ×Ihere. 3 To find all double α-circulant codes over R, we can run over all lifts of all double ¯α-circulant codes over R/I. The crucial point now is that for finding at least one representative all equivalence classes of double α-circulant codes over R, it is enough to run over the lifts of a set of representatives of the group action of ¯ Mon the set of all ¯α-circulant codes over R/I: LEMMA 4.1. Let Aand Bbe two ¯α-circulant matrices over R/I which are in the same ¯ Morbit. Then for each lift of Athere is a lift of Bwhich is in the same M-orbit. PROOF. Because Aand Bare in the same ¯ M-orbit, there is a pair of monomial matrices (N, M)∈Msuch that ¯ N−1A¯ M=B. Let a∈(R/I)kbe the generating vector of Aand b∈(R/I)kthe generating vector of B. Since circα(e(a)) = Aand circα(e(b)) = Bit holds N−1circα(e(a))M= circα(e(b)) + K, where K∈Ik×k.circα(e(b)) is of course α-circulant, and N−1circα(e(a))Mis α-circulant because of (N, M)∈M. Thus, also Kis α-circulant and therefore there is a z∈Ikwith circα(z) = K. Now, let w∈Ikbe some lift vector. N−1circα(w)M∈Ik×kis α-circulant and generated by a lift vector w0∈Ik. Then N−1(circα(e(a)) + circα(w))M= circα(e(b)) + circα(z+w0), and z+w0∈Ik. Therefore, the lift of Aby the lift vector wand the lift of Bby the lift vector z+w0are in the same M-orbit.  It is not hard to adapt this approach to bordered α-circulant codes. One difference is an additional restriction on the appearing monomial matrices: Its diagonal part must be a scalar matrix. The reason for this is that otherwise the monomial transformations would destroy the border vectors (γ . . . γ)and (δ . . . δ)t. Circulant matrices are often used to construct self-dual codes. Thus we are interested in a fast way to generate the lifts that lead to self-dual codes. The next section gives such an algorithm for the case that Ris a finite chain ring and Iis its minimal ideal. 5. Self-dual double α-circulant codes over finite commutative chain rings We want to investigate self-dual double α-circulant codes. Here we need α2= 1. This is seen by denoting the rows of a generator matrix Gof such a code by w0. . . wk−1, and by comparing the scalar products hw0, w1iand hw1, w2i, which must be both zero. Furthermore, given α2= 1, we see that hw0, wii=hwj, wi+ji, where i+jare taken modulo k. Thus G generates a self-dual code if hw0, w0i= 1 and for all j∈ {1,...,bk/2c} the scalar products hw0, wjiare equal to 0. DEFINITION 5.1. A ring Ris called chain ring, if its left ideals are linearily ordered by inclusion. For the theory of finite chain rings and linear codes over finite chain rings see [2]. In this section Rwill be a finite commutative chain ring, which is not a finite field, and αan element of Rwith α2= 1. There is a ring element θ∈Rwhich generates the maximal ideal Rθ of R. The number qis defined by R/Rθ ∼ =Fq, and mis defined by |R|=qm. Because Ris not a field, we have m≥2. The minimal ideal of Ris Rθm−1.Mis defined as in section 2, with with the difference that all monomial matrices Mshould be orthogonal, that is MMt=Ik. Thus each M-image of a generator matrix of a self-dual code again generates a self-dual code. Now let I=Rθm−1be the minimal ideal of R. As in section 4 let e:R/I →Rbe a mapping that assignes each element of R/I to a representative in R, now with the additional condition e(¯α) = α. 4 We mention that if (Ik|B)generates a double α-circulant self-dual code over R, then (Ik|¯ B) generates a double ¯α-circulant self-dual code over R/I. So Bis among the lifts of all ¯αcirculant matrices Aover R/I such that (Ik|A)generates a self-dual double ¯α-circulant code. Let A= circ¯α(a)be an ¯α-circulant matrix over R/I such that (Ik|A)generates a self-dual code. So AAt=−Ik, and therefore c0:= 1 + k−1 X i=0 e(ai)2∈Iand cj:= j−1 X i=0 αe(ai)e(ak−j+i) + k−1 X i=j e(ai)e(ai−j)∈Ifor all j∈ {1,...,bk/2c} We want to find all lifts B= circα(e(a)) + circα(w)of Awith w∈Iksuch that BBt=−Ik. As we have seen, this is equivalent to 0 = 1 + k−1 X i=0 (e(ai) + wi)2and 0 = j−1 X i=0 (e(ai) + wi)(αe(ak−j+i) + wk−j+i) + k−1 X i=j (e(ai) + wi)(e(ai−j) + wi−j) where the second equation holds for all j∈ {1,...,bk/2c}. Using I·I= 0, we get 0 = c0+ 2 k−1 X i=0 e(ai)wiand 0 = cj+ j−1 X i=0 (e(ai)wk−j+i+αe(ak−j+i)wi) + k−1 X i=j (e(ai)wi−j+e(ai−j)wi) This is a R-linear system of equations for the components wi∈Iof the lift vector. Using the fact that the R-modules R/(Rθ)and Iare isomorphic, and R/(Rθ)∼ =Fq, this can be reformulated as a linear system of equations over the finite field Fq, which can be solved efficiently. Since R/I is again a commutative chain ring, the lifting step can be applied repeatedly. Thus, starting with the codes over Fq, the codes over Rcan be constructed by m−1nested lifting steps. Again, this method can be adapted to bordered α-circulant matrices over commutative finite chain rings. 6. Application: Self-dual codes over Z4 For a fixed length nwe want to find the highest minimum Lee distance dLee of double negacirculant and bordered circulant self-dual codes over Z4. In [5] codes of the bordered circulant type of length up to 32 were investigated. First we notice that the length nmust be a multiple of 8: Let Cbe a bordered circulant or a double nega-circulant code of length nand ca codeword of C. We have 0 = hc, ci= Pn−1 i=0 c2 i∈Z4. The last expression equals the number of units in cmodulo 4, so the number of units of each codeword is a multiple of 4. It follows that the image ¯ Cof Cover Z2is a doubly-even self-dual code of length n, which can only exist for lengths ndivisible by 8. Furthermore, it holds dLee(C)≤2dHam(¯ C)(1) 5 As a result, we only need to consider the lifts of codes ¯ Cwhich have a sufficiently high minimum Hamming distance. We explain the algorithm for the case of the nega-circulant codes: In a first step, for a given length nwe generate all doubly-even double circulant self-dual codes over Z2. This is done by enumerating Lyndon words of length nwhich serve as generating vectors for the circulant matrix. Next, we filter out all duplicates with respect to the group action of M, where Mis the group generated by the elements given in section 3 which consist of pairs of orthogonal monomial matrices. A variable dwill keep the best minimum Lee distance we already found. We initialize dwith 0. Now we loop over all binary codes CZ2in our list, from the higher to the lower minimum Hamming distance of CZ2: If 2dHam(CZ2)≤dwe are finished because of (1). Otherwise, as explained in section 5, we solve a system of linear equations over Z2and get all self-dual lifts of CZ2. For these lifts we compute the minimum Lee distance and update daccordingly. Most of the computation time is spent on the computation of the minimum Lee distances. Thus it was a crucial point to write a specialized algorithm for this purpose. It is described in [3]. The results of our search are displayed in the following table. For given length n, it lists the highest minimum Lee distance of a self-dual code of the respective type: n8 16 24 32 40 48 56 64 double nega-circulant 6 8 12 14 14 18 16 20 bordered circulant 6 8 12 14 14 18 18 20 We see that the results are identical for the two classes of codes, except for length 56. Using (1) there is a simple reason that for this length no double circulant self-dual code over Z4with minimum Lee distance greater than 16 exists: The best doubly-even double circulant self-dual binary code has only minimum Hamming distance 8. Acknowledgment This research was supported in part by Deutsche Forschungsgemeinschaft WA 1666/4-1. References [1] Philip J. Davis. Circulant Matrices. Chelesa publishing, New York, second edition, 1994. [2] Thomas Honold and Ivan Landjev. Linear codes over finite chain rings. Electr. J. Comb., 7, 2000. [3] Michael Kiermaier and Alfred Wassermann. On the Minimum Lee Distance of Quadratic Residue Codes over Z4. In Proceedings of the International Symposium on Information Theory (ISIT), 2008. to appear. [4] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977. [5] Masaaki Harada T. Aaron Gulliver. Extremal double circulant Type II codes over Z4and construction of 5-(24, 10, 36) designs. Discrete Mathematics, 194:129–137, 1999. MICHAEL KIERMAIER, MATHEMATICAL DEPARTMENT, UNIVERSITY OF BAYREUTH, D-95440 BAYREUTH, GERMANY E-mail address:[email protected] URL:http://www.mathe2.uni-bayreuth.de/michaelk/ ALFRED WASSERMANN, MATHEMATICAL DEPARTMENT, UNIVERSITY OF BAYREUTH, D-95440 BAYREUTH, GERMANY E-mail address:[email protected] URL:http://did.mat.uni-bayreuth.de/~alfred/home/index.html 6