An algorithm for computing cocyclic matrices developed over some semidirect products

An Algo i hm o Compu ing Cocyclic Ma ices De eloped o e Some Semidi ec P oduc s 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 . An algo i hm o calcula ing a se o gene a o s o ep e- sen a i e 2-cocycles on semidi ec p oduc o fini e abelian g oups is cons uc ed, in ligh o he heo y o e cocyclic ma ices de eloped by Ho adam and de Launey in [7,8]. The me hod in ol es some homolog- ical pe u ba ion echniques [3,1], in he homological co esponden o he wo k which G abmeie and Lambe desc ibed in [12] om he iew- poin o cohomology. Examples o explici compu a ions o e all dihed al g oups D4 a e gi en, wi h aid o Ma hema ica. 1 In oduc ion Le Gbe a g oup, Ua i ial G-module. Func ions ψ:G×G→Uwhich sa is y ψ(a, b)ψ(ab, c)=ψ(b, c)ψ(a, bc), a, b, c ∈Ga e called 2-cocycles [19]. A cocycle is a cobounda y δα i i is de i ed om a se mapping α:G→Uha ing α(1)=1 by δα(a, b)=α(a)−1α(b)−1α(ab).Fo each Gand U, he se o cocycles o ms an abelian g oup Z2(G, U) unde poin wise mul iplica ion, and he cobounda ies o m a subg oup B2(G, U). Two cocycles ψand ψa e cohomologous i he e exis s a cobounda y δα such ha ψ=ψ·δα. Cohomology is an equi alence ela ion and he cohomology class o ψis deno ed [ψ]. I ollows ha he quo- ien g oup Z2(G, U)/B2(G, U) consis ing o he cohomology classes, o ms an abelian g oup H2(G, U), which is known as he second cohomology g oup o G wi h coefficien s in U. Fo each n≥0 one may define he cocycle analogous in dimension n(n-cocycle). In spi e o he impo an ole played by cocycles in Algeb aic Topology, Rep esen a ion Theo y and Quan um Sys ems, he p oblem o explici ly de e mining a ull ep esen a i e se o n-cocycles o gi en Gand Udoes no appea o ha e been adi ionally s udied by cohomologis s, a leas , ill he las decade. A 2-cocycle ψis na u ally displayed as a cocyclic ma ix (associa ed o ψ, de eloped o e G); ha is, a |G|×|G|squa e ma ix whose ows and columns a e indexed by he elemen s o G(unde some fixed o de ing) and whose en y 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 and he DGESIC esea ch p ojec PB98–1621–C02–02 om Educa ion and Science Minis y (Spain). S. Boz a¸s and I.E. Shpa linski (Eds.): AAECC-14, LNCS 2227, pp. 287–296, 2001. c Sp inge -Ve lag Be lin Heidelbe g 2001 288 V. ´ Al a ez e al. in posi ion (g,h)isψ(g,h). This no ion was ui ully used by Ho adam and de Launey [6,7,15] p o ing some in e es ing connec ions be ween combina o ial design heo y and 2-cocycles, as well as connec ions be ween coding heo y and 2-cocycles. I is also appa en ha cocyclic ma ices, associa ed wi h cocycles wi h coefficien s in K2={−1,1}, accoun o la ge classes o so-called Hadama d ma ices [8], and may consequen ly p o ide an uni o m app oach o he amous Hadama d conjec u e. These ac s ha e yield ha o e he pas decade conside able effo has been de o ed o compu a ions o cocycles and cocyclic ma ices. Using clas- sical me hods in ol ing he Uni e sal Coefficien Theo em, Schu mul iplie s, infla ion and ansg ession, wo algo i hms o finding 2-cocycles ep esen ing 2-dimensional cohomology classes can be wo ked ou . The fi s one [7,8] applies o an abelian g oup Gand he second [10] o e g oups G o which he wo d p oblem is sol able. Ho adam and de Launey’s me hod is based on an explici e sion o he well- known Uni e sal Coefficien Theo em, which p o ides a decomposi ion o he second cohomology g oup in o he di ec sum o wo summands, H2(G, U)∼ =Ex (G/[G, G],U)⊕Hom(H2(G),U). These connec ions make possible he ansla ion o cocyclic de elopmen on o a (co)homological amewo k. This link becomes s onge no ing he “Ba cons uc ion” [19] ela ed o G. I is a DG-module, which consis s o he Z–modules M0(G)=Z,M m(G)=<[g1,...,g m]: gi∈G, 1≤i≤m>, and diffe en ial ∂, ∂1([g1])=0,∂ m+1([g1,...,g m+1])=(−1)m+1([g1,...g m])+ +([g2,...,g m+1]) + m  i=1 (−1)i([g1,...,g igi+1,...,g m+1]). The quo ien Ke (∂m)/Im(∂m+1) is known o be he m h in eg al homology g oup o G,Hm(G). Le R2(G) deno e he quo ien M2(G)/Im(∂3)⊇H2(G). Taking in o accoun wha ∂3means, i is eadily checked ha he map φ:Z2(G, K2)→Hom(R2(G),K2) h→ φ(h) such ha φ(h)  (a,b)∈G×G λ(a,b)(a, b)+Im(∂2) = (a,b)∈G×G λ(a,b)h[a, b] defines an isomo phism be ween he se o 2-cocycles and Hom(R2(G),K2) [7]. Cocyclic Ma ices o e Semidi ec P oduc s 289 The p oblem o compu ing a se o gene a o s o 2-cocycles hence ansla es o he p oblem o de e mining a se o cobounda y,symme ic and commu a o gene a o s, such ha Z2(G, K2)∼ =B2(G, K2)⊕Ex Z(G/[G, G],K2)⊕Hom(H2(G),K2). A minimal se o symme ic gene a o s may be calcula ed om a p ima y in a ian decomposi ion o G/[G, G]∼ =H1(G), as a K onecke p oduc o back negacyclic ma ices [7]. A minimal se o cobounda y gene a o s is de i ed om he mul iplica ion able o Gby means o linea algeb a manipula ions. Bu i is a om clea how o ge a minimal se o commu a o gene a o s, in gene al. One should y o compu e he second homology g oup o Gby means o (M2,∂ 2,∂ 3). Indeed, ∂2is no needed o fini e g oups G, since H2(G)isa di ec sum o fini e cyclic g oups as i is he case. This p ocedu e is no sui able in p ac ice, since ma ices in ol ed a e la ge in mos cases. On he o he hand, Flanne y calcula es hese summands as he images o ce - ain embeddings which a e complemen a y, called infla ion and ansg ession. Calcula ion o ep esen a i e 2-cocycles associa ed o Ex (G/[G, G],U) (infla- ion) is canonical. Howe e , calcula ion o a complemen o he image by he embeddings o infla ion in H2(G, U) as he image o ansg ession is no canon- ical, anyway. As a ma e o ac , i depends on he choice o a Schu comple- men . This is a po en ial sou ce o difficul ies in compu a ion o ep esen a i e 2-cocycles associa ed wi h elemen s o Hom(H2(G),U). This me hod has al eady been implemen ed in [11], using he symbolic compu a ional sys em MAGMA. Using a a diffe en app oach, G abmeie and Lambe p esen in [12] al e na e me hods o calcula ing ep esen a i e 2-cocycles o all fini e p–g oups om he poin o iew o Homological Pe u ba ion Theo y [13,14,20]. The compu e algeb a sys em Axiom has been used in o de o make calcula ions in p ac ice. He e we p esen a me hod o explici ly de e mining a ull se o ep esen a- i e 2-cocycles o he elemen s o he second cohomology g oup H2(G, Z) whe e Gis Z ×χZs. All gene al s a emen s gi en in his pape a e applicable o any semidi ec p oduc o fini e abelian g oups, bu o simplici y in he exposi ion, o his class, only he case Z ×χZswill be p esen ed. Ou me hod could be seen as a mix u e o bo h he algo i hms gi en by Flanne y in [10] and G abmeie –Lambe in [12]. Indeed, we compu e ep esen a- i e 2-cocycles p oceeding om Hom(H2(Z ×χZs),K2). This al e na e me hod is based on some Homological Pe u ba ion echniques de eloped in he wo k o au ho s [3,1] on he de e mina ion o “homological models”( hose diffe en ial g aded modules hG wi h Hn(G)=Hn(hG), see [4] o ins ance), o semidi ec p oduc s o fini e abelian g oups wi h g oup ac ion. The algo i hm is s aigh - o wa d enough o be p og ammed in any compu e algeb a sys em, as we ha e done in Ma hema ica[2]. The main s eps a e o define unc ions and F:M2(Z ×χZs)→V2and di:Vi→Vi−1, whe e Via e ce ain “pe u bed” simple algeb as. These will be defined in such a way ha o any ep esen a i e 2-cycle zin he quo ien ke d2/Im d3, he ele a ion o z h ough Fwill define a ep esen a i e 2-cocycle. This is he homology analogous o he wo k o G abmeie –Lambe in [12]. 290 V. ´ Al a ez e al. I should be no ed ha explici o mulae o ep esen a i e 2-cocycles o H2(Z ×χZs,Z2) a e gi en in [21]. The app oach explained in his pape co e s he mo e gene al case o any semidi ec p oduc o fini e abelian g oups. Simila algo i hms may be conside ed o each many o he se ings, p og ess- ing om any fini e g oup wi h known homological model. 2 The Algo i hm Le Z ×χZsbe a semidi ec p oduc , χa g oup ac ion such ha (a1,b 1)·(a2,b 2)=(a1+χ(b1,a 2),b 1+b2),a 1,a 2∈Z ,b 1,b 2∈Zs. Le conside he ollowing auxilia y se s V2=Z[x2,xy,y2],V 3=Z[x3,x 2y,xy2,y3], B2={[n, m]⊗[]: 1≤n,m< }∪{[n]⊗[m]: 1≤n< ,1≤m<s}∪ ∪{[]⊗[n, m]: 1≤n,m<s}, B3={[n, m, k]⊗[]: 1≤n, m, k < }∪{[n, m]⊗[k]: 1≤n,m< ,1≤k<s}∪ ∪{[n]⊗[m, k]: 1≤n< ,1≤m, k < s}∪{[]⊗[n, m, k]: 1≤n, m, k < s}. We will define Z–linea unc ions g3:V3→B3, i:Bi→Vi o i=2,3, φ2:B2→B3,ρ3:B3→B2,d3:V3→V2and ∞:B2→V2. Le g3(x3) = ([1,1,1] + ···+[1, −1,1]) ⊗[], g3(x2y) = ([1,1] + ···+[1, −1]) ⊗[1], g3(xy2) = [1] ⊗([1,1] + ···+[1,s−1]), g3(y3)=[]⊗([1,1,1] + ···+[1, −1,1]) 2([n, m]⊗[])=x2,i n+m≥ , 2([n]⊗[m])=(nm)xy, 2([ ] ⊗[n, m]) = y2,i n+m≥s, 3([n, m, k]⊗[])=kx 3,i n+m≥ , 3([n, m]⊗[k]) = kx 2y,i n+m≥ , 3([n]⊗[m, k]) = nxy2,i m+k≥s, 3([ ] ⊗[n, m, k]) = ky 3,i n+m≥s, φ2([n, m]⊗[])=−([1,1,m]+···[1,n−1,m]) ⊗[] φ2([n]⊗[m]) = −([1,1] + ···[1,n−1]) ⊗[m]+[n]⊗([1,1] + ···[1,m−1]), φ2([ ] ⊗[n, m]) = −[]⊗([1,1,m]+···[1,n−1,m]) ρ3([n, m]⊗[k])=[χ(k,n),χ(k,m)] ⊗[]−[n, m]⊗[], ρ3([n]⊗[m, k])=[n]⊗[k]−[χ(m, n)] ⊗[k], D3(x2y)= xy, D3(xy2)=−sxy. Cocyclic Ma ices o e Semidi ec P oduc s 291 These mo phisms a e unde s ood o be ze o o he wise. Le define d3=D3+ 2ρ3g3− 2ρ3φ2ρ3g3+ 2(ρ3φ2)2ρ3g3−···, and ∞:B2→V2, ∞= 2− 2ρ3φ2+ 2(ρ3φ2)2−··· Geome ic se ies o hese ypes con e ge o define a map, as i is p o ed in he mo e gene al se ing o gene alized semidi ec p oduc s o fini e abelian g oups in [1]. The ac is ha ρ∗dec eases he dimension on he second componen , and φ∗ei he inc emen s he dimension only on he fi s componen o dec eases he alue o he elemen in he second componen . Hence he composi ion φi−1ρi becomes nilpo en . No ice ha he se s Bidefined abo e consis o he p oduc s Bi= 0≤j≤i (Mj(Z )⊗Mi−j(Zs)). The e is a connec ing map F2:M2(Z ×χZs)→B2, so ha F2[(a1,b 1),(a2,b 2)]=[]⊗[b2,b 1]+2[χ(b2,a 2)]⊗[b1]+2[χ(b2,a 2),χ(b2b1,a 1)]⊗[]− −[χ(b2b1b2,a 2),χ(b2b1b2b1,a 1)] ⊗[]−[χ(b2b2,a 2)] ⊗[b1]. Theo em 1. Assume he no a ion abo e. 1. H2(Z ×χZs)=H2(V2),which is compu ed om d3. 2. The map F= ∞◦F2:M2(Z ×χZs)→V2induces an isomo phism in homology, such ha o any z∈H2(V2) he ele a ion o z h ough Fdefines a cocyclic ma ix o e Z ×χZs. In [1] he au ho s find a homological model o semidi ec p oduc s o fini e abelian g oups. In pa icula , a ending o he g oups Z ×χZs, i is p o ed ha H2(M2(Z ×χZs)=H2(V2). Mo eo e Fis shown o induce an isomo phism in homology. Ne e heless he o mula o Fis no explici ly gi en he e, since i is compli- ca ed o gi e an explici o mula o ∞in he gene al case o semidi ec p oduc s o g oups. I is a ema kable ac ha o e e y fini e g oup G,H2(G) is a fini e abelian g oup [5]. This way, i is only needed d3in o de o compu e H2(V2) by means o Veblen’s algo i hm [22]. This p ocess consis s in calcula ing he in ege Smi h no mal o m Do he ma ix M ep esen ing d3wi h ega ds o basis B={x3,x 2y,xy,y3}and B={x2,xy,y2}. Le U={u1,u 2,u 3,u 4}and V={ 1, 2, 3}define hese change basis, such ha DU,V=PMB,BQ, o app op ia ed change basis ma ices Pand Q. Now we explain wha we mean wi h “ele a e z h ough F”. 292 V. ´ Al a ez e al. We wan o de e mine all cocyclic ma ices o e Z ×χZs. Tha is, all ep- esen a i e 2-cocycles o Z ×χZs. Thus i suffices o calcula e which xin M2(Z ×χZs) a e shown o gi e non i ial homological in o ma ion in H2(V2). Fo each gene a o zin H2(V2), he ele a ion o z h ough F ela es o he se o elemen s in M2(Z ×χZs) which p ojec s on o zwi h 2-homological in- o ma ion. This can be achie ed in wo single ele a ions: one om V2 o B2, he o he om B2 o M2(Z ×χZs). ¿F om he heo em abo e, an algo i hm o calcula ing ep esen a i e 2- cocycles may be de i ed in a s aigh o wa d manne . No ice ha map Fshould be called he uni e sal 2–cochain, ollowing G ab- meie –Lambe’s no a ion in [12]. Algo i hm 1 Inpu Da a: a semidi ec p oduc Z ×χZs. S ep 1. Compu e d3:V3→V2, he diffe en ial o he homological model o Z ×χZsin dimension 3. S ep 2. Compu e H2(Z ×χZs)and ep esen a i e cycles om d3. S ep 3. Ele a e he ep esen a i e cycles om H2(Z ×χZs) o M2(Z ×χZs) ia F. Ou pu Da a: Se o commu a o gene a o s o a basis o cocyclic ma ices o e Z ×Zs. I should be aken in o accoun ha S ep 2 o en equi es o compu e he Smi h no mal o m o he ma ix co esponding o d3, which is always o size 4×3, independen ly o indexes and so he ac o s. This is he undamen al imp o emen in he calculus o he commu a o gene a o s, since he size o ma ices which a ises om he complex (M∗,∂ ∗) depends on he o de o he g oup ( he ma ix co esponding o ope a o ∂3is o size ( s)3×( s)2 o he semidi ec p oduc Z ×χZs). I may be possible o ex end he Theo em 1 and i s associa ed algo i hm o o he ce ain amilies o g oups, wi h homological models al eady known, such as cen al ex ensions [18], fini ely gene a ed o sion ee nilpo en g oups [16], me acyclic g oups [17] and many o he s. I is only needed o find explici o mulae o he analogous o maps F2and F. 3 An Example: Dihed al G oups D2 ·2 In his sec ion we apply Algo i hm 1 in he pa icula case o dihed al g oups. AMa hema ica p og am is used, which au ho s p o ide in [2]. I should be no ed ha dihed al g oups D ·2 o odd alues o do no p o ide 2-homological in o ma ion, since H2(D ·2) is known o be ze o in his case. Le D2 ·2={(0,0),(1,0),...,(2 −1,0),(1,1),...,(2 −1,1)}, χ(0,n)=n, χ(1,n)=2 −n, ∀n∈Z2 . Cocyclic Ma ices o e Semidi ec P oduc s 293 An explici o mula o Fcan be wo ked ou o hese g oups, so ha i we define λ:Zk×Zk→Z2,k≥2, as λ[x, y]=1i x+y≥kand 0 o he wise, i is eadily checked ha F[(a1,b 1),(a2,b 2)] = b1b2y2+2b1χ(b2,a 2)xy +2b1(χ(b2,a 2)−1)x2+ +2λ[χ(b2,a 2),χ(b2b1,a 1)]x2−λ[χ(b1,a 2),a 1]x2−a2b1xy −b1(a2−1)x2. Le conside he cases =1,D2·2={(0,0),(1,0),(0,1),(1,1)}, =2,D4·2={(0,0),(1,0),(2,0),(3,0),(0,1),(1,1),(2,1),(3,1)}, and =6,D12·2={(0,0),(1,0),...,(11,0),(0,1),(1,1),...,(11,1)}. S ep 1. Compu e d3. d(V3) =1 =2 =6 x30 0 0 x2y2xy 2x2+4xy 10x2+12xy xy2−2xy −2x2−4xy −10x2−12xy y30 0 0 S ep 2. Compu e H2(D2 ·2) and ep esen a i e cycles om d3. In o de o compu e H2(D2 ·2) in he cases =1,2,6, i is use ul o calcula e he Smi h no mal o m D =P M Q o he ma ix M associa ed o d3, wi h basis change ma ices P and Q , espec i ely. In hese cases, =1 =2 =6 D     200 000 000 000         200 000 000 000         200 000 000 000     Q   010 100 001    1−20 010 001    −1−60 150 001   Hence, H2(D2 ·2)=Z2 o =1,2,6 and he ep esen a i e cycle is he fi s elemen in he new basis Uo Z[V2]. In o de o ansla e o he basis Bo Z[V2] he homological in o ma- ion which H2(D2 ·2) p o ides, i suffices o selec he odd en ies o each o he columns o Q co esponding o each ep esen a i e cycle in he basis U( ha is, o selec which elemen s o Z[V2] wi h ega ds o basis Bha e an odd en y in he posi ion co esponding o a ep esen- a i e cycle wi h coo dina es in basis U). The homological in o ma ion is concen a ed in elemen s wi h coo dina es (−,n,−)B o odd alues o nin he case = 1, in elemen s (n, −,−)B o odd alues o nin he case = 2, and in elemen s (n, m, −)B o n, m o dis inc pa i y in he case =6. 294 V. ´ Al a ez e al. S ep 3. Ele a e he ep esen a i e cycles om H2(D2 ·2) oM2(D2 ·2) ia F. I suffices o de ec which elemen s o M2(D2 ·2) a e ca ied ou ia F o elemen s (−,n,−)B o odd n( = 1), (n, −,−)B o odd n( = 2), and (n, m, −)B o n, m o dis inc pa i y ( = 6). These elemen s indica e he posi ions in he |D2 ·2|×|D2 ·2|commu a o cocyclic gene a o ma ix which a e no i ial. In he case = 1, we ob ain he ollowing elemen s: [(0,1),(1,0)],[(1,1),(1,0)],[(0,1),(1,1)],[(1,1),(1,1)]. Fo =2, [(1,0),(3,0)],[(1,0),(3,1)],[(2,0),(2,0)],[(2,0),(3,0)],[(2,0),(2,1)], [(2,0),(3,1)],[(3,0),(1,0)],[(3,0),(2,0)],[(3,0),(3,0)],[(3,0),(0,1)], [(3,0),(2,1)],[(3,0),(3,1)],[(0,1),(2,0)],[(0,1),(2,1)],[(1,1),(1,0)], [(1,1),(2,0)],[(1,1),(1,1)],[(1,1),(3,1)],[(2,1),(1,0)],[(2,1),(1,1)], [(3,1),(1,0)],[(3,1),(3,0)],[(3,1),(1,1)],[(3,1),(3,1)]. In he case = 6, he elemen s which a e ca ied ou ia F o elemen s (n, m, −)B o n, m o dis inc pa i y a e hose [(a1,b 1),(a2,b 2)] such ha    b1=0,a1+a2>11; o b1=1,a1<a 2. Ou pu da a: se o commu a o gene a o s o a basis o cocyclic ma ices o e D2 ·2, =1,2,6. Assuming K2= 1, we ob ain =1 =2 =6 A1A1 B1B1A2A2 B2B2A6A6 B6B6 whe e A1=11 11,B 1=1K 1K,A 2=    1111 11 1K 11KK 1KKK     ,B 2=    11K1 1KK 1 1K11 1K1K     , A6=        11··· 11 11··· 1K . . .. . .. . .. . . 11···KK 1K···KK        ,B 6=        1K···KK 11···KK . . .. . .. . .. . . 11··· 1K 11··· 11        . No e ha A6is usually called back negacyclic. In gene al, i may be p o ed ha o >2 he compu a ion o H2(D2 ·2) educes o he ma ices D =    200 000 000 000     and Q =  −1− 0 1 −10 001   Cocyclic Ma ices o e Semidi ec P oduc s 295 so ha H2(D2 ·2)=Z2and he homological in o ma ion is concen a ed in elemen s wi h coo dina es (n, m, −)B o n, m o dis inc pa i y. Hence, he se o commu a o gene a o s o a basis o cocyclic ma ices o e D2 ·2 educes o A A B B ,whe e A is he co espondan back negacyclic ma ix and B consis s in he ma ix whose ows a e he ones o A displayed in e e se o de . I should be no ed ha he cocyclic ma ices o e dihed al g oups ha e al- eady been ound om Flanne y’s echniques in [10]. Rema k 1. The case = 2 is also s udied in [7], whe e he commu a o gene a o is said o be             11 1 1 111 1 11 1BB11 1 11BBB11B 1BBBB1BB 11 1 1 111 1 1BBBB1BB 11BBB11B 11 1BB11 1             wi h B2=1. Bo h ma ices diffe in he (Hadama d) p oduc o a cobounda y gene a o Cand a symme ic gene a o S, which a e C=             11111111 1A1AAA11 1111A1A1 1A1AA11A 11A111A1 1A11A111 1AAAAA1A 111AA111             ,S=             11111111 1D1D1D1D 11111111 1D1D1D1D 11111111 1D1D1D1D 11111111 1D1D1D1D             , wi h A=D=−1. The ma ix Ca ises om any o he se map αk:D4·2→K2,k∈{1,−1}, α(0,0)=1,α(1,0) = −1,α(2,0) = −1,α(3,0)=1, α(0,1) = k, α(1,1) = k, α(2,1) = k, α(3,1) = −k. Re e ences 1. V. ´ Al a ez, J.A. A ma io, M.D. F au and P. Real. Homology o semidi ec p oduc s o fini e abelian g oups wi h g oup ac ion. P ep in o Dp o. Ma em´a ica Aplicada I, Uni e si y o Se ille (Spain, 2001).