A Heuristic Procedure with Guided Reproduction for Constructing Cocyclic Hadamard Matrices

A Heuristic Procedure with Guided Reproduction for Constructing Cocyclic Hadamard Matrices V. ´ Alvarez, M.D. Frau, and A. Osuna Dpto. Matem´atica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n 41012 Sevilla, Spain {valvarez,mdfrau,aosuna}@us.es Abstract. A genetic algorithm for constructing cocyclic Hadamard matrices over a given group is described. The novelty of this algorithm is the guided heuristic procedure for reproduction, instead of the classical crossover and mutation operators. We include some runs of the algorithm for dihedral groups, which are known to give rise to a large amount of cocyclic Hadamard matrices. 1 Introduction A Hadamard matrix is a n×nsquare (−1,1) matrix Hnso that Hn·HT n=nI. Equivalently, a Hadamard matrix is a square matrix over {1,−1}so that its rows are pairwise orthogonal. The knowledge of Hadamard matrices is a major question for applications in a wide range of different disciplines, as in the design of good (even optimal) errorcorrecting codes meeting the Plotkin bounds (see [15] for details). A classical reference on Hadamard matrices and their uses is [9]. It may be easily proved that the size nof a Hadamard matrix Hnmust be 1, 2 or a multiple of 4. It is conjectured that such a Hnexists for all ndivisible by 4. However, the proof of this conjecture remains an important problem in Coding Theory, since there is no evidence of this fact until now. In fact, there are infinitely many orders multiple of four for which uncertainty about the existence of these matrices has not been removed at all. Furthermore, even in the case that a Hadamard matrix is known to exist for a given order n=4t, there is no algorithm available which outputs a Hadamard matrix of this order 4tin reasonable time, as it is pointed out in [14]. The cocyclic framework concerning Hadamard matrices was introduced in the 90s [12,13] as a promising context to solve the questions above. A cocyclic matrix Mfover a finite group G={g1,...,g 4t}of order |G|=4t consists in a matrix M=(f(gi,g j)), f:G×G→{1,−1}being a 2-cocycle over Gwith coefficients in {1,−1},sothat f(gi,g j)f(gigj,g k)=f(gj,g k)f(gi,g jgk),∀gi,g j,g k∈G All authors are partially supported by the research projects FQM–296 and P07– FQM–02980 from JJAA and MTM2008-06578 from MICINN (Spain). The link between cocyclic and Hadamard matrices was first noticed in [12]. A more recent reference is [11], in which many of the classical and more recently discovered constructions of Hadamard matrices are shown to be cocyclic. This support the idea that cocyclic construction is the most uniform construction technique for Hadamard matrices yet known. Consequently, the cocyclic Hadamard Conjecture arises in turn. The main advantages of working with cocyclic Hadamard matrices may be resumed in the following facts: –The cocyclic Hadamard test (which claims that it suffices to check whether the summation of every row but the first is zero, see [13] for details) runs in O(t2) time, better than the O(t3) algorithm for usual (not necessarily cocyclic) Hadamard matrices. –The search space is reduced to the set of cocyclic matrices over a given group (that is, 2smatrices, provided that a basis for 2-cocycles over Gconsists of sgenerators), instead of the whole set of ⎛ ⎝4t 2t 4t−1 ⎞ ⎠matrices with entries in {−1,1}consisting of the row (1,t ...,1) and 4t−3 vectors of length 4t orthogonal to (1,t ...,1). In particular, the work in [5] suggest that the cocyclic framework (c.f. in the table below) may reduce significantly the size of the search space in the general framework (g.f. for brevity) case, as the table below indicates: t1 2 3 4 5 6 7 8 c.f. O(100)O(101)O(102)O(103)O(105)O(106)O(107)O(108) g.f. O(101)O(109)O(1024)O(1049)O(1082)O(10125)O(10177)O(10238) Considerable effort has been devoted to the design of efficient algorithms for constructing cocyclic Hadamard matrices. Exhaustive search is not feasible for orders 4tgreater than 20 (the search space grows exponentially on t,see[5]for instance). Consequently, alternative methods are required. As far as we know, two different heuristic methods have been proposed until now, in terms of image restorations [6] and genetic algorithms [2]. We present here a new genetic algorithm for constructing cocyclic Hadamard matrices. The main difference with respect to that of [2] is a novel heuristic for reproduction: instead of the usual crossover and mutation operators we shall better use a guided reproduction procedure. Calculations in Section 5 suggest that this new feature improves the original algorithm. This heuristic involves the notions of i-paths and intersections introduced in [5], to be described further in Section 2. As it is shown in [5], dihedral groups seems to be the most prolific familiy of groups giving rise to cocyclic Hadamard matrices. We particularize the algorithm to the case of these groups. We also include some runs of the algorithm, which have been worked out in Mathematica 4.0, running on a Pentium IV 2.400 Mhz DIMM DDR266 512 MB. A deeper study on the way in which 2-coboundaries over Ghave to be combined in order to give rise to cocyclic Hadamard matrices (attending to i-paths and intersections, as described in [5]) would lead to an improvement of the performance of the guided genetic algorithm in a straightforward manner. We organize the paper as follows. Section 2 collects some general notions and results about cocyclic Hadamard matrices. The algorithm looking for cocyclic Hadamard matrices equipped with the new heuristic for reproduction is described in Section 3. Section 4 is devoted to particularize the algorithm to the case of dihedral group. 2 Generalities about Cocyclic Hadamard 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). Effective methods for constructing a basis Bfor 2-cocycles over a given group Gare known ([12,13],[7],[4]). Such a basis consists 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 [4] for instance). 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 [13]. In what follows, the rows whose summation is zero are termed Hadamard rows. We now reproduce the notions of generalized coboundary matrix,i-walk and intersection introduced in Definition 2 of [5]. 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 [5], 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 [5], every set of generalized coboundary matrices may be uniquely partitioned into disjoint maximal i-walks. A characterization of Hadamard rows may be easily described attending to i-paths. Proposition 1. [5] The ith row of a cocyclic matrix M=M∂i1...M ∂iw·Ris a Hadamard row 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∂iw share a common −1 in a given row simply as intersections,forbrevity. Equation (2) is the heart of the guided heuristic procedure for reproduction which is applied in the genetic algorithm described in this paper. 3 The Algorithm The genetic algorithm described in [2] and implemented in [3] is based upon the natural evolution principles of Holland’s [10]: –The population consists of a subset of 4tcocyclic matrices Mfover G,Mf= (f(gi,g j)), which are identified to a binary tuple, the coordinates (f1,...,f s) of the 2-cocycle fwith regards to the basis B. Accordingly, the coordinates fiare the genes of the individual f. –The evaluation function counts the number of Hadamard rows in Mf: the more Hadamard rows Mfposses, the fittest Mfis. In particular, an individual ind gives rise to a cocyclic Hadamard matrix if and only if evaluate(ind)= 4t−1. –Crossover combines the features of two parent chromosomes to form two similar offspring by swapping corresponding segments of the parents. –Mutation arbitrarily alters just one gene of a selected individual (the mutation rate is fixed in 1%). In the reproduction process, the individuals of the population are paired at random, so that the application of the crossover operator gives rise to another 4t individuals, which are added to the population. The generation i+1isformed from generation iby choosing the 4tfittest individuals after the reproduction process. We now propose a different approach. Instead of the usual crossover and mutation operators described above, we shall better use another heuristic for reproduction. With probability pr1, an individual Mfrandomly selected from the population gives rise to 4t−1 children, so that the (i+1) th-row of the ithchild is Hadamard. Otherwise the usual crossover operator is used, applied over two individuals randomly selected. Generation Pw+1 is obtained from generation Pwkeeping the fittest individuals and replacing a set of less fit individuals with the children just constructed, so that a population of 8tindividuals is formed. In this process duplicate copies of the same individual are not permitted. Consequently, the blinded processes of crossover and mutation are now substituted by a completely oriented procedure for reproduction: this way it is guaranteed that anytime an individual exists such that its ith-row is Hadamard. In order to generate these children, the genes of Mfhave to be modified so that equation (2) is satisfied. It is remarkable that the magnitudes ciand Ii depends heavily on the subset of 2-coboundaries which gives rise to Mf.On the contrary, the magnitude ridepends only on the representative 2-cocycles implicated in the generation of Mf. Attending to these facts, a heuristic procedure for reproduction may be straightforwardly defined in the following way. The key idea is to modify the genes of Mfcorresponding to 2-coboundaries in such a manner that the magnitudes ciand Iiare also modified in turn, so that the difference 2ci−2Iiis closer to the constant value 2t−ri. Depending on whether 2ci−2Ii>2t−rior 2ci−2Ii<2t−ri, we need to increase or decrease Ii(resp. decrease or increase ci) so that the equality may hold. More concretely: 1. If 2ci−2Ii>2t−ri, the algorithm randomly chooses one of the following possibilities: –Collapses two different i-paths into just one i-path, so that cidecreases 1 unit. –Introduces a new negative sharing position between Rand the product of M∂j,sothatIiincreases 1 unit. 2. If 2ci−2Ii<2t−ri, the algorithm randomly chooses one of the following possibilities: –Splits one i-path into two different i-paths, so that ciincreases 1 unit. –Adds a new i-path, introducing a new 2-coboundary generator, so that ciincreases 1 unit. –Eliminates a negative sharing position between Rand the product of M∂j,sothatIidecreases 1 unit. The way in which these procedures have to be implemented depends on the group Gover which 2-cocycles are considered. In the following section we will 1Experimental results show that a good value for the parameter pris 0.8. explicitly show a pseudo-code of the particular heuristic procedure for reproduction in the case of dihedral groups. The population is expected to evolve generation through generation until an optimum individual (i.e. a cocyclic Hadamard matrix) is located. This has been the case in the examples showed in the last section. We include now a pseudo-code of the algorithm. Input: a group (G, ·)of order |G|=4t Output: some (eventually one) cocyclic Hadamard matrices over G \\ the initial population is created pob ←∅ fit ←∅ for ifrom 1 to 8t{ ind ←create new() pob ←pob ∪{ind} fit ←fit∪{evaluate(ind)} } pr←0.8 while (max(fit)<4t−1){ \\ reproduction starts if random(0,1) ≤prthen{ j←random(1,8t) indj←the jth-individual of pob list ←guidedreproduction(indj) else i←random(1,8t) j←random(1,8t)=i (indi,ind j)←the (ith,jth)-individuals of pob list ←usualreproduction(indi,ind j) } remove in (pob, fit)those entries corresponding to the less size(list)fit individuals for ifrom 1 to size(list){ pob ←pob ∪{list(i)} fit ←fit∪{evaluate(list(i))} } } List the individuals in pob meeting the optimal fitness, 4t−1 Some auxiliar functions have been used, which we describe now: –create new() outputs a binary tuple of length s(sbeing the dimension of the basis Bof 2-cocycles over G), each bit randomly generated as 0 or 1 with the same probability. A deeper knowledge about the properties of the group Gmight lead to improved versions of this procedure. As a matter of fact, in the case of dihedral groups, the number of 1s should be forced to 2t,asthe tables in [5] suggest, since the density of cocyclic Hadamard matrices seems to be maximum with this rate of 1s. –evaluate(ind) measures the fitness of the individual ind, that is, counts the number of the Hadamard rows (i.e. those whose summation is zero) in the cocyclic matrix generated by the pointwise product of the matrices related to the 2-cocycles of Bcorresponding to the 1s in ind. In particular, an individual ind gives rise to a cocyclic Hadamard matrix if and only if evaluate(ind)= 4t−1. –random(min, max) outputs a integer in the range [min, max] randomly generated. –guidedreproduction(ind) applies the heuristic procedure for reproduction on the individual ind. The output consists in 4t−1 new individuals, the (i+1)throw of the ith-individual being Hadamard. –usualreproduction(indi,ind j) applies the usual crossover operator for reproduction on the individuals indiand indj. The output consists in 2 new individuals. 4 Guided Reproduction on Dihedral Groups 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 [8] 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 [5], 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,γ}. We focus in the case (A, B, K)=(1,−1,−1) (that is, R=β2γ), since computational results in [8,5] suggest that this case contains a large density of cocyclic Hadamard matrices. Furthermore, as it is pointed out in Theorem 2 of [5], cocyclic matrices over D4tusing Rare Hadamard matrices if and only if rows from 2 to tare Hadamard. We have updated the genetic algorithm in turn, so that only rows from 2 to t are used in order to check whether their summations are zero. Accordingly, the fitness of an individual runs through the range [0,t−1]. In order to define the heuristic procedure for reproduction we need 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 [5]. Proposition 2. [5] 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). We now have enough information about how to combine 2-coboundaries in Bin order to modify the value of 2ci−2Ii,sothat2ci−2Ii=2t−ri,thatis,the ith-row of our individual being Hadamard. Notice that since ri=2(i−1) for 2 ≤i≤t, the cocyclic Hadamard test reduces to ci−Ii=t−i+1,for2≤i≤t. We include below a pseudo-code of the guidedreproduction procedure described in the section before, particularized to the case of dihedral groups. Input: an individual ind of the population Output: a list newpob of 4t−1individuals, the (i+1) th-row of the ith-individual being Hadamard newpob ←∅ for ifrom 2 to t{ ipaths ←list with the maximal i-paths naturally related to ind c←size of ipaths intersec ←intersecting positions of −1s in the ith-row of ind I←size of intersec while c−I=t−i+1{ if c−I>t−i+1{ ind ←decrease(ipaths, intersec, i −1,random(1,2)) else{ ind ←increase(ipaths, intersec, i −1,random(1,3)) } recompute the values ipaths,c,intersec and Irelated to ind } newpob ←newpob ∪{ind} } newpob Some auxiliar functions have been used, which we describe now: –decrease(ipaths, intersec, i −1,j) tries to decrease the value c−I,thatis, size(ipaths)−size(intersec). This function acts in a different way, depending on the value of 1 ≤j≤2: •decrease(ipaths, intersec, i−1,1) outputs an individual ind with exactly size(ipaths)−1i-paths. More concretely, it extends one of the i-paths (say p1, randomly selected) in ipath to the left, until this i-path is connected to a previously existent i-path, say p2. There are two possibilities now: if p1=p2,thenp1and p2have been merged into a solely path. On the contrary, if p1=p2,thenp1has been extended to form a i-cycle. In both cases, we have effectively generated a new individual consisting of size(ipaths)−1i-paths. •decrease(ipaths, intersec, i −1,2) outputs an individual ind with exactly size(intersec) + 1 intersections. It suffices to randomly choose a 2-coboundary sharing a negative entry with Rin the ith-row, in case that it exists. Otherwise the function decrease(ipaths, intersec, i −1,1) should be called. –increase(ipaths, intersec, i −1,j) tries to increase the value c−I,thatis, size(ipaths)−size(intersec). This function acts in a different way, depending on the value of 1 ≤j≤3: •increase(ipaths, intersec, i −1,1) tries to increase the number of the i-paths in ipaths, by splitting an existent i-path into two different ipaths. This is only possible for i-paths consisting of at least three 2- coboundaries. If it is the case, it suffices to delete any 2-coboundary different from the extremes of the i-path. If not, the function increase(ipaths, intersec, i −1,1+random(1,2)) is called. •increase(ipaths, intersec, i −1,2) tries to increase the number of the i-paths in ipaths, by adding a new i-path in ipaths which does not extend any of the previously existent i-paths. This is only possible if a 2-coboundary exists such that it is not adjacent to any of the i-paths in ipaths. If it is not the case, the function increase(ipaths, intersec, i −1,2+(−1)random(1,2)) is called. •increase(ipaths, intersec, i −1,3) tries to create an individual ind with size(intersec)−1 intersections. It suffices to randomly delete a 2-coboun- dary sharing a negative entry with Rin the ith-row,incasethatitexists. Otherwise the function increase(ipaths, intersec, i −1,random(1,2)) is called.