An algorithm for computing cocyclic matrices developed over some semidirect products

An Algorithm for Computing Cocyclic Matrices Developed over Some Semidirect Products 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. An algorithm for calculating a set of generators of representative 2-cocycles on semidirect product of finite abelian groups is constructed, in light of the theory over cocyclic matrices developed by Horadam and de Launey in [7,8]. The method involves some homological perturbation techniques [3,1], in the homological correspondent to the work which Grabmeier and Lambe described in [12] from the viewpoint of cohomology. Examples of explicit computations over all dihedral groups D4tare given, with aid of Mathematica. 1 Introduction Let Gbe a group, Ua trivial G-module. Functions ψ:G×G→Uwhich satisfy ψ(a, b)ψ(ab, c)=ψ(b, c)ψ(a, bc), a, b, c ∈Gare called 2-cocycles [19]. A cocycle is a coboundary δα if it is derived from a set mapping α:G→Uhaving α(1)=1 by δα(a, b)=α(a)−1α(b)−1α(ab).For each Gand U, the set of cocycles forms an abelian group Z2(G, U) under pointwise multiplication, and the coboundaries form a subgroup B2(G, U). Two cocycles ψand ψare cohomologous if there exists a coboundary δα such that ψ=ψ·δα. Cohomology is an equivalence relation and the cohomology class of ψis denoted [ψ]. It follows that the quotient group Z2(G, U)/B2(G, U) consisting of the cohomology classes, forms an abelian group H2(G, U), which is known as the second cohomology group of G with coefficients in U. For each n≥0 one may define the cocycle analogous in dimension n(n-cocycle). In spite of the important role played by cocycles in Algebraic Topology, Representation Theory and Quantum Systems, the problem of explicitly determining a full representative set of n-cocycles for given Gand Udoes not appear to have been traditionally studied by cohomologists, at least, till the last decade. A 2-cocycle ψis naturally displayed as a cocyclic matrix (associated to ψ, developed over G); that is, a |G|×|G|square matrix whose rows and columns are indexed by the elements of G(under some fixed ordering) and whose entry All authors are partially supported by the PAICYT research project FQM–296 from Junta de Andaluc´ıa and the DGESIC research project PB98–1621–C02–02 from Education and Science Ministry (Spain). S. Bozta¸s and I.E. Shparlinski (Eds.): AAECC-14, LNCS 2227, pp. 287–296, 2001. c Springer-Verlag Berlin Heidelberg 2001 288 V. ´ Alvarez et al. in position (g,h)isψ(g,h). This notion was fruitfully used by Horadam and de Launey [6,7,15] proving some interesting connections between combinatorial design theory and 2-cocycles, as well as connections between coding theory and 2-cocycles. It is also apparent that cocyclic matrices, associated with cocycles with coefficients in K2={−1,1}, account for large classes of so-called Hadamard matrices [8], and may consequently provide an uniform approach to the famous Hadamard conjecture. These facts have yield that over the past decade considerable effort has been devoted to computations of cocycles and cocyclic matrices. Using classical methods involving the Universal Coefficient Theorem, Schur multipliers, inflation and transgression, two algorithms for finding 2-cocycles representing 2-dimensional cohomology classes can be worked out. The first one [7,8] applies to an abelian group Gand the second [10] over groups Gfor which the word problem is solvable. Horadam and de Launey’s method is based on an explicit version of the wellknown Universal Coefficient Theorem, which provides a decomposition of the second cohomology group into the direct sum of two summands, H2(G, U)∼ =Ext(G/[G, G],U)⊕Hom(H2(G),U). These connections make possible the translation of cocyclic development onto a (co)homological framework. This link becomes stronger noting the “Bar construction” [19] related to G. It is a DG-module, which consists of the Z–modules M0(G)=Z,M m(G)=<[g1,...,g m]: gi∈G, 1≤i≤m>, and differential ∂, ∂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 quotient Ker(∂m)/Im(∂m+1) is known to be the mth integral homology group of G,Hm(G). Let R2(G) denote the quotient M2(G)/Im(∂3)⊇H2(G). Taking into account what ∂3means, it is readily checked that the map φ:Z2(G, K2)→Hom(R2(G),K2) h→ φ(h) such that φ(h)  (a,b)∈G×G λ(a,b)(a, b)+Im(∂2) = (a,b)∈G×G λ(a,b)h[a, b] defines an isomorphism between the set of 2-cocycles and Hom(R2(G),K2) [7]. Cocyclic Matrices over Semidirect Products 289 The problem of computing a set of generators for 2-cocycles hence translates to the problem of determining a set of coboundary,symmetric and commutator generators, such that Z2(G, K2)∼ =B2(G, K2)⊕ExtZ(G/[G, G],K2)⊕Hom(H2(G),K2). A minimal set for symmetric generators may be calculated from a primary invariant decomposition of G/[G, G]∼ =H1(G), as a Kronecker product of back negacyclic matrices [7]. A minimal set for coboundary generators is derived from the multiplication table of Gby means of linear algebra manipulations. But it is far from clear how to get a minimal set for commutator generators, in general. One should try to compute the second homology group of Gby means of (M2,∂ 2,∂ 3). Indeed, ∂2is not needed for finite groups G, since H2(G)isa direct sum of finite cyclic groups as it is the case. This procedure is not suitable in practice, since matrices involved are large in most cases. On the other hand, Flannery calculates these summands as the images of certain embeddings which are complementary, called inflation and transgression. Calculation of representative 2-cocycles associated to Ext(G/[G, G],U) (inflation) is canonical. However, calculation of a complement of the image by the embeddings of inflation in H2(G, U) as the image of transgression is not canonical, anyway. As a matter of fact, it depends on the choice of a Schur complement. This is a potential source of difficulties in computation of representative 2-cocycles associated with elements of Hom(H2(G),U). This method has already been implemented in [11], using the symbolic computational system MAGMA. Using a far different approach, Grabmeier and Lambe present in [12] alternate methods for calculating representative 2-cocycles for all finite p–groups from the point of view of Homological Perturbation Theory [13,14,20]. The computer algebra system Axiom has been used in order to make calculations in practice. Here we present a method for explicitly determining a full set of representative 2-cocycles for the elements of the second cohomology group H2(G, Z) where Gis Zr×χZs. All general statements given in this paper are applicable to any semidirect product of finite abelian groups, but for simplicity in the exposition, for this class, only the case Zr×χZswill be presented. Our method could be seen as a mixture of both the algorithms given by Flannery in [10] and Grabmeier–Lambe in [12]. Indeed, we compute representative 2-cocycles proceeding from Hom(H2(Zr×χZs),K2). This alternate method is based on some Homological Perturbation techniques developed in the work of authors [3,1] on the determination of “homological models”(those differential graded modules hG with Hn(G)=Hn(hG), see [4] for instance), for semidirect products of finite abelian groups with group action. The algorithm is straightforward enough to be programmed in any computer algebra system, as we have done in Mathematica[2]. The main steps are to define functions and F:M2(Zr×χZs)→V2and di:Vi→Vi−1, where Viare certain “perturbed” simple algebras. These will be defined in such a way that for any representative 2-cycle zin the quotient ker d2/Im d3, the elevation of zthrough Fwill define a representative 2-cocycle. This is the homology analogous to the work of Grabmeier–Lambe in [12]. 290 V. ´ Alvarez et al. It should be noted that explicit formulae for representative 2-cocycles of H2(Zr×χZs,Z2) are given in [21]. The approach explained in this paper covers the more general case of any semidirect product of finite abelian groups. Similar algorithms may be considered to reach many other settings, progressing from any finite group with known homological model. 2 The Algorithm Let Zr×χZsbe a semidirect product, χa group action such that (a1,b 1)·(a2,b 2)=(a1+χ(b1,a 2),b 1+b2),a 1,a 2∈Zr,b 1,b 2∈Zs. Let consider the following auxiliary sets V2=Z[x2,xy,y2],V 3=Z[x3,x 2y,xy2,y3], B2={[n, m]⊗[]: 1≤n,m<r}∪{[n]⊗[m]: 1≤n<r,1≤m<s}∪ ∪{[]⊗[n, m]: 1≤n,m<s}, B3={[n, m, k]⊗[]: 1≤n, m, k < r}∪{[n, m]⊗[k]: 1≤n,m<r,1≤k<s}∪ ∪{[n]⊗[m, k]: 1≤n<r,1≤m, k < s}∪{[]⊗[n, m, k]: 1≤n, m, k < s}. We will define Z–linear functions g3:V3→B3,fi:Bi→Vifor i=2,3, φ2:B2→B3,ρ3:B3→B2,d3:V3→V2and f∞:B2→V2. Let g3(x3) = ([1,1,1] + ···+[1,r−1,1]) ⊗[], g3(x2y) = ([1,1] + ···+[1,r−1]) ⊗[1], g3(xy2) = [1] ⊗([1,1] + ···+[1,s−1]), g3(y3)=[]⊗([1,1,1] + ···+[1,r−1,1]) f2([n, m]⊗[])=x2,ifn+m≥r, f2([n]⊗[m])=(nm)xy, f2([ ] ⊗[n, m]) = y2,ifn+m≥s, f3([n, m, k]⊗[])=kx 3,ifn+m≥r, f3([n, m]⊗[k]) = kx 2y,ifn+m≥r, f3([n]⊗[m, k]) = nxy2,ifm+k≥s, f3([ ] ⊗[n, m, k]) = ky 3,ifn+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)=rxy, D3(xy2)=−sxy. Cocyclic Matrices over Semidirect Products 291 These morphisms are understood to be zero otherwise. Let define d3=D3+f2ρ3g3−f2ρ3φ2ρ3g3+f2(ρ3φ2)2ρ3g3−···, and f∞:B2→V2, f∞=f2−f2ρ3φ2+f2(ρ3φ2)2−··· Geometric series of these types converge to define a map, as it is proved in the more general setting of generalized semidirect products of finite abelian groups in [1]. The fact is that ρ∗decreases the dimension on the second component, and φ∗either increments the dimension only on the first component or decreases the value of the element in the second component. Hence the composition φi−1ρi becomes nilpotent. Notice that the sets Bidefined above consist of the products Bi= 0≤j≤i (Mj(Zr)⊗Mi−j(Zs)). There is a connecting map F2:M2(Zr×χZs)→B2, so that 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]. Theorem 1. Assume the notation above. 1. H2(Zr×χZs)=H2(V2),which is computed from d3. 2. The map F=f∞◦F2:M2(Zr×χZs)→V2induces an isomorphism in homology, such that for any z∈H2(V2)the elevation of zthrough Fdefines a cocyclic matrix over Zr×χZs. In [1] the authors find a homological model for semidirect products of finite abelian groups. In particular, attending to the groups Zr×χZs, it is proved that H2(M2(Zr×χZs)=H2(V2). Moreover Fis shown to induce an isomorphism in homology. Nevertheless the formula for Fis not explicitly given there, since it is complicated to give an explicit formula for f∞in the general case of semidirect products of groups. It is a remarkable fact that for every finite group G,H2(G) is a finite abelian group [5]. This way, it is only needed d3in order to compute H2(V2) by means of Veblen’s algorithm [22]. This process consists in calculating the integer Smith normal form Dof the matrix Mrepresenting d3with regards to basis B={x3,x 2y,xy,y3}and B={x2,xy,y2}. Let U={u1,u 2,u 3,u 4}and V={v1,v 2,v 3}define these change basis, such that DU,V=PMB,BQ, for appropriated change basis matrices Pand Q. Now we explain what we mean with “elevate zthrough F”. 292 V. ´ Alvarez et al. We want to determine all cocyclic matrices over Zr×χZs. That is, all representative 2-cocycles of Zr×χZs. Thus it suffices to calculate which xin M2(Zr×χZs) are shown to give non trivial homological information in H2(V2). For each generator zin H2(V2), the elevation of zthrough Frelates to the set of elements in M2(Zr×χZs) which projects onto zwith 2-homological information. This can be achieved in two single elevations: one from V2to B2, the other from B2to M2(Zr×χZs). ¿From the theorem above, an algorithm for calculating representative 2- cocycles may be derived in a straightforward manner. Notice that map Fshould be called the universal 2–cochain, following Grabmeier–Lambe’s notation in [12]. Algorithm 1 Input Data: a semidirect product Zr×χZs. Step 1. Compute d3:V3→V2, the differential of the homological model of Zr×χZsin dimension 3. Step 2. Compute H2(Zr×χZs)and representative cycles from d3. Step 3. Elevate the representative cycles from H2(Zr×χZs)to M2(Zr×χZs) via F. Output Data: Set of commutator generators for a basis of cocyclic matrices over Zr×Zs. It should be taken into account that Step 2 often requires to compute the Smith normal form of the matrix corresponding to d3, which is always of size 4×3, independently of indexes rand sof the factors. This is the fundamental improvement in the calculus of the commutator generators, since the size of matrices which arises from the complex (M∗,∂ ∗) depends on the order of the group (the matrix corresponding to operator ∂3is of size (rs)3×(rs)2for the semidirect product Zr×χZs). It may be possible to extend the Theorem 1 and its associated algorithm to other certain families of groups, with homological models already known, such as central extensions [18], finitely generated torsion free nilpotent groups [16], metacyclic groups [17] and many others. It is only needed to find explicit formulae for the analogous of maps F2and F. 3 An Example: Dihedral Groups D2t·2 In this section we apply Algorithm 1 in the particular case of dihedral groups. AMathematica program is used, which authors provide in [2]. It should be noted that dihedral groups Dt·2for odd values of tdo not provide 2-homological information, since H2(Dt·2) is known to be zero in this case. Let D2t·2={(0,0),(1,0),...,(2t−1,0),(1,1),...,(2t−1,1)}, χ(0,n)=n, χ(1,n)=2t−n, ∀n∈Z2t. Cocyclic Matrices over Semidirect Products 293 An explicit formula for Fcan be worked out for these groups, so that if we define λ:Zk×Zk→Z2,k≥2, as λ[x, y]=1ifx+y≥kand 0 otherwise, it is readily checked that 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. Let consider the cases t=1,D2·2={(0,0),(1,0),(0,1),(1,1)}, t=2,D4·2={(0,0),(1,0),(2,0),(3,0),(0,1),(1,1),(2,1),(3,1)}, and t=6,D12·2={(0,0),(1,0),...,(11,0),(0,1),(1,1),...,(11,1)}. Step 1. Compute d3. d(V3)t=1 t=2 t=6 x30 0 0 x2y2xy 2x2+4xy 10x2+12xy xy2−2xy −2x2−4xy −10x2−12xy y30 0 0 Step 2. Compute H2(D2t·2) and representative cycles from d3. In order to compute H2(D2t·2) in the cases t=1,2,6, it is useful to calculate the Smith normal form Dt=PtMtQtof the matrix Mt associated to d3, with basis change matrices Ptand Qt, respectively. In these cases, t=1 t=2 t=6 Dt    200 000 000 000         200 000 000 000         200 000 000 000     Qt  010 100 001    1−20 010 001    −1−60 150 001   Hence, H2(D2t·2)=Z2for t=1,2,6 and the representative cycle is the first element in the new basis Uof Z[V2]. In order to translate to the basis Bof Z[V2] the homological information which H2(D2t·2) provides, it suffices to select the odd entries of each of the columns of Qtcorresponding to each representative cycle in the basis U(that is, to select which elements of Z[V2] with regards to basis Bhave an odd entry in the position corresponding to a representative cycle with coordinates in basis U). The homological information is concentrated in elements with coordinates (−,n,−)Bfor odd values of nin the case t= 1, in elements (n, −,−)Bfor odd values of nin the case t= 2, and in elements (n, m, −)Bfor n, m of distinct parity in the case t=6. 294 V. ´ Alvarez et al. Step 3. Elevate the representative cycles from H2(D2t·2)toM2(D2t·2) via F. It suffices to detect which elements of M2(D2t·2) are carried out via Fto elements (−,n,−)Bfor odd n(t= 1), (n, −,−)Bfor odd n(t= 2), and (n, m, −)Bfor n, m of distinct parity (t= 6). These elements indicate the positions in the |D2t·2|×|D2t·2|commutator cocyclic generator matrix which are not trivial. In the case t= 1, we obtain the following elements: [(0,1),(1,0)],[(1,1),(1,0)],[(0,1),(1,1)],[(1,1),(1,1)]. For t=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 the case t= 6, the elements which are carried out via Fto elements (n, m, −)Bfor n, m of distinct parity are those [(a1,b 1),(a2,b 2)] such that    b1=0,a1+a2>11; or b1=1,a1<a 2. Output data: set of commutator generators for a basis of cocyclic matrices over D2t·2,t=1,2,6. Assuming K2= 1, we obtain t=1 t=2 t=6 A1A1 B1B1A2A2 B2B2A6A6 B6B6 where 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        . Note that A6is usually called back negacyclic. In general, it may be proved that for t>2 the computation of H2(D2t·2) reduces to the matrices Dt=    200 000 000 000     and Qt=  −1−t0 1t−10 001   Cocyclic Matrices over Semidirect Products 295 so that H2(D2t·2)=Z2and the homological information is concentrated in elements with coordinates (n, m, −)Bfor n, m of distinct parity. Hence, the set of commutator generators for a basis of cocyclic matrices over D2t·2reduces to AtAt BtBt,where Atis the correspondant back negacyclic matrix and Btconsists in the matrix whose rows are the ones of Atdisplayed in reverse order. It should be noted that the cocyclic matrices over dihedral groups have already been found from Flannery’s techniques in [10]. Remark 1. The case t= 2 is also studied in [7], where the commutator generator is said to be             11 1 1 111 1 11 1BB11 1 11BBB11B 1BBBB1BB 11 1 1 111 1 1BBBB1BB 11BBB11B 11 1BB11 1             with B2=1. Both matrices differ in the (Hadamard) product of a coboundary generator Cand a symmetric generator S, which are C=             11111111 1A1AAA11 1111A1A1 1A1AA11A 11A111A1 1A11A111 1AAAAA1A 111AA111             ,S=             11111111 1D1D1D1D 11111111 1D1D1D1D 11111111 1D1D1D1D 11111111 1D1D1D1D             , with A=D=−1. The matrix Carises from any of the set 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. References 1. V. ´ Alvarez, J.A. Armario, M.D. Frau and P. Real. Homology of semidirect products of finite abelian groups with group action. Preprint of Dpto. Matem´atica Aplicada I, University of Seville (Spain, 2001).