A Heuristic Procedure with Guided Reproduction for Constructing Cocyclic Hadamard Matrices

A Heu is ic P ocedu e wi h Guided Rep oduc ion o Cons uc ing Cocyclic Hadama d Ma ices V. ´ Al a ez, M.D. F au, and A. Osuna Dp o. Ma em´a ica Aplicada I, Uni e sidad de Se illa, A da. Reina Me cedes s/n 41012 Se illa, Spain { al a ez,md au,aosuna}@us.es Abs ac . A gene ic algo i hm o cons uc ing cocyclic Hadama d ma- ices o e a gi en g oup is desc ibed. The no el y o his algo i hm is he guided heu is ic p ocedu e o ep oduc ion, ins ead o he classical c osso e and mu a ion ope a o s. We include some uns o he algo i hm o dihed al g oups, which a e known o gi e ise o a la ge amoun o cocyclic Hadama d ma ices. 1 In oduc ion A Hadama d ma ix is a n×nsqua e (−1,1) ma ix Hnso ha Hn·HT n=nI. Equi alen ly, a Hadama d ma ix is a squa e ma ix o e {1,−1}so ha i s ows a e pai wise o hogonal. The knowledge o Hadama d ma ices is a majo ques ion o applica ions in a wide ange o diffe en disciplines, as in he design o good (e en op imal) e o - co ec ing codes mee ing he Plo kin bounds (see [15] o de ails). A classical e e ence on Hadama d ma ices and hei uses is [9]. I may be easily p o ed ha he size no a Hadama d ma ix Hnmus be 1, 2 o a mul iple o 4. I is conjec u ed ha such a Hnexis s o all ndi isible by 4. Howe e , he p oo o his conjec u e emains an impo an p oblem in Coding Theo y, since he e is no e idence o his ac un il now. In ac , he e a e infini ely many o de s mul iple o ou o which unce ain y abou he exis ence o hese ma ices has no been emo ed a all. Fu he mo e, e en in he case ha a Hadama d ma ix is known o exis o a gi en o de n=4 , he e is no algo i hm a ailable which ou pu s a Hadama d ma ix o his o de 4 in easonable ime, as i is poin ed ou in [14]. The cocyclic amewo k conce ning Hadama d ma ices was in oduced in he 90s [12,13] as a p omising con ex o sol e he ques ions abo e. A cocyclic ma ix M o e a fini e g oup G={g1,...,g 4 }o o de |G|=4 consis s in a ma ix M=( (gi,g j)), :G×G→{1,−1}being a 2-cocycle o e Gwi h coefficien s in {1,−1},so ha (gi,g j) (gigj,g k)= (gj,g k) (gi,g jgk),∀gi,g j,g k∈G All au ho s a e pa ially suppo ed by he esea ch p ojec s FQM–296 and P07– FQM–02980 om JJAA and MTM2008-06578 om MICINN (Spain). The link be ween cocyclic and Hadama d ma ices was fi s no iced in [12]. A mo e ecen e e ence is [11], in which many o he classical and mo e e- cen ly disco e ed cons uc ions o Hadama d ma ices a e shown o be cocyclic. This suppo he idea ha cocyclic cons uc ion is he mos uni o m cons uc- ion echnique o Hadama d ma ices ye known. Consequen ly, he cocyclic Hadama d Conjec u e a ises in u n. The main ad an ages o wo king wi h cocyclic Hadama d ma ices may be esumed in he ollowing ac s: –The cocyclic Hadama d es (which claims ha i suffices o check whe he he summa ion o e e y ow bu he fi s is ze o, see [13] o de ails) uns in O( 2) ime, be e han he O( 3) algo i hm o usual (no necessa ily cocyclic) Hadama d ma ices. –The sea ch space is educed o he se o cocyclic ma ices o e a gi en g oup ( ha is, 2sma ices, p o ided ha a basis o 2-cocycles o e Gconsis s o sgene a o s), ins ead o he whole se o ⎛ ⎝4 2  4 −1 ⎞ ⎠ma ices wi h en ies in {−1,1}consis ing o he ow (1, ...,1) and 4 −3 ec o s o leng h 4 o hogonal o (1, ...,1). In pa icula , he wo k in [5] sugges ha he cocyclic amewo k (c. . in he able below) may educe significan ly he size o he sea ch space in he gene al amewo k (g. . o b e i y) case, as he able below indica es: 1 2 3 4 5 6 7 8 c. . O(100)O(101)O(102)O(103)O(105)O(106)O(107)O(108) g. . O(101)O(109)O(1024)O(1049)O(1082)O(10125)O(10177)O(10238) Conside able effo has been de o ed o he design o efficien algo i hms o cons uc ing cocyclic Hadama d ma ices. Exhaus i e sea ch is no easible o o de s 4 g ea e han 20 ( he sea ch space g ows exponen ially on ,see[5] o ins ance). Consequen ly, al e na i e me hods a e equi ed. As a as we know, wo diffe en heu is ic me hods ha e been p oposed un il now, in e ms o image es o a ions [6] and gene ic algo i hms [2]. We p esen he e a new gene ic algo i hm o cons uc ing cocyclic Hadama d ma ices. The main diffe ence wi h espec o ha o [2] is a no el heu is ic o ep oduc ion: ins ead o he usual c osso e and mu a ion ope a o s we shall be e use a guided ep oduc ion p ocedu e. Calcula ions in Sec ion 5 sugges ha his new ea u e imp o es he o iginal algo i hm. This heu is ic in ol es he no ions o i-pa hs and in e sec ions in oduced in [5], o be desc ibed u he in Sec ion 2. As i is shown in [5], dihed al g oups seems o be he mos p olific amiliy o g oups gi ing ise o cocyclic Hadama d ma ices. We pa icula ize he algo i hm o he case o hese g oups. We also include some uns o he algo i hm, which ha e been wo ked ou in Ma hema ica 4.0, unning on a Pen ium IV 2.400 Mhz DIMM DDR266 512 MB. A deepe s udy on he way in which 2-cobounda ies o e Gha e o be com- bined in o de o gi e ise o cocyclic Hadama d ma ices (a ending o i-pa hs and in e sec ions, as desc ibed in [5]) would lead o an imp o emen o he pe - o mance o he guided gene ic algo i hm in a s aigh o wa d manne . We o ganize he pape as ollows. Sec ion 2 collec s some gene al no ions and esul s abou cocyclic Hadama d ma ices. The algo i hm looking o co- cyclic Hadama d ma ices equipped wi h he new heu is ic o ep oduc ion is desc ibed in Sec ion 3. Sec ion 4 is de o ed o pa icula ize he algo i hm o he case o dihed al g oup. 2 Gene ali ies abou Cocyclic Hadama d Ma ices Conside a mul iplica i e g oup G={g1=1,g 2,...,g 4 }, no necessa ily abelian. A cocyclic ma ix M o e Gconsis s in a bina y ma ix M =( (gi,g j)) coming om a 2-cocycle o e G, ha is,amap :G×G→{1,−1}such ha (gi,g j) (gigj,g k)= (gj,g k) (gi,g jgk),∀gi,g j,g k∈G. We will only use no malized cocycles (and hence no malized cocyclic ma ices M ), so ha (1,g j)= (gi,1) = 1 o all gi,g j∈G(and co espondingly M =( (gi,g j)) consis s o a fi s ow and column all o 1s). Effec i e me hods o cons uc ing a basis B o 2-cocycles o e a gi en g oup Ga e known ([12,13],[7],[4]). Such a basis consis s o some ep esen a- i e 2-cocycles (coming om infla ion and ansg ession) and some elemen a y 2-cobounda ies ∂i, so ha e e y cocyclic ma ix admi s a unique ep esen a ion as a Hadama d (poin wise) p oduc M=M∂i1...M ∂iw·R, in e ms o some cobounda y ma ices M∂ijand a ma ix R o med om ep esen a i e cocycles. Recall ha e e y elemen a y cobounda y ∂dis cons uc ed om he cha ac- e is ic se map δd:G→{±1}associa ed o an elemen gd∈G,so ha ∂d(gi,g j)=δd(gi)δd(gj)δd(gigj) o δd(gi)=−1gd=gi 1gd=gi(1) Al hough he elemen a y cobounda ies gene a e he se o all cobounda ies, hey migh no be linea ly independen (see [4] o ins ance). Mo eo e , since he ele- men a y cobounda y ∂g1 ela ed o he iden i y elemen in Gis no no malized, we may assume ha ∂g1/∈B. The cocyclic Hadama d es asse s ha a cocyclic ma ix is Hadama d i and only i he summa ion o each ow (bu he fi s ) is ze o [13]. In wha ollows, he ows whose summa ion is ze o a e e med Hadama d ows. We now ep oduce he no ions o gene alized cobounda y ma ix,i-walk and in e sec ion in oduced in Defini ion 2 o [5]. The gene alized cobounda y ma ix ¯ M∂j ela ed o a elemen a y cobounda y ∂jconsis s in nega ing he j h- ow o he ma ix M∂j. No e ha nega ing a ow o a ma ix does no change i s Hadama d cha ac e . As i is poin ed ou in [5], e e y gene alized cobounda y ma ix ¯ M∂jcon ains exac ly wo nega i e en ies in each ow s= 1, which a e loca ed a posi ions (s, i)and(s, e), o ge=g−1 sgi. We will wo k wi h gene alized cobounda y ma ices om now on. Ase {¯ M∂ij:1≤j≤w}o gene alized cobounda y ma ices defines an i-walk i hese ma ices may be o de ed in a sequence ( ¯ Ml1,..., ¯ Mlw)so ha consecu i e ma ices sha e exac ly one nega i e en y a he i h- ow. Such a walk is called an i-pa h i he ini ial and final ma ices do no sha e a common −1, and an i-cycle o he wise. As i is poin ed ou in [5], e e y se o gene alized cobounda y ma ices may be uniquely pa i ioned in o disjoin maximal i-walks. A cha ac e iza ion o Hadama d ows may be easily desc ibed a ending o i-pa hs. P oposi ion 1. [5] The i h ow o a cocyclic ma ix M=M∂i1...M ∂iw·Ris a Hadama d ow i and only i 2ci−2Ii=2 − i(2) whe e cideno es he numbe o maximal i-pa hs in {¯ M∂i1,..., ¯ M∂iw}, icoun s he numbe o −1sin hei h- ow o Rand Iiindica es he numbe o posi ions in which Rand ¯ M∂i1... ¯ M∂iwsha e a common −1in hei i h- ow. F om now on, we will e e o he posi ions in which Rand ¯ M∂i1... ¯ M∂iw sha e a common −1 in a gi en ow simply as in e sec ions, o b e i y. Equa ion (2) is he hea o he guided heu is ic p ocedu e o ep oduc ion which is applied in he gene ic algo i hm desc ibed in his pape . 3 The Algo i hm The gene ic algo i hm desc ibed in [2] and implemen ed in [3] is based upon he na u al e olu ion p inciples o Holland’s [10]: –The popula ion consis s o a subse o 4 cocyclic ma ices M o e G,M = ( (gi,g j)), which a e iden ified o a bina y uple, he coo dina es ( 1,..., s) o he 2-cocycle wi h ega ds o he basis B. Acco dingly, he coo dina es ia e he genes o he indi idual . –The e alua ion unc ion coun s he numbe o Hadama d ows in M : he mo e Hadama d ows M posses, he fi es M is. In pa icula , an indi idual ind gi es ise o a cocyclic Hadama d ma ix i and only i e alua e(ind)= 4 −1. –C osso e combines he ea u es o wo pa en ch omosomes o o m wo simila offsp ing by swapping co esponding segmen s o he pa en s. –Mu a ion a bi a ily al e s jus one gene o a selec ed indi idual ( he mu a- ion a e is fixed in 1%). In he ep oduc ion p ocess, he indi iduals o he popula ion a e pai ed a andom, so ha he applica ion o he c osso e ope a o gi es ise o ano he 4 indi iduals, which a e added o he popula ion. The gene a ion i+1is o med om gene a ion iby choosing he 4 fi es indi iduals a e he ep oduc ion p ocess. We now p opose a diffe en app oach. Ins ead o he usual c osso e and mu a ion ope a o s desc ibed abo e, we shall be e use ano he heu is ic o ep oduc ion. Wi h p obabili y p 1, an indi idual M andomly selec ed om he popula ion gi es ise o 4 −1 child en, so ha he (i+1) h- ow o he i h- child is Hadama d. O he wise he usual c osso e ope a o is used, applied o e wo indi iduals andomly selec ed. Gene a ion Pw+1 is ob ained om gene a ion Pwkeeping he fi es indi iduals and eplacing a se o less fi indi iduals wi h he child en jus cons uc ed, so ha a popula ion o 8 indi iduals is o med. In his p ocess duplica e copies o he same indi idual a e no pe mi ed. Consequen ly, he blinded p ocesses o c osso e and mu a ion a e now sub- s i u ed by a comple ely o ien ed p ocedu e o ep oduc ion: his way i is gua - an eed ha any ime an indi idual exis s such ha i s i h- ow is Hadama d. In o de o gene a e hese child en, he genes o M ha e o be modified so ha equa ion (2) is sa isfied. I is ema kable ha he magni udes ciand Ii depends hea ily on he subse o 2-cobounda ies which gi es ise o M .On he con a y, he magni ude idepends only on he ep esen a i e 2-cocycles implica ed in he gene a ion o M . A ending o hese ac s, a heu is ic p ocedu e o ep oduc ion may be s aigh o wa dly defined in he ollowing way. The key idea is o modi y he genes o M co esponding o 2-cobounda ies in such a manne ha he magni- udes ciand Iia e also modified in u n, so ha he diffe ence 2ci−2Iiis close o he cons an alue 2 − i. Depending on whe he 2ci−2Ii>2 − io 2ci−2Ii<2 − i, we need o inc ease o dec ease Ii( esp. dec ease o inc ease ci) so ha he equali y may hold. Mo e conc e ely: 1. I 2ci−2Ii>2 − i, he algo i hm andomly chooses one o he ollowing possibili ies: –Collapses wo diffe en i-pa hs in o jus one i-pa h, so ha cidec eases 1 uni . –In oduces a new nega i e sha ing posi ion be ween Rand he p oduc o M∂j,so ha Iiinc eases 1 uni . 2. I 2ci−2Ii<2 − i, he algo i hm andomly chooses one o he ollowing possibili ies: –Spli s one i-pa h in o wo diffe en i-pa hs, so ha ciinc eases 1 uni . –Adds a new i-pa h, in oducing a new 2-cobounda y gene a o , so ha ciinc eases 1 uni . –Elimina es a nega i e sha ing posi ion be ween Rand he p oduc o M∂j,so ha Iidec eases 1 uni . The way in which hese p ocedu es ha e o be implemen ed depends on he g oup Go e which 2-cocycles a e conside ed. In he ollowing sec ion we will 1Expe imen al esul s show ha a good alue o he pa ame e p is 0.8. explici ly show a pseudo-code o he pa icula heu is ic p ocedu e o ep oduc- ion in he case o dihed al g oups. The popula ion is expec ed o e ol e gene a ion h ough gene a ion un il an op imum indi idual (i.e. a cocyclic Hadama d ma ix) is loca ed. This has been he case in he examples showed in he las sec ion. We include now a pseudo-code o he algo i hm. Inpu : a g oup (G, ·)o o de |G|=4 Ou pu : some (e en ually one) cocyclic Hadama d ma ices o e G he ini ial popula ion is c ea ed pob ←∅ i ←∅ o i om 1 o 8 { ind ←c ea e new() pob ←pob ∪{ind} i ← i ∪{e alua e(ind)} } p ←0.8 while (max( i )<4 −1){ ep oduc ion s a s i andom(0,1) ≤p hen{ j← andom(1,8 ) indj← he j h-indi idual o pob lis ←guided ep oduc ion(indj) else i← andom(1,8 ) j← andom(1,8 )=i (indi,ind j)← he (i h,j h)-indi iduals o pob lis ←usual ep oduc ion(indi,ind j) } emo e in (pob, i ) hose en ies co esponding o he less size(lis ) i indi iduals o i om 1 o size(lis ){ pob ←pob ∪{lis (i)} i ← i ∪{e alua e(lis (i))} } } Lis he indi iduals in pob mee ing he op imal i ness, 4 −1 Some auxilia unc ions ha e been used, which we desc ibe now: –c ea e new() ou pu s a bina y uple o leng h s(sbeing he dimension o he basis Bo 2-cocycles o e G), each bi andomly gene a ed as 0 o 1 wi h he same p obabili y. A deepe knowledge abou he p ope ies o he g oup Gmigh lead o imp o ed e sions o his p ocedu e. As a ma e o ac , in he case o dihed al g oups, he numbe o 1s should be o ced o 2 ,as he ables in [5] sugges , since he densi y o cocyclic Hadama d ma ices seems o be maximum wi h his a e o 1s. –e alua e(ind) measu es he fi ness o he indi idual ind, ha is, coun s he numbe o he Hadama d ows (i.e. hose whose summa ion is ze o) in he cocyclic ma ix gene a ed by he poin wise p oduc o he ma ices ela ed o he 2-cocycles o Bco esponding o he 1s in ind. In pa icula , an indi idual ind gi es ise o a cocyclic Hadama d ma ix i and only i e alua e(ind)= 4 −1. – andom(min, max) ou pu s a in ege in he ange [min, max] andomly gen- e a ed. –guided ep oduc ion(ind) applies he heu is ic p ocedu e o ep oduc ion on he indi idual ind. The ou pu consis s in 4 −1 new indi iduals, he (i+1) h- ow o he i h-indi idual being Hadama d. –usual ep oduc ion(indi,ind j) applies he usual c osso e ope a o o ep o- duc ion on he indi iduals indiand indj. The ou pu consis s in 2 new indi iduals. 4 Guided Rep oduc ion on Dihed al G oups Deno e by D4 he dihed al g oup ZZ2 ×χZZ2o o de 4 , ≥1, gi en by he p esen a ion <a,b|a2 =b2=(ab)2=1> and o de ing {1=(0,0),a=(1,0),...,a 2 −1=(2 −1,0),b=(0,1),...,a 2 −1b=(2 −1,1)} In [8] a ep esen a i e 2-cocycle o [ ]∈H2(D4 ,ZZ2)∼ =ZZ3 2is w i en in e - changeably as a iple (A, B, K), whe e Aand Ba e he infla ion a iables and Kis he ansg ession a iable. All a iables ake alues ±1. Explici ly, (ai,a jbk)=Aij ,i+j<2 , Aij K, i +j≥2 , (aib, ajbk)=Aij Bk,i≥j, Aij BkK, i < j, Le β1,β2and γdeno e he ep esen a i e 2-cocycles ela ed o (A, B, K)= (−1,1,1),(1,−1,1),(1,1,−1) espec i ely. A basis o 2-cobounda ies is desc ibed in [5], and consis s o he elemen a y cobounda ies {∂a,...,∂ a2 −3b}. This way, a basis o 2-cocycles o e D4 is gi en by B={∂a,...,∂ a2 −3b,β 1,β 2,γ}. We ocus in he case (A, B, K)=(1,−1,−1) ( ha is, R=β2γ), since compu- a ional esul s in [8,5] sugges ha his case con ains a la ge densi y o cocyclic Hadama d ma ices. Fu he mo e, as i is poin ed ou in Theo em 2 o [5], cocyclic ma ices o e D4 using Ra e Hadama d ma ices i and only i ows om 2 o a e Hadama d. We ha e upda ed he gene ic algo i hm in u n, so ha only ows om 2 o a e used in o de o check whe he hei summa ions a e ze o. Acco dingly, he fi ness o an indi idual uns h ough he ange [0, −1]. In o de o define he heu is ic p ocedu e o ep oduc ion we need o know how he 2-cobounda ies in Bha e o be combined o o m i-pa hs, 2 ≤i≤ . This in o ma ion is gi en in P oposi ion 7 o [5]. P oposi ion 2. [5] Fo 1≤i≤2 , a maximal i-walk consis s o a maximal subse in (M∂1,...,M ∂2 )o (M∂2 +1 ,...,M ∂4 ) o med om ma ices (...,M j,M k,...)which a e cyclically sepa a ed in i−1 posi ions ( ha is j±(i−1) ≡kmod2 ). We now ha e enough in o ma ion abou how o combine 2-cobounda ies in Bin o de o modi y he alue o 2ci−2Ii,so ha 2ci−2Ii=2 − i, ha is, he i h- ow o ou indi idual being Hadama d. No ice ha since i=2(i−1) o 2 ≤i≤ , he cocyclic Hadama d es educes o ci−Ii= −i+1, o 2≤i≤ . We include below a pseudo-code o he guided ep oduc ion p ocedu e de- sc ibed in he sec ion be o e, pa icula ized o he case o dihed al g oups. Inpu : an indi idual ind o he popula ion Ou pu : a lis newpob o 4 −1indi iduals, he (i+1) h- ow o he i h-indi idual being Hadama d newpob ←∅ o i om 2 o { ipa hs ←lis wi h he maximal i-pa hs na u ally ela ed o ind c←size o ipa hs in e sec ←in e sec ing posi ions o −1s in he i h- ow o ind I←size o in e sec while c−I= −i+1{ i c−I> −i+1{ ind ←dec ease(ipa hs, in e sec, i −1, andom(1,2)) else{ ind ←inc ease(ipa hs, in e sec, i −1, andom(1,3)) } ecompu e he alues ipa hs,c,in e sec and I ela ed o ind } newpob ←newpob ∪{ind} } newpob Some auxilia unc ions ha e been used, which we desc ibe now: –dec ease(ipa hs, in e sec, i −1,j) ies o dec ease he alue c−I, ha is, size(ipa hs)−size(in e sec). This unc ion ac s in a diffe en way, depending on he alue o 1 ≤j≤2: •dec ease(ipa hs, in e sec, i−1,1) ou pu s an indi idual ind wi h exac ly size(ipa hs)−1i-pa hs. Mo e conc e ely, i ex ends one o he i-pa hs (say p1, andomly selec ed) in ipa h o he le , un il his i-pa h is con- nec ed o a p e iously exis en i-pa h, say p2. The e a e wo possibili ies now: i p1=p2, henp1and p2ha e been me ged in o a solely pa h. On he con a y, i p1=p2, henp1has been ex ended o o m a i-cycle. In bo h cases, we ha e effec i ely gene a ed a new indi idual consis ing o size(ipa hs)−1i-pa hs. •dec ease(ipa hs, in e sec, i −1,2) ou pu s an indi idual ind wi h ex- ac ly size(in e sec) + 1 in e sec ions. I suffices o andomly choose a 2-cobounda y sha ing a nega i e en y wi h Rin he i h- ow, in case ha i exis s. O he wise he unc ion dec ease(ipa hs, in e sec, i −1,1) should be called. –inc ease(ipa hs, in e sec, i −1,j) ies o inc ease he alue c−I, ha is, size(ipa hs)−size(in e sec). This unc ion ac s in a diffe en way, depending on he alue o 1 ≤j≤3: •inc ease(ipa hs, in e sec, i −1,1) ies o inc ease he numbe o he i-pa hs in ipa hs, by spli ing an exis en i-pa h in o wo diffe en i- pa hs. This is only possible o i-pa hs consis ing o a leas h ee 2- cobounda ies. I i is he case, i suffices o dele e any 2-cobounda y diffe en om he ex emes o he i-pa h. I no , he unc ion inc ease(ipa hs, in e sec, i −1,1+ andom(1,2)) is called. •inc ease(ipa hs, in e sec, i −1,2) ies o inc ease he numbe o he i-pa hs in ipa hs, by adding a new i-pa h in ipa hs which does no ex end any o he p e iously exis en i-pa hs. This is only possible i a 2-cobounda y exis s such ha i is no adjacen o any o he i-pa hs in ipa hs. I i is no he case, he unc ion inc ease(ipa hs, in e sec, i −1,2+(−1) andom(1,2)) is called. •inc ease(ipa hs, in e sec, i −1,3) ies o c ea e an indi idual ind wi h size(in e sec)−1 in e sec ions. I suffices o andomly dele e a 2-coboun- da y sha ing a nega i e en y wi h Rin he i h- ow,incase ha i exis s. O he wise he unc ion inc ease(ipa hs, in e sec, i −1, andom(1,2)) is called.