Calculating cocyclic hadamard matrices in Mathematica: exhaustive and heuristic searches

Calculating Cocyclic Hadamard Matrices in Mathematica: Exhaustive and Heuristic Searches V. ´ Alvarez, J.A. Armario, M.D. Frau, and P. Real Dpto. Matem´atica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n 41012 Sevilla, Spain {valvarez, armario, mdfrau, real}@us.es Abstract. We describe a notebook in Mathematica which, taking as input data a homological model for a finite group Gof order |G|=4t, performs an exhaustive search for constructing the whole set of cocyclic Hadamard matrices over G. Since such an exhaustive search is not practical for orders 4t≥28, the program also provides an alternate method, in whichanheuristicsearch(intermsofa genetic algorithm) is performed. We include some executions and examples. Nowadays, most of Computer Algebra Systems (CAS) begin to be concerned with the computation of homological information. This is the case of Gap [13], MAGMA [17]. In a parallel way, some specific softwares for achieving calculations in homological algebra are being developed, as it is the case of Kenzo [7] and Hap [15]. However none of them are concerned with the explicit calculation of Hadamard cocyclic matrices. In spite of that, some researchers have developed their own computations, working on different systems [6,11,12,14,2]. Inthispaperwepresentanotebook[1]inMathematica 4.0, which implements the homological reduction method described in [4]. When exhaustive search is not feasible, the notebook provides a second routine for performing an heuristic search, which corresponds to the implementation of the genetic algorithm in [3]. The interested reader is referred to these papers for the theoretical background. Another non exhaustive method for finding out Hadamard cocyclic matrices is described in [5], in terms of image restorations. The notebook takes as input data a homological model φ:¯ B(ZZ[G]) f   g(hG, d) for a finite group Gof order |G|=4t.Thetermhomological model refers to a contraction φ:¯ B(ZZ[G]) f   ghG from the reduced bar construction of the group G (i.e. the reduced complex associated to the standard bar resolution [18]) to a differential graded module of finite type hG,sothatH∗(G)=H∗(hG)andthe homology of hG may be effectively computed by means of Veblen’s algorithm [19] (involving the Smith’s normal forms of the matrices representing the differential operator). All authors are partially supported by the PAICYT research project FQM–296 from Junta de Andaluc´ıa (Spain). A. Iglesias and N. Takayama (Eds.): ICMS 2006, LNCS 4151, pp. 419–422, 2006. c Springer-Verlag Berlin Heidelberg 2006 420 V. ´ Alvarez et al. In order to construct a basis for 2-coboundaries, the program needs to know the group law on G. To this end, the user must fix an ordering on the elements of G,sayG={g1=1,...,g 4t}.Now,amatrixPrepresenting the group law in Gmay be constructed at once, so that P(i, j)=kif and only if gigj=gk. The only additional information which is needed is that of the diagrams ¯ B1(ZZ[G]) f −→ B1 ↓Q ¯ B1 ¯ B2(ZZ[G]) f −→ B2 ↓Q ¯ B2 That is, the matrices M2and M3representing the differentials operators d2 and d3of hG, as well as the matrices F1and F2representing the maps f1: ¯ B1(ZZ[G]) →B 1and f2:¯ B2(ZZ[G]) →B 2. In these circumstances, we may now determine exactly what the input and output data are. Input data –The matrices P,Mi+1,Firepresenting the group law, di+1 and fi,1≤i≤2. –The searching method to use: introduce 1 for an exhaustive search, anything else for a heuristic search. Output data –A full basis for normalized 2-cocycles over G. –In case that an exhaustive search was chosen, the whole set of Hadamard cocyclic matrices over G. Otherwise, a few Hadamard cocyclic matrices, obtained from the heuristic search. All the executions and examples included below have been worked out with aid of the Mathematica 4.0 notebook which we have described here, running on a Pentium IV 2.400 Mhz DIMM DDR266 512 MB. Since some calculations obtained from the heuristic search are provided in [3], we focus on calculations obtained from an exhaustive search. In the sequel, the elements of a product A×Bare ordered as the rows of a matrix indexed in |A|×|B|. For instance, if |A|=rand |B|=c, the ordering is <a 1b1,a 1b2,...,a 1,b c,a 2b1,a 2b2,...,a 2bc,...,a rb1,...,a rbc> We assume ZZk={0,1,...,k −1}with additive law. Next we include a table with the number of cocyclic Hadamard matrices that we have found in each case. tZZ4tZZ2×ZZ2tZZ4×ZZtZZ2 2×ZZtD4tZZ2t×fZZ2(ZZt×fZZ2)×χZZ2 1 2 6 2 6 6 6 6 2 0 16 16 168 32 16 168 3 0 24 024 72 072 4 0 96 192 1984 768 0272 5 0 120 0120 2200 120 2200 Calculating Cocyclic Hadamard Matrices in Mathematica 421 Here fdenotes the 2-cocycle f(gi,g j)=t 2+1ifgi=gj=1 0otherwise and χdenotes the dihedral action χ(a, b)=−bif a=1 bif a=0 The computing time required in all cases was practically of the same order: less than 3 seconds for 1 ≤t≤3, a couple of minutes for t= 4 and about 30 minutes for t= 5. The black entries correspond to new results, as far as we know (the case of G5 5=D4·5is included, since the computation of Flannery in [16], 2380, differs from ours, 2200). References 1. V. ´ Alvarez. http://mathworld.wolfram.com/HadamardSearch.html (2006). To appear. 2. V. ´ Alvarez, J.A. Armario, M.D. Frau and P. Real. An algorithm for computing cocyclic matrices developed over some semidirect products. AAECC-14 Proceedings, LNCS 2227, 287–296 (2001). 3. V. ´ Alvarez, J.A. Armario, M.D. Frau and P. Real. A genetic algorithm for cocyclic Hadamard matrices. AAECC-16 Proceedings,LNCS3857, 144–153, (2006). 4. V. ´ Alvarez, J.A. Armario, M.D. Frau and P. Real. Homological reduction method for constructing Hadamard cocyclic matrices. Communication submitted to the EACA-06 conference, Sevilla (2006). 5. A. Baliga and J. Chua. Self-dual codes using image resoration techniques. Proceedings AAECC’14. Eds. S. Boztas, I.E. Shparlinski. Springer Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, (2001). 6. A. Baliga and K.J. Horadam. Cocyclic Hadamard matrices over ZZt×ZZ2 2.Australas. J. Combin.,11, 123–134, (1995). 7. X. Dousson, J. Rubio, F. Sergeraert and Y. Siret. The Kenzo program. Institute Fourier, Grenoble (19998). http://www-fourier.ujf-grenoble.fr/˜sergeraert/Kenzo/ 8. W. de Launey and K.J. Horadam. Cocyclic development of designs. J. Algebraic Combin.,2(3), 267–290, 1993. Erratum: J. Algebraic Combin., (1), pp. 129, 1994. 9. W. de Launey and K.J. Horadam. Generation of cocyclic Hadamard matrices. Computational algebra and number theory (Sydney, 1992), volume 325 of Math. Appl., 279–290. Kluwer Acad. Publ., Dordrecht, (1995). 10. D.L. Flannery. Calculation of cocyclic matrices. J. of Pure and Applied Algebra, 112, 181–190, (1996). 11. D.L. Flannery. Cocyclic Hadamard matrices and Hadamard groups are equivalent. J. Algebra,192, 749–779, (1997). 12. D.L. Flannery and E.A. O’Brien. Computing 2-cocycles for central extensions and relative difference sets. Comm. Algebra,28(4), 1939–1955, (2000). 13. The GAP group, ‘GAP- Group, Algorithms and programming’, School of Mathematical and Computational Sciences, University of St. Andrews, Scotland (1998). 14. J. Grabmeier, L.A. Lambe. Computing Resolutions Over Finite p-Groups. Proceedings ALCOMA’99. Eds. A. Betten, A. Kohnert, R. Lave, A. Wassermann. Springer Lecture Notes in Computational Science and Engineering, Springer-Verlag, Heidelberg, (2000). 15. G. Ellis. GAP package HAP, ‘Homological Algebra Programming’, http:// hamilton.nuigalway.ie/Hap/www/ 422 V. ´ Alvarez et al. 16. K. Horadam. Progress in cocyclic matrices. Congressus numerantium,118, 161–171 (1996). 17. The MAGMA computational algebra system, http://magma.maths.usyd.edu.au 18. S. Mac Lane. Homology. Classics in Mathematics, Springer-Verlag, Berlin, (1995). Reprint of the 1975 edition. 19. O. Veblen. Analisis situs. A.M.S. Publications, 5(1931).