Rooted Trees Searching for Cocyclic Hadamard Matrices over D4t

Rooted Trees Searching for Cocyclic Hadamard Matrices over D4t V´ıctor ´ Alvarez, Jos´e´ Andr´es Armario, Mar´ıa Dolores Frau, F´elix Gudiel, and Amparo Osuna Dpto. Matem´atica Aplicada 1, E.T.S.I.Inform´atica, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain Abstract. A new reduction on the size of the search space for cocyclic Hadamard matrices over dihedral groups D4tis described, in terms of the so called central distribution. This new search space adopt the form of a forest consisting of two rooted trees (the vertices representing subsets of coboundaries) which contains all cocyclic Hadamard matrices satisfying the constraining condition. Experimental calculations indicate that the ratio between the number of constrained cocyclic Hadamard matrices and the size of the constrained search space is greater than the usual ratio. Keywords: Hadamard matrix, cocyclic matrix, dihedral groups. 1 Introduction Since Hadamard matrices (that is, {1, −1}-square matrices whose rows are pairwise orthogonal) were introduced at the end of the XIXth century, the interest in their construction has grown substantially, because of their multiple applications (see [7] for instance). For this reason, many attempts and efforts have been devoted to the design of good construction procedures, the latest involving heuristic techniques (see [5], [1], [4] for instance). Even alternative theoretical descriptions characterizing Hadamard matrices have been proposed (for instance, Ito’s works involving Hadamard graphs [11] in the middle eighties, and Hadamard groups [6,12] more recently). But no matter what one may think, Hadamard matrices keep on being elusive anyway. The point is that though it may be easily checked that the size of a Hadamard matrix is to be 2 or a multiple of 4, there is no certainty whether such a Hadamard matrix exists for every size 4t.Thisisthe Hadamard conjecture,whichremains unsolved for more than a century. In fact, the design of a procedure which outputs a Hadamard matrix of the desired size has shown to be as important as solving the Hadamard conjecture itself. All authors are partially supported by the research projects FQM–296 and P07- FQM-02980 from Junta de Andaluc´ıa and MTM2008-06578 from Ministerio de Ciencia e Innovaci´on (Spain). In the early 90s, a surprising link between homological algebra and Hadamard matrices [9] led to the study of cocyclic Hadamard matrices [10]. The main advantages of the cocyclic framework are that: –On one hand, the Hadamard test for cocyclic matrices [10] runs in O(t2) time, better than the O(t3) algorithm for usual (not necessarily cocyclic) Hadamard matrices. –On the other hand, the search space reduces drastically, though it still is often of exponential size (see [4,2] for details). Among the groups for which cocyclic Hadamard matrices have been found, it seems that dihedral groups D4tare more likely to give a more density of cocyclic Hadamard matrices, even for every order multiple of 4 (see [8,3,2] for instance). Unfortunately, the task of explicitly construct cocyclic Hadamard matrices over D4tis considerably difficult, since the search space inherits a exponential size. New ideas dealing with this problem are welcome. The purpose of this paper is to describe a new reduction on the size of the search space for cocyclic Hadamard matrices over dihedral groups D4t.Thekey idea is exploiting the notions of i-paths and intersections introduced in [2], in order to design a forest consisting of two rooted trees (the vertices representing subsets of coboundaries) which contains all cocyclic Hadamard matrices satisfying the so called central distribution. We will explain these notions in the following section. We organize the paper as follows. Section 2 is devoted to preliminaries on cocyclic matrices. Section 3 describes the new search space for cocyclic Hadamard matrices over D4t. We include some final remarks and comments. 2 Preliminaries on Cocyclic Matrices Consider a multiplicative group G={g1=1,g 2,...,g 4t}, not necessarily abelian. A cocyclic matrix Mfover Gconsists in a binary matrix Mf=(f(gi,g j)) coming from a 2-cocycle fover G,thatis,amapf:G×G→{1,−1}such that f(gi,g j)f(gigj,g k)=f(gj,g k)f(gi,g jgk),∀gi,g j,g k∈G. We will only use normalized cocycles f(and hence normalized cocyclic matrices Mf), so that f(1,g j)=f(gi,1) = 1 for all gi,g j∈G(and correspondingly Mf=(f(gi,g j)) consists of a first row and column all of 1s). AbasisBfor 2-cocycles over Gconsists of some representative 2-cocycles (coming from inflation and transgression) and some elementary 2-coboundaries ∂i, so that every cocyclic matrix admits a unique representation as a Hadamard (pointwise) product M=M∂i1...M ∂iw·R, in terms of some coboundary matrices M∂ijand a matrix Rformed from representative cocycles. Recall that every elementary coboundary ∂dis constructed from the characteristic set map δd:G→{±1}associated to an element gd∈G,sothat ∂d(gi,g j)=δd(gi)δd(gj)δd(gigj)forδd(gi)=−1gd=gi 1gd=gi(1) Although the elementary coboundaries generate the set of all coboundaries, they might not be linearly independent (see [3] for details). Moreover, since the elementary coboundary ∂g1related to the identity element in Gis not normalized, we may assume that ∂g1/∈B. The cocyclic Hadamard test asserts that a cocyclic matrix is Hadamard if and only if the summation of each row (but the first) is zero [10]. In what follows, the rows whose summation is zero are termed Hadamard rows. This way, a cocyclic matrix Mfis Hadamard if and only if every row (Mf)i is a Hadamard row, 2 ≤i≤4t. In [2] the Hadamard character of a cocyclic matrix is described in an equivalent way, in terms of generalized coboundary matrices,i-walks and intersections.We reproduce now these notions. The generalized coboundary matrix ¯ M∂jrelated to a elementary coboundary ∂jconsists in negating the jth-row of the matrix M∂j. Note that negating a row of a matrix does not change its Hadamard character. As it is pointed out in [2], every generalized coboundary matrix ¯ M∂jcontains exactly two negative entries in each row s= 1, which are located at positions (s, i)and(s, e), for ge=g−1 sgi. We will work with generalized coboundary matrices from now on. Aset{¯ M∂ij:1≤j≤w}of generalized coboundary matrices defines an i-walk if these matrices may be ordered in a sequence ( ¯ Ml1,..., ¯ Mlw)sothat consecutive matrices share exactly one negative entry at the ith-row. Such a walk is called an i-path if the initial and final matrices do not share a common −1, and an i-cycle otherwise. As it is pointed out in [2], every set of generalized coboundary matrices may be uniquely partitioned into disjoint maximal i-walks. From the definition above, it is clear that every maximal i-path contributes two negative occurrences at the ith-row. This way, a characterization of Hadamard rows (consequently, of Hadamard matrices) may be easily described in terms of i-paths. Proposition 1. [2] The ith row of a cocyclic matrix M=M∂i1...M ∂iw·Ris Hadamard if and only if 2ci−2Ii=2t−ri(2) where cidenotes the number of maximal i-paths in {¯ M∂i1,..., ¯ M∂iw},ricounts the number of −1sintheith-row of Rand Iiindicates the number of positions in which Rand ¯ M∂i1... ¯ M∂iwshare a common −1in their ith-row. From now on, we will refer to the positions in which Rand ¯ M∂i1... ¯ M∂iwshare a common −1 in a given row simply as intersections,forbrevity. We will now focus on the case of dihedral groups. 3 Cocyclic Matrices over D4t Denote by D4tthe dihedral group ZZ2t×χZZ2of order 4t,t≥1, given by the presentation <a,b|a2t=b2=(ab)2=1> and ordering {1=(0,0),a=(1,0),...,a 2t−1=(2t−1,0),b=(0,1),...,a 2t−1b=(2t−1,1)} In [6] a representative 2-cocycle fof [f]∈H2(D4t,ZZ2)∼ =ZZ3 2is written interchangeably as a triple (A, B, K), where Aand Bare the inflation variables and Kis the transgression variable. All variables take values ±1. Explicitly, f(ai,a jbk)=Aij ,i+j<2t, Aij K, i +j≥2t, f(aib, ajbk)=Aij Bk,i≥j, Aij BkK, i < j, Let β1,β2and γdenote the representative 2-cocycles related to (A, B, K)= (−1,1,1),(1,−1,1),(1,1,−1) respectively. A basis for 2-coboundaries is described in [2], and consists of the elementary coboundaries {∂a,...,∂ a2t−3b}. This way, a basis for 2-cocycles over D4tis given by B={∂a,...,∂ a2t−3b,β 1,β 2,γ}. Computational results in [6,2] suggest that the case (A, B, K)=(1,−1,−1) contains a large density of cocyclic Hadamard matrices. Furthermore, as it is pointed out in Theorem 2 of [2], cocyclic matrices over D4tusing R=β2γare Hadamard matrices if and only if rows from 2 to tare Hadamard, so that the cocyclic test runs four times faster than usual. From now on, we assume that R=Mβ2·Mγ=AA B−Bfor A=⎛ ⎜ ⎜ ⎜ ⎝ 11··· 1 1···−1 . . .······. . . 1−1···−1 ⎞ ⎟ ⎟ ⎟ ⎠ and B= ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ 1−1···−1 . . ........ . . 1...−1 11··· 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ (3) Now we would like to know how the 2-coboundaries in Bhave to be combined to form i-paths, 2 ≤i≤t. This information is given in Proposition 7 of [2]. Proposition 2. [2] For 1≤i≤2t, a maximal i-walk consists of a maximal subset in (M∂1,...,M ∂2t)or (M∂2t+1 ,...,M ∂4t) formed from matrices (...,M j,M k,...)which are cyclically separated in i−1 positions (that is j±(i−1) ≡kmod2t). Notice that since ri=2(i−1) for 2 ≤i≤t, the cocyclic Hadamard test reduces to check whether ci−Ii=t−i+1,for 2≤i≤t.Thusciuniquely determines Iiand reciprocally, 2 ≤i≤t. In fact, the way in which intersections may be introduced at the ith-row is uniquely determined. More explicitly Lemma 1. The following table gives a complete distribution of the coboundaries in Bwhich may create an intersection at a given row. For clarity in the reading, we note the generalized coboundary ¯ M∂isimply by i: row coboundaries 2 2t, 2t+1 3 2,2t−1,2t, 2t+1,2t+2 4≤k≤t2,...,k−1,2t−k+2,...,2t+k−1,4t−k+2,...,4t−2 Proof It may be seen by inspection, taking into account the distribution of the negative occurrences in Rand the form of the generalized coboundary matrices.  Lemma 2. In particular, there are some coboundaries which do not produce any intersection at all, at rows 2≤k≤t, which we term free intersection coboundaries. More concretely, tcoboundaries 2 2,3,6 t>2t, t +1,3t, 3t+1 Proof It suffices to take the set difference between Band the set of coboundaries used in the lemma above.  Lemma 3. Furthermore, the following table distributes the coboundaries which produce a intersection at every row, so that coboundaries which produce the same negative occurrence at a row are displayed vertically in the same column. row coboundaries 2 2t2t+1 32t-1 2t 22t+1 2t+2 4≤k≤t2t-k+2 2t−k+3 2 ... ... 2t−1 k−2 2t k-1 2t+1 4t-k+2 2t+2 4t−k+1 ... ... 2t+k−3 4t−22t+k−22t+k-1 Proof It may be seen by inspection.  Remark 1. Notice that: –The set of coboundaries which may produce an intersection at the ith-row is included in the analog set corresponding to the (i+1) th-row. –The boxed coboundaries do not produce any intersection at the precedent rows. Now one could ask whether cocyclic Hadamard matrices exist for any formal distribution of pairs (ci,I i) satisfying the relations ci−Ii=t−i+1, for 2 ≤i≤t. Actually, this is not the case. Proposition 3. Not all of the formal sequences [(c2,I 2),...,(ct,I t)] satisfying ci−Ii=t−i+1give rise to cocyclic Hadamard matrices over D4t,fort≥3. Proof Proposition 10 of [2] bounds the number wof coboundaries in Bto multiply with Rso that a cocyclic Hadamard matrix is formed, so that t−1≤w≤3t+2. In particular, for t≥6, we know that 5 ≤w. Consequently, the case I2= ... =It= 0 is not feasible, since from Lemma 2 we know that only up to 4 coboundaries may be combined so that no intersection is generated at any row. This proves the Lemma for t≥6. We now study the remaining cases. Taking into account that 0 ≤Ii≤ri=2i−2, we may have a look in the way in which cocyclic Hadamard matrices are distributed regarding the number of intersections Ii, for those groups D4tfor which the whole set of cocyclic Hadamard matrices have been computed until now. These are precisely t= 2,3,4,5. For t= 2, we formally have 3 solutions for the equation c2−I2=1, c21 2 3 I20 1 2 Each of these solutions gives rise to some cocyclic Hadamard matrices Mf, I20 1 2 |Mf|410 2 For t= 3, we formally have 15 solutions for the system c2−I2=2 c3−I3=1 coming from the combination of any solution of each of the equations c22 3 4 I20 1 2 c31 2 3 4 5 I30 1 2 3 4 Only 9 of the 15 hypothetical solutions are real solutions (there are no combinations of coboundaries meeting the other 6 “theoretical” solutions), distributed in the following way: (I2,I 3)(0,1) (0,2) (0,3) (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) |Mf|610 2 8 20 8 2 10 6 For t= 4, we formally have 105 solutions for the system ⎧ ⎨ ⎩ c2−I2=3 c3−I3=2 c4−I4=1 coming from the combination of any solution of each of the equations c2345 I2012 c32 3 4 5 6 I30 1 2 3 4 c41 2 3 4 5 6 7 I40 1 2 3 4 5 6 Only 36 of the 105 hypothetical solutions are real solutions, distributed in the following way: (I2,I 3,I 4) (0,0,2) (0,1,1) (0,1,2) (0,1,3) (0,1,4) (0,2,2) (0,2,3) (0,2,4) (0,2,5) |Mf|8 6 18 18 6 12 12 24 12 (I2,I 3,I 4) (0,3,3) (0,3,4) (1,0,3) (1,1,1) (1,1,2) (1,1,3) (1,1,4) (1,1,5) (1,2,1) |Mf|4 8 12 18 12 8 4 6 4 (I2,I 3,I 4) (1,2,2) (1,2,3) (1,2,4) (1,2,5) (1,3,2) (1,3,3) (1,3,4) (1,4,3) (2,1,2) |Mf|24 72 24 4 12 32 20 20 2 (I2,I 3,I 4) (2,2,1) (2,2,2) (2,2,3) (2,2,4) (2,3,2) (2,3,3) (2,1,3) (2,1,4) (2,1,5) |Mf|6 6 2 12 24 12 12 24 12 For t= 5, we formally have 945 solutions for the system ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ c2−I2=4 c3−I3=3 c4−I4=2 c5−I5=1 coming from the combination of any solution of each of the equations c24 5 6 I20 1 2 c334567 I301234 c42 3 4 5 6 7 8 I40 1 2 3 4 5 6 c5123456789 I4012345678 Only 153 of the 945 hypothetical solutions are real solutions, (I2,I 3,I 4,I 5)(0,0,1,3) (0,0,2,3) (0,1,1,4) (0,1,2,2) (0,1,2,3) (0,1,2,4) |Mf|412 3 6 12 21 (I2,I 3,I 4,I 5)(0,1,2,5) (0,1,3,2) (0,1,3,3) (0,1,3,4) (0,1,3,5) (0,1,3,6) |Mf|6 6 12 21 21 9 (I2,I 3,I 4,I 5)(0,1,3,7) (0,1,4,3) (0,1,4,4) (0,1,4,5) (0,1,4,6) (0,1,4,7) |Mf|3 6 3 9 18 6 (I2,I 3,I 4,I 5)(0,2,0,2) (0,2,1,2) (0,2,1,3) (0,2,1,4) (0,2,2,2) (0,2,2,3) |Mf|2 4 2 2 4 12 (I2,I 3,I 4,I 5)(0,2,2,4) (0,2,3,2) (0,2,3,3) (0,2,3,4) (0,2,3,5) (0,2,3,6) |Mf|4 8 8 24 14 2 (I2,I 3,I 4,I 5)(0,2,4,4) (0,2,4,5) (0,2,4,6) (0,2,5,4) (0,3,2,5) (0,3,3,2) |Mf|12 26 4 4 2 2 (I2,I 3,I 4,I 5)(0,3,3,3) (0,3,3,4) (0,3,3,5) (0,3,4,2) (0,3,4,3) (0,3,4,4) |Mf|7 6 6 1 4 5 (I2,I 3,I 4,I 5)(0,3,4,5) (0,3,5,4) (1,0,1,4) (1,0,2,2) (1,0,2,3) (1,0,2,4) |Mf|6 1 2 4 2 4 (I2,I 3,I 4,I 5)(1,0,4,2) (1,0,4,3) (1,0,4,4) (1,0,5,4) (1,1,1,3) (1,1,1,4) |Mf|4 2 4 2 6 3 (I2,I 3,I 4,I 5)(1,1,2,3) (1,1,2,4) (1,1,2,5) (1,1,2,6) (1,1,3,2) (1,1,3,3) |Mf|714 22 8 4 16 (I2,I 3,I 4,I 5)(1,1,3,4) (1,1,3,5) (1,1,3,6) (1,1,3,7) (1,1,4,3) (1,1,4,4) |Mf|20 816 16 510 (I2,I 3,I 4,I 5)(1,1,4,5) (1,1,4,6) (1,1,5,3) (1,1,5,4) (1,2,1,3) (1,2,1,4) |Mf|18 8 2 1 4 8 (I2,I 3,I 4,I 5)(1,2,2,2) (1,2,2,3) (1,2,2,4) (1,2,2,5) (1,2,3,2) (1,2,3,3) |Mf|416 28 16 24 20 (I2,I 3,I 4,I 5)(1,2,3,4) (1,2,3,5) (1,2,4,2) (1,2,4,3) (1,2,4,4) (1,2,4,5) |Mf|32 56 412 24 24 (I2,I 3,I 4,I 5)(1,2,5,4) (1,3,1,2) (1,3,1,3) (1,3,1,4) (1,3,2,2) (1,3,2,3) |Mf|8 1 3 2 8 16 (I2,I 3,I 4,I 5)(1,3,2,4) (1,3,2,5) (1,3,3,3) (1,3,3,4) (1,3,3,5) (1,3,4,2) |Mf|10 624 32 16 8 (I2,I 3,I 4,I 5)(1,3,4,3) (1,3,4,4) (1,3,4,5) (1,3,5,2) (1,3,5,3) (1,3,5,4) |Mf|16 22 10 3 9 6 (I2,I 3,I 4,I 5)(1,4,1,3) (1,4,2,3) (1,4,2,4) (1,4,3,3) (1,4,3,4) (1,4,4,3) |Mf|2 6 6 16 8 6 (I2,I 3,I 4,I 5)(1,4,4,4) (1,4,5,3) (2,1,2,3) (2,1,2,4) (2,1,2,5) (2,1,2,6) |Mf|6 2 2 1 3 6 (I2,I 3,I 4,I 5)(2,1,2,7) (2,1,3,2) (2,1,3,3) (2,1,3,4) (2,1,3,5) (2,1,3,6) |Mf|2 2 4 7 7 3 (I2,I 3,I 4,I 5)(2,1,3,7) (2,1,4,2) (2,1,4,3) (2,1,4,4) (2,1,4,5) (2,1,5,4) |Mf|1 2 4 7 2 1 (I2,I 3,I 4,I 5)(2,2,1,4) (2,2,2,4) (2,2,2,5) (2,2,2,6) (2,2,3,2) (2,2,3,3) |Mf|412 26 4 8 8 (I2,I 3,I 4,I 5)(2,2,3,4) (2,2,3,5) (2,2,3,6) (2,2,4,2) (2,2,4,3) (2,2,4,4) |Mf|24 14 2 4 12 4 (I2,I 3,I 4,I 5)(2,2,5,2) (2,2,5,3) (2,2,5,4) (2,2,6,2) (2,3,1,4) (2,3,2,2) |Mf|4 2 2 2 3 3 (I2,I 3,I 4,I 5)(2,3,2,3) (2,3,2,4) (2,3,2,5) (2,3,3,2) (2,3,3,3) (2,3,3,4) |Mf|12 15 18 621 18 (I2,I 3,I 4,I 5)(2,3,3,5) (2,3,4,5) (2,4,2,3) |Mf|18 612  Attending to the tables above, we conclude that, for 2 ≤t≤5, there is a large density of cocyclic Hadamard matrices in the case ci=tfor 2 ≤i≤t, that is, (I2,...,I t)=(1,...t−1). We call this case the central distribution for intersections and i-paths on D4t. We include now a table comparing the number central of cocyclic Hadamard matrices in the central distribution with the proportion % = |Mf| cases of the amount |Mf|of cocyclic Hadamard matrices over D4tby the total number cases of valid distributions of intersections (I2,...,I t). The last column contains the number of cocyclic Hadamard matrices of the most prolific case: tcases |Mf|%central best 2 3 16 5.33 10 10 3 9 72 820 20 436 512 14.22 72 72 5153 1400 9.15 32 56 It seems then reasonable trying to constraint the search for cocyclic Hadamard matrices over D4tto the central distribution case. The search space in the central distribution (I2,...,I t)=(1,...,t−1) may be represented as a forest of two rooted trees of depth t−1. We identify each level of the tree to the correspondent row of the cocyclic matrix at which intersections are being counted, so that the roots of the trees are located at level 2 (corresponding to the intersections created at the second row of the cocyclic matrix). This way the level icontains those coboundaries which must be added to the father configuration in order to get the desired i−1 intersections at the ith-row, for 2 ≤i≤t. The root of the first tree is ∂2t, whereas the root of the second tree is ∂2t+1, since from Lemma 1 these are the only coboundaries which may give an intersection at the second row. As soon as one of these coboundaries is used, the other one is forbidden, since otherwise a second intersection would be introduced at the second row. Now one must add some coboundaries to get two intersections at the third row. Since ∂2tis already used and ∂2t+1 is forbidden, there are only 3 coboundaries left (those boxed in the table of Lemma 3). Successively, in order to construct the nodes at level k, one must add some of the correspondent boxed coboundaries of the table of Lemma 3, since the remaining coboundaries are either used or forbidden. We include the forests corresponding to the cases t=2,3,4 for clarity. t trees 2Level 2 4 5 3 Level 2 Level 3 6 58(2,5,8) Level 2 Level 3 7 258 4 8 7 10 (2,7,10) 6 11 14 (3,6,11) (3,6,14) (3,11,14) 6 11 14 (3,6,11) (3,6,14) (3,11,14) 6 11 14 (3,6,11) (3,6,14) (3,11,14) Level 2 Level 3 Level 4 9 27 10 3 6 11 (14,3,6) (14,3,11) (14,6,11) 3 6 11 (14,3,6) (14,3,11) (14,6,11) 3 6 11 (14,3,6) (14,3,11) (14,6,11) Level 2 Level 3 Level 4