Calcula ing Cocyclic Hadama d Ma ices in
Ma hema ica: Exhaus i e and Heu is ic Sea ches
V. ´
Al a ez, J.A. A ma io, M.D. F au, and P. Real
Dp o. Ma em´a ica Aplicada I, Uni e sidad de Se illa, A da. Reina Me cedes s/n
41012 Se illa, Spain
{ al a ez, a ma io, md au, eal}@us.es
Abs ac . We desc ibe a no ebook in Ma hema ica which, aking as in-
pu da a a homological model o a fini e g oup Go o de |G|=4 ,
pe o ms an exhaus i e sea ch o cons uc ing he whole se o cocyclic
Hadama d ma ices o e G. Since such an exhaus i e sea ch is no p ac i-
cal o o de s 4 ≥28, he p og am also p o ides an al e na e me hod, in
whichanheu is icsea ch(in e mso a gene ic algo i hm) is pe o med.
We include some execu ions and examples.
Nowadays, mos o Compu e Algeb a Sys ems (CAS) begin o be conce ned
wi h he compu a ion o homological in o ma ion. This is he case o Gap [13],
MAGMA [17]. In a pa allel way, some specific so wa es o achie ing calcula-
ions in homological algeb a a e being de eloped, as i is he case o Kenzo [7]
and Hap [15]. Howe e none o hem a e conce ned wi h he explici calcula ion
o Hadama d cocyclic ma ices. In spi e o ha , some esea che s ha e de eloped
hei own compu a ions, wo king on diffe en sys ems [6,11,12,14,2].
In hispape wep esen ano ebook[1]inMa hema ica 4.0, which implemen s
he homological educ ion me hod desc ibed in [4]. When exhaus i e sea ch is
no easible, he no ebook p o ides a second ou ine o pe o ming an heu is ic
sea ch, which co esponds o he implemen a ion o he gene ic algo i hm in [3].
The in e es ed eade is e e ed o hese pape s o he heo e ical backg ound.
Ano he non exhaus i e me hod o finding ou Hadama d cocyclic ma ices is
desc ibed in [5], in e ms o image es o a ions.
The no ebook akes as inpu da a a homological model φ:¯
B(ZZ[G])


g(hG, d)
o a fini e g oup Go o de |G|=4 .The e mhomological model e e s o a
con ac ion φ:¯
B(ZZ[G])


ghG om he educed ba cons uc ion o he g oup G
(i.e. he educed complex associa ed o he s anda d ba esolu ion [18]) o a
diffe en ial g aded module o fini e ype hG,so ha H∗(G)=H∗(hG)and he
homology o hG may be effec i ely compu ed by means o Veblen’s algo i hm [19]
(in ol ing he Smi h’s no mal o ms o he ma ices ep esen ing he diffe en ial
ope a o ).
All au ho s a e pa ially suppo ed by he PAICYT esea ch p ojec FQM–296 om
Jun a de Andaluc´ıa (Spain).
A. Iglesias and N. Takayama (Eds.): ICMS 2006, LNCS 4151, pp. 419–422, 2006.
c
Sp inge -Ve lag Be lin Heidelbe g 2006
420 V. ´
Al a ez e al.
In o de o cons uc a basis o 2-cobounda ies, he p og am needs o know
he g oup law on G. To his end, he use mus fix an o de ing on he elemen s
o G,sayG={g1=1,...,g
4 }.Now,ama ixP ep esen ing he g oup law in
Gmay be cons uc ed a once, so ha P(i, j)=ki and only i gigj=gk.
The only addi ional in o ma ion which is needed is ha o he diag ams
¯
B1(ZZ[G])
−→ B1
↓Q
¯
B1
¯
B2(ZZ[G])
−→ B2
↓Q
¯
B2
Tha is, he ma ices M2and M3 ep esen ing he diffe en ials ope a o s d2
and d3o hG, as well as he ma ices F1and F2 ep esen ing he maps 1:
¯
B1(ZZ[G]) →B
1and 2:¯
B2(ZZ[G]) →B
2.
In hese ci cums ances, we may now de e mine exac ly wha he inpu and
ou pu da a a e.
Inpu da a
–The ma ices P,Mi+1,Fi ep esen ing he g oup law, di+1 and i,1≤i≤2.
–The sea ching me hod o use: in oduce 1 o an exhaus i e sea ch, any hing
else o a heu is ic sea ch.
Ou pu da a
–A ull basis o no malized 2-cocycles o e G.
–In case ha an exhaus i e sea ch was chosen, he whole se o Hadama d
cocyclic ma ices o e G. O he wise, a ew Hadama d cocyclic ma ices,
ob ained om he heu is ic sea ch.
All he execu ions and examples included below ha e been wo ked ou wi h
aid o he Ma hema ica 4.0 no ebook which we ha e desc ibed he e, unning
on a Pen ium IV 2.400 Mhz DIMM DDR266 512 MB. Since some calcula ions
ob ained om he heu is ic sea ch a e p o ided in [3], we ocus on calcula ions
ob ained om an exhaus i e sea ch.
In he sequel, he elemen s o a p oduc A×Ba e o de ed as he ows o a
ma ix indexed in |A|×|B|. Fo ins ance, i |A|= and |B|=c, he o de ing is
<a
1b1,a
1b2,...,a
1,b
c,a
2b1,a
2b2,...,a
2bc,...,a
b1,...,a
bc>
We assume ZZk={0,1,...,k −1}wi h addi i e law. Nex we include a able
wi h he numbe o cocyclic Hadama d ma ices ha we ha e ound in each case.
ZZ4 ZZ2×ZZ2 ZZ4×ZZ ZZ2
2×ZZ D4 ZZ2 × ZZ2(ZZ × ZZ2)×χ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
Calcula ing Cocyclic Hadama d Ma ices in Ma hema ica 421
He e deno es he 2-cocycle (gi,g
j)=
2+1i gi=gj=1
0o he wise
and χdeno es
he dihed al ac ion χ(a, b)=−bi a=1
bi a=0
The compu ing ime equi ed in all cases was p ac ically o he same o de :
less han 3 seconds o 1 ≤ ≤3, a couple o minu es o = 4 and abou 30
minu es o = 5. The black en ies co espond o new esul s, as a as we know
( he case o G5
5=D4·5is included, since he compu a ion o Flanne y in [16],
2380, diffe s om ou s, 2200).
Re e ences
1. V. ´
Al a ez. h p://ma hwo ld.wol am.com/Hadama dSea ch.h ml (2006). To ap-
pea .
2. V. ´
Al a ez, J.A. A ma io, M.D. F au and P. Real. An algo i hm o compu ing co-
cyclic ma ices de eloped o e some semidi ec p oduc s. AAECC-14 P oceedings,
LNCS 2227, 287–296 (2001).
3. V. ´
Al a ez, J.A. A ma io, M.D. F au and P. Real. A gene ic algo i hm o cocyclic
Hadama d ma ices. AAECC-16 P oceedings,LNCS3857, 144–153, (2006).
4. V. ´
Al a ez, J.A. A ma io, M.D. F au and P. Real. Homological educ ion me hod
o cons uc ing Hadama d cocyclic ma ices. Communica ion submi ed o he
EACA-06 con e ence, Se illa (2006).
5. A. Baliga and J. Chua. Sel -dual codes using image eso a ion echniques. P o-
ceedings AAECC’14. Eds. S. Boz as, I.E. Shpa linski. Sp inge Lec u e No es in
Compu e Science, Sp inge -Ve lag, Heidelbe g, (2001).
6. A. Baliga and K.J. Ho adam. Cocyclic Hadama d ma ices o e ZZ ×ZZ2
2.Aus alas.
J. Combin.,11, 123–134, (1995).
7. X. Dousson, J. Rubio, F. Se ge ae and Y. Si e . The Kenzo p og am. Ins i u e
Fou ie , G enoble (19998). h p://www- ou ie .uj -g enoble. /˜se ge ae /Kenzo/
8. W. de Launey and K.J. Ho adam. Cocyclic de elopmen o designs. J. Algeb aic
Combin.,2(3), 267–290, 1993. E a um: J. Algeb aic Combin., (1), pp. 129, 1994.
9. W. de Launey and K.J. Ho adam. Gene a ion o cocyclic Hadama d ma ices.
Compu a ional algeb a and numbe heo y (Sydney, 1992), olume 325 o Ma h.
Appl., 279–290. Kluwe Acad. Publ., Do d ech , (1995).
10. D.L. Flanne y. Calcula ion o cocyclic ma ices. J. o Pu e and Applied Algeb a,
112, 181–190, (1996).
11. D.L. Flanne y. Cocyclic Hadama d ma ices and Hadama d g oups a e equi alen .
J. Algeb a,192, 749–779, (1997).
12. D.L. Flanne y and E.A. O’B ien. Compu ing 2-cocycles o cen al ex ensions and
ela i e diffe ence se s. Comm. Algeb a,28(4), 1939–1955, (2000).
13. The GAP g oup, ‘GAP- G oup, Algo i hms and p og amming’, School o Ma he-
ma ical and Compu a ional Sciences, Uni e si y o S . And ews, Sco land (1998).
14. J. G abmeie , L.A. Lambe. Compu ing Resolu ions O e Fini e p-G oups. P oceed-
ings ALCOMA’99. Eds. A. Be en, A. Kohne , R. La e, A. Wasse mann. Sp inge
Lec u e No es in Compu a ional Science and Enginee ing, Sp inge -Ve lag, Heidel-
be g, (2000).
15. G. Ellis. GAP package HAP, ‘Homological Algeb a P og amming’, h p:// hamil-
on.nuigalway.ie/Hap/www/
422 V. ´
Al a ez e al.
16. K. Ho adam. P og ess in cocyclic ma ices. Cong essus nume an ium,118,
161–171 (1996).
17. The MAGMA compu a ional algeb a sys em, h p://magma.ma hs.usyd.edu.au
18. S. Mac Lane. Homology. Classics in Ma hema ics, Sp inge -Ve lag, Be lin, (1995).
Rep in o he 1975 edi ion.
19. O. Veblen. Analisis si us. A.M.S. Publica ions, 5(1931).