The maximal de e minan o cocyclic (−1, 1)-Ma ices
o e D2
V. Ál a ez , J.A. A ma io ∗ ,M.D.F au,F. Gudiel
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
ABSTRACT
AMS classi ica ion:
05B20
05B30
15A15
Keywo ds:
Cocyclic ma ices
Maximal de e minan s
D-op imal designs
G am ma ices
Cocyclic cons uc ion has been success ully used o Hadama d
ma ices o o de n.These (−1, 1)-ma ices sa is y ha HHT = HT
H = nI and gi e he solu ion o he maximal de e minan p oblem
whenn = 1, 2o amul ipleo 4.In hispape ,weapp oach hemaximal
de e minan p oblem using cocyclic ma ices when n ≡ 2 (mod 4).
Mo e conc e ely, we gi e a e o mula ion o he c i e ion o decide
whe he o no he2 × 2 de e minan wi h en ies ±1 a ains
he Ehlich–Woj as’boundin heD2 -
cocyclic amewo k.Wealsop o ide some algo i hms o
cons uc ing D2 -cocyclic ma ices wi h la ge de e minan s and
some explici calcula ions up o =19.
1. Mo i a ion o he p oblem – in oduc ion
AD-op imal design o o de n is a n×n(1,−1)-ma ix ha ing maximal de e minan . He e and
h oughou his pape , o con enience, when we say de e minan o a ma ix we mean he absolu e
alue o he de e minan . 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 [15] ha o e e y (−1,1)-ma ix M,
de (M)⩽nn
2.(1)
Fu he mo e, Hadama dp o ed ha equali yholdsi andonly i MMT=nI. Ma ices sa is ying his
condi ion a e e med Hadama d ma ices, and mus ha e o de 1, 2 o a mul iple o 4. I is conjec u ed
∗Co esponding au ho .
E-mail add esses: al a [email p o ec ed] (V. Ál a ez), [email p o ec ed] (J.A. A ma io), [email p o ec ed] (M.D. F au), [email p o ec ed] (F. Gudiel).
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).
Tigh e bounds o he maximal de e minan o all (−1,1)-ma ices o o de n= 0(mod 4)a e
known (see [5,11,12,35,23], o ins ance). Fo n≡1(mod 4),Ehlichp o edin[11] ha
de (M)⩽(2n−1)1
2(n−1)n−1
2.(2)
Mo eo e , equali y holds i and only i he e exis s a (−1,1)-ma ix Mo o de nsuch ha MMT=
(n−1)In+Jn(see [5]). He e, as usual, Indeno es he iden i y ma ix o o de n, and Jndeno es he
n×nma ix all o whose en ies en ies a e equal o one. I equali y holds, 2n−1isape ec squa e
(2k+1)2(o equi alen ly, nis he summa ion o wo consecu i e squa es, n=k2+(k+1)2). I has
been conjec u ed ha a ma ix a aining he bound exis s whene e his is he case. Howe e , o de
85 =62+72is he smalles o which his has no been p o en.
Fo n≡2(mod 4),Ehlichin[11] and independen ly Woj as in [35] p o ed ha
de (M)⩽(2n−2)(n−2)n−2
2.(3)
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. In hese ci cums ances, i may be p o ed 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 [13]). To be mo e p ecise, Ehlich p o ed in
[11] ha 2n−2=(n
2−2 )2+(n
2−2s)2, whe e ( esp. s) is he numbe o ows in M om 1 o n
2( esp.
n
2+1 on) o which he i s en y is posi i e. Al e na i ely, Cohn p o ed in [7] ha Mcan be chosen
o he ype M=⎛
⎝
XY
ZW
⎞
⎠,so ha L=XXT+YYT=ZZT+WWT=XTX+ZTZ=YTY+WTW,
0=XZT+YWT=XTY+ZTW, and 2n−2=x2+y2, o x⩾y⩾0, whe e e e y ow sum and
column sum o each o Xand Wis x, each ow sum and each column sum o Yis yand each ow sum
and column sum o Zis −y.
The case n≡3(mod 4)appea s o be he mos di icul one. In spi e o he ac ha he bound (2)
also holds o hese ma ices, Ehlich de i ed a igh e one in [12],
(n−3)n−s
2(n−3+4 )u
2(n+1+4 )
21−u
n−3+4 − ( +1)
n+1+4 ,(4)
whe e s=3 o n=3, s=5 o n=7, s=5o 6 o n=11, s=6 o n=15,19,...,59, and s=7
o n⩾63, =
n
s,n= s + and u=s− .Cohnshowedin[9] ha his numbe is an in ege
only when n=112 2±28 +7 o some in ege . Ne e heless, many o de s allowed by Cohn’s
c i e ion a e uled ou by he Hasse–Minkowski heo em on a ional equi alence o quad a ic o ms
(see [34]). In pa icula , Ehlich’s bound is no achie able o o de 91. The smalles o de o which i
is po encially a ainable is 511.
I is well known ha he Hadama d bound (1) is a ained in ini ely o en, and has o be conside ed
sha pin hissense.In[23] hisques ionwass udied o he emainingbounds,(2),(3)and(4),andsome
lowe bounds we e desc ibed which we e a ained in ini ely o en. Today we know ha he bounds
(1), (2) and (3) a e sha p, in he abo e sense. Ne e heless, i is no known whe he he bound (4)is
sha p in he same sense, o e en i i is achie able beyond n=3. I is concei able ha i is no sha p.
Whena n×nde e minan is ound ha a ains he ele an oneo he abo e bounds,i isimmedia e
ha he maximal de e minan o ha o de is jus he bound i sel . Ne e heless when he uppe
bound is no a ained, inding he maximal n×nde e minan can be exceedingly di icul . Fo n⩽30,
o de s 19, 22, 23, 27 and 29 a e un esol ed. The in e es ed eade is add essed o [20] and he websi e
[30] o u he in o ma ion on wha is known abou maximal de e minan s.
Table 1
P opo ion o inequi alen Hadama d ma ices (cocyclic/gene al amewo k).
n4812162024 28 32 36
#[CH]111 5 3 16 6 100 35
#[H]111 5 3 60 487 ⩾13.7 ×106⩾3·106
#[CH]
#[H]111 1 1 2.67·10−11.23 ·10−2⩽7.29 ·10−6⩽1.16 ·10−5
T adi ionally, ma ices mee ing he bound (1) a e classi ied a ending o Hadama d equi alence,
so ha wo Hadama d ma ices a e equi alen i and only i one can be con e ed in o he o he by a
sequence o pe mu a ions o ows and columns, and nega ions o ows and columns. This classi ica ion
p oblem ansla esna u ally o hecaseo he emainingbounds.Theclassi ica iono (−1,1)-ma ices
achie ing he maximal de e minan emains as an unanswe ed ques ion in gene al. Wha is known
(see [19,29,21] o de ails), is ha he e is only one equi alence class o D-op imal designs o each o
heo de sup on=15, excep o n=11. And he e a e 3 equi alence classes o n=11, 5 o n=16,
3 o n=17,18,20, 7 o n=21, 60 o n=24, 78 o n=25 and 487 o n=28. Fo upda es on
he lowe bounds o he numbe o equi alence classes o o he o de s, isi hese websi es [22,30].
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]. As was in oduced be o e, a Hadama d ma ix o o de
4 is a (−1,1)squa e 4 ×4 ma ix such ha i s dis inc ow ( esp. column) ec o s a e pai wise
o hogonal. A Hadama d ma ix is said o be no malized i i has i s i s ow and column all o 1’s (see
[19] o mo e de ails and cons uc ions me hods).
Hadama d ma ices o many ypes a e e ealed o be (equi alen o) cocyclic ma ices [10,19].
Among hem, Syl es e Hadama d ma ices, Williamson Hadama d ma ices, I o Hadama d ma ices
andPaleyHadama dma ices.Fu he mo e, hecocycliccons uc ionis hemos uni o mcons uc ion
echnique o Hadama dma icescu en lyknown,andcocyclicHadama dma icesmayconsequen ly
p o ide a uni o m app oach o he amous Hadama d conjec u e.
Themainad an ageso hecocyclic amewo kconce ningHadama dma icesmaybesumma 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 sgene a o s), ins ead o he whole se o 216 2
ma ices o o de 4 wi h en ies in {−1,1}.
Now an in e es ing ques ion a ises, is i be e o look o Hadama d ma ices in he gene al ame-
wo k o in he cocyclic con ex ins ead?
A ecen wo k o Ó Ca háin and Röde (see [27] o de ails) has pe mi ed he calcula ion o he
exac numbe #[CH]o inequi alen cocyclic Hadama d ma ices, o o de s less han 40. This way, a
compa ison in e ms o he o al numbe #[H]o inequi alen Hadama d ma ices is easible, up o
o de 36 (see Table 1). He e we ha e aken in o accoun he wo k o Kha aghani and Tay eh-Rezaie in
[21], abou he numbe o equi alence classes o Hadama d ma ices o o de 32.
No ice ha a cocyclic Hadama d ma ix may be Hadama d equi alen o a ma ix which is no
cocyclic a all. The cocyclic cha ac e is no p ese ed by Hadama d equi alence, in gene al.
F om Table 1, i seems ha whe eas inc eases he quo ien #[CH]
#[H]be ween he numbe o in-
equi alen cocyclic Hadama d ma ices and he numbe o inequi alen Hadama d ma ices dec eases
d as ically. Ne e heless, his compa ison is somehow biassed, since he se o Hadama d ma ices is
no uni o mly dis ibu ed among he equi alence classes. I we a end o he summa ion o he num-
be o Hadama d ma ices equi alen o a ma ix o [H]and [CH]in Table 1, deno ed by #Hand #CH
espec i ely ( he equi ed in o ma ion may be ex ac ed om [27] and [32]),weob ainTable2.
No ice ha he numbe #Ho Hadama d ma ices o a gi en o de , and he numbe #[H]o equi a-
lence classes in which heydis ibu e, a e linked by he no ion o mass. The mass o Hadama d ma ices
o a gi en o de is de ined o be he sum o he ecip ocals o he sizes o he au omo phism g oups o e
Table 2
P opo ion o Hadama d ma ices belonging o equi alence classes [CH]and [H].
n4 8 12 16 20 24 28
#CH 192 21,504 190,080 10,838,016 16,440 790,224 64,488
#H192 21,504 190,080 10,838,016 16,440 823,616 74,306
#CH
#H1 1 1 1 1 0.9594 0.8678
Table 3
Densi y o D4 -Hadama d ma ices e sus ha o usual Hadama d ma ices.
n4 8 12 16 20 24 28
%H(D4 )3.75 ·10−11.25 ·10−11.76 ·10−21.17 ·10−22.1·10−34.46 ·10−44.23 ·10−5
%H2.99 ·10−31.17 ·10−15 8.52 ·10−39 9.36 ·10−71 6.37 ·10−117 3.33 ·10−168 7.30 ·10−232
he equi alence classes o Hadama d ma ices o his o de . This gi es ano he measu e o how many
dis inc Hadama d ma ices he e a e, wi hou ega d o equi alence. See [33, A048615,A048616] o
de ails.
In ac , sea ching o Hadama d ma ices, no ma e he con ex (cocyclic o gene al), is compu a-
ionally a e y ha d ask, as di icul as looking o a needle in a hays ack. Ne e heless, one should
compa e he sizes o he needle and he hays ack o ge an objec i e imp ession abou he di icul y
o inding such a needle in such a hays ack. Thus wha can be said abou he p opo ion o Hadama d
ma ices in he gene al amewo k and in he cocyclic con ex ? Un o una ely, we ha e no in o ma ion
abou he o al numbe o cocyclic ma ices, e en o small alues o .Thewo kin[27] could shed
ligh on his p oblem.
Anyway, we can compa e he amewo k o he usual Hadama d ma ices wi h a conc e e amily o
cocyclic ma ices. Among hem, he mos p oli ic case seems o be dihed al g oups D4 (see [19,3] o
ins ance). Since a basis o no malized cocycles o e D4 consis s o 4 cocycles (see [3], o ins ance),
hen a ull basis o cocycles o e D4 consis so 4 +1 elemen s, and hence he size o he sea ch
space o D4 -cocyclic Hadama d ma ices is 24 +1. The sea ch space o he usual Hadama d ma ices
is he comple e se o (−1,1)-ma ices squa e ma ices o o de 4 , which consis s o 216 2ma ices.
The numbe o D4 -cocyclic Hadama d ma ices o small alues o may be calcula ed p og essing
om he wo k in [2]. Now we can compa e he densi y %H(D4 )o D4 -Hadama d ma ices among D4 -
cocyclic ma ices, and he densi y %Ho usual Hadama d ma ices among he se o (−1,1)-ma ices
o o de 4 .
Undoub edly, he in o ma ion in Table 3 is once again biassed, since we should be compa ing wi h
he ull se o cocyclic ma ices o o de 4 . Anyway, he e is some e idence ha sea ching o cocyclic
Hadama d ma ices, and in pa icula o D4 -cocyclic Hadama d ma ices, makes sense.
Despi e he ac ha cocyclic cons uc ion p o ides a success ul app oach o Hadama d ma ices,
and hence o (−1,1)-ma ices mee ing he bound (1), as a as he au ho s know his echnique has
no ye been used o ackle he maximal de e minan p oblem when n= 0(mod 4).
The main pu pose o his pape is o show 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, we will
ocus on cocyclic ma ices o e he dihed al g oup D2 ,wi h odd, so ha we gi e:
•A e o mula ion o he c i e ion o decide whe he o no a D2 -cocyclic ma ix has a de e minan
a aining Ehlich–Woj as’ bound.
•Some algo i hms o cons uc ing D2 -cocyclic ma ices wi h la ge de e minan s, based on exhaus-
i e and heu is ic sea ches. Un o una ely, al hough he la ges de e minan s ob ained by hese
me hods so a (up o n=2 =38) mee he op imal bound (3) when n−1is hesumo wo
squa es, no D2 -cocyclic ma ix has been ound nei he mee ing no imp o ing he al eady known
lowe bounds when n=22,34.
Apa om hisin oduc o ysec ion,weo ganize hepape as ollows.Thesecondsec ionisde o ed
o explain he heo e ical esul s abou how o de e mine D2 -ma ices mee ing Ehlich and Woj as’
bound (3). The algo i hms and some execu ions a e desc ibed in he hi d sec ion. The las sec ion is
de o ed o conclusions and u u e wo k.
2. Main esul s
F om now on, we assume ha n≡2(mod 4). When necessa y, we will use n=2 , o some odd
in ege ⩾1.
Ou goal in his sec ion is o cha ac e ize he o m o D2 -cocyclic ma ices which migh mee Ehlich
andWoj as’bound (3).The i s pa o he sec ionis de o ed oin oducesome no a ionsand echnical
esul s. A e wa ds, he main s a emen s o he pape a e desc ibed and p o ed.
As in oduced in Sec ion 1, equali y in (3) holds i and only i he e exis s a (1,−1)-ma ix Bo
o de n, such ha
BBT=BTB=⎛
⎝
L0
0L⎞
⎠,(5)
wi h L =(n−2)I +2J . Mo eo e , in hese ci cums ances n−1 is necessa ily he sum o wo squa es.
Condi ion (5) implies some combina o ial p ope ies, ega ding he numbe o posi i e en ies o
he ows ( esp. columns) o B. The ows o any (−1,1)-ma ix o size ncan be classi ied as o e en o
odd ype, depending on he pa i y o he numbe o 1s ha hey con ain. I is appa en ha he inne
p oduc o wo ows o he same ype is cong uen o 2 modulo 4, while he inne p oduc o wo ows
o opposi e ype is cong uen o 0 modulo 4. In hese ci cums ances, he block s uc u e o he ma ix
in (5) implies ha ows om 1 o o Bsha e a common ype, whe eas ows om +1 o2 sha e he
opposi e ype. The same a gumen ansla es o he columns o B. This is a main di e ence wi h usual
Hadama d ma ices o o de a mul iple o 4, in which ows o di e en ype canno occu .
No ice ha his balanced s uc u e o e en and odd ype ows does no need o be a ained anymo e
when n−1 is no he sum o wo squa es. In pa icula , eco d-de e minan ma ices a e known in
sizes 22, 34, 70 and 106 o which he numbe o e en ype ows is g ea e han he numbe o odd
ype ows (see [30] o de ails).
How do hese condi ions ansla e o he cocyclic amewo k? In o de o answe his ques ion
p ope ly, i seems easonable o gi e in ad ance a b ie in oduc ion o cocyclic 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→−1∼
=Z2which sa is y
ψ(gi,gj)ψ(gigj,gk)=ψ(gj,gk)ψ(gi,gjgk), ∀gi,gj,gk∈G(6)
a e called (bina y) cocycles (o e G)[24]. A cocycle is a cobounda y ∂φ i i is de i ed om a se
mapping φ:G→−1by ∂φ(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, he en y in he
(i,j) h posi ion o he cocyclic ma ix is ψ(gi,gj), o all1⩽i,j⩽n.
A cocycle ψis no malized i ψ(1,gj)=ψ(gi,1)=1 o allgi,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 cobound-
a ies o m a subg oup B(G).AbasisB 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,
1gd= gi.

Rema k 1 [2, Lemma 1].In pa icula , o d= 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 ing 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).
A his poin , i is wo hwhile o no ice ha e e y ow ( esp. column) in M∂dconsis s o an e en
numbe o 1s (see Rema k 1). Consequen ly, o a cocyclic ma ix M=M∂i1◦···◦M∂iw◦R o be
a candida e B o mee ing (5), a necessa y (in gene al, no su icien ) condi ion is ha hal he ows
( esp. columns) o Ra e o e en ype, whe eas he emaining ows ( esp. columns) a e o odd ype.
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 1. [19, lemma 6.6]
Le Mψbe a cocyclic ma ix,
[G (Mψ)]ij =ψ(gig−1
j,gj)
g∈G
ψ(gig−1
j,g), (7)
[Gc(Mψ)]ij =ψ(gi,g−1
igj)
g∈G
ψ(g,g−1
igj). (8)
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 di andonlyi e e y ow sum(apa om he i s )is ze o[18].In ac , hisis a s aigh o wa d
consequence o P oposi ion 1.
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) 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 now p o e 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

i=2
n

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) i and only i RE(M)is minimum. This condi ion
may be gene alized o he case n≡2(mod 4).
P oposi ion 2. Le M be a no malized cocyclic ma ix o e G. Then RE(M)⩾2 −2.
P oo . Le Mbe a cocyclic ma ix o e G.Le Mha e e ows o e en ype (p ecisely, hose whose
summa ions a e cong uen o 2 modulo 4), and consequen ly 2 −e ows o odd ype ( hose whose
summa ionsa econg uen o0modulo4)In heseci cums ances,ino de op o e ha RE(M)⩾2 −2
i su ices o p o e ha e⩾ (no ice ha he i s ow o Mis always o e en ype).
As we commen ed be o e, since n≡2(mod 4), he inne p oduc o wo ows o he same ype
is cong uen o 2 modulo 4, while he inne p oduc o wo ows o opposi e ype is cong uen o 0
modulo 4. This way, he numbe o inne p oduc s ≡0(mod 4)is 2e(2 −e), he o alnumbe o
o de ed pai s o ows o di e en ype. An uppe bound o his alue is 2e(2 −e)⩽2 2, and equali y
holds i and only i e= since 2e(2 −e)⩽2 2⇔2 2−4e +2e2⩾0⇔2( −e)2⩾0.
Since each o he 2 −eg oup elemen s g co esponding o ows o odd ype can be ep esen ed as
gsg−1
j, whe e gj=g−1
gs, P oposi ion 1implies ha ow so he G am ma ix G (M)=MMTcon ains
2 −eelemen s ≡0(mod 4) o each 1 ⩽s⩽2 , and he e o e ha he G am ma ix G con ains
2 (2 −e)elemen s ≡0(mod 4).Hence2 (2 −e)⩽2 2⇔2 −e⩽ ⇔e⩾ .
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 (3).
P oposi ion 3. I a cocyclic ma ix M mee s he bound (3), hen RE(M)=2 −2.
P oo . Le Mbe a cocyclic ma ix mee ing (3). By means o ows and columns pe mu a ions and ow
nega ions (no column nega ions a e needed), Mcan be ans o med in a Hadama d equi alen ma ix
Bsa is ying (5). F om (5), i is e iden ha RE(B)=2 −2. Since no column nega ions ha e been used,
RE(M)=RE(B).
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 hebound(1), i is jus a necessa y (bu no su icien , ingene al,seeTable5) condi ion
o mee ing he bound (3).
F om now on, we ix G=D2 , he dihed al g oup wi h p esen a ion a,b:a =b2=(ab)2=1,
wi h o de ing {1,a,...,a −1,b,ab,...,a −1b}and indexed as {1,...,2 }whe e is an odd posi i e
in ege .
F om he esul s in [2] and [1], i may be p o ed ha a basis o cocycles o e D2 consis s in 2 −1
gene a o s, B={∂2,...,∂
2 −1,β}.He e∂ideno es he cobounda y associa ed wi h he i h-elemen
o he dihed al g oup D2 , ha is ai−1(mod )bi−1
.Andβis he ep esen a i e cocycle in cohomology,
i.e. Mβ=⎛
⎝
J J
J −J ⎞
⎠.
Rema k 2. Since hal he ows o Mβa e o e en ype ( hose om 1s o 2 h), i is appa en ha a
cocyclic ma ix Mo e D2 can a ain he bound (3)onlyi Mdecomposes as a combina ion o he o m
M∂i1◦···◦M∂iw◦Mβ. I , on he con a y, Mβis no used, hen all he ows o he cocyclic ma ix would
be o e en ype, and he condi ion (5) could no be sa is ied. No ice ha o e e y D2 -cocyclic ma ix
o he o m M∂i1◦···◦M∂iw◦Mβ, ows ( esp. columns) om 1s o 2 h a e o e en ype, whe eas
he emaining ows ( esp. columns) a e o odd ype.
The ollowing echnical esul will be used h oughou he pape .
Lemma 4. Le M be a cocyclic ma ix o e D2 .
•MMThas he o m ⎛
⎝
X0
0Y⎞
⎠, o some symme ic squa e ma ices X and Y o o de , i and only i i
admi s a decomposi ion o he o m M =M∂i1◦···◦M∂iw◦Mβ.
•I i is he case, in addi ion, hen MMT=MTM.
P oo . The a gumen desc ibed in [2, P oposi ion 11] may be adap ed o he case o dihed al g oups
D2 , so ha he summa ion o any ow s, +1⩽s⩽2 ,is0.
Ac ually, conside a ma ix N=M∂i1◦···◦M∂iw. A ending o he p esen a ion o D2 ,i maybe
eadily checked ha (akb)−1=akb. In hese ci cums ances, Rema k 1implies ha he (necessa ily
e en) numbe 2 so −1s loca ed a ow s, +1⩽s⩽2 , a e dis ibu ed in such a way ha p ecisely
so hem occu h ough columns 1 o , whe eas he emaining soccu h ough columns +1 o2 .
Fu he mo e, ixed a ow s, +1⩽s⩽2 , any wocobounda y ma ices M∂iand M∂jei he sha e hei
wo −1s en ies a ow s, o do no sha e any o hem a ow s. Consequen ly, a ending o he o m o
Mβ, he summa ion o ow s, +1⩽s⩽2 , o any cocyclic ma ix M∂i1◦···◦M∂iw◦Mβis ze o.
Now he i s pa o he Lemma becomes appa en , om P oposi ion 1and Rema k 2.
The p oo o he second pa o his lemma ollows om he s udy o he dis ibu ion o −1by ows
and by columns in he elemen a y cobounda y (see [2,4]). This s udy leads o he no ion o called ( ow)
n-pa hs in [2], analogously he no ion o columns can be de ined. The dis ibu ion o −1by owsand
columns in M=[mi,j]can be ound by means o n-pa h. As a consequence, we ha e he ollowing
p ope ies o M:
1. I +1⩽j⩽2 , henj h column sum is ze o and mj,j=1.
2. Assume 1 ⩽i⩽ . Then, any sequence o cobounda ies making up a i-pa h o ows, also makes
upai-pa h o columns.(Un o una ely, hissi ua iondoesno holdwhen +1⩽i⩽2 .)Hence:
•The i h ow sum is equal o he i h column sum.
•I 1 ⩽j⩽ hen he inne p oduc o ows i h and j h is equal o he inne p oduc o columns
i h and j h.
Le us dis inguish h ee cases:
1. I 1 ⩽i⩽ and +1⩽j⩽2 (o ice e sa) hen by (8), we ha e:
[MTM]i,j=±
2

l=1
ml,k
wi h +1⩽k⩽2 . Using he p ope ies abo e, we ha e ha his column sum is ze o.
2. Assuming 1 ⩽i,j,⩽ , and aking in o accoun he las p ope y s a ed abo e. I ollows ha
[MTM]i,j=[MMT]i,j.
3. Le us show ha [MTM]i,j=[MMT]i,jwhen +1⩽i,j⩽2 .
Fi s ly, le us obse e ha i=j he esul is i ial. Fo he emainde ing o he p oo , we
suppose ha i= j.Using(7) and (8), we ha e:
[MMT]i,j=mk,j
2

l=1
mk,l,
and
[MTM]i,j=mi,k
2

l=1
ml,k.
whe e 2 ⩽k⩽ since g−1
i=giand gig−1
j=g−1
igj=gk. In his si ua ion, he k h ow sum
is equal o he k h column sum. Now, using ha he en ies o Msa is ying (6) and mi,i=1, i
ollows ha mk,j=mi,k, and his concludes he p oo . 
In his pape , no only do we pu sue a cha ac e iza ion o he D2 -cocyclic ma ices whose de e -
minan is equal o (4 −2)(2 −2) −1, bu we will also de elop some me hods o inding hem.
I Mis a D2 -cocyclic ma ix whose de e minan is equal o (4 −2)(2 −2) −1 hen G (M)is
equi alen o
C=⎛
⎝
L0
0L⎞
⎠,
wi h L=(2 −2)I +2J .
S a ing om Cone may cons uc S he ull se o equi alen ma ices UTCUT, such ha UTis he
nega ion o he diagonal en ies wi h indices in T⊂{1,...,2 }=Qo he iden i y ma ix I2 .
S={UTCUT:T⊂Q}.(9)
This lis has ca dinali y 22 −1since UTCUT=UQ TCUQ T. I is a ema kable ac ha Scons i u es
he comple e lis o candida e G am ma ices (i.e., symme ic, ha e diagonal elemen s equal o 2 and
posi i e de ini e and de e minan equal o (4 −2)2(2 −2)2 −2in ou cocyclic con ex . In he gen-
e al amewo k, simul aneous pe mu a ion o ows and he co esponding columns in he candida e
G am ma ices is also allowed. Because o he assumed o de ing o he g oup elemen s, and he e-
la ion o elemen s o he o m ajbwi h ows o odd ype, a bi a y pe mu a ion is no allowed in ou
con ex .
Gi en a candida e G am ma ix, no only would we like o de e mine whe he i admi s a decompo-
si ion UTCUT=MMT,Mbeing a D2 -cocyclic ma ix, bu we also aim o compu e such decomposi ion
whene e possible. The nex esul will play an essen ial ole in he design o he algo i hm sol ing
his p oblem.
Theo em 5. Le M be a no malized cocyclic ma ix o e D2 and G (M)=⎛
⎝
X0
0Y⎞
⎠be he G am ma ix
o M. I X and Y a e squa e ma ices o o de , hen he en ies o M =[mi,j]a e gi en by he o mulas:
1. 1 ⩽i,j⩽2
m1,j=1=mi,1(M no malized)
2. 2 ⩽i⩽
2.1. 2 ⩽j⩽
mi,j=x[j+i−1],j
xi,1
,whe e [n]=1+(n−1)mod
2.2. +1⩽j⩽2
mi,j=y[j+i−1− ],j−
xi,1
3. i= +1(By lemma 4,MM
T=MTM. Hence we ha e uniqueness o he en ies and hese a e he
alues gi en below.)
3.1. 2 ⩽j⩽
m +1,j=y1, +2−j
x1,j
3.2. j= +1
m +1, +1=−

j=1
m +1,j⎛
⎝1+
2

j= +2
mj− , +1m +1,j− m2 +2−j, +1⎞
⎠.
3.3. +2⩽j⩽2
m +1,j=mj− , +1m +1,j− m2 +2−j, +1m +1, +1
4. +2⩽i⩽2
4.1. 2 ⩽j⩽
mi,j=mi− ,2 −j+2mi− , +1m +1,j
[6] T. Chadjipan elis, S. Kounias, C. Moyssiadis, The maximum de e minan o 21 ×21 (1,−1)-ma ices and D-op imal designs,
J. S a . Plann. In e ence 16 (1987) 167–178.
[7] J.H.E. Cohn, On de e minan s wi h elemen s ±1, II, Bull. London Ma h. Soc. 21 (1989) 36–42.
[8] J.H.E. Cohn, On he numbe o D-op imal designs, J. Combin. Theo y Se . A 66 (1994) 214–225.
[9] J.H.E. Cohn, Almos D-op imal designs, U il. Ma h. 57 (2000) 121–128.
[10] W. de Launey, K.J. Ho adam, A weak di e ence se cons uc ion o highe dimensional designs, Des. Codes C yp og . 3 (1993)
75–87.
[11] H. Ehlich, De e mian enabschä zungen ü binä e Ma izen, Ma h. Z. 83 (1964) 123–132.
[12] H. Ehlich, De e mian enabschä zung ü binä e Ma izen mi n≡3mod4), Ma h. Z. 84 (1964) 438–447.
[13] R.J. Fle che , C. Koukou inos, 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 ehma ics 286 (2004) 252–253.
[14] Z. Galil, J. Kie e , D-op imum weighing designs, Ann. S a . 8 (1980) 1293–1306.
[15] J. Hadama d, Résolu ion d’une ques ion ela i e aux dé e minan s, Bull. Sci. Ma h. 2 (17) (1893) 240–246.
[16] J.H. Holland, Adap a ion in Na u al and A i icial Sys ems, Uni e si y o Michigan P ess, Ann A bo , 1975.
[17] K.J. Ho adam, W. de Launey, Cocyclic de elopmen o designs, J. Algeb aic Combin. 2 (3) (1993) 267–290 (E a um: J. Algeb aic
Combin.3(1)(1994)129).
[18] K.J. Ho adam, W. de Launey, Gene a ion o Cocyclic Hadama d ma ices, Compu a ional Algeb a and Numbe Theo y, Ma h.
Appl., Kluwe Acad. Publ., Do d ech , 1995, pp. 279–290.
[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, W.P. O ick, D-op imal designs, in: C. Colbou n, J. Dini z (Eds.), The CRC Handbook o Combina o ial Designs,
Taylo and F ancis, Boca Ra on, 2006
[21] H. Kha aghani, B. Tay eh-Rezaie, On he classi ica ion o Hadama d ma ices o o de 32, J. Comb. Des. 18 (2010) 328–336.
[22] C. Koukou inos, <h p://ma h.n ua.g / ckoukou />.
[23] C. Koukou inos,M. Mi oulli, J. Sebe y, Bounds on he maximum de e minan o (−1,1)ma ices, Bull. ICA 29 (2000) 39–48.
[24] S. MacLane, Homology, Classics in Ma hema ics, Sp inge -Ve lang, Be lin, 1995.. (Rep in o he 1975 edi ion).
[25] Z. Michalewicz, Gene ic Algo i hms + Da a S uc u es = E olu ion P og ams, Sp inge -Ve lag, 1992.
[26] C. Moyssiadis, S. Kounias, The exac D-op imal i s o de sa u a ed design wi h 17 obse a ions, J. S a is . Plann. In e ence 7
(1982) 13–27.
[27] P. Ó Ca háin, M. Röde , The Cocyclic Hadama d ma ices o o de less han 40, Des. Codes C yp og . 58 (1) (2011) 73–88.
[28] W.P. O ick, The maximal {−1,1}-de e minan o o de 15, Me ika 62 (2005) 195–219.
[29] W.P. O ick, On he enume a ion o some D-op imal designs, J. S a is . Plann. In e ence 138 (2008) 286–293.
[30] W. O ick, B. Solomon, The Hadama d Maximal De e minan P oblem (websi e), <h p://www.indiana.edu/maxde />.
[31] J. Sebe y, T. Xia, C. Koukou inos, M. Mi ouli, The maximal de e minan and subde e minan s o ±1 ma ices, Linea Algeb a
Appl. 373 (2003) 297–310.
[32] N.J.A. Sloane, A Lib a y o Hadama d Ma ices (websi e), <h p://www2. esea ch.a .com/ njas/hadama d/>.
[33] N.J.A. Sloane, The On-line Encyclopedia o In ege Sequences (websi e), <h p://oeis.o g/>.
[34] H. Tamu a, D-op imal designs and g oup di isible designs, J. Comb. Des. 14 (2006) 451–462.
[35] 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 (1964) 73–83.