G öbne bases and cocyclic Hadama d ma ices
Víc o Ál a ez, José And és A ma io, Raúl M. Falcón,
Ma ía Dolo es F au, Félix Gudiel
Dp o. Ma emá ica Aplicada I, Uni . Se illa, A da. Reina Me cedes s/n, 41012 Se illa, Spain
a b s a c
Keywo ds:
Hadama d ma ix
Basis o cocycles
Polynomial ing
Ideal
Hadama d ideals we e in oduced in 2006 as a se o nonlin-
ea polynomial equa ions whose ze os a e uniquely ela ed o
Hadama d ma ices wi h one o wo ci culan co es o a gi en o -
de . Based on his idea, he cocyclic Hadama d es enables us o
desc ibe a polynomial ideal ha cha ac e izes he se o cocyclic
Hadama d ma ices o e a fixed fini e g oup Go o de 4 . Ne -
e heless, he complexi y o he compu a ion o he educed G öb-
ne basis o his ideal is 2O( 2), which is excessi e e en o e y
small o de s. In o de o imp o e he efficiency o his polynomial
me hod, we ake ad an age o some ecen esul s on he inne
s uc u e o a cocyclic ma ix o desc ibe an al e na i e polyno-
mial ideal ha also cha ac e izes he a o emen ioned se o cocyclic
Hadama d ma ices o e G. The complexi y o he compu a ion de-
c eases in his way o 2O( ). Pa icula ly, we design wo specific
p ocedu es o looking o Z ×Z2
2-cocyclic Hadama d ma ices and
D4 -cocyclic Hadama d ma ices, so ha la ge cocyclic Hadama d
ma ices (up o ≤39) a e explici ly ob ained.
1. In oduc ion
A bina y Hadama d ma ix H o o de nis an n ×nma ix wi h e e y en y ei he 1o −1, which
sa isfies HHT=nI, whe e Iis he iden i y ma ix o o de n. Al hough i is well-known ha nhas
o be necessa ily 1, 2o a mul iple o 4(as soon as h ee o mo e ows ha e o be simul aneously
o hogonal), he e is no ce ain y whe he such a Hadama d ma ix exis s a e e y possible o de .
Cu en ly, he smalles o de o which no Hadama d ma ix is known is 668, and he e a e only 12
such o de s below 2000 (Ðoko ic e al. (2014)). The Hadama d conjec u e asse s ha he e exis s a
Hadama d ma ix o o de 4 o e e y na u al numbe .
The e exis many di e en cons uc ions o Hadama d ma ices: Syl es e , Paley, Williamson, I o,
Goe hals–Seidel, one and wo ci culan co es o cocyclic ma ices, amongs o he s (see Ho adam
(2007)). Ne e heless, mos o hem ail o yield Hadama d ma ices o e e y o de which is a mul i-
ple o 4 and he e o e a e no sui able candida es o a p oo o he Hadama d conjec u e. Among all
hese cons uc ions, i seems ha he mos p omising a e he wo ci culan co es ma ices (Fle che
e al. (2001); Ko si eas e al. (2006b)), he Goe hals–Seidel a ays (Goe hals and Seidel (1967); Se-
be y and Yamada (1992)) and he cocyclic cons uc ions (Ho adam (2007)). Ac ually, he one and
wo ci culan co es cons uc ions ha e ecen ly been desc ibed o be somehow cocyclic-based ( he
co es hemsel es a e cocyclic o e Z4 −1and D4 −2, espec i ely, see Ál a ez e al. (2017) o de ails).
A s onge e sion o he Hadama d conjec u e, posed by Ho adam and de Launey (1995) is he co-
cyclic Hadama d conjec u e: his s a es ha he e exis s a cocyclic Hadama d ma ix a e e y possible
o de . Cu en ly he smalles o de o which no cocyclic Hadama d ma ix is known is 188 (Ho adam
(2007)).
Ko si eas e al. (2006a) in oduced he concep o Hadama d ideal as a se o nonlinea polynomial
equa ions whose ze os de e mine he se o Hadama d ma ices wi h one ci culan co e. Sho ly a e ,
Ko si eas e al. (2006b) used he same ideal oge he wi h a se ies o new polynomials in o de o
de e mine he se o Hadama d ma ices wi h wo ci culan co es, by means o which hey compu ed
he Hadama d ma ices wi h wo ci culan co es up o o de 52.
In his pape , we define se e al cocyclic Hadama d ideals, whose ze os de e mine he se o cocyclic
Hadama d ma ices o e a fini e g oup Go o de 4 . Based on he cocyclic es o Ho adam and
de Launey (1995), ou fi s app oach (Theo em 2) gi es ise o a p ocedu e CocGM( , G, op )which
wo ks jus o e y small , ac ually ≤3.
In o de o imp o e he efficiency o his polynomial me hod and p o ided a basis o G-cocycles
is known (which is always he case, see Flanne y and O’B ien (2000); Flanne y and Egan (2015)),
we define in Theo em 5 an al e na i e ideal based upon he sys em o equa ions desc ibed by Ál a ez
e al. (2008), which also cha ac e izes he se o G-cocyclic Hadama d ma ices. This gi es a p ocedu e
CocCB( , G, op )sui able o la ge alues o .
Fu he mo e, om he knowledge o he p ope ies o cocyclic ma ices o e Z ×Z2
2and D4 de-
sc ibed by Ál a ez e al. (2015, 2016), imp o ed e sions o his p ocedu e (CocAH( , col, dis , H)and
CocDH( , dis , op , H), based on Theo ems 7 and 9, espec i ely) a e used o pe o m local sea ches
o Z ×Z2
2-cocyclic Hadama d ma ices and D4 -cocyclic Hadama d ma ices.
All he p ocedu es ha e been implemen ed as a lib a y hadama d.lib in he open compu e algeb a
sys em o polynomial compu a ions Singula , de eloped by Decke e al. (2016). Examples illus a -
ing he use o his lib a y and helib a y i sel a e a ailable onlinea h p://pe sonales.us.es/
au algan/LS/hadama d.lib. Fu he , all he compu a ions ha a e exposed h oughou he
pape a e implemen ed in a sys em wi h an AMD Op e on 6348, wi h a 2.8 GHz p ocesso (48 co es), 256
GB RAM and 3 TB Ha d D i e. Running he p ocedu es on his sys em, cocyclic Hadama d ma ices ha e
been ound up o o de 4 ≤156.
The emainde o he pape is o ganized as ollows. The fi s pa o Sec ion 2is de o ed o de-
sc ibing some p elimina y concep s and esul s on Hadama d ma ices and Algeb aic Geome y, ha
a e used in he es o he pape . La e , we define a ze o-dimensional ideal ha de e mines he se
o cocyclic Hadama d ma ices o e a gi en g oup Go o de 4 , which comes om a s aigh o wa d
ansla ion o he cocyclic Hadama d es o Ho adam and de Launey (1995). In Sec ion 3, we p opose
an al e na i e o he p e ious cons uc ion by defining a new ze o-dimensional ideal, based on he
esul s o Ál a ez e al. (2008). Ac ually, we specialize his p ocedu e o Z ×Z2
2-cocyclic Hadama d
ma ices and D4 -cocyclic Hadama d ma ices, a ending o he p ope ies desc ibed by Ál a ez e al.
(2015, 2016). The las sec ion is de o ed o conclusions and ou lines o u he wo k.
2. P elimina ies
We desc ibe in his sec ion some basic concep s and esul s on Hadama d ma ices and Algeb aic
Geome y ha a e used h oughou he pape . We e e o he monog aphs o Mac Lane (1995),
Ho adam (2007), De Launey and Flanne y (2011) and Cox e al. (1998, 2007) o mo e de ails abou
hese opics.
2.1. Hadama d ma ices
Assume h oughou ha G ={g1=1, ..., g4 }is a mul iplica i e fini e g oup o 4 elemen s, no
necessa ily abelian. A unc ion ψ:G ×G →−1
∼
=Z2is said o be a (bina y) cocycle o e G, o simply
G-cocycle o sho , i i sa isfies ha
ψ(gi,gj)ψ(gigj,gk)=ψ(gj,gk)ψ(gi,gjgk), o all gi,gj,gk∈G.(1)
The cocycle ψis na u ally displayed as a cocyclic ma ix Mψo o de 4 ×4 , whose (i, j) h en y
is ψ(gi, gj) o all gi, gj∈G. Since i mus be ψ(1, gj) =ψ(gi, 1) o all gi, gj∈G, he fi s ow
and column o Mψa e all ei he 1 o −1. In he fi s case, he cocycle ψand i s cocyclic ma ix
Mψa e said o be no malized. The e is a one o one co espondence be ween no malized and non
no malized cocycles. Wi hou loss o gene ali y, we will assume ha all cocycles conside ed he ea e
a e no malized, and will be e med simply cocycles o sho .
Le gd∈G. The elemen a y cobounda y ∂dis he cocycle o e Gdefined as
∂d(i,j):= δgd(gi)δgd(gj)δgd(gigj),
whe e δgd:G →−1is he cha ac e is ic se map such ha δgd(gi) =−1i gi=gdand 1, o he wise.
The gene alized cobounda y ma ix M∂dconsis s o nega ing he d h- ow o he ma ix M∂d. No e ha
nega ing a ow o a column o a ma ix does no change i s Hadama d cha ac e . This is jus a pa -
icula case o a mo e gene al se : he e is an equi alence ela ion ( e med Hadama d equi alence) on
Hadama d ma ices, so ha wo ma ices a e Hadama d equi alen whene e hey di e in a se ies
o ow and/o column nega ions and/o pe mu a ions. These Hadama d equi alence classes may be
g ouped by means o a b oade no ion o equi alence ela ion which inco po a es some di e en o -
hogonali y p ese ing mo es, e med swi ching ope a ions. The in e es ed eade is e e ed o O ick
(2008) and he e e ences he ein o de ails.
The ollowing echnical esul summa izes some p ope ies which a e sa isfied by gene alized
cobounda y ma ices, as desc ibed in Ál a ez e al. (2008), and will be o in e es o la e use.
Lemma 1 (Ál a ez e al. (2008)). The nex esul s hold.
a) M∂dcon ains exac ly wo nega i e en ies in each ow s = 1, which a e loca ed a posi ions (s, d)and
(s, e), o ge=g−1
sgd.
b) Gi en gs= 1and gcin G, he e a e exac ly wo gene alized cobounda y ma ices (M∂cand M∂d), wi h a
nega i e en y in he posi ion (s, c), whe e gd=gsgc.
c) Two gene alized cobounda y ma ices sha e hei wo nega i e en ies a he s h ow i and only i g2
s=1.
A basis B ={ψ1, ..., ψk}o cocycles o e Gconsis s o some elemen a y cobounda ies ∂iand some
ep esen a i e cocycles. Since he elemen a y cobounda y ∂1 ela ed o he iden i y elemen 1 ∈Gis
no no malized, we may assume ha ∂1/∈B. A basis o cobounda ies consis s o 4 − −1 elemen s,
o being he ank o he Sylow 2-subg oup o G/[G, G], and may be calcula ed s aigh o wa dly
(see Ho adam and de Launey (1995); Flanne y and Egan (2015)). A basis o ep esen a i e cocycles
consis s o cocycles coming om Ex (G/[G, G], Z2)and k −4 +1 cocycles (one o each 2-powe
componen o H2(G)) coming om Hom(H2(G), Z2), and may be calcula ed by means o aMagma
(Bosma e al. (1997)) p ocedu e as desc ibed in Flanne y (1996); Flanne y and O’B ien (2000).
E e y cocycle o e Gadmi s a unique ep esen a ion as a p oduc o he gene a o s in B,
ψ=ψx1
1···ψxk
k, xi∈{0, 1}. The uple (x1, ..., xk)Bdefines he coo dina es o ψwi h ega ds o B. Ac-
co dingly, e e y cocyclic ma ix Mψ=(ψ(i, j)), o ψ=(x1, ..., xk)B, admi s a unique decomposi ion
Mψ=Mx1
ψ1···Mxk
ψkas he Hadama d poin wise p oduc o hose ma ices Mψico esponding o en-
ies xi=1. In wha ollows, we use gene alized cobounda y ma ices ins ead o classical cobounda y
ma ices. Le us poin ou ha any ma ix ob ained as he Hadama d p oduc o gene alized cobound-
a y ma ices and ep esen a i e cocycles is Hadama d equi alen o a cocyclic ma ix by means o
nega ions o ce ain ows.
A cocycle ψ(o e G) is said o be o hogonal i i s cocyclic ma ix Mψis Hadama d. In such a case,
Mψis said o be a cocyclic Hadama d ma ix o e Go a G-cocyclic Hadama d ma ix. The se o cocyclic
Hadama d ma ices o e Gis deno ed by HG. The cocyclic Hadama d es o Ho adam and de Launey
(1995) asse s ha a cocyclic ma ix Mψis Hadama d i and only i

j∈G
ψ(i,j)=0, o all i∈G {1}.(2)
A ow o Mψis e med Hadama d ow p ecisely when i s summa ion is ze o. The e o e, Mψis
Hadama d i and only i e e y ow (bu he fi s ) is a Hadama d ow.
2.2. Algeb aic geome y
Le {X}and K[X]be, espec i ely, he se o m a iables {x1, ..., xm}and he associa ed mul i a i-
a e polynomial ing o e a field K. The affine a ie y V (I)o an ideal I⊆K[X]is he se o poin s
in Km ha a e ze os o all he polynomials o I. The ideal Iis said o be ze o-dimensional i V(I)
is fini e. I is said o be adical i e e y polynomial p ∈K[X]belongs o Iwhene e he e exis s a
na u al numbe nsuch ha pn∈I. A e m o de <on he se o monomials o K[X]is a mul iplica-
i e well-o de ing ha has he cons an monomial 1as i s smalles elemen . The la ges monomial
o a polynomial po Iwi h espec o he e m o de <is i s leading monomial. The ideal gene a ed
by he leading monomials o all he non-ze o elemen s o Iis i s ini ial ideal I<. Those monomi-
als o polynomials o I ha a e no leading monomials o any polynomial o Ia e called s anda d
monomials. I he ideal Iis ze o-dimensional, hen he numbe o s anda d monomials o Icoincides
wi h he dimension o K[X]/Io e K, which is g ea e han o equal o he numbe o poin s o
V(I). The equali y holds when Iis adical. This dimension can be ob ained by compu ing he Hilbe
unc ion HFK[X]/I, which maps each non-nega i e in ege don o dimK(K[X]d/Id), whe e K[X]dde-
no es he se o homogeneous polynomials in K[X]o deg ee dand Id=K[X]d∩I. In pa icula ,
dimK(K[X]/I) =0≤dHFK[X]/I(d). I he ideal Iis ze o-dimensional, hen he numbe HFK[X]/I(d)
coincides wi h he se o s anda d monomials o deg ee d, ega dless o he e m o de . As a conse-
quence, he Hilbe unc ion o K[X]/Icoincides wi h ha o K[X]/I<, o any e m o de <, which
can be ob ained by using o ins ance he algo i hm o Mo a and Mölle (1983). P e iously, i was
equi ed o de e mine he ini ial ideal I<. In any case, Baye and S illman (1992) al eady p o ed ha
he p oblem o compu ing Hilbe unc ions is NP-comple e.
A G öbne basis (Buchbe ge (2006)) o he ideal Iis any subse GB o polynomials o Iwhose
leading monomials wi h espec o a gi en e m o de gene a e he ini ial ideal I<. I is educed i
all i s polynomials a e monic and no monomial o a polynomial in GB is gene a ed by he leading
monomials o he es o polynomials in he basis. The e exis s a unique educed G öbne basis o he
ideal I. This basis gene a es he ini ial ideal I<and can be used, he e o e, o de e mine he ca dinal-
i y o i s affine a ie y V(I). Fu he , he poin s o his a ie y can be enume a ed once he educed
G öbne basis is decomposed in o fini ely many disjoin subse s, each o hem being o med by he
polynomials o a iangula sys em o polynomial equa ions, whose ac o iza ion and subsequen es-
olu ion a e easie han he sys em ela ed o he gene a o s o he o iginal ideal I. See in his ega d
he a icles o Hilleb and (1999), Laza d (1992) and Mölle (1993).
G öbne bases can, he e o e, be used o de e mine bo h he ca dinali y and he elemen s o he
se HGo cocyclic Hadama d ma ices o e a mul iplica i e fini e g oup Go 4 elemen s. To his
end, le Q[XG]be he polynomial ing o e he field Qo a ional numbe s, wi h se o 16 2 a iables
{XG} ={xi,j:gi, gj∈G}and le us define he polynomial
pi,j,k(X):= xi,jxij,k−xj,kxi,jk, o all gi,gj,gk∈G,
whe e he p oduc s ij and jk a e induced by he g oup law in G. The nex esul shows how he
se HGo cocyclic Hadama d ma ices o e Gcan be iden ified wi h he affine a ie y defined by a
ze o-dimensional adical ideal o nonlinea polynomials in Q[XG].
Theo em 2. The se HGcan be iden ified wi h he se o ze os o he ze o-dimensional ideal IG=I1
G+I2
G+
I3
G+I4
G⊂Q[XG]consis ing in he summa ion o he ollowing ou subideals:
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
I1
G=x2
i,j−1:i,j∈G,
I2
G=pi,j,k(X):i,j,k∈G,
I3
G=x1,i−1,xi,1−1:i∈G,
I4
G=j∈Gxi,j:i∈G {1}.
Besides, |HG| =dimQ(Q[XG]/IG).
P oo . Le P=(p1,1, ..., p4 ,4 )be a poin o he affine a ie y V(IG). A ending o I1
G, e e y com-
ponen pi,jo Pis ei he 1o −1, o all i, j ∈G. Le ψ:G ×G →{±1}be defined such ha
ψ(i, j) =pi,j, o all gi, gj∈G. Since I2
Gimplies by cons uc ion ha ψsa isfies iden i y (1) o all
gi, gj, gk∈G, he poin Pcan be iden ified wi h he cocyclic ma ix Mψ ela ed o ψ(which is, in
addi ion, no malized, because o he defini ion o he subideal I3
G). Finally, I4
Gimplies ha Mψsa is-
fies iden i y (2) and hence, Mψis Hadama d. The affine a ie y V(IG)coincides, he e o e, wi h he
se HG, whose fini eness in ol es he ideal IG o be ze o-dimensional.
Besides, since IG∩Q[xi,j] = x2
i,j−1  ⊆IG o all i, j ∈Gand all hese polynomials a e squa e- ee,
P oposi ion 2.7 o Cox e al. (1998) implies ha
IG=IG+
i,j
IG∩Q[xi,j]=IG,
so IGis he e o e adical. And hence, |HG| =|V(IG)| =dimQ(Q[XG]/IG).2
No ice ha , as defined, each o he subideals I1
G, I2
G, I3
Gand I4
Ga e gene a ed by 16 2, 64 3, 8 −1
and 4 −1 polynomials o e he se o 16 2 a iables XG. Ne e heless, some o hese polynomials
a e edundan and may s aigh o wa dly be emo ed om a sys em o gene a o s o IG. Namely,
i is easy o check ha I3
G⊂x1,1−1 +I2
G, as he esul o a s anda d p oo on he ac ha any
cocycle is ei he no malized o unno malized (see Lemma 1.3 o Ho adam and de Launey (1995) o
de ails). Fu he mo e, he 8 −1 polynomials {x2
1,i−1, x2
i,1−1 :i ∈G}in I1
Gmay be emo ed as well,
since hey a e also in I3
G. Anyway, he se o polynomials gene a ing IGwhich we ha e jus desc ibed
consis s o O( 3)polynomials o deg ee up o 2o e O( 2) a iables.
I is a ema kable ac ha he compu a ion o he educed G öbne basis o a ze o-dimensional
ideal is ex emely sensi i e o he numbe o a iables. See in his ega d he a icles o Hashemi
(2009), Hashemi and Laza d (2011), Lakshman (1991) and Lakshman and Laza d (1991). In he las
e e ence, he au ho s p o ed ha he complexi y o ou compu a ion is dO(n), whe e dis he maximal
deg ee o he gene a o s o ideal and nis he numbe o a iables. In he case o Theo em 2, his
complexi y is 2O( 2), which ende s he compu a ion only possible o e y low alues o .
The p ocedu e CocGM( , G, op )(included in he lib a y hadama d.lib which is a ailable online
o ee a he pe sonal web page o one o he au ho s, as no iced be o e) p o ides an implemen-
a ion o he me hod ha uns on Singula (Decke e al. (2016)). I is specifically designed o he
g oup Z ×Z2
2( aking G =1as inpu ) and he dihed al g oup D4 ( aking G =2as inpu ), hough
i migh be s aigh o wa dly modified o fix o any o he g oup G. I would suffice o include he

polynomials gene a ing he subideal I2
G, a ending o he pa icula g oup law o G. Depending on
whe he he pa ame e op is equal o 1 o 2, he p ocedu e calcula es ei he jus he numbe o
cocyclic Hadama d ma ices o e Go he explici ull se o hese ma ices. No ice ha i makes use
o he Singula p ocedu es elimlinea pa and oless a s which speed up and simpli y he
calcula ions, educing he numbe o a iables and polynomials in u n.
Example 3. As an illus a ion o he me hod, conside he g oup G =Z2
2. The ideal IG, as desc ibed in
Theo em 2, is defined o e he se o 16 a iables {XG} ={xi,j:gi, gj∈G}and ini ially consis s o 90
gene a ing polynomials, al hough we al eady poin ed ou be o e ha some o hese polynomials a e
edundan and may be emo ed s aigh o wa dly om he e y beginning. Assuming x1,i=xi,1=1
o 1 ≤i ≤4, we educe o 9 a iables, namely xi,j, o 2 ≤i, j ≤4.
A educed G öbne basis o IGwi h espec o he deg ee e e se lexicog aphical o de consis s o
he ollowing 14 polynomials: p1=x4,2+x4,3+x4,4+1, p2=x3,2+x3,3+x3,4+1, p3=x2,4+x3,4+
x4,4+1, p4=x2,3+x3,3+x4,3+1, p5=x2,2+x2,3+x2,4+1, p6=x2
4,4−1, p7=x4,3x4,4+x4,3+x4,4+1,
p8=x3,4x4,4+x3,4+x4,4+1, p9=x2
4,3−1, p10 =x3,4x4,3+x3,3x4,4−x3,3−x3,4−x4,3−x4,4−2,
p11 =x3,3x4,3−x3,3−x4,3−1, p12 =x2
3,4−1, p13 =x3,3x3,4−x3,3−x3,4−1, p14 =x2
3,3−1.
These polynomials consis o monomials which may be o ganized in o wo subse s, leade mono-
mials LM ={x2,2, x2,3, x2,4, x3,2, x4,2, x2
3,3, x3,3x3,4, x3,3x4,3, x2
3,4, x3,4x4,3, x3,4x4,4, x2
4,3, x4,3x4,4, x2
4,4}
and s anda d monomials SM ={1, x3,3, x3,4, x4,3, x4,4, x3,3x4,4}. Since |SM| =6, he affine a ie y
V(IG)consis s o 6 poin s Pk=(x(k)
2,2, x(k)
2,3, x(k)
2,4, x(k)
3,2, x(k)
3,3, x(k)
3,4, x(k)
4,2, x(k)
4,3, x(k)
4,4), 1 ≤k ≤6, as well. These
poin s
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
P1=(−1,−1,1,−1,1,−1,1,−1,−1),
P2=(−1,1,−1,−1,−1,1,1,−1,−1),
P3=(−1,−1,1,1,−1,−1,−1,1,−1),
P4=(1,−1,−1,−1,−1,1,−1,1,−1),
P5=(−1,1,−1,1,−1,−1,−1,−1,1),
P6=(1,−1,−1,−1,1,−1,−1,−1,1),
p o ide he 6 no malized cocyclic Hadama d ma ices o e Z2
2, consis ing o 3 ×3 co es wi h exac ly
one posi i e en y a each ow iand a each column j, 2 ≤i, j ≤4. 
As a ma e o ac , unning he p ocedu e CocGM( , G, op )in ou compu e sys em, he compu-
a ion o he educed G öbne bases o he ideals ela ed o he g oup Z ×Z2
2and he dihed al g oup
D4 a e only easible o ≤3(see Table 1). Un o una ely, o highe o de s, he sys em uns ou o
memo y, and some new insigh is needed o imp o e he me hod.
In Sec ion 3we define ano he ideal JG o compu ing HGin a mo e sub le way, based on he
p e ious wo k o Ál a ez e al. (2008). Un o una ely, i will s ill be ex emely ha d o compu e HG o
la ge |G|. Ne e heless, aking ad an age o he p ope ies o cocyclic ma ices o e D4 and Z ×Z2
2
desc ibed by Ál a ez e al. (2015, 2016), his ideal JGmay be specifically simplified o compu ing
HD4 and HZ ×Z2
2in a be e way.
3. Ideals buil om a basis o G-cocycles
In o de o educe he complexi y o he compu a ion o he educed G öbne basis ha has been
desc ibed in he p e ious sec ion, we conside a new ze o-dimensional adical ideal JG ela ed o he
se HG, whe e we diminish he numbe o a iables and he maximal deg ee o he polynomials. Fo
his pu pose, wha is needed is jus knowing an explici basis o cocycles o e G, which he me hods
o Ho adam and de Launey (1995); Flanne y (1996); Flanne y and O’B ien (2000); Flanne y and Egan
(2015); Ál a ez e al. (2009) p o ide.
Le Gbe a mul iplica i e fini e g oup o o de 4 , B ={ψ1, ..., ψk}be a basis o no malized
cocycles o e Gand ψbe a no malized cocycle o e Go coo dina es (x1, ..., xk)Bwi h ega ds o B,
so ha ψ=ψx1
1···ψxk
k, o some xi∈{0, 1}, 1 ≤i ≤k. Le md
i,jdeno e he (i, j) h en y o Mψd,
so ha he (i, j) h en y o Mψis (m1
i,j)x1···(mk
i,j)xk. Recall ha cocyclic Hadama d ma ices a e
p ecisely hose ma ices ha a e buil up om Hadama d ows (excep ing he fi s ow, consis ing all
o 1s). In hese ci cums ances, he i h- ow o he p e ious ma ix Mψis Hadama d i and only i
4

j=1
(m1
i,j)x1···(mk
i,j)xk=0.
The nex esul holds.
Theo em 4 (Ál a ez e al. (2008)). The ma ix Mψis Hadama d i and only i he ec o o coo dina es
(x1, ..., xk)Bo ψwi h ega ds o Bsa isfies he ollowing sys em o 4 −1equa ions and k unknowns
⎧
⎪
⎨
⎪
⎩
(m1
2,1)x1...(mk
2,1)xk+...+(m1
2,4 )x1...(mk
2,4 )xk=0
.
.
.
(m1
4 ,1)x1...(mk
4 ,1)xk+...+(m1
4 ,4 )x1···(mk
4 ,4 )xk=0
(3)
The solu ions o he sys em (3) cons i u e p ecisely he whole se o no malized cocyclic Hadama d
ma ices o e G. T ying o sol e his sys em may be as complica ed as pe o ming an exhaus i e
sea ch o cocyclic Hadama d ma ices o e G. Ins ead, we in end o ansla e he sys em (3) in e ms
o a se o nonlinea Q[X]-polynomial equa ions o e he se o a iables {X} ={x1, ..., xk}(whose
0, 1 alues a e ela ed o he coo dina es o G-cocycles wi h ega ds o B), and o s udy he s uc u e
o he associa ed ideal.
A succinc algeb aic desc ip ion o he quad a ic cons ain s {X} ⊂{0, 1}kis p o ided by he ol-
lowing se o kalgeb aic equa ions:
xi(xi−1)=0, o all i∈{1,...,k}.(4)
In o de o define he es o polynomial equa ions ha a ise om he sys em (3), we use he nex
wo main ideas o simplifica ions:
•F om a p ac ical poin o iew, we may assume we wo k wi h a fixed ep esen a i e cocycle ρ
among all o he possible choices o ep esen a i e cocycles. In ac , empi ically, in he g oups
mos in ensi ely s udied, he e always exis s a choice ρo ep esen a i e cocycle ha ends o
be he mos success ul o p o iding Hadama d ma ices. See in his ega d he wo ks o Ál a ez
e al. (2008, 2015, 2016), Baliga and Ho adam (1995), Flanne y (1997) and Ho adam (2007). We
will deno e by Mρ=( i,j) he ma ix ela ed o his ep esen a i e cocycle ρ. Ob iously, his
p uning in he sea ching space leads o he ci cums ance ha some G-cocyclic Hadama d ma-
ices a e los (namely, i hey do exis , hose lying on a cocyclic equi alence class di e en o
ha o ρ). Fo ins ance, his is he case o he 1400 cocyclic Hadama d ma ices o e D4·5, lis ed
in Table 1, whe e 800 ma ices Mψa e missing om he o al amoun o 2200 D4·5-cocyclic
Hadama d ma ices. I we wan o find he whole se o cocyclic Hadama d ma ices, we ha e o
pe o m an analogous sea ch o he o he possible choices o Mρ. In wha ollows we assume
ha ψ1, ..., ψk−m∈Ba e G-cobounda ies, ψk−m+1, ..., ψk∈Ba e ep esen a i e G-cocycles and
ρ=
k

i=k−m+1
ψxi
iis a fixed linea combina ion o hese ep esen a i e cocycles.
•The second p ope y o Lemma 1 implies ha he h h summand o he l h equa ion in (3) educes
o be l+1,h(mi
l+1,h)xi(mj
l+1,h)xj, o iand jdefining he (unique) wo gene alized cobounda ies
M∂iand M∂jsha ing a nega i e en y in he posi ion (l +1, h). Namely, {i, j} ={h, (l +1)h}.
No ice ha , e en ually, one o e en bo h o hese cobounda ies ∂h, ∂(l+1)hmigh no be in B.
Ac ually, he monomial sl,h(X) ela ed o he a o emen ioned h h summand o he l h equa ion in
(3) depends on whe he he wo, jus one o none o he cobounda ies ∂h, ∂(l+1)h(p ecisely hose
whose ela ed gene alized cobounda y ma ices con ibu e a nega i e en y a posi ion (l +1, h)) a e
in B. Mo e conc e ely,
•I bo h ∂h, ∂(l+1)h, ∈B, hen
sl,h(X):= l+1,h(1−2xh)(1−2x(l+1)h).
•I jus one o hem is in B, say {i} ={h, (l +1)h} ∩B, hen
sl,h(X):= l+1,h(1−2xi).
•I bo h ∂h, ∂(l+1)h/∈B, hen
sl,h(X):= l+1,h.
Le Sl(X) :=
4

j=1
sl,j(X)and le Hρ
Gbe he se o solu ions o (3) o he o m ψ=ρ
k−m

i=1
ψxi
i. The se
Hρ
Gcoincides wi h he se o solu ions o he sys em o polynomial equa ions
xi(xi−1)=0,i 1 ≤i≤k−m,
Sl(X)=0,i 1 ≤l≤4 −1.
Simila ly o Theo em 2, he nex esul holds.
Theo em 5. The se Hρ
Gcan be iden ified wi h he se o ze os o he ze o-dimensional ideal JG=J1
G+J2
G⊂
Q[X]consis ing in he summa ion o he ollowing wo subideals:
J1
G=x2
i−xi:i∈{1,...,k−m},
J2
G=Sl(X):l∈{1,...4 −1}.
Mo eo e , |Hρ
G| =dimQ(Q[X]/JG).
P oo . Simila ly o Theo em 2, le P=(p1, ..., pk−m)be a poin o he affine a ie y V(JG). A ending
o J1
G, e e y componen pio Pis ei he 1o 0, o all 1 ≤i ≤k −m. Le ψ:G ×G →{±1}be defined
such ha
ψ=ρ
k−m

i=1
ψxi
i.
Since J2
Gimplies by cons uc ion ha Mψsa isfies (4), he poin Pcan be iden ified wi h he cocyclic
Hadama d ma ix Mψ ela ed o ψ. The affine a ie y V(JG)coincides, he e o e, wi h he se HG,
whose fini eness in ol es he ideal JG o be ze o-dimensional.
Besides, since JG∩Q[xi] = x2
i−xi ⊆JG o all 1 ≤i ≤k −mand all hese polynomials a e
squa e- ee, P oposi ion 2.7 o Cox e al. (1998) implies ha
JG=JG+
i
JG∩Q[xi]= JG,
so JGis he e o e adical. And hence, |Hρ
G| =|V(JG)| =dimQ(Q[X]/JG).2
No ice ha , as defined, he ideal JGis gene a ed by O( )polynomials o deg ee up o 2o e he
se o O( ) a iables {x1, ..., xk−m}. Obse e in pa icula ha , acco ding o Lakshman and Laza d, he
Table 1
Running imes ela ed o CocGM and CocCB.
|Hρ
Z ×Z2
2
|Running ime in seconds |Hρ
D4 |Running ime in seconds
CocGM CocCB CocGM CocCB
16 0(0)0(0)60(0)0(0)
324 102(4255)0(0)72 −0(0)
5 120 −7(93)1400 −11 (5826)
7−−−7488 −52282 (−)
complexi y o he compu a ion o he educed G öbne dec eases om 2O( 2)in Theo em 2 o 2O( )
in Theo em 5.
The p ocedu e CocCB( , G, op )(included in he lib a y hadama d.lib as well) p o ides an imple-
men a ion o his me hod. I is specifically designed o he g oup Z ×Z2
2( aking G =1as inpu
and using (5) as he ep esen a i e cocycle ρ) and he dihed al g oup D4 ( aking G =2as inpu and
using (6) as he ep esen a i e cocycle ρ), hough i migh be s aigh o wa dly modified o fix o
any o he g oup G. I would suffice o ac ualize he polynomials Sl(X), a ending o he pa icula
g oup law o Gand he co esponding ep esen a i e cocycle ρ. Once again, depending on whe he
he pa ame e op is equal o 1 o 2, he p ocedu e calcula es ei he jus he numbe o cocyclic
Hadama d ma ices o e Go he explici ull se o hese ma ices.
In o de o check he efficiency o his al e na i e, he p ocedu e has been es ed in he compu a-
ion o he numbe o cocyclic Hadama d ma ices de eloped o e he g oup Z ×Z2
2and he dihed al
g oup D4 o o de 4 . Running imes o compu e his numbe on ou compu e sys em a e exposed
in Table 1, whe e we also indica e in pa en heses he unning ime ha is equi ed o de e mine he
explici ull se o ma ices.
No ice ha al hough he e a e ac ually 2200 cocyclic Hadama d ma ices o e D4·5, jus 1400 o
hem lies on he cocyclic equi alence class [ρ]o ρas defined in (6) (see Ál a ez e al. (2008) o
de ails). This explains he ou pu o he p ocedu e, which limi s o compu e hose cocyclic Hadama d
ma ices lying on he cocyclic equi alence class o [ρ]. Anyway, his is no a sou ce o p oblems as
we commen ed be o e, since his case seems o p o ide mos o he D4 -cocyclic Hadama d ma ices
known so a (see Flanne y (1997); Ál a ez e al. (2008, 2016)).
Ac ually, his p ocedu e CocCB( , G, op )migh be imp o ed i a deepe knowledge abou he
inne s uc u e o cocyclic ma ices o e Gis known. In pa icula , building on he wo ks o Ál-
a ez e al. (2015, 2016), we ha e been able o design wo specific p ocedu es o looking o
Z ×Z2
2-cocyclic Hadama d ma ices and D4 -cocyclic Hadama d ma ices, so ha la ge cocyclic
Hadama d ma ices (up o ≤39) a e ob ained. The de ails a e desc ibed in he nex wo subsec-
ions.
3.1. The g oup Z ×Z2
2
Le Gbe he abelian g oup Z ×Z2
2=a, b, c:a =b2=c2=1, >1 odd, wi h o de ing
{1,c,b,bc,a,ac,ab,abc,...,a −1,a −1c,a −1b,a −1bc},
indexed as {1, ..., 4 }. A basis B ={∂2, ..., ∂4 −2, β1, β2, β3} o cocycles o e Gis desc ibed by Ál a ez
e al. (2008, 2009), and consis s o 4 −3 cobounda ies and h ee ep esen a i e cocycles. As usual, ∂i
e e s o he cobounda y associa ed o he i h-elemen in G. An explici desc ip ion o hese cocycles
may be ound in Ál a ez e al. (2008). No ice ha all cocyclic Hadama d ma ices o e Z ×Z2
2known
so a use all he h ee ep esen a i e cocycles β1, β2and β3simul aneously (see he pape o Baliga
and Ho adam (1995) o de ails). Thus, we assume
Mρ=1 ⊗⎛
⎜
⎜
⎝
1111
1−11−1
1−1−11
11
−1−1
⎞
⎟
⎟
⎠
(5)