Embedding cocylic D-optimal designs in cocylic Hadamard matrices

Elec onic Jou nal o Linea Algeb a Volume 24 ELA Volume 24 (2012/2013) A icle 7 2012 Embedding cocylic D-op imal designs in cocylic Hadama d ma ices Vic o Al a ez Jose And es A ma io a ma [email protected] Ma ia Dolo es F au Felix Guidiel Follow his and addi ional wo ks a : h p:// eposi o y.uwyo.edu/ela This A icle is b ough o you o ee and open access by Wyoming Schola s Reposi o y. I has been accep ed o inclusion in Elec onic Jou nal o Linea Algeb a by an au ho ized edi o o Wyoming Schola s Reposi o y. Fo mo e in o ma ion, please con ac [email protected]. Recommended Ci a ion Al a ez, Vic o ; A ma io, Jose And es; F au, Ma ia Dolo es; and Guidiel, Felix. (2012), "Embedding cocylic D-op imal designs in cocylic Hadama d ma ices", Elec onic Jou nal o Linea Algeb a, Volume 24. DOI: h ps://doi.o g/10.13001/1081-3810.1580 ELA EMBEDDING COCYCLIC D-OPTIMAL DESIGNS IN COCYCLIC HADAMARD MATRICES∗ V´ ICTOR ´ ALVAREZ†, JOS´ E ANDR´ ES ARMARIO†, MAR´ IA DOLORES FRAU†,AND F´ ELIX GUDIEL† Abs ac . A me hod o embedding cocyclic subma ices wi h “la ge” de e minan s o o de s 2 in ce ain cocyclic Hadama d ma ices o o de s 4 is desc ibed ( an odd in ege ). I hese de e minan s a ain he la ges possible alue, we a e embedding D-op imal designs. Applica ions o he pi o alues ha appea when Gaussian elimina ion wi h comple e pi o ing is pe o med on hese cocyclic Hadama d ma ices a e s udied. Key wo ds. D-op imal Designs, Cocyclic Hadama d ma ices, Embedded ma ices, Gaussian elimina ion pi o s. AMS subjec classi ica ions. 05B20, 15A15, 65F40, 65F05. 1. In oduc ion. AHadama d ma ix Ho o de nis an n×nma ix wi h elemen s ±1 and HHT=nI. A Hadama d ma ix is said o be no malized i i has i s i s ow and column all ones. We can always no malize a Hadama d ma ix by mul iplying ows and columns by −1. These ma ices mus ha e o de 1, 2 o a mul iple o 4. I is conjec u ed ha Hadama d ma ices exis o e e y n≡0 (mod 4). Al hough no p oo o his ac is known, he e is much e idence abou i s alidi y (see [19] and he e e ences he e ci ed). Two Hadama d ma ices H1and H2a e called equi alen (o Hadama d equi - alen , o H-equi alen ) i one can be ob ained om he o he by a sequence o ow and/o column in e changes and ow and/o column nega ions. The ques ion o clas- si ying Hadama d ma ices o o de n > 28 emains unanswe ed and only pa ial esul s a e known [6, 20]. P oblems in ol ing Hadama d ma ices sound e y easy, bu hey a e no o iously di icul o sol e. One in e es ing open p oblem, among o he s, is he ques ion o he la ges pi o encoun e ed du ing he p ocess o Gaussian elimina ion (GE) wi h comple e pi o ing o an n×nHadama d ma ix H( he so called “g ow h ac o ” o H). T adi ionally, backwa d e o analysis o Gaussian elimina ion (GE), see e.g. ∗Recei ed by he edi o s on No embe 23, 2011. Accep ed o publica ion on Ma ch 24, 2012 Handling Edi o : Oska Ma ia Baksala y. †Depa men o Applied Ma h I, Uni e si y o Se ille, A da. Reina Me cedes s/n, 41012 Se ille, Spain ({ al a ez,a ma io,md au,gudiel}@us.es). 66 Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA Embedding cocyclic D-op imal designs in cocyclic Hadama d ma ices 67 [8], on a ma ix A=ha(1) ij iis exp essed in e ms o he g ow h ac o g(n, A) = maxi,j,k |a(k) ij | maxi,j |a(1) ij | which in ol es all he elemen s a(k) ij , k = 1,2,...,n, ha occu du ing he elimina ion o a choice o pi o ing s a egy gi en. Ma ices wi h he p ope y whe e no ow and column exchanges a e needed du ing GE wi h comple e pi o ing a e called comple ely pi o ed (CP) o easible. In o he wo ds, a each s ep o he elimina ion he elemen o la ges magni ude ( he “pi o ”, deno ed by pk) is loca ed a he op le posi ion o e e y appea ing subma ix du ing he p ocess. I A(k) deno es he absolu e alue o k×kp incipal mino o A, hen ma hema ically Abeing CP means (o is equi alen o) ha o each k, we ha e ha A(k) is g ea e han o equal o he absolu e alue o any o he k×kde e minan ha includes he i s k−1 ows and columns. This is no necessa ily he maximum k×kmino o A, bu only he maximum k×kmino o Awhen i s i s k−1 ows and columns a e ixed. Fo a CP ma ix Awe ha e g(n, A) = max{p1, p2,...,pn} |a(1) 11 |. I a ma ix is no ini ially CP, by applying ow and column ope a ions wi h comple e pi o ing we can always b ing i o CP o m. The ollowing lemma gi es a use ul ela ion be ween pi o s and mino s. Lemma 1.1. [7] Le Abe a CP ma ix. The magni ude o he pi o s which appea a e applica ion o GE ope a ions o Ais gi en by pj=A(j) A(j−1), j = 1,2, . . . , n, A(0) = 1. In 1969, C ye [7] conjec u ed ha i Ais a eal n×nma ix such ha |ai,j | ≤ 1, hen g(n, A)≤n, wi h equali y i and only i Ais a Hadama d ma ix. In 1991 Gould [15] p o ed ha he i s pa o he conjec u e is no ue. He ound ma ices wi h g ow h bigge han hei o de s. Thus, he ollowing emains open: Conjec u e(C ye ) The g ow h o a Hadama d ma ix is i s o de . This conjec u e has been p o en only o n= 4,8,12 and 16 (see [7, 10, 23]). G ea di icul y a ises in he s udy o his p oblem because H-equi alence ope a ions do no p ese e pi o s, i.e. he H-equi alen ma ices do no necessa ily ha e he same Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA 68 V. ´ Al a ez, J.A. A ma io, M.D. F au, and F. Gudiel pi o pa e n. Fo ins ance, o n= 16 he e a e 34 pi o pa e ns al hough he e a e only 5 equi alence classes o Hadama d ma ices o his o de . Fu he mo e, many pi o pa e ns can be obse ed by pe mu ing he ows and columns o any 20 by 20 Hadama d ma ix and he e a e jus 3 inequi alen ma ices. Howe e , he exis ence o D-op imal designs (and o he speci ic subma ices wi h conc e e de e minan s) ha exis embedded in a Hadama d ma ix ha e p o ided some clues on he pi o pa e ns (see [27, 25]). AD-op imal design o o de nis an n×n(1,−1)-ma ix ha ing maximal de e - minan . He e and h oughou his pape , o con enience, whene e a de e minan o mino is men ioned, we mean i s absolu e alue. The ques ion o inding he de e - minan o a D-op imal design o o de nis an old one which emains unanswe ed in gene al. In 1893 Hadama d p o ed in [16] ha o e e y (−1,1)-ma ix M, de (M)≤nn 2.(1.1) We ecall ha he o iginal in e es in Hadama d ma ices s emmed om he ac ha hese ma ices a e he only ones ha sa is y equali y in (1.1). This has led o u he s udy and igh e bounds o he maximal de e minan o all (−1,1)-ma ices o o de n6= 0 (mod 4) ha e been ound (see [5, 11, 12, 29, 21]). Fo ins ance, when n≡2 (mod 4), Ehlich in [11] and independen ly Woj as in [29] p o ed ha de (M)≤(2n−2)(n−2)n−2 2.(1.2) In o de o equali y o hold, i is equi ed ha he e exis s a (−1,1)-ma ix Mo o de nsuch ha MMT=L0 0L, whe e L= (n−2)In 2+2Jn 2. He e, as usual, In deno es he iden i y ma ix o o de n, and Jndeno es he n×nma ix all o whose en ies a e equal o one. In hese ci cums ances, i may be p o en ha , in addi ion, 2n−2 is he sum o wo squa es, a condi ion which is belie ed o be su icien (o de 138 is he lowes o which he ques ion has no been se led ye , [14]). In he ea ly 90s, a su p ising link be ween homological algeb a and Hadama d ma ices [17] led o he s udy o cocyclic Hadama d ma ices [18]. Hadama d ma ices o many ypes a e e ealed o be (equi alen o) cocyclic ma ices [9, 19]. Among hem, Syl es e Hadama d ma ices, Williamson Hadama d ma ices, I o Hadama d ma ices and Paley Hadama d ma ices. Fu he mo e, he cocyclic cons uc ion is he mos uni o m cons uc ion echnique o Hadama d ma ices cu en ly known, and cocyclic Hadama d ma ices may consequen ly p o ide a uni o m app oach o he amous Hadama d conjec u e. Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA Embedding cocyclic D-op imal designs in cocyclic Hadama d ma ices 69 The main ad an ages o he cocyclic amewo k conce ning 4 by 4 Hadama d ma ices may be summa ized in he ollowing ac s: •The es o decide whe he a cocyclic ma ix is Hadama d uns in O( 2) ime, be e han he O( 3) algo i hm o usual (no necessa ily cocyclic) 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 cocycles o e Gconsis s o s gene a o s), ins ead o he whole se o 216 2ma ices o o de 4 wi h en ies in {−1,1}. I was shown in [1] ha he cocyclic echnique can ce ainly be ex ended o handle he maximal de e minan p oblem a leas when n≡2 (mod 4). Mo e conc e ely, he s udy ocused on cocyclic ma ices o e he dihed al g oup o 2 elemen s wi h odd. Based on exhaus i e and heu is ic sea ches, h ee algo i hms o cons uc ing cocyclic ma ices wi h la ge de e minan s we e p o ided. In his pape we a e in e es ed in embedding (cocyclic) subma ices o o de s 2 wi h la ge de e minan s in ce ain cocyclic Hadama d ma ices o o de s 4 . I hese de e minan s a ain he la ges possible alue, we a e embedding D-op imal designs. Also, we discuss he ela ion be ween he exis ence o hese subma ices and he g ow h ac o o hese Hadama d ma ices. In Sec ion 2, an algeb aic o malism (in e ms o cocycles) o desc ibe wo com- bina o ial ope a ions on a ma ix (elimina e and add ce ain ows and columns) is p o ided. As a consequence o his o malism a me hod a ises o embedding (co- cyclic) subma ices o o de s 2 wi h la ge de e minan s in ce ain cocyclic Hadama d ma ices o o de s 4 . In Sec ion 3, we connec he exis ence o speci ic ma ices em- bedded in cocyclic Hadama d ma ices o o de 20 wi h he alues o he pi o s ha appea when we pe o m Gaussian elimina ion wi h comple e pi o ing on hem. The las sec ion is de o ed o conclusions and u u e wo k. No a ion. Th oughou his pape we use − o −1 and 1 o +1. We w i e H o a Hadama d ma ix and Dj o a D-op imal design o o de j. The no a ion Dj∈H means Djis embedded in H. 2. Cocyclic D-op imal designs embedded in Cocyclic Hadama d ma- ices. Assume h oughou ha G={g1= 1, g2,...,gn}is a mul iplica i e g oup, no necessa ily abelian. Func ions ψ:G×G→ h−1i∼ =Z2which sa is y ψ(gi, gj)ψ(gigj, gk) = ψ(gj, gk)ψ(gi, gjgk),∀gi, gj, gk∈G(2.1) a e called (bina y) cocycles (o e G) [22]. A cocycle is a cobounda y ∂φ i i is de i ed om a se mapping φ:G→ h−1iby ∂φ(a, b) = φ(a)φ(b)φ(ab)−1. A cocycle ψis na u ally displayed as a cocyclic ma ix (o G-ma ix) Mψ; ha is, Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA 70 V. ´ Al a ez, J.A. A ma io, M.D. F au, and F. Gudiel he en y in he (i, j) h posi ion o he cocyclic ma ix is ψ(gi, gj), o all 1 ≤i, j ≤n. A cocycle ψis no malized i ψ(1, gj) = ψ(gi,1) = 1 o all gi, gj∈G. The cocyclic ma ix coming om a no malized cocycle is called no malized as well. Each unno malized cocycle ψde e mines a no malized one −ψ, and ice e sa. The e o e, we may educe, wi hou loss o gene ali y, o he case o no malized cocycles. The se o cocycles o ms an abelian g oup Z(G) unde poin wise mul iplica ion, and he cobounda ies o m a subg oup B(G). A basis B o cocycles o e Gconsis s o some elemen a y cobounda ies ∂iand some ep esen a i e cocycles, 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,1}associa ed wi h an elemen gd∈G, so ha ∂d(gi, gj) = δd(gi)δd(gj)δd(gigj) o δd(gi) = −1gd=gi, 1gd6=gi. Rema k 2.1. ([2, Lemma 1]) In pa icula , o d6= 1, e e y ow s /∈ {1, d}in M∂dcon ains p ecisely wo −1s, which a e loca ed a he posi ions (s, d)and (s, e), o ge=g−1 sgd. Fu he mo e, he i s ow is always o med by 1s, while he d- h ow is o med all by −1s, excep in he posi ions (d, 1) and (d, d). 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 [3] o de ails). Le G (M) ( esp. Gc(M)) be he G am ma ix o he ows ( esp. columns) o M, G (M) = MMT,( esp. Gc(M) = MTM). The G am ma ices o a cocyclic ma ix can be calcula ed as ollows. P oposi ion 2.2. ([19, lemma 6.6]) Le Mψbe a cocyclic ma ix, [G (Mψ)]ij =ψ(gig−1 j, gj)X g∈G ψ(gig−1 j, g),(2.2) [Gc(Mψ)]ij =ψ(gi, g−1 igj)X g∈G ψ(g, g−1 igj).(2.3) Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA Embedding cocyclic D-op imal designs in cocyclic Hadama d ma ices 71 I a cocyclic ma ix Mψis Hadama d, we say ha he cocycle in ol ed, ψ, is o hogonal and Mψis a cocyclic Hadama d ma ix. The cocyclic Hadama d es asse s ha a no malized cocyclic ma ix is Hadama d i and only i e e y ow sum (apa om he i s ) is ze o [18]. In ac , his is a s aigh o wa d consequence o P oposi ion 2.2. Analyzing his ela ion om a new pe spec i e, one could hink o no malized cocyclic ma ices mee ing he bound (1.1) as no malized cocyclic ma ices o which e e y ow sum is ze o. Could i be possible ha such a ela ion ansla es somehow o he case n≡2 (mod 4)? We p o ed in [1] ha , in ac , he answe o his ques ion is a i ma i e. A na u al way o measu e i he ows o a no malized cocyclic ma ix M= [mij ] a e close o sum ze o, is o de ine an absolu e ow excess unc ion RE, such ha RE(M) = n X i=2  n X j=1 mij  . This is a na u al ex ension o he usual no ion o excess o a Hadama d ma ix, E(H), which consis s in he summa ion o he en ies o H. Wi h his de ini ion a hand, i is e iden ha a cocyclic ma ix Mis Hadama d i and only i RE(M) = 0. Tha is, a cocyclic ma ix Mmee s (1.1) i and only i RE(M) is minimum. This condi ion may be gene alized o he case n≡2 (mod 4). Fo he emainde o he pape deno es an odd posi i e in ege . P oposi ion 2.3. [1] Le Mbe a no malized cocyclic ma ix o e Go o de n= 2 . Then RE(M)≥2 −2. Bu we may go e en u he . Ha ing he minimum possible alue 2 −2 is a necessa y condi ion o a cocyclic ma ix M o mee he bound (1.2). P oposi ion 2.4. [1] I a cocyclic ma ix Mo o de n= 2 mee s he bound (1.2), hen RE(M) = 2 −2. Un o una ely, al hough ha ing minimum absolu e ow excess is a necessa y and su icien condi ion o mee ing he bound (1.1), i is jus a necessa y (bu no su - icien , in gene al, see [1, Table 5] ) condi ion o mee ing he bound (1.2). Bu he e is some empi ical e idence ha ma ices ha ing minimum absolu e ow excess co espond wi h ma ices ha ing la ge de e minan s, see Table 2.1., page 11. F om now on, we ix G=D2mas he dihed al g oup wi h p esen a ion ha, b:am= b2= (ab)2= 1i, wi h o de ing {1, a, . . . , am−1, b, ab, . . . , am−1b}and indexed as Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA 72 V. ´ Al a ez, J.A. A ma io, M.D. F au, and F. Gudiel {1,...,2m}. A basis o cocycles o e D2mconsis s in (see [1, 2]): •Le mbe an odd posi i e in ege . B={∂2,...,∂2m−1, β2}. •Le mbe an e en posi i e in ege . B={∂2,...,∂2m−2, β1, β2, γ}. He e ∂ideno es he cobounda y associa ed wi h he i h-elemen o he dihed al g oup D2m, ha is ai−1 (mod m)b⌊i−1 m⌋. And β1, β2and γa e he ep esen a i e cocycles in cohomology, i.e. he cocyclic ma ices coming om in la ion a e Mβ1=Jm⊗ 1 1 1−and Mβ2=1 1 1−⊗Jm. We use A⊗B o deno ing he usual K onecke p oduc o ma ices, ha is, he block ma ix whose blocks a e aij B. The ansg ession cocyclic ma ix Mγis Mγ=AmAm BmBm o he m×m ma ices Am= (aij) and Bm= (bij) whe e aij =−1i+j > m + 1 1 o he wise, and bij =−1i < j 1 o he wise. I has been obse ed ha cocyclic Hadama d ma ices o e he dihed al g oup mos ly use Mβ2◦Mγand do no use Mβ1(see [3, 13]). In he sequel, we conside only cocyclic Hadama d ma ices o his o m M∂i1◦ · · · ◦ M∂iw◦Mβ2◦Mγ. In wha ollows, he goal is o p o ide an algeb aic o malism (in e ms o co- cycles) o desc ibe wo combina o ial ope a ions on a ma ix: he i s consis ing in elimina ing and he second in adding ce ain ows and columns. Rema k 2.5. D2 is i ially embedded as a subg oup o D4 , he dihed al g oup o 4 elemen s. Conc e ely, i D4 =ha, b:a2 =b2= (ab)2= 1i hen D2 ∼ =ha2, bi ⊂ D4 . P oposi ion 2.6. Le Mψbe a cocyclic ma ix o e D4 , hen he 2 by 2 ma ix ob ained by elimina ing om Mψ he ows and columns indexed wi h an e en numbe is a cocyclic ma ix o e D2 and we deno e i as ˜ Mψ. P oo . On he one hand, aking in o accoun he o de ing ixed abo e, D4 = {1, a, . . ., a2 −1, b, ab, . . . , a2 −1b}, he ows and columns in Mψindexed wi h an odd numbe co espond wi h {1, a2,...,a2 −2, b, a2b, . . . , a2 −2b}=ha2, bi. On he o he hand, i ψ|ha2,bideno es he es ic ion o ψ o he subg oup ha2, bi, hen ψ|ha2,bisa is ies (2.1) o G=ha2, bi∼ =D2 since ψsa is ies (2.1) o G=D4 . Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA Embedding cocyclic D-op imal designs in cocyclic Hadama d ma ices 73 In o he wo ds, ψ|ha2,biis a cocycle o G=ha2, biand ˜ Mψ=Mψ|ha2,bi. Lemma 2.7. Le Mψ1and Mψ2be cocyclic ma ices o e D4 hen ˜ Mψ1·ψ2=˜ Mψ1◦˜ Mψ2, whe e Mψ1·ψ2=Mψ1◦Mψ2. P oo . I is a s aigh o wa d consequence o he poin wise mul iplica ion. F om now on, B={∂2,...,∂4 −2, β1, β2, γ}and ˜ B={˜ ∂2,...,˜ ∂2 −1,˜ β2}deno e a basis o cocycles o D4 and D2 , espec i ely. Lemma 2.8. The ollowing iden i ies hold: ˜ M∂i=(J2 ie en M˜ ∂i+1 2 iodd ,˜ Mβi=(J2 i= 1 M˜ ∂β2i= 2 and ˜ Mγ= −1 2 Y i=1 M˜ ∂2i◦M˜ ∂2 −2i+1 . P oo . The iden i ies abo e ollow by di ec inspec ion. Gi en MψaD4 -ma ix. The ollowing esul desc ibes, in e ms o cocycles, he unique D2 -ma ix ob ained by elimina ing om Mψ he ows and columns indexed wi h an e en numbe . Theo em 2.9. Gi en a D4 -ma ix Mψ=Mα2 ∂2◦ · · · ◦ Mα4 −2 ∂4 −2◦Mk1 β1◦Mk2 β2◦Mk3 γ whe e (α2,...,α4 −2, k1, k2, k3)deno es a conc e e 4 -uple wi h en ies 0 o 1. Then ˜ Mψ=˜ Mα2 ∂2◦ · · · ◦ ˜ Mα4 −2 ∂4 −2◦˜ Mk1 β1◦˜ Mk2 β2◦˜ Mk3 γ = 2 −2 Y j=1 Mα2j+1 ˜ ∂j+1 ◦Mk2 ˜ β2◦  −1 2 Y i=1 M˜ ∂2i◦M˜ ∂2 −2i+1   k3 . P oo . I ollows om Lemmas 2.7 and 2.8. The whole se o D4 -ma ices cons uc ed by adding ce ain ows and columns o a D2 -ma ix M˜ ψis p o ided in he nex heo em. Theo em 2.10. Gi en a D2 -ma ix M˜ ψ=M˜ ∂i1◦ · · · ◦ M˜ ∂iw◦M˜ β2. Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA 80 V. ´ Al a ez, J.A. A ma io, M.D. F au, and F. Gudiel 8×8 ma ices, we ha e ha i is always lesse han o equal o D10(7) = 2560. The e o e, D10(8) = H′(8). •Taking in o accoun ha D9/∈D10, hen he maximum 9 ×9 mino o D10 is lesse han o equal o 12288 ( he second g ea es , see he spec um o he de e minan unc ion [26]). Due o D10(9) = 12288 hen D10(9) = H′(9). Now, aking H′as he CP ex ension o ˆ H, he p oo ollows. Co olla y 3.4. The pi o pa e n (1,2,2,4,3,10/3,16/5,5,24/5,6) o he i s en pi o s appea s in he h ee classes o Hadama d ma ices o o den 20. In a ecen sea ch ha we ha e pe o med, we ha e ound his esul : •The e is a CP ma ix Hequi alen o he ollowing D20-Hadama d ma ix Mψ=M∂2◦M∂4◦M∂8◦M∂10 ◦M∂13 ◦M∂14 ◦Mβ2◦Mγsuch ha H(10) = 125·29. Al hough we didn’ ind any esul in he li e a u e asse ing ha i he exis- ence o a subma ix wi h la ge de e minan is p o en o a ma ix A, hen we can indeed assume ha i always appea s in he uppe le co ne o some CP ma ix A′ equi alen o A. I seems o be ue a leas when his subma ix eaches he la ges de e minan (see [25, p.1763]). Also, he abo e esul con i ms his o o he la ge de e minan ( he second la ges in Table 2.1). 4. Conclusions and u he wo k. In his pape we ha e desc ibed a me hod o embedding a D2 -ma ix in he ows and columns indexed wi h an odd numbe o aD4 -Hadama d ma ix whene e i is possible. I his D2 -ma ix has a de e minan a aining he la ges possible alue, we ge a D-op imal design. This me hod elies on wo combina o ial ope a ions on a cocyclic ma ix: elimina e and add ce ain ows and columns. The idea behind his app oach has been o ansla e hese wo combina o ial ope a ions in o a pu e algeb aic amewo k (conc e ely, in e ms o cocycles). Finally, ou s udy has p o ided some in o ma ion abou he pi o alues when Gaussian elimina ion wi h comple e pi o ing is pe o med on D20-Hadama d ma ices. Ou nex goals a e: •S udy he ela ionship be ween he RE and he alues o he de e minan o D2 -ma ices. •Design heu is ic sea ches based on RE o Algo i hm 2.12. •S udy i ˜ Mψsa is ies ha de ( ˜ Mψ) (4 −2)(2 −2) −1≥0.85 implies ha a CP ma ix M equi alen o Mψexis s such ha M(2 ) = de ( ˜ Mψ). •S udy he pi o s uc u e o D4 -Hadama d ma ices. •Design an “e icien ” me hod o cons uc D4 -Hadama d ma ices om D2 - ma ices. Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA Embedding cocyclic D-op imal designs in cocyclic Hadama d ma ices 81 Acknowledgmen . This wo k has been pa ially suppo ed by he esea ch p ojec s FQM-016 and P07-FQM-02980 om JJAA and MTM2008-06578 om MIC- INN (Spain) and FEDER (Eu opean Union). The au ho s would also like o hank K is een Cheng o he eading o his a icle. REFERENCES [1] V. ´ Al a ez, J.A. A ma io, M.D. F au and F. Gudiel. The maximal de e minan o cocyclic (−1,1)-ma ices o e D2 .Linea Algeb a Appl., 436:858–873, 2011. [2] V. ´ Al a ez, J.A. A ma io, M.D. F au and P. Real. A sys em o equa ions o desc ibing cocyclic Hadama d ma ices. J. Comb. Des., 16:276–290, 2008. [3] V. ´ Al a ez, J.A. A ma io, M.D. F au and P. Real. The homological educ ion me hod o compu ing cocyclic Hadama d ma ices. J. Symb. Compu ., 44:558-570, 2009. [4] J.A. A ma io. On an inequi alence c i e ion o cocyclic Hadama d ma ices. C yp og . Com- mun., 2:247–259, 2010. [5] G. Ba ba. In o no al eo ema di Hadama d sui de e minan i a ol e massimo. Gio nale di Ma ema iche di Ba aglini, 71:70–86, 1933. [6] R. C aigen and H. Kha aghani. Hadama d ma ices and Hadama d designs. In: Handbook o Combina o ial Designs, 2nd edn., Chapman and Hall/CRC p ess, Boca Ra on, 273–280, 2006. [7] C. W. C ye . Pi o size in Gaussian elimina ion. Nume . Ma h., 12:335–345, 1968. [8] J. Day and B. Pe e son. G ow h in Gaussian elimina ion. Ame . Ma h. Mon hly, 95:489–513, 1988. [9] W. de Launey and K.J. Ho adam. A weak di e ence se cons uc ion o highe dimensional designs. Des. Codes C yp og . 3:75–87, 1993. [10] A. Edelman and W. Masca enhas. On he comple e pi o ing conjec u e o a Hadama d ma ix o o de 12. Linea and Mul ilinea Algeb a, 38:181–187, 1995. [11] H. Ehlich. De e mian enabsch¨a zungen ¨u bin¨a e Ma izen. Ma h. Z., 83:123–132, 1964. [12] H. Ehlich. De e mian enabsch¨a zung ¨u bin¨a e Ma izen mi n≡3 (mod 4). Ma h. Z., 84:438–447, 1964. [13] D. L. Flanne y. Cocyclic Hadama d ma ices and Hadama d g oups a e equi alen . J. Algeb a, 192:749–779, 1997. [14] R. J. Fle che , C. Koukou inos and J. Sebe y. New skew-Hadama d ma ices o o de 4 ·59 and new D-op imal designs o o de 2 ·59. Disc e e Ma h., 286:252–253, 2004. [15] N. Gould. On g ow h in Gaussian elimina ion wi h pi o ing. SIAM J. Ma ix Anal. Appl., 12:354–361, 1991. [16] J. Hadama d. R´esolu ion d’une ques ion ela i e aux d´e e minan s. Bull. des Sciences Ma h., (2) 17:240–246, 1893. [17] K.J. Ho adam and W. de Launey. Cocyclic de elopmen o designs. J. Algeb aic Combin., 2:267–290, 1993; E a um: J. Algeb aic Combin., 3:129, 1994. [18] K.J. Ho adam and W. de Launey. Gene a ion o Cocyclic Hadama d ma ices. In: Compu a- ional algeb a and numbe heo y. Ma h. Appl., Kluwe Acad. Publ, Do d ech , 279–290, 1995. [19] K.J. Ho adam. Hadama d Ma ices and Thei Applica ions. P ince on Uni e si y P ess, P ince- on, NJ, 2007. [20] H. Kha aghani and B. Tay eh-Rezaie. On he classi ica ion o Hadama d ma ices o o de 32. J. Comb. Des., 18:328-336, 2010. [21] C. Koukou inos, M. Mi oulli and J. Sebe y. Bounds on he Maximum De e minan o (−1,1) Ma ices. Bulle in o he ICA, 29:39–48, 2000. Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela ELA 82 V. ´ Al a ez, J.A. A ma io, M.D. F au, and F. Gudiel [22] S. MacLane. Homology. Classics in Ma hema ics Sp inge -Ve lang, Be lin, 1995, Rep in o he 1975 edi ion. [23] K. K a a i is and M. Mi ouli. The g ow h ac o o a Hadama d ma ix o o de 16 is 16. Nume . Linea Algeb a Appl., 16:715–743, 2009. [24] H. Kha aghani and W. O ick. D-op imal ma ices. In: Handbook o Combina o ial Designs, 2nd edn., Chapman and Hall/CRC p ess, Boca Ra on, 317–321, 2006. [25] M. Mi ouli. D-op imal designs embedded in Hadama d ma ices and hei e ec on he pi o pa e ns. Linea Algeb a Appl., 434:1761–1772, 2011. [26] W. O ick and B. Solomon. The Hadama d Maximal De e minan P oblem. (websi e), h p://www.indiana.edu/∼maxde /. [27] J. Sebe y and M. Mi ouli. Some Rema ks on Hadama d ma ices. C yp og . Commun., 2:293–306, 2010. [28] J. Sebe y, T. Xia, C. Koukou inos and M. Mi ouli. The maximal de e minan and subde e - minan s o ±1 ma ices. Linea Algeb a Appl., 373:297–310, 2003. [29] W. Woj as. On Hadama d’s inequalli y o he de e minan s o o de non-di isible by 4. Colloq. Ma h., 12:73–83, 1964. Elec onic Jou nal o Linea Algeb a ISSN 1081-3810 A publica ion o he In e na ional Linea Algeb a Socie y Volume 24, pp. 66-82, June 2012 h p://ma h. echnion.ac.il/iic/ela