On ZZt × ZZ2 2-cocyclic Hadamard matrices

On ZZt×ZZ2 2-cocyclic Hadamard matrices Víctor Álvarez, Department of Applied Mathematics 1, University of Seville, Seville, Spain e-mail: [email protected] Félix Gudiel, Department of Applied Mathematics 1, University of Seville, Seville, Spain e-mail: [email protected] Maria Belén Güemes Department of Algebra, University of Seville, Seville, Spain e-mail: b[email protected] ABSTRACT A characterization of ZZt×ZZ2 2-cocyclic Hadamard matrices is described, depending on the notions of distributions,ingredients and recipes. In particular, these notions lead to the establishment of some bounds on the number and distribution of 2-coboundaries over ZZt×ZZ2 2to use and the way in which they have to be combined in order to obtain a ZZt×ZZ2 2-cocyclic Hadamard matrix. Exhaustive searches have been performed, so that the table in p. 132 in [4] is corrected and completed. Furthermore, we identify four different operations on the set of coboundaries defining ZZt×ZZ2 2-cocyclic matrices, which preserve orthogonality. We split the set of Hadamard matrices into disjoint orbits, define representatives for them and take advantage of this fact to compute them in an easier way than the usual purely exhaustive way, in terms of diagrams. Let Hbe the set of cocyclic Hadamard matrices over ZZt×ZZ2 2having a symmetric diagram. We also prove that the set of Williamson type matrices is a subset of Hof size |H| t. 1 2ALVAREZ, GUDIEL AND GUEMES 1. INTRODUCTION Hadamard matrices are n×nsquare matrices Hwith entries in {1,−1}such that every pair of rows (respectively, columns) are orthogonal, that is, HHT=nIn. Due to this nice combinatorial property, Hadamard matrices have many applications in a wide variety of fields, such as Signal Processing, Coding Theory and Cryptography (see [6] for details). Consequently, there is a real interest in knowing enough Hadamard matrices for practical use. It is a straightforward exercise to prove that the order of a Hadamard matrix has to be 1, 2 or a multiple of 4 (as soon as three or more rows have to be simultaneously orthogonal one to each other). Unfortunately, the Hadamard Conjecture about the existence of these matrices for every order 4tremains unproved since the XIXth Century. Nowadays, there are three orders less than 1000 for which no Hadamard matrix is known: 668 = 4 ·167,716 = 4 ·179, and 892 = 4 ·223. Furthermore, there are 9 orders in the range [1000,2000] for which no Hadamard matrix is known (see [6, 5] for details). One of the most promising techniques for constructing Hadamard matrices is the cocyclic approach (see [7, 8, 6]). A cocyclic matrix Mfover a group Gis a matrix Mf= (f(g, h)), for fa2-cocycle over G, that is, a function f:G×G→ {1,−1} such that for every a, b, c ∈G,f(a, b)·f(ab, c)·f(a, bc)·f(b, c) = 1. Actually, many well known families of Hadamard matrices, such as Sylvester’s, Paley’s, Williamson’s and Ito’s, have shown to be cocyclic over appropriate groups (see [6] for details). This has provided inspiration for the Cocyclic Hadamard Conjecture, which states that cocyclic Hadamard matrices exist for every order 4t. In this paper we are interested in characterizing cocyclic Hadamard matrices over ZZt×ZZ2 2, which include the family of symmetric Williamson type Hadamard matrices. Following the indications of [1], we will describe bounds on the number of 2- coboundaries over ZZt×ZZ2 2to be combined, as well as their distribution (in terms of what we call ingredients and recipes), in order to construct a ZZt×ZZ2 2-cocyclic Hadamard matrix. This information will allow us to design an exhaustive search for ZZt×ZZ2 2-cocyclic Hadamard matrices for 3≤t≤13, so that the table in p. 132 in [4] is corrected and completed. Next, we will introduce what we call diagrams, a visual representation of the coboundaries which define a ZZt×ZZ2 2-cocyclic matrix and we will study four different operations on the set of coboundary matrices over ZZt×ZZ2 2: complements, rotations, swappings and dilatations. In particular, these operations extend to operations over ZZt×ZZ2 2-cocyclic matrices, which will be proved to preserve orthogonality. These operations partition the set of ZZt×ZZ2 2-cocyclic matrices into disjoint orbits, which can be easily computed once one element is known. Among all the elements of an orbit, a representative can be chosen, in a standard way that will be made precise. Finally, by applying these ideas to the task of searching for cocyclic Hadamard matrices over ZZt×ZZ2 2, we have been able to extend the table in p. 132 in [4] for values of tin the range 3≤t≤23, and to explain the fact that the set of symmetric Williamson type Hadamard matrices obtained from symmetric diagrams is in proportion 1 twith respect to the full set of ZZt×ZZ2 2-cocyclic Hadamard matrices. ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 3 We organize the paper as follows. Section 2 is dedicated to describe all about ZZt×ZZ2 2-cocyclic Hadamard matrices. In Section 3 we introduce the notions of distribution,ingredients and recipes, in terms of which we find some upper and lower bounds on the number of 2-coboundaries over ZZt×ZZ2 2which have to be combined in order to get ZZt×ZZ2 2-cocyclic Hadamard matrices, as well as the way in which they have to be distributed, and the results obtained. Section 4 is dedicated to the description of diagrams, after a discussion about the convenience of using the whole set of coboundaries instead of the basis, in order to represent ZZt×ZZ2 2-cocyclic matrices. Section 5 defines four operations on ZZt×ZZ2 2-cocyclic matrices which preserve orthogonality, and which have a nice interpretation in terms of diagrams. These operations split the set of ZZt×ZZ2 2-cocyclic Hadamard matrices into disjoint orbits, which can be generated from any of their elements (for instance by its representative). In Section 6 we focus on the case of ZZt×ZZ2 2- cocyclic Hadamard matrices obtained from symmetric diagrams, which in turn permit counting the number of Williamson type Hadamard matrices. We also include some final remarks and further work. 2. ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES Consider the group G=ZZt×ZZ2 2, a basis B={∂2,...,∂4t−2, β1, β2, γ}for 2-cocycles over Gis described in [2], and consists of 4t−3coboundaries ∂k, two cocycles βi coming from inflation and one cocycle γcoming from transgression. It has been observed that cocyclic Hadamard matrices over ZZt×ZZ2 2mostly use all the three representative cocycles β1, β2and γsimultaneously (see [4] for details). We will assume that every cocyclic matrix Mis obtained as a product M=M∂i1...M∂iw·R, for 2≤i1< . . . < iw≤4t−2, where R=Mβ1·Mβ2·Mγ. Here M∂irefers to the generalized coboundary matrix associated to the ithelement in G, with the ith-row and the ith-column negated, as introduced in [2]. In particular, there are three coboundary matrices which are not in B:M∂1, M∂4t−1and M∂4t. Consequently, every ZZt×ZZ2 2-cocyclic matrix Mfusing Rmay be expressed as a pointwise product of matrices in {M∂1,...,M∂4t}in 8 different ways, just one of which does not use any of M∂1,M∂4t−1and M∂4t(and gives precisely the expression of Mfas a linear combination of elements in B). Actually, suppose that Mf=R· 4 Y k=1 Y ij∈Jk M∂ij, where Jk⊂ {1,...,4t}is a subset of indexes which are congruent to kmodulo 4. Then Mfmay be expressed as the pointwise product of the coboundary matrices of indexes belonging to any of the following 8 subsets: (J1, J2, J3, J4),(¯ J1,¯ J2, J3, J4),(J1,¯ J2,¯ J3, J4),(J1,¯ J2, J3,¯ J4),(¯ J1, J2,¯ J3, J4), (¯ J1, J2, J3,¯ J4),(J1, J2,¯ J3,¯ J4),(¯ J1,¯ J2,¯ J3,¯ J4), where ¯ Jk={k+4i: 0 ≤i≤t−1}\Jk denotes the complementary subset of Jk. It is known that a cocyclic matrix is Hadamard if and only if the summation of each row but the first is zero (this is the cocyclic Hadamard test, see [8, 4] for instance). Furthermore, as proved in [1], a ZZt×ZZ2 2-cocyclic matrix is Hadamard if and only if the summation of each of the rows from 5 to 2t+2 is 0, and an equivalent characterization of the cocyclic Hadamard test may be described in terms of n-paths (cn) and n-intersections (In) (the interested reader is referred to [1] for a precise 4ALVAREZ, GUDIEL AND GUEMES definition about paths and intersections). In particular, the following result derives straightforwardly from the work in [1]. Proposition 2.1. For ZZt×ZZ2 2-cocyclic matrices: 1. the summation of a row n≡1mod 4is zero if and only if cn=t, (1) 2. the summation of a row n≡0,2,3mod 4is zero if and only if cn=In.(2) In the following section we analyze the number cnof n-paths of a ZZt×ZZ2 2-cocyclic matrix. Focusing in rows n≡1mod 4, we will obtain upper and lower bounds on the number of coboundaries to combine in order to get a ZZt×ZZ2 2-cocyclic Hadamard matrix. Furthermore, we will characterize the distribution of these coboundaries in terms of ingredients and recipes. 3. DISTRIBUTIONS, INGREDIENTS AND RECIPES Firstly, we analyze the way in which n-paths are generated on ZZt×ZZ2 2-cocyclic matrices, depending on the value of nmodulo 4. Lemma 3.1. Characterization of n-paths of coboundaries on ZZt×ZZ2 2-cocyclic matrices: 1. If n≡1mod 4,M∂i−n+1 forms an n-path with M∂i. 2. If n≡2mod 4,M∂i−n+2−(−1)iforms an n-path with M∂i. 3. If n≡3mod 4,M∂ i−n+3−2(−1)⌈i mod 4 2⌉forms an n-path with M∂i. 4. If n≡0mod 4,M∂i−n+4+(−1)i(1−4(1−⌊ i mod 4 2⌋)) forms an n-path with M∂i. Proof. This may be checked by direct inspection. Now we focus our attention on rows n≡1mod 4. From Lemma 3.1, it is clear that n-paths consists of groups of coboundaries in the same coset modulo 4. Lemma 3.2. Given 1≤i6=j≤4t,i≡j mod 4, there exists one and only one row n,5≤n≤2t+ 2,n≡1mod 4, such that M∂iand M∂jform an n-path. Corollary 3.3. Along the t−1 2rows n≡1mod 4,5≤n≤2t+2, any kcoboundaries ∂i1,...,∂ikin the same coset modulo 4 give rise to a total amount of k(t−k) 2 paths. Proof. ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 5 Along the t−1 2rows n≡1mod 4,5≤n≤2t+2, any kcoboundaries ∂i1,...,∂ik in the same coset modulo 4 might give rise to kt−1 2paths. Actually, this is not the case, since we know from Lemma 3.2 that every pair of such coboundaries forms a path at one and only one of these rows n. Thus the total amount of paths has to be reduced in the number of pairs in which the kcoboundaries may be grouped. This gives kt−1 2−k(k−1) 2=kt−k 2, as claimed. Example: For t= 5, the set of k= 2 coboundaries {∂14, ∂18}defines exactly 25−2 2= 3 paths in rows congruent to 1, namely, 1path at row 5,{(∂18, ∂14)}and 2paths at row 9,{(∂14),(∂18)}. Table A in Appendix [3], shows the total amount k(t−k) 2of paths produced by k coboundaries in the same coset modulo 4, for odd values of t. Proposition 3.4. This table has many valuable combinatorial properties: 1. The table is symmetric. 2. The numbers in the central columns are triangular numbers, of the type n(n+1) 2. 3. Subtracting from a number in the central columns any of the numbers of the same row, gives as result a triangular number as well. 4. Reciprocally, subtracting from a number in the central columns any triangular number gives as result a number of the same row. Proof. 1. The table is symmetric, since kcoboundaries give rise to k(t−k) 2paths, exactly the same amount of paths produced by t−kcoboundaries, (t−k)k 2. 2. The numbers in the central columns are triangular numbers. Actually, t−1 2 coboundaries give rise to n(n+1) 2paths, where t= 2n+ 1. 3. Subtracting from a number in the central columns any of the numbers of the same row, gives as result a triangular number as well. Indeed, subtracting k(t−k) 2paths from t2−1 8gives t2−1−4kt+4k2 8=(t−2k)2−1 8= t−2k−1 2·t−2k+1 2 2. 4. The argument above fits here as well. Attending to the condition (1), in order to get a ZZt×ZZ2 2-cocyclic Hadamard matrix, a necessary (but not sufficient!) condition is to select kicoboundaries in the coset i mod 4, such that there is a total amount of tt−1 2paths along the t−1 2 rows n≡1mod 4,5≤n≤2t+ 2. This motivates the following definition. Definition 3.5. Adistribution is a tuple (k0(t−k0) 2,k1(t−k1) 2,k2(t−k2) 2,k3(t−k3) 2), 0≤kj≤ki≤t−1 2for j≥i, such that 3 X i=0 ki(t−ki) 2=t(t−1) 2.(3) 6ALVAREZ, GUDIEL AND GUEMES Proposition 3.6. For any odd t, there always exists at least one distribution (k0(t−k0) 2,k1(t−k1) 2,k2(t−k2) 2,k3(t−k3) 2). Furthermore, there are as many different distributions as decompositions of t−1 2as the summation of four triangular numbers. Proof. The maximum possible number of paths is 4t2−1 8=t2−1 2, when ki=t−1 2,∀i, so that the relation (3) fails to hold by a difference m=t2−1 2−t(t−1) 2. In 1796 Gauss proved that any positive integer can be decomposed as the summation of three (not necessarily different) triangular numbers, some of which may be eventually zero. Consequently, there exist three triangular numbers 0≤t1, t2, t3≤ t2−1 8such that m=t1+t2+t3. Thus t2−1 2= 4t2−1 8−m=t2−1 8+ (t2−1 8−t1) + (t2−1 8−t2) + (t2−1 8−t3). Taking into account Proposition 3.4, there exist integers 0≤k3≤k2≤k1≤t−1 2such that (t2−1 8−ti) = ki(t−ki) 2, and therefore (t2−1 8,k1(t−k1) 2,k2(t−k2) 2,k3(t−k3) 2)is a distribution, in the sense of Definition 3.5. The second part is a straightforward consequence. This proposition provides a method for finding the set of distributions for a given t, in terms of decompositions of t−1 2as the summation of four triangular numbers 0≤t0≤t1≤t2≤t3≤t2−1 8. Proposition 3.7. Let kbe a positive integer. Then: 1. kis a triangular number if and only if −1+√1+8k 2is an integer. 2. The greatest triangular number less or equal to kis tn, for n=⌊−1+√1+8k 2⌋. 3. If kis decomposed as the summation of mtriangular numbers tij,1≤j≤m, then max j{tij} ≥ tn, for n=⌈−1+√1+8 k m 2⌉. Proof. It suffices to notice that kis a triangular number if and only if there exists an integer nsuch that tn=nn+1 2=k. Equivalently, if and only if the equation n2 2+n 2−khas a positive integer solution (which, a fortiori, is −1+√1+8k 2). Proposition 3.7 leads straightforwardly to an algorithm for constructing the full set of distributions for a given t(see Algorithm 1 in Appendix [3]). Table B in Appendix [3], shows the complete set of distributions obtained from Algorithm 1, for 3≤t≤25. Notice that the knowledge of the full set of distributions implies the knowledge about the number of coboundaries which have to be used in order to get a ZZt×ZZ2 2-cocyclic Hadamard matrix, since each summand ki(t−ki) 2is in one to one correspondence to the values kiand t−ki(see Table A). In spite of this fact, we may bound the number of coboundaries to be combined a bit further. ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 7 Lemma 3.8. For any decomposition of ninto ksummands, say n=n1+...+nk We have Pk i=1 n2 i≥1 kPk i=1 ni2. In fact, one could check that k X i=1 n2 i−1 k k X i=1 ni!2 =1 kX 1≤j<i≤k (ni−nj)2≥0.(4) Proposition 3.9. Let (k0(t−k0) 2,k1(t−k1) 2,k2(t−k2) 2,k3(t−k3) 2)be a distribution. Call n=k0+k1+k2+k3. Then 1. ⌈t−√4t−3 2⌉ ≤ k3≤ ⌊t+√4t−3 2⌋.(5) 2. ⌈2(t−√t)⌉ ≤ n≤ ⌊2(t+√t)⌋.(6) Proof. Let (k0, k1, k2, k3)generate a distribution (k0(t−k0) 2,k1(t−k1) 2,k2(t−k2) 2,k3(t−k3) 2). On one hand, condition (3), gives 4k2 3−4k3t+t2−4t+ 3 ≤0which proves (5). On the other hand, simplifying (3), we get t 3 X i=0 ki−t2+t= 3 X i=0 k2 i.Now, by Lemma 3.8 3 X i=0 k2 i≥ 3 X i=0 (n 4)2,(7) and so tn −t2+t≥n2 4, obtaining (6). Remark 1. Condition (6) may be tightened, depending on the coset of n= k0+k1+k2+k3modulo 4, substituting the lower bound in (7) by the most homogeneously distributed partition of ninto four parts. Remark 2. The bounds in Proposition 3.9 are very tight, as has been checked experimentally. The first gap occurs for t= 71, and consists in just one coboundary. Once we know that a distribution is available for a given value of t, the next step is looking for appropriate subsets of nicoboundaries in the cosets i mod 4in Bsuch that the amount of n-paths along rows n≡1mod 4,5≤n≤2t−1fits that distribution. Example: For t= 5, the distribution (3,3,2,2) corresponds to a repartition of (2,2,1,1) coboundaries in each of the cosets modulo 4 (although we can consider 3instead of 2and 4instead of 1coboundaries in each case). Now, for each subset of kicoboundaries, we can compute the number of n-paths defined along the rows congruent to 1(this can be computed in only one coset, they are disjoint). 8ALVAREZ, GUDIEL AND GUEMES Definition 3.10. An ingredient produced by a subset of kcoboundaries in Bin the same coset modulo 4 is the column vector whose entries are the number of npaths produced by these kcoboundaries along rows n≡1mod 4,5≤n≤2t−1. Arecipe is a collection of 4 ingredients (one for each different coset imodulo 4), arranged as a matrix of 4 columns, such that the sum of each of the rows is t. Example: For t= 5, the set of k= 2 coboundaries {∂14, ∂18}(and also any set {∂14+i, ∂18+i}mod 4tfor any i) define the ingredient [1,2]t. One recipe for t= 5, will be 1 2,2 1,1 1,1 1. Consequently, if a subset of {n1, n2, n3, n4}coboundaries in Bdefines a recipe, this subset of coboundaries satisfies the condition (1), and therefore the summation of each of the rows n≡1mod 4,5≤n≤2t−1is zero. Proposition 3.11. The notion of recipe does not depend on the order of its ingredients. Proof. Attending to Lemma 3.1, ∂iforms an n-path with ∂i−n+1, independently on the coset i mod 4, for n≡1mod 4,5≤n≤2t−1. In particular, n-paths are constructed from those coboundaries in Bin the same coset mod 4, which differ in n−1 4positions in the 5-cycles. This way, if a subset of coboundaries of the coset i mod 4produces an ingredient, the same is produced by the translation of this subset to any other coset mod 4. Eventually, this translation could produce a coboundary ∂iwhich is not in B. This is not a source of difficulties, since such prohibited subsets of coboundaries may be substituted by their complements in the 5-cycles. Since the substitution of any amount of paths by their complementary in a cycle does not change the total amount of paths, this operation preserves the ingredient. Finding a recipe is the first step in the process of constructing a ZZt×ZZ2 2-cocyclic Hadamard matrix, since any subset of coboundaries in Bdefining a recipe satisfies condition (1) and conversely. Turning our attention to rows not congruent to 1, where the number of paths must be equal to the number of intersections in order to fullfill the Hadamard test, the following proposition gives a condition about when the relation (2) is also satisfied (and hence a ZZt×ZZ2 2-cocyclic Hadamard matrix has been found). Proposition 3.12. A subset of coboundaries in Bsatisfies condition (2) (i.e. the summation of the nth-row is zero, for n≡0,2,3mod 4,6≤n≤2t+ 2), if and only if the number of n-paths of even length is itself even, half of them starting and ending with coboundaries in cosets i1, i2mod 4, the other half starting and ending in coboundaries in cosets i3, i4mod 4,ij6=ikfor j6=k. Proof. ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 9 As we commented in Section 2., we are using R= 1t⊗    1111 1−1 1 −1 1−1−1 1 1 1 −1−1     as the matrix coming from representative cocycles. Consequently, intersections in rows n≡2mod 4can occur in positions (n, i), for i≡2,0mod 4. Similarly, intersections in rows n≡3mod 4can occur in positions (n, i), for i≡2,3mod 4. Finally, intersections in rows n≡0mod 4can occur in positions (n, i), for i≡3,0mod 4. Taking into account Lemma 3.1, it follows that n-paths consists in properly alternating coboundaries in: •Either cosets (1,2) mod 4, either cosets (3,0) mod 4, for n≡2mod 4. •Either cosets (2,0) mod 4, either cosets (1,3) mod 4, for n≡3mod 4. •Either cosets (2,3) mod 4, either cosets (1,0) mod 4, for n≡0mod 4. Hence any n-path of odd length produces exactly one intersection (i.e. shares exactly one negative entry) with Rat the nth-row. On the other hand, n-paths of even length produces either 2 or 0 intersections, depending on the cosets modulo 4 of nand the initial coboundary of the n-path. More precisely: •If n≡2mod 4, then an n-path of even length will produce two intersections at the nth-row if and only if the coset iof the initial coboundary is i≡2,0mod 4. •If n≡3mod 4, then an n-path of even length will produce two intersections at the nth-row if and only if the coset iof the initial coboundary is i≡2,3mod 4. •If n≡0mod 4, then an n-path of even length will produce two intersections at the nth-row if and only if the coset iof the initial coboundary is i≡3,0mod 4. Summing up, each n-path of odd length produces 1 intersection, and each n-path of even length produces either 2 or 0 intersections. Hence, the only circumstance in which the amounts of intersections and n-paths both coincide is precisely when half the n-paths of even length give rise to 2 intersections, whereas the remaining half of n-paths of even length do not produce any intersections at all. Example: For t= 5, the set {{∂14, ∂18},{∂3, ∂11},{∂8},{∂5}}, of 6 = 2 + 2 + 1 + 1coboundaries corresponding to the recipe showed after Definition 3.10 defines a Hadamard matrix, because paths of even length at rows congruent to 2,3,0 are balanced. On the other hand, the set {{∂10, ∂14},{∂3, ∂11},{∂8},{∂5}} (which corresponds to the same recipe) does not define a Hadamard matrix, because it fails the Hadamard test at row 8, being its 8-paths (∂14, ∂11),(∂10),(∂3),(∂5),(∂8), there is only one path of even length, so the number of intersections at row 8can not be equal to the number of 8-paths. Now it is straightforward to design an algorithm (see algorithm 2 in Appendix [3]), searching exhaustively for ZZt×ZZ2 2-cocyclic Hadamard matrices for odd t. Table I shows an exhaustive calculation of ZZt×ZZ2 2-cocyclic Hadamard matrices (last column) for odd t,3≤t≤13, in terms of distributions (second column), number of different ingredients produced by the coboundaries needed (third column) and recipes found (fourth column). The fifth column shows how many of the recipes are “productive", in the sense that they actually give rise to ZZt×ZZ2 2-cocyclic Hadamard matrices. 16 ALVAREZ, GUDIEL AND GUEMES 6. THE SYMMETRIC CASE We have computed the full set of Zt×Z2 2-cocyclic Hadamard matrices for t≤13. There are two special repartitions of coboundaries attending to their congruency, for every Hadamard matrix. One is the repartition given by the expression of the matrix with respect to the basis. And the other is the minimal repartition (this last one can correspond to the matrix, or to its complement). When performing calculations we can restrict to the minimal repartition, in order to simplify the search, avoiding 15 of the 16 possible repartitions for each distribution. The rotation, swapping and dilatations preserve the number of coboundaries involved. On the other hand, the image of the Hadamard matrix does not depend on the chosen representation (from the possible eight). Thus we can obtain the whole orbit of the matrix under all these operations by only knowing the expression of the matrix with the minimal repartition, so we can restrict the searching to this easier case. Once this is done, we can compute the complement of each of the obtained matrices, to complete the orbit under all operations. 6.1 The symmetric-diagram case (t∈[15,23]) The diagrams of all the matrices obtained for t≤13 were symmetric (symmetry is a sufficient condition to pass the Hadamard test in rows congruent to 2,3,0module 4, so, assuming symmetry, the Hadamard test reduces to check if the number of paths in rows congruent to 1is exactly t). By following this idea, we have computed the set of cocyclic Hadamard matrices over ZZt×ZZ2 2, having a symmetric diagram for 15 ≤t≤23, which are listed in Tables D and E in Appendix [3], in terms of their representatives and the size of their total orbit under complement/rotation/swapping/dilatations, when providing new matrices. 6.2 Williamson type matrices The first row of Table II shows the number of Williamson type matrices obtained in [4], together with the total number of cocyclic Hadamard matrices over ZZt×ZZ2 2 which we have computed. t3 5 7 9 11 13 15 17 19 21 23 ♯W ill. 8 24 120 264 240 648 576 − − − − ♯H. 24 120 840 2376 2640 8424 8640 13056 34200 31248 12144 TABLE II. Williamson type / ZZt×ZZ2 2-cocyclic Hadamard matrices (only for symmetric diagrams if t≥15) It can be observed that the set of Williamson type Hadamard matrices seems to be in proportion 1 twith respect to the set of ZZt×ZZ2 2-cocyclic Hadamard matrices consisting of symmetric diagrams. We now prove the validity of this fact. ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 17 By Lemma 3.4 in [4], any Williamson type matrix is Hadamard equivalent to a cocyclic matrix over ZZt×ZZ2 2, which is t×tback-circulant by blocks 4×4,     W1... ... Wt W2···WtW1 ············ WtW1. . . Wt−1     , Wi=    nixiyizi xi−nizi−yi yi−zi−nixi ziyi−xi−ni     ,(9) with Wi+1 =Wt−i+1 for 1≤i≤t−1. This matrix (9) is a pointwise product of the representative matrix Rand a certain set of generalized coboundaries {M∂d1,...,M∂dk}. The additional condition Wi+1 =Wt−i+1 for 1≤i≤t−1, leaving W1alone means that the symmetry column in the diagram representing the matrix (9) is, precisely, the last one to the right, which is associated to the coboundaries ∂2, ∂3, ∂4, ∂1. This fact leads us to conclude that: Proposition 6.1. Let Hthe set of cocyclic Hadamard matrices over ZZt×ZZ2 2, having a symmetric diagram. Then, the set of Williamson type matrices of type (9) is a subset of Hof size |H| t. Moreover, for each element H∈ H, one and only one of the rotated matrices TiH,1≤i≤t, is a Williamson type matrix. Proof. The condition needed tells us that the diagram has to be symmetric with respect to the last column, which is only possible for one of the rotated. So, the predicted number of Williamson type matrices for t∈[17,23] will be 13056/17 = 768,34200/19 = 1800,31248/21 = 1488 and 12144/23 = 528. 6.3 More Hadamard matrices (t∈[25,63]) Moreover, the result about Williamson type matrices allows us to go beyond t= 23. Actually, we have identified every Williamson type matrix exhibited in the Koukouvinos website [9] (which corresponds to a certain decomposition of 4tas a sum of squares) as a pointwise product of coboundaries and computed the whole orbit of matrices for t∈[25,39]. We show the results obtained in Table F in Appendix [3], and give the size of its orbit under the action of complement/rotation/swapping/dilatations, when providing new matrices. The Koukouvinos website [9] only gives an example of each equivalence class of Williamson type Hadamard matrices for small orders, and not the total number of these matrices. However we have checked that the numbers of Williamson type Hadamard matrices we predict by using our computation of symmetric-diagram cocyclic Hadamard matrices and dividing by t, for t∈[17,23], is the same as if we take the examples in [9] in each order and compute the sum of their orbit sizes under our operations. We conjecture that one can obtain the total number of Williamson type Hadamard matrices for t∈[25,63] from [9] by just computing the sum of the orbit sizes for each order. That is to say, we conjecture that any Williamson type matrix H′ 18 ALVAREZ, GUDIEL AND GUEMES Hadamard equivalent to a given Williamson type matrix His in the orbit of H under our operations. Finally we show the total number of Hadamard matrices that we have computed so far t3 5 7 9 11 13 15 17 19 21 23 ♯H. 24 120 840 2376 2640 8424 8640 13056 34200 31248 12144 t25 27 29 31 33 35 37 39 41 43 45 ♯H. 75000 64152 19488 33480 79200 −53280 7488 4920 14448 12960 t47 49 51 53 55 57 59 61 63 ♯H. −24696 58752 −26400 24624 −21960 9072 TABLE III. ZZt×ZZ2 2-cocyclic Hadamard matrices computed 6.4 Further questions After an observation process, some questions come into our minds: •All ZZt×ZZ2 2-cocyclic Hadamard matrices obtained so far have a symmetric diagram up to t= 13, and we have taken advantage of it when computing them for t∈[15,23] by restricting ourselves to the symmetric case. Can this symmetry assumption be proved? Does a ZZt×ZZ2 2-cocyclic Hadamard matrix exist coming from a non symmetric diagram? •In case that the answer to the second question above is affirmative, then it would be interesting to look for ZZt×ZZ2 2-cocyclic Hadamard matrices in those orders for which no Williamson type Hadamard matrix is known to exist, such as t= 35 [9]. •Now that we have proved that our operations preserve orthogonality, arises the question: do these operations preserve Hadamard equivalence classes? Rotations, dilatations and some of the swappings do, because they can be expressed in terms of the bundle operation defined by Horadam in [6] (this fact will be detailed elsewhere). In addition, for values of tbelow 23, the number of orbits coincide with the number of non equivalent Williamson type matrices computed in [9], so the result is probably true in general. ACKNOWLEDGMENTS The authors want to express their gratitude to the anonymous referees for their comments and suggestions, which have permitted to improve the readability and understandability of the paper. All authors are partially supported by the research project FQM-016 from JJAA (Spain). ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 19 REFERENCES [1] V. Álvarez, J.A. Armario, M.D. Frau and P. Real, "A system of equations for describing cocyclic Hadamard matrices", J. Comb. Des., vol. 16, pp. 276–290, 2008. [2] V. Álvarez, J.A. Armario, M.D. Frau and P. Real, "The homological reduction method for computing cocyclic Hadamard matrices", J. Symb. Comput., vol. 44, pp. 558-570, 2009. [3] V. Álvarez, F. Gudiel and M.B. Güemes, Appendix to "On ZZt×ZZ2 2-cocyclic Hadamard matrices". Available online at http://grupo.us.es/codico/appendix-on- abelian-cocyclic-hadamard-matrices.pdf [4] A. Baliga and K.J. Horadam, "Cocyclic Hadamard matrices over ZZt×ZZ2 2,Australas. J. Combin., vol. 11, pp. 123–134, 1995. [5] D.Ž. Ðokovic, O. Golubitsky, I.S. Kotsireas. "Some new orders of Hadamard and Skew-Hadamard matrices", J. Comb. Des. DOI 10.1002/jcd.21358. [6] K.J. Horadam, Hadamard matrices and their applications. Princeton: Princeton University Press, 2007. [7] K.J. Horadam and W. de Launey, "Cocyclic development of designs", J. Algebraic Combin., vol. 2, no. 3, pp. 267–290, 1993. Erratum, J. Algebraic Combin., vol. 3, pp. 129, 1994. [8] K.J. Horadam and W. de Launey, "Generation of cocyclic Hadamard matrices", in: Proc. Computational Algebra and Number Theory, Sydney, 1992, in Math. Appl., vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 279–290. [9] C. Koukouvinos, web page, http://www.math.ntua.gr/∼ckoukouv/ 20 ALVAREZ, GUDIEL AND GUEMES APPENDIX: TABLES AND ALGORITHMS Algorithm 1: Constructing the set of distributions for t. Input: t k={ } for i1from ⌈−1+√t 2⌉to ⌊−1+√4t−3 2⌋do for i2from ⌈−1+p1+4 t−1−i1(i1+1) 3 2⌉to min(i1,⌊−1+√1+4(t−1−i1(i1+1)) 2⌋)do for i3from ⌈−1+√1+2(t−1−i1(i1+1)−i2(i2+1)) 2⌉ to min(i2,⌊−1+√1+4(t−1−i1(i1+1)−i2(i2+1)) 2⌋) do x=−1+√1+4(t−1−i1(i1+1)−i2(i2+1)−i3(i3+1)) 2 if xis an integer, then k=k∪{(x, i3, i2, i1)}fi od od od l={ } for ifrom 1 to length(k)do l=l∪{(t2−1 8−ki,1,t2−1 8−ki,2,t2−1 8−ki,3,t2−1 8−ki,4)} od Output: l ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 21 Algorithm 2: Exhaustive search for ZZt×ZZ2 2-Hadamard matrices. Input: t. Calculate the valid distributions for t. Calculate all the ingredients associated to every distribution. Construct the set of recipes corresponding to each distribution. Determine those subsets of coboundaries defining a recipe. Check whether these subsets satisfy the balanced distribution of even n-paths for n≡ 2,3,0mod 4,6≤n≤2t+ 2. Output: the full set of ZZt×ZZ2 2-Hadamard matrices. Table A shows the total amount k(t−k) 2of paths produced by kcoboundaries in the same coset modulo 4, for odd values of t. t\k1... t−1 2 t+1 2. . . 1 3 1 1 5 2 3 3 2 7 3 5 6 6 5 3 9 4 7 9 10 10 9 7 4 11 5 9 12 14 15 15 14 12 9 5 13 6 11 15 18 20 21 21 20 18 15 11 6 . . .. . .. . .. . . TABLE A. Paths produced from kcoboundaries in rows n≡1mod 4. 22 ALVAREZ, GUDIEL AND GUEMES Table B shows the complete set of distributions obtained from Algorithm 1, for 3≤t≤25. tt(t−1) 2distributions t0+t1+t2+t3=t−1 2 3 3 (1,1,1,0) 0 + 0 + 0 + 1 = 1 5 10 (3,3,2,2) 0 + 0 + 1 + 1 = 2 7 21 (6,6,6,3) (6,5,5,5) 0 + 0 + 0 + 3 = 3 0 + 1 + 1 + 1 = 3 9 36 (10,10,9,7) (9,9,9,9) 0 + 0 + 1 + 3 = 4 1 + 1 + 1 + 1 = 4 11 55 (15,14,14,12) 0 + 1 + 1 + 3 = 5 13 78 (21,21,21,15) (21,21,18,18) (20,20,20,18) 0 + 0 + 0 + 6 = 6 0 + 0 + 3 + 3 = 6 1 + 1 + 1 + 3 = 6 15 105 (28,28,27,22) (28,27,25,25) 0 + 0 + 1 + 6 = 7 0 + 1 + 3 + 3 = 7 17 136 (36,35,35,30) (35,35,33,33) 0 + 1 + 1 + 6 = 8 1 + 1 + 3 + 3 = 8 19 171 (45,45,42,39) (45,42,42,42) (44,44,44,39) 0 + 0 + 3 + 6 = 9 0 + 3 + 3 + 3 = 9 1 + 1 + 1 + 6 = 9 21 210 (55,55,55,45) (55,54,52,49) (54,52,52,52) 0 + 0 + 0 + 10 = 10 0 + 1 + 3 + 6 = 10 1 + 3 + 3 + 3 = 10 23 253 (66,66,65,56) (65,65,63,60) 0 + 0 + 1 + 10 = 11 1 + 1 + 3 + 6 = 11 25 300 (78,78,72,72) (78,77,77,68) (78,75,75,73) (75,75,75,75) 0 + 0 + 6 + 6 = 12 0 + 1 + 1 + 10 = 12 0 + 3 + 3 + 6 = 12 3 + 3 + 3 + 3 = 12 TABLE B. Distributions in terms of decompositions of t−1 2=t0+t1+t2+t3. ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 23 t orbit representative 3 2 ×3×4×1 = 24 {{},{7},{8},{5}} 5 2 ×5×12 ×1 = 120 {{10},{11},{8,16},{1,17}} 7 2 ×7×24 ×1 = 336 {{14},{11,15,19},{8,16,24},{1,13,25}} 2×7×12 ×3 = 504 {{10,18},{11,19},{4,28},{1,13,25}} 9 2 ×9×12 ×3 = 648 {{14,22},{15,19,23},{4,16,24,36},{1,13,21,33}} 2×9×24 ×3 = 1296 {{14,22},{3,19,35},{12,16,24,28},{1,9,25,33}} 2×9×24 ×1 = 432 {{14,18,22},{11,19,27},{8,20,32},{1,17,33}} 11 2 ×11× {{18,22,26},{7,15,31,39}, 24 ×5 = 2640 {4,16,32,44},{9,13,21,29,33}} 13 2 ×13× {{22,26,30},{3,15,23,31,39,51}, 24 ×3 = 3744 {8,16,20,36,40,48},{1,5,17,33,45,49}} 2×13× {{18,22,30,34},{7,15,39,47}, 24 ×3 = 1872 {8,12,24,32,44,48},{1,5,21,29,45,49}} 2×13× {{14,18,34,38},{15,23,27,31,39}, 24 ×3 = 1872 {8,24,28,32,48},{5,17,25,33,45}} 2×13× {{14,18,34,38},{15,19,27,35,39}, 12 ×3 = 936 {4,12,28,44,52},{1,9,25,41,49}} TABLE C. Orbits of ZZt×ZZ2 2-cocyclic Hadamard matrices 24 ALVAREZ, GUDIEL AND GUEMES t/orbit/#H. representative 15 2 ×15 ×24 ×4 2880 {{18,22,38,42},{7,19,27,35,43,55}, {16,20,28,32,36,44,48},{1,9,25,29,33,49,57}} 15 2 ×15 ×24 ×4 2880 {{10,14,46,50},{7,19,27,35,43,55}, {8,12,24,32,40,52,56},{1,5,9,29,49,53,57}} 15 2 ×15 ×24 ×2 1440 {{14,26,34,46},{11,15,27,35,47,51}, {16,20,28,32,36,44,48},{1,5,21,29,37,53,57}} 15 2 ×15 ×12 ×4 1440 {{14,26,30,34,46},{15,27,31,35,47}, {12,16,24,40,48,52},{9,13,21,29,37,45,49}} 17 2 ×17 ×24 ×4 3264 {{18,30,34,38,50},{3,23,31,35,39,47,67}, {16,20,28,36,44,52,56},{1,13,21,25,41,45,53,65}} 17 2 ×17 ×24 ×4 3264 {{18,30,34,38,50},{3,23,27,35,43,47,67}, {4,16,28,36,44,56,68},{13,17,21,29,37,45,49,53}} 17 2 ×17 ×24 ×4 3264 {{18,30,34,38,50},{7,15,31,35,39,55,63}, {12,20,24,36,48,52,60},{5,9,13,21,45,53,57,61}} 17 2 ×17 ×24 ×4 3264 {{18,26,30,38,42,50},{3,19,31,39,51,67}, {8,24,32,36,40,48,64},{9,13,17,33,49,53,57}} 19 2 ×19 ×24 ×9 8208 {{18,30,34,42,46,58},{15,19,23,39,55,59,63}, {8,16,28,36,40,44,52,64,72},{5,21,25,29,37,45,49,53,69}} 19 2 ×19 ×12 ×9 4104 {{10,30,34,42,46,66},{11,31,35,39,43,47,67}, {4,12,16,32,40,48,64,68,76},{1,9,13,29,37,45,61,65,73}} 19 2 ×19 ×24 ×9 8208 {{10,30,34,42,46,66},{15,27,35,39,43,51,63}, {8,16,32,36,40,44,48,64,72},{5,9,25,33,37,41,49,65,69}} 19 2 ×19 ×24 ×3 2376 {{6,10,34,42,66,70},{11,23,27,35,43,51,55,67}, {8,16,20,36,44,60,64,72},{1,5,9,29,45,65,69,73}} 19 2 ×19 ×24 ×3 2736 {{6,10,34,42,66,70},{7,15,31,35,43,47,63,71}, {12,20,24,36,44,56,60,68},{1,5,9,25,49,65,69,73}} 19 2 ×19 ×24 ×9 8208 {{22,30,34,42,46,54},{7,15,19,35,43,59,63,71}, {4,16,20,36,44,60,64,76},{9,13,17,25,49,57,61,65}} TABLE D. ZZt×ZZ2 2-cocyclic Hadamard matrices [15-19] (only for symmetric diagrams) ON ZZt×ZZ2 2-COCYCLIC HADAMARD MATRICES 25 t/orbit/#H./representative 21 2 ×21 ×24 ×2 2016 {{22,26,38,46,58,62},{3,15,19,27,39,47,59,67,71,83}, {8,12,16,24,40,48,64,72,76,80},{13,21,25,29,33,49,53,27,61,69}} 21 2 ×21 ×24 ×6 6048 {{10,34,38,42,46,50,74},{3,19,23,31,55,63,67,83}, {12,24,28,36,44,52,60,64,76},{5,9,13,21,33,49,61,69,73,77}} 21 2 ×21 ×24 ×6 6048 {{18,26,38,42,46,58,66},{19,23,31,35,51,55,63,67}, {12,16,32,40,44,48,56,72,76},{1,5,17,29,37,45,53,65,77,81}} 21 2 ×21 ×24 ×6 6048 {{18,26,38,42,46,58,66},{11,23,27,35,51,59,63,75}, {12,16,32,40,44,48,56,72,76},{1,5,9,25,37,45,57,73,77,81}} 21 2 ×21 ×12 ×6 3024 {{6,30,34,38,46,50,54,78},{7,31,35,39,47,51,55,79}, {16,20,36,52,68,72,80},{13,17,33,41,49,65,69,77}} 21 2 ×21 ×24 ×6 6048 {{18,30,34,38,46,50,54,66},{3,7,31,39,47,55,79,83}, {8,24,32,36,52,56,64,80},{1,17,21,29,41,53,61,65,81}} 21 2 ×21 ×24 ×2 2016 {{14,18,30,38,46,54,66,70},{7,15,27,31,55,59,71,79}, {8,12,20,24,64,68,72,80},{13,21,25,37,41,45,57,61,69}} 23 2 ×23 ×24 ×11 12144 {{22,30,38,42,50,54,62,70},{15,19,23,35,47,59,71,75,79}, {12,20,28,40,44,52,56,68,76,84},{9,13,25,29,33,57,61,65,77,81}} TABLE E. ZZt×ZZ2 2-cocyclic Hadamard matrices [21-23] (only for symmetric diagrams)