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