The homological reduction method for computing cocyclic Hadamard matrices

Journal of Symbolic Computation 44 (2009) 558–570 Contents lists available at ScienceDirect Journal of Symbolic Computation journal homepage: www.elsevier.com/locate/jsc The homological reduction method for computing cocyclic Hadamard matricesI V. Alvarez, J.A. Armario, M.D. Frau, P. Real Dpto. Matemática Aplicada I, Univ. Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain article info Article history: Received 30 November 2006 Accepted 13 June 2007 Available online 30 September 2008 Keywords: Homological model Integer Smith normal form Cocyclic matrix Hadamard matrix abstract An alternate method for constructing (Hadamard) cocyclic matrices over a finite group Gis described. Provided that a homological model φ:¯ B(Z[G])F  HhG for Gis known, the homological reduction method automatically generates a full basis for 2-cocycles over G (including 2-coboundaries). From these data, either an exhaustive or a heuristic search for Hadamard cocyclic matrices is then developed. The knowledge of an explicit basis for 2-cocycles which includes 2-coboundaries is a key point for the designing of the heuristic search. It is worth noting that some Hadamard cocyclic matrices have been obtained over groups Gfor which the exhaustivesearchingtechniquesarenotfeasible.Fromthecomputationalcost point of view, even in the case that the calculation of such a homological model is also included, comparison with other methods in the literature shows that the homological reduction method drastically reduces the required computing time of the operations involved, so that even exhaustive searches succeeded at orders for which previous calculations could not be completed. With aid of an implementation of the method in Mathematica, some examples are discussed, including the case of very well-known groups (finite abelian groups, dihedral groups) for clarity. ©2008 Elsevier Ltd. All rights reserved. 1. Introduction Since the cocyclic Hadamard conjecture was stated (Horadam and de Launey,1995), interest in calculating cocyclic Hadamard matrices over finite groups Ghas increased considerably. Taking into account that only 2 ×2 Hadamard matrices exist whose sizes are not multiple of 4, we may assume in the sequel that |G| = 4t. IAll authors are partially supported by the PAICYT research project FQM–296 from Junta de Andalucía (Spain). E-mail addresses: [email protected] (V. Alvarez), [email protected] (J.A. Armario), [email protected] (M.D. Frau), [email protected] (P. Real). 0747-7171/$ – see front matter ©2008 Elsevier Ltd. All rights reserved. doi:10.1016/j.jsc.2007.06.009 V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 559 Basically, two methods have been proposed in order to compute the whole set of cocyclic HadamardmatricesoveragroupG.Inbothcases,onceasetofgeneratorsforrepresentative2-cocycles is determined, it suffices to add a basis for 2-coboundaries of G, so that a whole basis for 2-cocycles is finally achieved. The first method constitutes the foundational work on the subject Horadam and de Launey (1993, 1995), and is applied over abelian groups. Attending to the Universal Coefficient Theorem, a basis for representative 2-cocycles may be obtained from the relation H2(G,Z2)∼ =Ext(G/[G,G],Z2)⊕Hom(H2(G), Z2). Generators coming from the first factor are uniquely determined (up to the internal ordering in G) as the Kronecker product of back negacyclic matrices, accordingly to the primary invariant decomposition of the abelianization G/[G,G]of G, so that each 2tfactor on G/[G,G]contributes a 2t×2tback negacyclic matrix. Generators coming from the factor Hom(H2(G), Z2)may be computed as soon as a basis of 2-cycles in H2(G)is described. Unfortunately, in general, this is a difficult task. The method in Flannery (1996) applies over groups Gfor which the word problem is solvable, and uses the inflation and transgression maps. The inflation map generates the representative 2-cocycles of Ext(G/[G,G],Z2), once again in terms of back negacyclic matrices. However, the whole description of H2(G;Z2)depends on the choice of a Schur complement of the image of inflation, which is no longer canonical and could reveal itself as a computationally hard task. The case of dihedral groups and central extensions is described in Flannery (1996,1997) and Flannery and O’Brien (2000). We describe here, a third approximation to this question, which we term the homological reduction method. It is the crystallization of a previous work of the authors in Álvarez et al. (2001). Origins of the method may be located in Grabmeier and Lambe (2000), which includes the construction of a basis for cocyclic matrices over p-groups from a cohomological model for these groups. Provided a homological model hG for Gis known (that is, a differential graded module of finite type which shares the homology groups with G), we explicitly describe an algorithm for constructing a basis for 2-cocycles over Gin a straightforward manner. In fact, the goodness of this approximation is supported by the efficiency in which both H1(G)≃G/[G,G]and H2(G)are computed from the homological model hG. From such a basis, a search for Hadamard cocyclic matrices may be developed at once. At this point, it is remarkable that an exhaustive search is feasible only for low orders (limited up to |G| ≤ 28, attending to the computing capability of today more common processors, as it has been experimentally checked), since the search space often grows exponentially depending on the order of the group (e.g. see the examples described in Section 3). In case of higher orders, heuristic searches such as Álvarez et al. (2006a) are a better choice. The knowledge of an explicit basis for 2-cocycles which includes 2-coboundaries is a key point for the designing of such an heuristic search. From the computational-cost point of view, even in the case that the calculation of such a homological model is also included, comparison with other methods in the literature shows that the homological reduction method drastically reduces the required computing time of the operations involved, so that even exhaustive searches succeeded at orders for which previous calculations could not be completed (see Table 1 in page 20 for details). We organize the paper as follows. In Section 2we describe the homological reduction method itself, that is, how to construct a full basis for 2-cocycles over Gfrom a homological model hG of G. Section 3is devoted to showing several examples, including the well-known cases of dihedral groups D4tand abelian groups Zt×Z2 2for clarity. From these data, we construct Table 1, which completes that in Horadam (1996) about the total number of cocyclic Hadamard matrices over these groups for small orders. All the calculations have been made with aid of packages in Mathematica (Álvarez et al., 2006b,c,d,e,f). 2. Describing the homological reduction method Consider a multiplicative group G= {g1=1,g2,...,g4t}, not necessarily abelian. A cocyclic matrix Mfon Gconsists in a binary matrix Mf=(f(gi,gj)) coming from a 2-cocycle f, that is, a map f:G×G→ {1,−1}such that f(gi,gj)f(gigj,gk)=f(gj,gk)f(gi,gjgk), ∀gi,gj,gk∈G. 560 V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 We note Z(G)the group of 2-cocycles, with regards to the pointwise (also termed Hadamard) product. Let B(G)be the group of 2-coboundaries, which consist in the functions ∂α(gi,gj)=α(gi)α(gj)α(gigj)−1,gi,gj∈G, for set maps α:G→ {1,−1}. It is a well-known fact that Z(G)/B(G)∼ =H2(G;Z2). This way, the Universal Coefficient Theorem provides at once a first chance for computing cocyclic matrices, Z(G)/B(G)∼ =H2(G;Z2)∼ =Ext (H1(G), Z2)⊕Hom (H2(G), Z2) where H1(G)∼ =G/[G,G]. This way, a basis for 2-cocycles is performed by joining three different bases: a basis for 2- coboundaries, a basis for representative symmetric 2-cocycles coming from inflation (i.e. from the Ext (H1(G), Z2)factor), and a basis for 2-cocycles coming from transgression (i.e. the Hom (H2(G), Z2) factor). Such a basis consists, then, in a set B= {∂1, . . . , ∂b, β1, . . . , βs, γ1, . . . , γr}, for some 2- coboundaries ∂i, inflation 2-cocycles βjand transgression cocycles γk. As pointed out in Horadam and de Launey (1995), we may reduce to the case of normalized 2- cocycles f(such that f(1,1)=1), as well as the related normalized cocyclic matrices Mf. The term ‘‘normalized’’ means that the first row (and column) in Mfis formed all by 1. From now on, cocycle will mean normalized 2-cocycle. A basis for 2-coboundaries may be obtained by Linear Algebra. More concretely, denote ∂ithe 2- coboundary associated with the characteristic map of the element gi,δi:G→Z, δi(gj)=−1,if i=j 1,otherwise. Take the matrices M∂irelated to ∂ias vectors of length 16t2. Moreover, consider the 4t×16t2matrix Cwhose rows are the vectors M∂i. Then a row reduction on Cleads to a basis for 2-coboundaries. It suffices to keep trace of those coboundaries ∂iwhose transformed rows in M∂iafter the row reduction are not zero. Lemma 1. The morphisms ∂jabove define a basis for 2-coboundaries. Thehomologicalreduction method intends that the calculation of H1(G)and H2(G)isaseconomical as possible. Roughly speaking, the idea consists of determining a homological model hG for G, and then project the (co)homological information from hG to G. The term homological model refers to a contraction φ:¯ B(Z[G])F  HhG from the reduced bar construction of the group G(i.e. the reduced complex associated with the standard bar resolution (Mac Lane,1995)) to a differential graded module of finite type hG, so that H∗(G)=H∗(¯ B(Z[G])) ∼ =H∗(hG) and the homology of hG may be effectively computed by means of Veblen’s algorithm (Veblen,1931) (involving the Smith’s normal forms of the matrices representing the differential operator). Concerning to the inflation and transgression generators, the use of a homological model will often simplify the calculation of G/[G,G]∼ =H1(G)∼ =H1(hG)and H2(G)∼ =H2(hG). More concretely, the simplification depends on the decrease of the number of generators at each degree, as it will be clear from the description of Veblen’s algorithm below. However, we need to lift the (co)homological information from hG to ¯ B(Z[G])in order to explicitly generate a full set of representative 2-cocycles in G. The projection morphism F:¯ B(Z[G])−→ hG helps in this task. V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 561 From Horadam and de Launey (1995), we know that there are as many generators coming from inflation as factors Z2tjin the primary decomposition ⊕n i=1Zpti i of G/[G,G]. All of them are 2tj×2tj back negacyclic matrices of the type BN2tj=      1 1 · · · 1 1 1 1 · · · 1− . . .. . .. . .. . . 1 1 · · · − − 1− · · · − −       for a suitable ordering of the elements in G. We use here ‘‘−’’ instead of ‘‘−1’’ for short. The problem is that the initial ordering G= {1,g2,...,g4t}will differ in general from the above one. The difficulty lies in how to link such two orderings. Let d:hG →hG be the differential on hG and B1= {u1,...,um}and B2= {e1,...,en}be some basis of hG on dimensions 1 and 2, respectively. We compute G/[G,G]as H1(hG), which consists only of torsion part, as Gis a finite group. So Veblen’s algorithm reduces to compute the Smith’s normal form D2of M2(d), M2(d)=   d(e1) . . . d(en)   n×m D2=    b1 ...0 bl 0 0    n×m so that we get the torsion-invariant decomposition G/[G,G]∼ =H1(G)∼ =H1(hG)∼ =Zb1⊕ · · · ⊕ Zbl, 1≤b1|b2|···|bl, which is by no means a primary decomposition of G/[G,G]. Moreover, some (not uniquely determined) change basis matrices Pand Qexist such that B2 M2(d) −→ B1 P↑#↓Q ¯ B2 D2 −→ ¯ B1 D2=P·M2(d)·Q Now we proceed according to the following steps: (1) We select the columns jof D2with an even entry at the diagonal position, precisely the ones corresponding to those Zbjin H1(hG)which contribute a factor Z2tto the primary decomposition of G/[G,G]. There will be as many inflation generators as columns of this kind. (2) Choose one of these columns, say the j-th for instance. Furthermore, assume that bj=2tjqj, for qjodd. The symmetric matrix Mj=(βj(g,h)) which corresponds to the generator βjof this j-th column is constructed by lifting the map wj:Z2tj×Z2tj→ {1,−1},wj(k,l)=(−1)bk+l 2tjc, from Z2tj×Z2tjto the whole G×G. For g,h∈Gwe define βj(g,h)=wj([g]j,[h]j), where [g]jis the j-th coordinate of the coset of gin G/[G,G]regarding to the basis of H1(hG)canonically associated to ¯ B1. Explicitly, βj(g,h)is determined from F:¯ B1(Z[G])→hG, since [g]jis the j-th coordinate of F(g)with regards to ¯ B1; that is, the j-th coordinate of the vector F(g)·Qmodulo 2tj. Graphically, ¯ B1(Z[G])F −→ B1 ↓Q ¯ B1 Proposition 2. The morphisms βjabove define a basis for 2-cocycles coming from inflation. We proceed in an analogous way in order to construct the generators coming from transgression. 562 V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 Let B3= {v1,...,vs}be a basis for hG at dimension 3. Since Gis a finite group, again H2(G)∼ = H2(hG)consists only of torsion part, so that Veblen’s algorithm reduces to compute the Smith’s normal form D3of M3(d), M3(d)=   d(v1) . . . d(vs)   s×n D3=    b1 ...0 bl 0 0    s×n where H2(G)∼ =H2(hG)∼ =Zb1⊕ · · · ⊕ Zbl, and 1 ≤b1|b2|···|bl. Furthermore, some change basis matrices Pand Qexist such that B3 M3(d) −→ B2 P↑#↓Q ¯ B3 D3 −→ ¯ B2 D3=P·M3(d)·Q Now we proceed according to the following steps: (1) We select those columns jof D3with an even entry bjat the diagonal position: since Hom (Zn,Z2)∼ =Zgcd(n,2)we are only interested in factors Zbjwith bjeven. There will be as many generators coming from transgression as columns of this kind. (2) Set one of these columns, say the j-th for instance. The cocyclic matrix Mj=(γj(g,h)) which corresponds to the generator γjof this j-th column is constructed by projecting the elements (g,h)∈G×Gonto ¯ B2by means of the composition of Fand Q. For g,h∈Gwe define γj(g,h)=F([g,h])·Qmod 2. Graphically, ¯ B2(Z[G])F −→ B2 ↓Q ¯ B2 Proposition 3. The morphisms γjabove define a basis for 2-cocycles coming from transgression. Thehomologicalreductionmethod provides then the following algorithm for computing the whole set of Hadamard cocyclic matrices over G. Algorithm 1 (Homological Reduction Method). Input: group with homological model {G,hG,F,H, φ} Output: Some (eventually the full set of) cocyclic Hadamard matrices over G. P1 Construct a basis for 2-coboundaries (Lemma 1) P2 Construct a basis for inflation 2-cocycles (Proposition 2) P3 Construct a basis for transgression 2-cocycles (Proposition 3) P4 Construct a basis Bfor 2-cocycles over G P5 Develop from Ban exhaustive or heuristic search for Hadamard cocyclic matrices, depending on the size of |G|. Knowledge of such a basis Bfor 2-cocycles, which includes 2-coboundaries, is a key point for the designing of the genetic algorithm in Álvarez et al. (2006a) searching for Hadamard cocyclic matrices over G. The individuals of this genetic algorithm consist of binary tuples, which are to be understood as the coordinates of a 2-cocycle with regards to the basis B. The interested reader is referred to Álvarez et al. (2006a) for details. We want to emphasize that such a heuristic search is only possible since a basis for 2-coboundaries is explicitly used. It seems that other methods in the literature ignore the issue of finding a basis for 2- coboundaries. In the opinion of the authors, a deeper analysis on the way in which 2-coboundaries and representative 2-cocycles have to be combined in order to get a Hadamard cocyclic matrix becomes of capital interest (see Álvarez et al. (2008) for instance). 3. Examples All the executions and examples of this section have been worked out with aid of the Mathematica 4.0 notebooks (Álvarez et al.,2006d,e) described in Álvarez et al. (2006c,submitted for publication) V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 563 (for constructing homological models) and Álvarez et al. (2006b) (in order to form up basis for 2- cocycles from which the search for Hadamard cocyclic matrices is then developed), running on a Pentium IV 2.400 MHz DIMM DDR266 512 MB. 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 ha1b1,a1b2,...,a1bc,a2b1,a2b2,...,a2bc,...,arb1,...,arbci. The elements in the group are labeled from 1 to |G|, according to this ordering. Let consider the families of groups below (assume Zk= {0,1,...,k−1}with additive law). (1) Gt 1=Z4t. (2) Gt 2=Z2t×Z2. (3) Gt 3=Zt×Z4. Note that G2 3≃G2 2, and Gt 3≃Gt 1for odd t. (4) Gt 4=Zt×Z2 2=Zt×(Z2×Z2). Note that Gt 4≃Gt 2for odd t. (5) Gt 5=D4t=Z2χ×Z2t,χ:Z2×Z2t→Z2tsuch that χ(1,x)= −xand χ(0,x)=x. Note that G1 5≃G1 2is abelian, but Gt 5is not abelian, for t>1. (6) Gt 6=Z2t×fZ2, for f:Z2×Z2→Z2tbeing the 2-cocycle f(gi,gj)=dt 2e + 1 if gi=gj=1 0 otherwise. Note that Gt 6is abelian, since fis symmetric. Furthermore, Gt 6≃Gt 2for even dt 2e + 1 (that is, for t≡1,2(mod 4)), since fis a 2-coboundary in these circumstances (i.e. the extension is trivial). In fact, f=∂α, for α:Z2→Z2tsuch that α(0)=0, α(1)= b t 4c + 1. The extension is not trivial for t≡0,3 mod 4. (7) Gt 7=(Zt×fZ2)×χZ2, for f:Z2×Z2→Ztbeing the 2-cocycle f(gi,gj)=dt 2e + 1 if gi=gj=1 0 otherwise and χbeing the dihedral action χ(a,b)=−bif a=1 bif a=0. Note that Zt×fZ2is abelian (since fis symmetric), but Gt 7is not for t6= 2 (because of the dihedral action). Furthermore, Gt 7≃Gt 5for odd t, since fis a 2-coboundary in these circumstances: f=∂α, for α:Z2→Ztsuch that α(0)=0, α(1)=t2+3 4mod t. Analogously, the extension is also trivial for t≡2 mod 4, since f=∂α, for α(0)=0, α(1)= b t 4c + 1, so that Gt 7≃(Zt×Z2)×χZ2. In particular, G2 7≡G2 4. We may assume that t>1, since there are only two abelian groups of order 4, which are Z2×Z2 (this is the case of G1 i, for i=2,4,5,6,7) and Z4(the case of G1 i, for i=1,3). There are six Hadamard cocyclic matrices over Z2×Z2and two Hadamard cocyclic matrices over Z4. So we are interested in describing cocyclic Hadamard matrices for t>1. In this section, we will first use the homological reduction method for calculating the basis for 2- cocycles for these families of groups Gt i. For brevity, we will only characterize the homological models (hGt k,F,d)for Gt k, in terms of some basis Bifor hGt kon degree 1 ≤i≤3, differential operators dj:Bj+1→Bjand projections Fj:¯ Bj(Z[Gt k])→Bjfor 1 ≤j≤2. Notice that ¯ B1(Z[G])= h[g] : g∈Gi and ¯ B2(Z[G])= h[g,h] : g,h∈Gi. From these data, a basis for representative 2-cocycles may be formed in a straightforward manner. Afterwards, we will develop an exhaustive search for 2 ≤t≤5 and a heuristic search for 2 ≤t≤8 (notice that the cocyclic Hadamard matrices listed here are new, different from those of Álvarez et al. (2006b)). 564 V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 Note that the matrices Pand Qinvolved in the calculation of the Smith Normal Form, D, for A(so that D=P·A·Q) are not uniquely determined, in general. In the sequel we will use the matrices coming from the SmithNormalForm package programmed by the authors in Álvarez et al. (2006f). Due to space restrictions, we will include here only the cases of Gt 4,Gt 5(for comparison with other calculations available in the literature) and Gt 7(as far as we know, these calculations are new. Furthermore, this family of groups seems to provide a large amount of Hadamard cocyclic matrices). The remaining calculations are available at the following web address, http://ma1.eii.us.es/miembros/ armario/cvarmario.htm. Finally, we show in Table 1 the number of all cocyclic Hadamard matrices over Gt ifor 1 ≤i≤7, 2≤t≤5. This table corrects and completes that in Horadam (1996). 3.1. Construction basis for 2-cocycles In the sequel, we use the following notation. We define the set map λn:Z→Z2, so that λn(j)=λn j=1 if j≥nand 0 otherwise. The back negacyclic matrix of order jis denoted by BNj, as before. The square matrix of order nformed up all of 1s is denoted by 1n. The Kronecker product of matrices is denoted by ⊗, so that A⊗Bis the block matrix    a11B. . . a1nB . . .. . . an1B. . . annB   . The Hadamard (pointwise) product of matrices is simply denoted as A·B. Finally, the notation [x]mrefers to xmod m. 3.1.1. Basis for Gt 4=Zt×Z2 2=Zt×(Z2×Z2) B1= {u1,u2,u3},B2= {e1,...,e6},B3= {v1, . . . , v10}, d2(e1)=t·u1,d2(e4)=2·u2,d2(e6)=2·u3,d3(v2)=te2,d3(v3)=te3, d3(v4)= −2e2,d3(v6)= −2e3,d3(v8)=2e5,d3(v9)= −2e5, F[(g,h,i)] = g·u1+h·u2+i·u3, F[(g,h,i)|(a,b,c)] = λt g+a·e1+gb ·e2+gc ·e3+λ2 h+b·e4+hc ·e5+λ2 i+c·e6. From these data, the matrices Diand Qimay be described, in terms of the the coset of tmodulo 2: t D2Q2D3Q3 [t]2=0      200 020 0 0 t 000 000 000       t=2 I3 t6= 2 001 100 010!              200000 020000 002000 000000 000000 000000 000000 000000 000000 000000                    000010 100000 010000 000100 001000 000001       [t]2=1      1 0 0 0 2 0 002t 0 0 0 0 0 0 0 0 0        1 0 −2 −b t 2c0t 0 1 0               100000 010000 002000 000000 000000 000000 000000 000000 000000 000000                    000010 100000 010000 000100 001000 000001       V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 565 This way, a basis for 2-cocycles is given by Bt 4, for t=2rq,qodd: tBt 4= h∂2, . . . , ∂4t−2, β1, β2, γ1ifor odd t Bt 4= h∂2, . . . , ∂4t−3, β1, β2, β3, γ1, γ2, γ3ifor even t 2h∂2, . . . , ∂5,BN2⊗14,12⊗BN2⊗12,14⊗BN2,K2,K3,12⊗K1i [t]2=1h∂2, . . . , ∂4t−2,12t⊗BN2,1t⊗BN2⊗12,1t⊗K1i [t]2=0h∂2, . . . , ∂4t−3,1t⊗BN2⊗12,12t⊗BN2,1q⊗BN2r⊗14,1t 2⊗K2,1t 2⊗K3,1t⊗K1i The matrices K1,K2,K3are given by K1K2K3     1 1 1 1 1 1 1 1 1−1 1 −1 1−1 1 −1                1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 − − 1 1 − − 1 1 − − 1 1 − − 1 1 − − 1 1 − − 1 1 − − 1 1 − −                       11111111 11111111 11111111 11111111 1−1−1−1− 1−1−1−1− 1−1−1−1− 1−1−1−1−            3.1.2. Basis for Gt 5=D4t=Z2χ×Z2t B1= {u1,u2},B2= {e1,e2,e3},B3= {v1, v2, v3, v4}, d2(e1)=2·u1,d2(e2)=(2−2t)·u2,d2(e3)=2t·u2, d3(v2)=2t·e2+(2t−2)·e3,d3(v3)= −2t·e2−(2t−2)·e3, F[(g,h)] = g·u1+ [(−1)gh]2t·u2, F[(g,h)|(a,b)] = ag ·e1+ [−a(−1)gh]2t·e2+λ2t [(−1)ab]2t+[(−1)g+ah]2t·e3 +aλ1 h([(−1)g+ah]2t−1)·e3. From these data, it may be checked that D2Q2D3Q3 2 0 0 2 0 0!I2   200 000 000 000    t=2 0 0 1 0 1 0 1−2 0! t>2 001 1 1 −t0 −1t0! This way, a basis for 2-cocycles is given by Bt 5 tBt 5= h∂2, . . . , ∂4t−2, β1, β2, γ i 2h∂2, . . . , ∂6,BN2⊗12t,12t⊗BN2,K1i t>2h∂2, . . . , ∂4t−2,BN2⊗12t,12t⊗BN2,K2i The matrices K1and K2are given by K1K2           11111111 1 1 1 −1− − − 1 1 − − − 1 1 − 1− − − 1−1 1 11111111 1− − − 1−1 1 1 1 − − − 1 1 − 1 1 1 −1− − −                       1· · · 1 − BN2t . . .BN2t−1 − 1 FN2t−FN2t−1 . . . −1· · · 1             566 V. Alvarez et al. / Journal of Symbolic Computation 44 (2009) 558–570 Here FNkdenotes the forward negacyclic matrix of size k×k, FNk=    1· · · · · · 1 1− · · · − . . ........ . . 1· · · 1−    k×k . 3.1.3. Basis for Gt 7=(Zt×fZ2)×χZ2 B1= {u1,u2,u3},B2= {e1,...,e6},B3= {v1, . . . , v10}, d2(e1)=t·u1,d2(e3)=(2−t)·u1,d2(e4)=(bt 2c − 1)·u1+2·u2, d2(e5)=(1− b t 2c)·u1,d2(e6)=2·u3, d3(v2)=t·e2,d3(v3)=(t−2)·e1+t·e3,d3(v4)= −2·e2,d3(v5)=(t−2)·e2, d3(v6)=(2−t)·e1−t·e3,d3(v7)=(bt 2c − 1)·e2, d3(v8)=(bt 2c − 1)·e1+(bt 2c − 1)·e2+(bt 2c − 1)·e3+2·e5, d3(v9)=(1− b t 2c)·e1+(1− b t 2c)·e3−2·e5, F[(j,g,h)] = j·u1+g·u2+h·u3, F[(j,g,h)|(a,b,c)] = (λt [(−1)h(a+hf (b,b))]t+[j+f(g,b)]t−λt [−f(g,b)]t+[j+f(g,b)]t)·e1 +h(a−1)λ2 a·e1+λt [(−1)hhf (b,b)]t+[(−1)ha]t·e1+ [(−1)h(a+hf (b,b))]tg·e2 +ah ·e3+λ2 h+b·e4+bh ·e5+λ2 h+c·e6. From these data, the matrices Diand Qimay be described, in terms of the the coset of tmodulo 4: t D2Q2D3Q3 2        200 020 002 000 000 000           100 010 001                 200000 020000 002000 000000 000000 000000 000000 000000 000000 000000                        000010 100000 010000 000100 001000 000001         3        100 020 002 000 000 000           100 010 001                 100000 010000 002000 000000 000000 000000 000000 000000 000000 000000                        1000−3 0 0100 00 0000 10 0001 00 0010 00 0000 01         4,5        100 020 002 000 000 000           1−2 0 0 1 0 0 0 1                 100000 010000 002000 000000 000000 000000 000000 000000 000000 000000                        0 1 −1 0 −t0 1 0 0 0 0 0 0 0 1 0 t−2 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1        