´
A
Sea ching o pa ial Hadama d ma ices
V´ıc o ´Al a ez · Jos´e And ´es A ma io ·
Ma ´ıa Dolo es F au · F´elix Gudiel ·
Ma ´ıa Bel´en G¨uemes · Elena Ma ´ın ·
Ampa o Osuna
In honou o Ka hy Ho adam.
In Memo iam: This pape is dedica ed o he la e Wa wick Richa d de Launey
(Oc . 1, 1958 o No . 8, 2010), o his ou s anding con ibu ions in Design
Theo y and ela ed opics.
Abs ac Th ee algo i hms looking o p e y la ge pa ial Hadama d ma-
ices a e desc ibed. He e “la ge” means ha hope ully abou a hi d o a
Hadama d ma ix (which is he bes asymp o ic esul known so a , [8]) is
achie ed. The i s one pe o ms some kind o local exhaus i e sea ch, and
consequen ly is expensi e om he ime consuming poin o iew. The second
one comes om he adap a ion o he bes gene ic algo i hm known so a
sea ching o cliques in a g aph, due o Singh and Gup a [21]. The las one
consis s in ano he heu is ic sea ch, which p io i izes he equi ed p ocessing
ime be e han he inal size o he pa ial Hadama d ma ix o be ob ained. In
all cases, he key idea is cha ac e izing he adjacency p ope ies o e ices in a
pa icula subg aph G o I o’s Hadama d G aph ∆(4 ) [18], since cliques o
o de m in G can be seen as (m + 3) × 4 pa ial Hadama d ma ices.
Keywo ds Hadama d ma ix · clique · Hadama d G aph
V. l a ez, J.A. A ma io, M.D. F au, F. Gudiel, E. Ma ´ın, A. Osuna
Dep . Ma ema´ ica Aplicada 1, ETSII, A da. Reina Me cedes s/n, 41012, Se illa, Spain
Tel.: +34-95455-2797, -4386, -4389, -6225, -2798, -2798
Fax: +34-954557878
E-mail: { al a ez,a ma io,md au,gudiel,ema in,aosuna}@us.es
M.B. Gu¨emes
Dep . Algeb a, Fac. Ma ema´ icas, A da. Reina Me cedes s/n, 41012, Se illa, Spain
Tel.: +34-954556969
Fax: +34-954556938
E-mail: [email p o ec ed]
1 In oduc ion
Hadama d ma ices consis in {1,−1}-squa e ma ices whose ows a e pai wise
o hogonal. This nice p ope y makes Hadama d ma ices being objec s o
mul iple applica ions (see [13] and [14] o ins ance).
I may be s aigh o wa dly checked ha such a ma ix mus be o size 1, 2
o a mul iple o 4. The Hadama d Conjec u e claims ha a ma ix o his ype
exis s o e e y size mul iple o 4. Many a emp s ha e been de o ed o p o e
his conjec u e (bo h om a cons uc i e way [14] and also om a heo e ical
poin o iew in e ms o asymp o ic esul s o exis ence [9,11]), bu i emains
unsol ed so a .
F om he p ac ical poin o iew, aking in o accoun possible applica-
ions, some imes he e is no need o conside a ull Hadama d ma ix. In ac ,
i su ices o mee a la ge amoun o pai wise o hogonal ows [2]. This has
o igina ed he in e es in cons uc ing pa ial Hadama d ma ices P H, ha
is, m×n(1,−1)-ma ices P H sa is ying P H ·P HT=nIm, o m≤n. We
call m he dep h o P H.
F om he o hogonali y law, i is eadily checked ha he numbe no
columns mus be 1, 2 o a mul iple o 4.
No ice ha a pa ial Hadama d ma ix does no need o be a subma ix o a
p ope Hadama d ma ix ( o ins ance, cliques lis ed in Table 3 o 7 ≤ ≤10
a e maximal bu no maximum; in he sense ha al hough no la ge cliques
exis con aining hem, he e exis la ge cliques, o example, hose ela ed o
ull Hadama d ma ices).
Al hough pa ial Hadama d ma ices a e as use ul as Hadama d ma ices
hemsel es wi h ega ds o p ac ical pu poses, un o una ely i seems ha
hei explici cons uc ion is equally ha d as well.
De Launey p o ed in [8] ha pa ial Hadama d ma ices o size abou
a hi d o a 4 ×4 Hadama d ma ix exis o la ge . The p oo gi es a
polynomial ime algo i hm in o cons uc ing such a ma ix. Fu he mo e,
De Launey and Go don p o ed in [10] ha abou a hal o a Hadama d ma ix
4 ×4 exis s o la ge , assuming ha he Riemann hypo hesis is ue. The
idea is decomposing 2 −ias he sum o iodd p ime numbe s pi, 2 ≤i≤3, so
ha he jux aposi ion o he co esponding Paley con e ence ma ices p o ides
a pa ial Hadama d ma ix o dep h 2 min{pi}+2. Un o una ely, none o hese
me hods can p o ide a pa ial Hadama d ma ix o dep h g ea e han hal o
a ull Hadama d ma ix.
In his pape , we p esen h ee new algo i hms o cons uc ing pa ial
Hadama d ma ices o size m×4 . The i s one pe o ms some kind o local
exhaus i e sea ch, and consequen ly is expensi e om he ime consuming
poin o iew. The second one comes om he adap a ion o he bes gene ic
algo i hm known so a sea ching o cliques in a g aph, due o Singh and
Gup a [21]. The hi d one consis s in ano he heu is ic sea ch, which p io i izes
he equi ed p ocessing ime be e han he inal size o he pa ial Hadama d
ma ix ob ained so a . The idea is looking o la ge cliques (i.e. subg aphs
whose e ices a e pai wise adjacen ) in a subg aph G o I o’s Hadama d
G aph ∆(4 ) [18].
Al hough he esul s showed in [8] and [10] a e imp essi e and meaning ully
be e han any ob ained om he algo i hms desc ibed in his pape , i is a
ema kable ac ha ou algo i hms may p o ide pa ial Hadama d ma ices o
dep h g ea e han hal o a ull Hadama d ma ix. Fu he mo e, i is possible
(and desi able) o un ou algo i hms aking as inpu da a pa ial Hadama d
ma ices ob ained by he p ocedu es in [8,10], so ha deepe pa ial Hadama d
ma ices a e cons uc ed (see Table 4.2).
The pape is o ganized as ollows.
The g aph G and i s p ope ies a e desc ibed in Sec ion 2. Sec ion 3 is
de o ed o he desc ip ion o he local exhaus i e algo i hm looking o cliques
in G . In Sec ion 4, he wo heu is ics sea ching o cliques in G a e desc ibed.
Las sec ion is de o ed o conclusions.
2 The g aph G
In wha ollows, o cla i y in he exposi ion, we will simply use + and −
ins ead o 1 and −1.
Hadama d G aphs we e in oduced by I o in [18]. O iginally hey e e ed
o he g aph ∆(4 ) whose e ices a e he (1,−1)- ec o s o leng h 4 consis ing
o an e en numbe o 1s. The adjacency ela ion consis s in o hogonali y.
We call Hadama d g aph o he subg aph G o ∆(4 ) induced by he
(1,−1)- ec o s simul aneously o hogonal o he h ee i s ows o a no mal-
ized Hadama d ma ix,




+. . . + + . . . + + . . . + + . . . +
+...+ + . . . +−. . . − − . . . −
+...+−. . . −+. . . +−. . . −
. . . . . . . . . . . .




These o hogonali y condi ions s aigh o wa dly cha ac e ize he o m o
he e ices in G .
Lemma 1 The e ices o G consis o (1,−1)- ec o s o leng h 4 whe e he
2 nega i e en ies a e dis ibu ed ollowing his pa e n,

k

-k
 
k -k
so ha exac ly k, −k, −kand knega i e en ies occu among e e y
posi ions, o some 0≤k≤ .
We may hen classi y he se o e ices in G a ending o he numbe
ko nega i e en ies which appea in posi ions 1 h ough . In wha ollows,
ak- e ex in G e e s o a e ex wi h p ecisely knega i e en ies among
posi ions 1 o .
Lemma 2 In pa icula , he numbe o e ices in G is |G |=
X
k=0 
k4
.
The ables below gi e he numbe o k- e ices (n. .) and hei deg ee δ
(numbe o adjacen e ices), o 1 ≤ ≤7 and 0 ≤k≤ . The column o al
e e s o he numbe o e ices and edges in G (no ice ha he numbe o
edges is hal he summa ion o he deg ee o e e y e ex). I is e iden ha
o a ixed alue o k, e e y k- e ex has he same deg ee (since pe mu ing
some columns does no a ec o he o hogonali y ela ion).
Table 1 Ve ices and edges in G .
1
k0 1 o al
n. . 1 1 2
δ0 0 0
2
k0 1 2 o al
n. . 1 16 1 18
δ16 8 16 80
3
k0 1 2 3 o al
n. . 1 81 81 1 164
δ0 64 64 0 5184
4
k0 1 2 3 4 o al
n. . 1 256 1296 256 1 1810
δ1296 648 648 648 1296 587088
5
k0 1 2 3 4 5 o al
n. . 1 625 10000 10000 625 1 21252
δ0 6912 6912 6912 6912 0 73440000
6
k0123456 o al
n. . 1 1296 50625 160000 50625 1296 1 263844
δ160000 80000 79808 79712 79808 80000 160000 10521080000
7
k0 1 2 3 4 5 6 7 o al
n. . 1 2401 194481 1500625 1500625 194481 2401 1 3395016
δ0 960000 960000 960000 960000 960000 960000 0 1629606720000
I is eadily checked ha he size o G g ows exponen ially on . Since
cliques o size min G ansla e o pa ial Hadama d ma ices (m+3)×4 , we
would like o sea ch o la ge cliques in G . Since he la ges clique in ∆(4 ) is
a mos o size 4 (see [17] o de ails), he la ges clique in G is a mos o size
4 −3. Cliques mee ing he uppe bound would co espond o ull Hadama d
ma ices.
Example 1 Fo ins ance, conside he g aph G2, ob ained om = 2. The
pic u e below shows a clique o size 5, so ha adding he h ee no malized
ows we ob ain a ull Hadama d ma ix o size 8 ×8.
(−−++++−−) = 1
(−+−+−+−+) = 2
(−+−+−+ +−) = 3
(−+−+ + − −+) = 4
(−+−+ + −+−) = 5
(−+ + − − +−+) = 6
(−+ + − − + +−) = 7
(−+ + −+− −+) = 8
(−+ + −+−+−) = 9
(+ − − +−+−+) = 10
(+ − − +−+ +−) = 11
(+ − − + + − −+) = 12
(+ − − + + −+−) = 13
(+ −+− − +−+) = 14
(+ −+− − + +−) = 15
(+ −+−+− −+) = 16
(+ −+−+−+−) = 17
(+ + −−−−++) = 18
1
18
2
3
4
5
6
7
8
9 10
1112
13
14
15
16 17

Amaximum clique is a clique wi h he maximum ca dinali y (which is
called he maximum clique numbe ). This no ion is di e en om ha o
maximal clique, which e e s o a clique which is no a p ope subse o any
o he clique. Thus maximal cliques need no be maximum ones (as we had
al eady no iced in he in oduc ion), hough he con e se is always ue.
Gi en a g aph, he maximum clique p oblem (MCP) is o ind a maximum
clique, and i is NP-comple e [6]. Un o una ely, he e is no polynomial- ime
algo i hm o app oxima ing he maximum clique wi hin a ac o o n1−ǫunless
P=NP [12], whe e nis he numbe o he e ices o he g aph. Mo eo e , he e
is no polynomial- ime algo i hm app oxima ing he clique numbe wi hin a
ac o o n
(log n)1−ǫunless NP=ZPP [19].
Anyway, ou pu pose he e is o design an algo i hm o cons uc ing su -
icien ly la ge cliques in G , a leas o dep h g ea e han a hi d o a ull
Hadama d ma ix. To his end, we need o s udy he p ope ies o G in a
mo e de ailed way.
In wha ollows, o b e i y, we will adop he addi i e no a ion o ep-
esen ing Hadama d ma ices, so ha he 1s u n o 0s and he −1s u n o
1s.
This way, k- ec o s in G a e now desc ibed as (0,1)- ec o s o leng h 4
consis ing o p ecisely 2 ones (and hence 2 ze os), which a e dis ibu ed in
he ollowing way: he e a e exac ly kones in posi ions 1 h ough , o he −k
ones in posi ions +1 h ough 2 , ano he −kones in posi ions 2 +1 h ough
3 , he las kones being loca ed in posi ions 3 + 1 h ough 4 .
Each o hese k- ec o s may be s aigh o wa dly codi ied as an in ege ,
assuming ha he k- ec o is he bina y ep esen a ion o a decimal numbe .
The e o e cliques a e codi ied as lis s o in ege s, each o hem being he deci-

mal ep esen a ion o a bina y numbe consis ing o 2 ones and leng h less o
equal o 4 .
Lemma 3 Ac ually, i can be assumed ha 0≤k≤ ⌊
2⌋.
P oo This is a s aigh o wa d consequence o he ac ha he nega ion o a
ow does no a ec o he se o i s o hogonal ec o s.
Tha being so, he ull se o e ices adjacen o a gi en k- e ex may
be ob ained by calcula ing hose s- ec o s wo hogonal o , o 0 ≤s≤ ⌊
2⌋,
and hen adding hei complemen s. No ice ha wi h he addi i e no a ion a
hand, a k- ec o and a s- ec o wa e o hogonal i and only i hey sha e
exac ly 2 bi s.
We now desc ibe a p ocedu e o de e mining a se δ o gene a o s o he
adjacency lis ela ed o a ixed k- ec o , ha is, gene a ing hose s- ec o s
wo hogonal o .
In o de o compu e he o al amoun o coincidences be ween and w,
one may spli he ec o s by qua e s, and coun he amoun io 1-bi s ( o
he i s and las qua e s) and 0-bi s ( o he second and hi d qua e s) ha
hese ec o s sha e in each o hese basic qua e s.
Lemma 4 A he i s and ou h ( esp., he second and hi d) qua e s he
numbe io coincidences in 1s ( esp, in 0s) uns in he ange [max(0, s +k−
),min(k, s)]. Ac ually, assuming he condi ions in Lemma 3, i∈[0,min(k, s)].
Lemma 5 A each qua e , he numbe αio o al coincidences (bo h in 1s
and 0s) sa is ies αi= −s−k+2i, and uns in he ange [| −k−s|, −|s−k|].
Ac ually, assuming he condi ions in Lemma 3, αi∈[ −s−k, − |s−k|].
P oo Assume ha a a gi en qua e he ec o s and wsha e exac ly i
1-bi s. Then whas k−i0-bi s in hose posi ions whe e he emaining 1-bi s
o a e loca ed. Analogously, has s−i0-bi s in hose posi ions whe e he
emaining 1-bi s o wa e loca ed. Thus and wsha e exac ly −i−(k−
i)−(s−i) = −k−s+i0-bi s. Since and wsha e i1-bi s and −k−s+i
0-bi s, he o al numbe o coincidences is αi= −k−s+ 2i.
Co olla y 1 αi+1 =αi+ 2.
Le deno e n= min(k, s). In he condi ions abo e, he se o o al coin-
cidences is gi en by −s−k=α0< . . . < αn= − |s−k|. We may now
desc ibe he se o s- ec o s adjacen o a gi en k- ec o .
P oposi ion 1 The se o ec o s o hogonal o a gi en k- ec o co esponds
o he ull se o dis ibu ions o ec o s sa is ying uples o o al coincidences
(αi1, αi2, αi3, αi4)such ha αi1+αi2+αi3+αi4= 2 .
P oposi ion 2 The se o uples (αi1, αi2, αi3, αi4)which gi e ise o o hog-
onal s- ec o s a e cha ac e ized as he solu ions o he ollowing sys em o
diophan ine equa ions



x0α0+. . . +xnαn= 2
x0+. . . +xn= 4
xi∈Z: 0 ≤xi≤4
(1)
He e, n= min(k, s)and xiindica es how many coincidences o he ype αi
mus occu among he ou qua e s.
We now gi e a cons uc i e way o sol e he sys em abo e.
P oposi ion 3 The e exis s a solu ion o he sys em (1) i 4α0≤2 ≤4αn.
P oo F om Co olla y 1, we know ha he di e ence be ween wo consecu i e
αijis 2.
Since 4α0, 2 and 4αna e e en and aking in o accoun Co olla y 1, we
conclude ha e e y e en numbe in he ange [4α0,4αn] may be (no uniquely,
in gene al) w i en as a combina ion αi1+αi2+αi3+αi4 o some alues
α0≤αi1≤αi2≤αi3≤αi4≤αn.
The condi ion abo e may be s aigh o wa dly gene alized o he case o
solu ions ela ed o uples o he ype (αi1, αi2, αi3, αi4), αi1≤αi2≤αi3≤
αi4.
Co olla y 2 Fixed and 0≤k, s ≤ ⌊
2⌋, he se sol o solu ions o he sys em
(1) may be cons uc ed in he ollowing way:
sol ← ∅
α0← −k−s
αn← − |k−s|
o i1 om max{α1,2 −3αn} o min{αn,⌊2
4⌋} wi h s ep 2 do
o i2 om max{i1,2 −i1−2αn} o min{αn,⌊2 −i1
3⌋} wi h s ep 2
do
o i3 om max{i2,2 −i1−i2−αn} o min{αn,⌊2 −i1−i2
2⌋} wi h
s ep 2 do
sol ←sol ∪ {{i1, i2, i3,2 −i1−i2−i3}}
od
od
od
Gi en a uple (αi1, αi2, αi3, αi4) solu ion o (1), cons uc he ou ma ices
Nkwhose ows a e hose ec o s sa is ying αik o al coincidences wi h he
co esponding qua e o . By cons uc ion, he jux aposi ion o any o he
ows o hese ma ices gi es a ec o o hogonal o .
P oposi ion 4 A se δ o gene a o s o he adjacency lis o may be
s aigh o wa dly cons uc ed in e ms o ma ices o he ype abo e.
In spi e o he ac ha he size (bo h in edges and e ices) o G g ows
exponen ially in , he p ocedu e desc ibed in P oposi ion 4 is a cheape way
(in e ms o bo h ime and space) o sa ing his in o ma ion.
We will illus a e now how he p oposi ion abo e wo ks by means o an
example. In o de o simpli y he eading, in wha ollows we will use a e ical
line | o sepa a e he di e en qua e s o a k- ec o .
Example 2 Le us conside he case = 5, k= 2 and = 684646 (i s bina y
ep esen a ion gi es he 2- ec o = (10100|11100|10011|00110)). We a e go-
ing o calcula e he ull se o s- ec o s o hogonal o , o 0 ≤s≤2 = ⌊5
2⌋
( ecall ha he emaining o hogonal ec o s a e ob ained by simply in e -
changing he 0-bi s and 1-bi s, since hey a e he nega ion o he ec o s jus
calcula ed).
1. Case s= 0.
F om Lemma 4, we know ha he e is jus one alue o he numbe io
coincidences in 1-bi s, namely i= 0. Consequen ly, he e is jus one alue
αi, namely α0= 3.
Since 4α0= 12 6= 10 = 2 ·5, he sys em (1) has no solu ions, so he e is no
0- ec o o hogonal o .
This was e iden om he e y beginning, since he e is only one 0- ec o ,
w= 32736 (i.e. w= (00000|11111|11111|00000)), and i is no o hogonal
o .
2. Case s= 1.
F om Lemma 4, we know ha i∈ {0,1}, and hence αi∈ {2,4}. The se
o di e en ways in which ou αimay be o de less chosen o sum 10 is
desc ibed by he sys em (1),
2x0+ 4x1= 10
x0+x1= 4
Since 4α0= 8 ≤10 ≤4α1= 16, he e exis solu ions o he sys em. In
ac , he e is jus one solu ion, (x0, x1) = (3,1), which co esponds o he
ollowing dis ibu ion o o al coincidences (up o eo de ing): (2,2,2,4).
In o de o explici ly cons uc hose 1- ec o s wmee ing he dis ibu ion
(2,2,2,4), we ha e o ind hose 1- ec o s wi h 0 coincidences wi h in
1-bi s in he i s qua e , 0 coincidences in 0-bi s in he second and hi d
qua e s, and 1 coincidence in 1-bi s in he ou h qua e .
Since is a 2- ec o , in he i s qua e he e a e 5−2
1choices o plac-
ing he 1-bi o wamong he 0-bi s o . Analogously, he e a e 5−2
1
choices o placing he 0-bi o wamong he 1-bi s o in he second and
hi d qua e s. And he e a e 2
1choices o placing he 1-bi o wamong
he 1-bi s o .
In conclusion, he se o 1- ec o s mee ing he dis ibu ion o o al coin-
cidences (2,2,2,4) is gene a ed by he jux aposi ion o any o he ows o
he ollowing ma ices


0 1 0 0 0
0 0 0 1 0
0 0 0 0 1

×

0 1 1 1 1
1 0 1 1 1
1 1 0 1 1

×

01111
11101
11110

×0 0 1 0 0
0 0 0 1 0
Simila schemes a e achie ed wi h he emaining o de ings o he alid
dis ibu ion o o al coincidences, (2,2,4,2), (2,4,2,2) and (4,2,2,2). In
ac , hey may be ob ained by simply pe mu ing and/o nega ing some
sui able columns o he dis ibu ion abo e.
3. Case s= 2.
F om Lemma 4, we know ha i∈ {0,1,2}, and hence αi∈ {1,3,5}. The
se o di e en ways in which ou αimay be o de less chosen o sum 10 is
desc ibed by he sys em (1),
x0+ 3x1+ 5x2= 10
x0+x1+x2= 4
Since 4α0= 4 ≤10 ≤4α2= 20, he e exis solu ions o he sys em. In
ac , he e a e jus wo solu ions, (x0, x1, x2)∈ {(2,1,1),(1,3,0)}, which
co espond o he ollowing dis ibu ion o o al coincidences (up o e-
o de ing): (1,1,3,5) and (1,3,3,3).
In o de o explici ly cons uc hose 2- ec o s wmee ing he dis ibu ion
(1,1,3,5), we ha e o ind hose 2- ec o s wi h 0 coincidences wi h in
1-bi s in he i s qua e , 0 coincidences in 0-bi s in he second qua e , 1
coincidence in 0-bi s in he hi d qua e , and 2 coincidences in 1-bi s in
he ou h qua e .
Since is a 2- ec o , in he i s qua e he e a e 5−2
2choices o plac-
ing he 1-bi s o wamong he 0-bi s o . Analogously, he e a e 5−2
2
choices o placing he 0-bi s o wamong he 1-bi s o in he second
qua e . Analogously, in he hi d qua e , he e a e 2
1choices o plac-
ing one 0-bi o wamong he 0-bi s o , and o each o hem, he e a e
5−2
1choices o placing he second 0-bi o wamong he 1-bi s o .
Finally, he e a e 2
2choices (jus one!) o placing he 1-bi s o wamong
he 1-bi s o .
In conclusion, he se o 2- ec o s mee ing he dis ibu ion o o al coin-
cidences (1,1,3,5) is gene a ed by he jux aposi ion o any o he ows o
(αi1, αi2, αi3, αi4)), in e ms o dis ibu ions (i1, i2, i3, i4) o coincidences in 1s
( o he i s and las qua e s) and 0s ( o he second and hi d qua e s).
P oposi ion 5 The se o s- ec o s o hogonal o a gi en k- ec o co e-
sponds o he ull se o dis ibu ions o s- ec o s sa is ying uples o coin-
cidences in 1s ( i s and ou h qua e s) and 0s (second and hi d qua e s)
(i1, i2, i3, i4)such ha i1+i2+i3+i4= 2s+ 2k− . Fu he mo e, his is
possible i 2s+ 2k− ≥0.
P oo F om P oposi ion 1, we know ha he se o s- ec o s o hogonal o
a gi en k- ec o is cha ac e ized by hose dis ibu ions o o al coincidences
(αi1, αi2, αi3, αi4) such ha αi1+αi2+αi3+αi4= 2 .
Since αi= −s−k+ 2i om Lemma 5, he ela ion abo e comes o be
4 −4k−4s+ 2i1+ 2i2+ 2i3+ 2i4= 2 ⇔i1+i2+i3+i4= 2s+ 2k− .
Now, on one hand, since 0 ≤ij≤min(k, s), he alue i1+i2+i3+i4 uns
o e he ange 0 ≤i1+i2+i3+i4≤4 min(k, s).
On he o he hand, since 0 ≤s, k ≤ ⌊
2⌋, i is clea ha 2s+ 2k− ≤
2 min(k, s).
Thus, p o ided 2s+ 2k− ≥0, his alue is in he ange alid o i1+
i2+i3+i4, and he e o e he e exis s a dis ibu ion o coincidences in 1s (a
i s and ou h qua e s, i1and i4 espec i ely) and 0s (a second and hi d
qua e s, i2and i3 espec i ely), such ha i1+i2+i3+i4= 2s+ 2k− .
Now i is appa en ha no all possible alues sin he ange 0 ≤s≤ ⌊
2⌋
do p o ide s- ec o s o hogonal o a gi en k- ec o .
P oposi ion 6 Fixed a k- ec o , he e exis s- ec o s o hogonal o i
s∈[⌈
2⌉ − k, ⌊
2⌋].
P oo The uppe bound is gi en in Lemma 3.
On he o he hand, om P oposi ion 5, he e exis s- ec o s o hogonal
o a gi en k- ec o i 0 ≤2s+ 2k− . Consequen ly, s≥
2−k, ha is,
s≥ ⌈
2⌉ − k.
Fu he mo e, we may s aigh o wa dly p ecise he numbe o s- ec o s
o hogonal o a gi en k- ec o , o some ixed s∈[⌈
2⌉ − k, ⌊
2⌋].
Lemma 6 Fixed a alid dis ibu ion (i1, i2, i3, i4), he numbe o s- ec o s
o hogonal o a gi en k- ec o is gi en by he exp ession:
k
i1 −k
s−i1k
i2 −k
s−i2k
i3 −k
s−i3k
i4 −k
s−i4

Table 6 Dis ibu ion o s- ec o s o hogonal o a k- ec o .
= 3
k= 0 k= 1
s= 0 0 0
s= 1 0 32
= 4 = 5
k= 0 k= 1 k= 2 k= 0 k= 1 k= 2
s= 0 0 0 1 0 0 0
s= 1 0 81 96 0 0 216
s= 2 1296 486 454 0 3456 3240
= 6 = 7
k= 0 k= 1 k= 2 k= 3 k= 0 k= 1 k= 2 k= 3
s= 0 0 0 0 1 0 0 0 0
s= 1 0 0 256 486 0 0 0 768
s= 2 0 10000 14688 15795 0 0 40000 57024
s= 3 160000 60000 49920 47148 0 480000 440000 422208
= 8
k= 0 k= 1 k= 2 k= 3 k= 4
s= 0 0 0 0 0 1
s= 1 0 0 0 625 1536
s= 2 0 0 50625 147000 183904
s= 3 0 1500625 2352000 2601000 2655744
s= 4 24010000 9003750 7183750 6483750 6297030
= 9
k= 0 k= 1 k= 2 k= 3 k= 4
s= 0 0 0 0 0 0
s= 1 0 0 0 0 2000
s= 2 0 0 0 243000 464000
s= 3 0 0 7203000 11210000 12912000
s= 4 0 76832000 69629000 65367000 63430000
= 10
k= 0 k= 1 k= 2 k= 3 k= 4 k= 5
s= 0 0 0 0 0 0 1
s= 1 0 0 0 0 1296 3750
s= 2 0 0 0 194481 858600 1200625
s= 3 0 0 9834496 32773650 48326400 53560000
s= 4 0 252047376 407209600 453248775 468312600 472003750
s= 5 4032758016 1512284256 1180754176 1041640236 978746976 960098756
The ollowing ables show he numbe o s- ec o s o hogonal o a gi en
k- ec o , o 3 ≤ ≤10, 0 ≤k≤ ⌊
2⌋, and 0 ≤s≤ ⌊
2⌋.
In pa icula , hese esul s sugges ha la ge cliques in G should consis
o k- ec o s, o la ge alues o k, close o ⌊
2⌋.
This seems o be so, as he calcula ions below sugges .
Fo each 3 ≤ ≤9, we choose a andom a Hadama d ma ix o o -
de 4 om Sloane’s online lib a y [22], say had.12,had16.4,had20.hall.n,
had24.pal,had28.pal2,had32.pal,had36.pal2.
We now no malize hese ma ices, by means o he ollowing algo i hm.
No ice ha since jus nega ion and pe mu a ion o columns a e used, he
Hadama d cha ac e o he ma ix is p ese ed.
Algo i hm 3 Hadama d no maliza ion
–Nega e hose columns consis ing o a i s nega i e en y.
–Now, loca e hose columns i,1≤i≤2 , consis ing o a second nega i e
en y. Loca e hose columns j,2 + 1 ≤j≤4 , consis ing o a second
posi i e en y. In e change hem.
–P oceed as he s ep be o e, now by qua e s. As a esul , you will ob ain a
no malized Hadama d ma ix.
Now we andomly ix a ⌊
2⌋- ec o among he ows o hese ma ices ( o
ins ance, he i s such occu ence). The able below shows he dis ibu ion
o he alues s, o he s- ec o s o he emaining ows. In addi ion, we also
include he dis ibu ion o (no o de ed!) o al coincidences (αi1, . . . , αi4).
Table 7 Rows in Hadama d ma ices a e k- ows, o k∈ {⌊
2⌋ − 1,⌊
2⌋}.
ow s=⌊
2⌋s=⌊
2⌋ − 1 #{ o al coincidences}
3 4 8 0 (1,1,1,3) →8
4 6 8 4
(2,2,2,2) →4
(0,2,2,4) →4
(1,1,3,3) →4
5 5 15 1
(1,3,3,3) →12
(1,1,3,5) →3
(2,2,2,4) →1
6 4 11 9
(2,2,4,4) →9
(2,2,2,6) →1
(0,4,4,4) →1
(1,3,3,5) →6
(3,3,3,3) →3
7 5 21 3
(3,3,3,5) →16
(1,3,5,5) →3
(1,3,3,7) →2
(2,2,4,6) →2
(2,4,4,4) →1
8 4 12 16
(2,4,4,6) →12
(3,3,5,5) →12
(1,5,5,5) →2
(3,3,3,7) →2
9 4 26 6
(3,5,5,5) →20
(1,5,5,7) →6
(2,4,6,6) →6
The able abo e sugges s ha one should ocus on k- ec o s o k∈ {⌊
2⌋−
1,⌊
2⌋}. Fu he mo e, he ec o o o al coincidences pe qua e uses o be
homogeneously dis ibu ed.
Wi h hese ideas a hand, we nex design a as heu is ic sea ching o (o
e en ually ex ending) cliques in G .
Algo i hm 4 Fas heu is ic o ex ending cliques in G .
Inpu : a clique C in G
Ou pu : a clique C′ in G con aining C
C′=C
o k om ⌊
2⌋ o ⌊
2⌋ − 1s ep −1do
i e = 0
while i e < do
{bool, }=buildg apas(C′, k)
I bool hen i e = 0;C′=C′∪ { }else i e =i e + 1
od
od
C′
The unc ion buildg apas ies o cons uc an s- ec o qua e by qua e
(in a andom o de ing), a ending o he ollowing aspec s:
–Selec a numbe o o al coincidences o he qua e , acco ding o he
ange alid a his s ep (i.e. such ha equa ion (1) can be sa is ied), and
wi h p obabili y p opo ional o he numbe o i s appea ances in he se
o solu ions desc ibed in Co olla y 2.
–Once he desi ed numbe o o al coincidences has been ixed, a gene ic
p ocedu e is pe o med, o cons uc ing a alid qua e (i.e. such ha (1)
can be sa is ied). This heu is ic consis s o popula ions o 4 indi iduals.
I no alid qua e is ound a e 4 gene a ions, he sea ch ends wi h a
ailu e. In his case, he las qua e cons uc ed so a is dele ed, and he
p ocess goes on om his poin . This si ua ion is limi ed o occu a mos
imes.
–This sea ch is pe o med a mos 10 imes. I no alid ec o is cons uc ed
a e hese 10 a emp s, he sea ch s ops and a False boolean is e u ned.
The able below shows, o e e y 2 ≤ ≤10, he numbe o essays which
ha e been execu ed looking o cliques in G , he a e age ime equi ed in
hese calcula ions, he a e age size o hese cliques, he la ges size ound so
a , he ime equi ed in his calcula ion and one ins ance among he la ges
cliques al eady ound.
Table 8 Resul s ob ained om Algo i hm 4.
Essays A .Time A .Size La .S. Time Clique
2 10 1.4′′ 5 5 1.4′′ 86,101,149,89,60
3 10 0.565′′ 9 9 0.5′′ 1452,2396,1393,874,756,2482,921,
1242,2281
4 10 19.603′′ 11 12 17.28′′
25542,15462,13769,39626,50538,
22099,38294,22188,22876,52421,
22947,27802
Essays A .Time A .Size La .S. Time Clique
5 10 27.369′′ 9 17 76.924′′
193425,586090,808611,420073
350674,408358,222834,109987,
315192,341833,604856,662897,
171722,308468,121445,218540,
552900
6 10 51.38′′ 7.6 10 56.87′′
13215089,13015273,10053835,12875531,
12954262,6768979,3454163,9730420,
3324617,6759253,5685752,8874722,
999010,906181
7 10 1′23′′ 8 9 1′46′′
159860692,161016643,73886147,
142481171,173143250,170760901,
21953176,43986594,203259148
8 10 2′11′′ 7.6 9 2′53′′
866473426,1497876124,1273533381,
1697995341,1439971764,3784746441,
2345981979,2309832360,242628440
9 10 3′02′′ 7.8 9 3′05′′
56095030680,38163367817,
41103334725,54854789721,
22744355553,45279148512,
4785499937,52133944916,
60209197830
Al hough he size o he cliques ob ained so a a e smalle han hose
cons uc ed by he p eceden p ocedu es, i is a ema kable ac ha his
algo i hm is subs an ially as e . In ac , his p ocedu e should be conside ed as
an ex ension unc ion o cliques be e han a p ocedu e i sel o cons uc ing
cliques s a ing om he emp y g aph.
This idea is suppo ed by he calcula ions showed in he able below, whe e
cliques Co size |C| ≤ 2 in G cons uc ed by he p ocedu es desc ibed in [8,
10] (a e no maliza ion by Algo i hm 3) a e ex ended o la ge cliques C′(o
size |C′| ≥ 2 , mo e han a hal o a ull Hadama d ma ix!) wi h Algo i hm
4.
Table 9 Algo i hm 4 applied o P Hm×4 in [10] p oduces P H(m+n)×4 , wi h m+n≥2 .
|C| |C′| ime added e ices
4 5 12 17.97′′ 21930,50745,25500,13107,
37740,42330,51510
5 5 7 19.38′′ 118659,341714
6 9 15 1′07′′ 3099915,9123660,8841105,
10606050,4844385,4692870
7 9 9 1′03′′
8 13 17 2′51′′ 1923517785,3032697660,
1695521520,2956808130
No ice ha o = 7, he inpu clique has no been ex ended o a la ge
one. We suspec ha he inpu clique is maximal, and he e o e a la ge clique
con aining i could no exis .
5 Conclusions
In his pape we ha e desc ibed h ee algo i hms looking o p e y la ge pa ial
Hadama d ma ices (i.e. abou a hi d o a ull Hadama d ma ix), in e ms
o cliques o he Hadama d G aph G .
The i s one (Algo i hm 1) pe o med some kind o local exhaus i e sea ch,
and consequen ly is expensi e om he ime consuming poin o iew. So we
decided o design some heu is ic o cons uc ing pa ial Hadama d ma ices.
Ou i s app oach (Algo i hm 2) consis ed in an adap a ion o Singh and
Gup a’s gene ic algo i hm o he Maximum Clique P oblem. Un o una ely,
i did no wo k p ope ly, since i used Algo i hm 1 o ex ending cliques, and
consequen ly was e y expensi e in ime as well.
Algo i hm 4 p io i izes he equi ed p ocessing ime be e han he inal
size o he pa ial Hadama d ma ix o be ob ained. Expe imen al esul s show
ha his algo i hm may ou pu p e y la ge pa ial Hadama d ma ices (la ge
han hal a ull Hadama d ma ix!), p o ided a sui able ini ial clique is gi en
as inpu da a.
All he algo i hms ha we ha e p esen ed he e a e based on he p ope ies
o he Hadama d G aph G which ha e been desc ibed in Sec ion 2.
I would be an in e es ing ques ion whe he di e en echniques and me h-
ods could be conside ed o designing al e na i e algo i hms sea ching o la ge
pa ial Hadama d ma ices. Fo ins ance, one could ask abou he echniques
and me hods which ha e been shown o be use ul when manipula ing ull
Hadama d ma ices.
Un o una ely, his will no be he case, in gene al. Fo ins ance, conside
he case o he cocyclic app oach.
Mo e conc e ely, he cocyclic amewo k has a ised as a p omising way o
cons uc (cocyclic) Hadama d ma ices [14,1,3,4]. One could ask whe he he
cocyclic amewo k is also a good place o look o pa ial Hadama d ma ices.
Ac ually, his is no he case.
P oposi ion 7 The dep h o any pa ial Hadama d ma ix which is a subma-
ix o a cocyclic ma ix M is a mos a hal o he size o M .
P oo A ending o he p oo o he cocyclic Hadama d es in [16] (see Lemma
1.4 on p. 281), ixed a mul iplica i e g oup G={g1= 1, . . . , gn}and a cocyclic
ma ix M = ( (gi, gj)) o e G, ows gi6=gkin M a e o hogonal i and
only i he summa ion o he ow gig−1
k(6=g1) is ze o (and consequen ly, he
summa ion o he ow gkg−1
ias well).
I a ow gk6=g1in M ails o sum ze o, hen, o each 1 ≤i≤n, he pai
o ows {gi, g−1
kgi}(and also {gi, gkgi}) ails o be o hogonal. By pa i ioning
he ows o M in o pai s o he ype {gi, g−1
kgi}, i u ns ou ha such a pai
con ibu es a mos one ow o a pa ial Hadama d ma ix included in M .
Consequen ly, he dep h o any pa ial Hadama d ma ix which is a subma ix
o M is a mos n
2, as claimed.

I would be in e es ing o hink abou he way in which k- e ices in G
could be combined in o de o ge la ge cliques.
Ne e heless, i would be also in e es ing o in es iga e whe he imp o ed
e sions o he algo i hms desc ibed in his pape could be designed, a ending
o o he conside a ions.
Acknowledgemen s All au ho s a e pa ially suppo ed by he esea ch p ojec s FQM–
016 and P07-FQM-02980 om Jun a de Andaluc´ıa and MTM2008-06578 om Minis e io de
Ciencia e Inno aci´on (Spain).
Re e ences
1. V. ´
Al a ez, J.A. A ma io, M.D. F au, P. Real. A gene ic algo i hm o cocyclic Hadama d
ma ices. AAECC16, LNCS 3857, 144–153. Sp inge , Heidelbe g, (2006).
2. V. ´
Al a ez, J.A. A ma io, M.D. F au, E. Ma ´ın, A. Osuna. E o Co ec ing Codes om
Quasi-Hadama d Ma ices. WAIFI07, LNCS 4547, 294–302. Sp inge , Heidelbe g, (2007).
3. V. ´
Al a ez, J.A. A ma io, M.D. F au, P. Real. A sys em o equa ions o desc ibing
cocyclic Hadama d ma ices. Jou nal o Comb. Des., 16 (4), 276–290, (2008).
4. V. ´
Al a ez, J.A. A ma io, M.D. F au, P. Real. The homological educ ion me hod o
compu ing cocyclic Hadama d ma ices. J. Symb. Compu ., 44, 558–570, (2009).
5. V. ´
Al a ez, M.D. F au, A. Osuna: A gene ic algo i hm wi h guided ep oduc ion o
cons uc ing cocyclic Hadama d ma ices. ICANNGA09, LNCS 5495, 150–160. Sp inge ,
Heidelbe g, (2009).
6. I.M. Bomze, M. Budinich, P.M. Pa adalos and M. Pelillo. The maximum clique p oblem.
Handbook o Combina o ial Op imiza ion, D.Z. Du and P.M. Pa adalos Eds. No well,
MA: Kluwe , ol. 4 (1999).
7. R. Ca aghan, P.M. Pa dalos. An exac algo i hm o he maximum clique p oblem.
Ope . Res. Le ., 9, 375–382, (1990).
8. W. de Launey. On he assymp o ic exis ence o pa ial complex Hadama d ma ices and
ela ed combina o ial objec s. Disc e e Applied Ma hema ics 102, 37–45, (2000).
9. W. de Launey. On he assymp o ic exis ence o Hadama d ma ices. Jou nal o Combi-
na o ial Theo y, Se ies A 116, 1002–1008, (2009).
10. W. de Launey and D.M. Go don. A commen on he Hadama d conjec u e. Jou nal o
Combina o ial Theo y, Se ies A 95 (1), 180–184, (2001).
11. W. de Launey and H. Kha aghani. On he assymp o ic exis ence o cocyclic Hadama d
ma ices. Jou nal o Combina o ial Theo y, Se ies A 116, 1140–1153, (2009).
12. J. Has ad. Clique is ha d o app oxima e wi hin n1−ǫ.P oc. 37 h Annu. Symp. Found.
Compu . Sci., Bu ling on, 627-636, (1996).
13. A. Hedaya and W.D. Wallis. Hadama d Ma ices and Thei Applica ions. Ann. S a .
6, 1184–1238, (1978).
14. K.J. Ho adam. Hadama d ma ices and hei applica ions. P ince on Uni e si y P ess,
P ince on (2007).
15. K.J. Ho adam and W. de Launey. Cocyclic de elopmen o designs. J. Algeb aic Com-
bin.,2(3), 267–290, (1993). E a um: J. Algeb aic Combin., (1), pp. 129, (1994).
16. K.J. Ho adam and W. de Launey. Gene a ion o cocyclic Hadama d ma ices. Compu-
a ional algeb a and numbe heo y (Sydney, 1992), olume 325 o Ma h. Appl., 279–290.
Kluwe Acad. Publ., Do d ech , (1995).
17. N. I o. On a amily o conjugacy classes g aphs. Mem. Konan Uni . 31, 105–112, (1984).
18. N. I o. Hadama d G aphs I. G aphs Combin. 1(1), 57–64, (1985).
19. S. Kho . Imp o ed inapp oximabili y esul s o maxclique, ch oma ic numbe and ap-
p oxima e g aph colo ing. P oceedings o 42nd Annual IEEE Symposium on Founda ions
o Compu e Science (FOCS), 600-609 (2001).
20. E. Ma chio i. Gene ic, I e a ed and Mul is a Local Sea ch o he Maximum Clique
P oblem. E oWo kshop 2002, LNCS 2279, 112–121. Sp inge -Ve lag, Be lin Heidelbe g,
(2002).
21. A. Singh and A.K. Gup a. A hyb id heu is ic o he maximum clique p oblem. J.
Heu is ics, 15, 5-22 (2006).
22. N.J.A. Sloane. h p://www2. esea ch.a .com/˜njas/hadama d