i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 121 — #1
i
i
i
i
i
i
HADAMARDOVEMATRIKEINMISIJAMARINER9
ALEKSANDAR JURI
ˇ
SI
´
C
Fakulteta za raˇ cunalniˇ stvo in informatiko
Univerza v Ljubljani
Math. Subj. Class. (2000): 05B20, 05B25, 05B30, 05C12, 05C62, 05C50, 05E20, 05E30,
05E35, 68R05, 68R10, 68R141, 11T71, 51E, 52C
J. Hadamard (1865–1963) je bil eden izmed pomembnejˇ sih matematikov na prehodu
iz 19. v 20. stoletje. Njegova najpomembnejˇ sa dela zajemajo podroˇ cja teorije analitiˇ cnih
funkcijinmatematiˇ cneﬁzike. Najboljznanpajepodokazuizrekaogostotipraˇ stevil(leta
1896, hkrati s C. J. De La Vall´ ee-Poussinom). V temˇ clanku predstavljamo Hadamardove
matrike, njihove karakterizacije s Hadamardovimi graﬁ, geometrijami in Hadamardovimi
kodami ter nekaj zanimivih konstrukcij in uporabo Hadamardovih matrik v praksi.
HADAMARD MATRICES AND MARINER 9 MISSION
J. Hadamard (1865–1963) was one of more important mathematicians at the turn of
the 19
th
century. His is most celebrated for his contributions in analtycal functions and
mathematical physics. His most important result is the prime number theorem, which he
proved in 1896 (at the same time as C. J. De La Vall´ ee-Poussin). In this article we intro-
duce Hadamard matrices, their characterizations with Hadamard graphs, geometries and
Hadamard codes, some interesting constructions and applications of Hadamard matrices
in practice.
Hadamardove matrike
Naj bo A kvadratna matrika z n stolpci, za katero velja |(A)
ij
| ≤ 1.
Kako velika je lahko detA?
ˇ
Ce si vrstice (oziroma stolpce) matrike A pred-
stavljamo kot vektorje v R
n
, potem je njihova dolˇ zina navzgoraj omejena
s
√
n. Po drugi strani pa vemo, da absolutna vrednost determinante pred-
stavlja prostornino paralelepipeda, ki ga doloˇ cajo ti vektorji, torej velja
|detA|≤n
n/2
. Ali lahko v tej neenakosti velja enakost? V tem primeru so
vsi elementi matrike enaki ±1, vsaki dve razliˇ cni vrstici (oziroma stolpca)
pa morata biti paroma pravokotni. To je bila motivacija Brennerja (1972)
za naslednjo deﬁnicijo.
Kvadratni matriki H z n vrsticami in z elementi ±1, za katero velja
HH
T
=nI
n
, (1)
pravimo Hadamardova matrika reda n. Glede na to, da matriˇ cni produkt
v (1) sestavljajo produkti vrstic matrike H, lahko stolpce (oziroma vrstice)
Obzornik mat. ﬁz. 56 (2009) 4 121
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 122 — #2
i
i
i
i
i
i
Aleksandar Juriši´ c
Hadamardove matrike poljubno premeˇ samo (permutiramo) ali pa pomno-
ˇ zimo z−1, pa bo nova matrikaˇ se vedno Hadamardova. Rekli bomo, da sta
si taki Hadamardovi matriki ekvivalentni. Na prvi pogled se zdi, da iden-
titeta (1) zagotavlja le pravokotnost vrstic. Vendar jo lahko pomnoˇ zimo
z desne s H in dobimo HH
T
H = nI
n
H oziroma HH
T
H = HnI
n
. Upo-
ˇ stevamo ˇ se obrnljivost matrike H, in ˇ ze smo pri identiteti H
T
H = nI
n
, v
kateri sta vlogi vrstic in stolpcev zamenjani glede na identiteto (1). To po-
meni med drugim tudi, da so razliˇ cni stolpci matrikeH paroma pravokotni.
Predstavimo nekaj manjˇ sih Hadamardovih matrik:
(1),
  1 1
1 −1
  ,




1 1 1 1
1 −1 1 −1
1 1 −1 −1
1 −1 −1 1




in












+ + + + + + + +
+ − + − + − + −
+ + − − + + − −
+ − − + + − − +
+ + + + − − − −
+ − + − − + − +
+ + − − − − + +
+ − − + − + + −












(v slednji smo ±1 zamenjali s + in −). Zgornje Hadamardove matrike
oznaˇ cimo zaporedoma s H
1
, H
2
, H
4
in H
8
(indeks torej kaˇ ze njihovo veli-
kost). Opazimo, da sta v vseh ˇ stirih primerih prva vrstica in prvi stolpec
sestavljenaizsamihenic. SameenicevprvemstolpcuoziromavrsticiHada-
mardove matrike dobimo tako, da vrstice oziroma stolpce matrike H, ki se
zaˇ cnejo z negativnim ˇ stevilom, pomnoˇ zimo z −1. Temu postopku pravimo
normalizacija.
ˇ
Cejen>1, potemmoraimetivnormaliziranimatrikivsaka
preostala vrstica polovico pozitivnih in polovico negativnih elementov, kar
pomeni, da je n sod. S podobnim razmislekom pridemo do ˇ se moˇ cnejˇ sega
sklepa.
Trditev.
ˇ
Ce je H Hadamarova matrika reda n, potem je n = 1, n = 2 ali
pa 4|n.
Dokaz. Naj bo n> 2. Normaliziramo H, potem pa s permutacijo stolpcev
spravimo prve tri vrstice matrike H v naslednjo obliko:
1. vrstica
2. vrstica
3. vrstica
+++...+++
+++...+++
+++...+++
| {z }
a stolpcev
+++...+++
+++...+++
−−−...−−−
| {z }
b stolpcev
+++...+++
−−−...−−−
+++...+++
| {z }
c stolpcev
+++...+++
−−−...−−−
−−−...−−−
| {z }
d stolpcev
122 Obzornik mat. ﬁz. 56 (2009) 4
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 123 — #3
i
i
i
i
i
i
Hadamardove matrike in misija Mariner 9
Za a,b,c,d∈N
0
velja:
a+b+c+d = n,
a−b+c−d = 0 (produkt tretje vrstice s prvo vrstico),
a+b−c−d = 0 (produkt druge vrstice s prvo vrstico),
a−b−c+d = 0 (produkt druge in tretje vrstice),
vsota zgornjih ˇ stirih enaˇ cb pa nam da 4a=n.
ˇ
Ce se v zgornjem sistemu enaˇ cb osredotoˇ cimo samo na predznake, v
njem zagledamo matriko, ki je ekvivalentna H
4
. Kot bomo videli, lahko
pridemo do H
4
na veˇ c naˇ cinov. Do naslednjega si v naslednjem razdelku
pomagamo z graﬁ, bolj natanˇ cno s 4-razseˇ zno kocko.
Karakterizaciji z graﬁ in geometrijami
Vpovezanemgrafuje razdalja meddvemavozliˇ sˇ cemadeﬁniranakotˇ ste-
vilo povezav najkrajˇ se poti med njima, njegov premer pa je enak najveˇ cji
razdaljimednjegovimivozliˇ sˇ ci. Vpovezanemgrafupremerad∈Nizberimo
vozliˇ sˇ ci u in v, ki sta na razdalji i∈{0,1,...,d}, ter opazujmo sosede voz-
liˇ sˇ ca v glede na razdaljo od vozliˇ sˇ ca u. Zaradi trikotniˇ ske neenakosti velja,
da so le-ta od u lahko oddaljena bodisi i−1 (kadar je i> 0), i ali pa i+1
(kadar jei<d).
ˇ
Stevilo teh sosedov na razdaljii−1,i ini+1 oznaˇ cimo za-
poredoma sc
i
,a
i
inb
i
. Oˇ citno jea
0
=0 inc
1
=1, smiselno pa je privzetiˇ se
c
0
=0=b
d
.
ˇ
Ceˇ stevilaa
i
,b
i
inc
i
nisoodvisnaodizbirevozliˇ sˇ cuinv naraz-
daljiizavsaki∈{0,...,d}, bomorekli, dajegraf razdaljno-regularen. Tak
graf je seveda regularen, saj je ˇ stevilo sosedov vsakega njegovega vozliˇ sˇ ca
enako b
0
. Zato velja tudi b
0
= a
i
+b
i
+c
i
in v njegovem preseˇ cnem zapo-
redju: {b
0
,...,b
d−1
;c
1
,...,c
d
}obiˇ cajnoizpustimoˇ stevilaa
1
,...,a
d
(vseeno
pa je treba omeniti, daˇ stevilo a
i
predstavlja ravno regularnost grafa, ki ga
inducirajo vozliˇ sˇ ca na razdalji i od poljubnega vozliˇ sˇ ca).
Hadamardov graf reda 2n,n∈N,jerazdaljno-regularengrafspreseˇ cnim
zaporedjem
{2n,2n−1,n,1; 1,n,2n−1,2n}.
Pri Hadamardovem grafu torej velja a
i
= 0 za i = 1,2,3,4. Za n = 1
dobimo 8-cikel (C
8
), za n = 2 pa 4-razseˇ zno kocko (Q
4
). Glej sliko 1, s
katere se lahko hitro prepriˇ camo, da gre pri n=2 res za Hadamardov graf.
ˇ
Ce pa se ˇ zelimo prepriˇ cati, da je za n = 2 vsak Hadamardov graf izo-
morfen Q
4
, je morda smiselno preuˇ citi ˇ se kakˇ sno lastnost teh grafov. Za
121–135 123
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 124 — #4
i
i
i
i
i
i
Aleksandar Juriši´ c
Slika 1. 4-razseˇ zna kocka, predstavljena na tri naˇ cine (prva dva sta povezana z vloˇ zitvijo
na torus): zaradi simetrije lahko izberemo za vozliˇ sˇ ce u iz deﬁnicije razdaljno-regularnega
grafa poljubno vozliˇ sˇ ce. Potem je oˇ citno b0 = 4. Ker v tem grafu ni trikotnikov, velja
a1 = 0inzatotudib1 = 3. Sledic2 = 2,a2 = 0(gledenato,davgrafuninitipetkotnikov)
ter b2 = 2. Tako nadaljujemo vse do konca.
graf premera d pravimo, da je antipoden, ˇ ce je biti na razdalji d ali 0 ekvi-
valenˇ cna relacija na mnoˇ zici vozliˇ sˇ c.
ˇ
Ce pa je v antipodnem grafu velikost
vsakega antipodnega razreda enaka 2, reˇ cemo, da je G 2-krov. In v resnici
gre za topoloˇ ske 2-krove. Npr. C
8
krije C
4
, Q
8
pa poln dvodelen graf K
4,4
,
kot bomo videli v nadaljevanju.
Lema. Hadamardov graf reda 2n je dvodelen 2-krov premera 4 z 8n vozliˇ sˇ ci.
Dokaz. Naj bo G Hadamardov graf reda 2n. Ker je c
4
= b
0
, je premer
grafa G enak ˇ stiri.
2n
0
1
2n
0
1
−1 2n
−1 2n 2n
−
v
2n
+
v
0
n
n
−2 4n
Slika 2. Razdaljna particija Hadamardovega grafa glede na izbrano vozliˇ sˇ ce: na levi je
vozliˇ sˇ cev
+
, nato proti desni sledijo v prvem krogu zbrani njegovi sosedi, v drugem zbrana
vozliˇ sˇ ca na razdalji 2 od v
+
, v tretjem vozliˇ sˇ ca na razdalji 3 in konˇ cno ˇ se vozliˇ sˇ ce v
−
na
maksimalni razdalji. Povezave lahko potekajo le med zaporednimi krogi ali znotraj njih.
ˇ
Stevilaznotrajkrogovpredstavljajoˇ stevilaki, tiknadˇ crtosoˇ stevilabi, podnjopaˇ stevila
ci. Pod krogi pa so ˇ se ˇ stevila ai.
Naj bo k
i
oznaka za ˇ stevilo vozliˇ sˇ c na razdalji i od ﬁksnega vozliˇ sˇ ca.
Ker poznamo preseˇ cno zaporedje grafa G, lahko izraˇ cunamo iz rekurzivne
zveze k
i
c
i
= k
i−1
b
i−1
(ki na dva naˇ cina ˇ steje povezave med vozliˇ sˇ ci, ki so
na razdalji i in i + 1): k
1
= b
0
= 2n, k
2
= 4n− 2, k
3
= 2n in konˇ cno
k
4
= 1. To pomeni, da ima G res 8n vozliˇ sˇ c in da za vsako vozliˇ sˇ ce v
+
v
grafu G obstaja natanko eno vozliˇ sˇ ce v
−
, ki je na razdalji 4 od vozliˇ sˇ ca v
+
,
torej je grafG 2-krov. Sedaj izberemo poljubno vozliˇ sˇ cev, nato pa mnoˇ zico
vseh vozliˇ sˇ c grafa G razdelimo na dva dela glede na to, ali je razdalja do
124 Obzornik mat. ﬁz. 56 (2009) 4
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 125 — #5
i
i
i
i
i
i
Hadamardove matrike in misija Mariner 9
vozliˇ sˇ ca v soda oziroma liha. Vozliˇ sˇ ca, ki so na razdalji i ∈ {1,2,3,4} od
vozliˇ sˇ ca v, inducirajo graf stopnje a
i
. Ker pa je a
i
= 0, to pa pomeni, da
nam je uspelo razdeliti vozliˇ sˇ ca grafa G na dva dela, tako da vsak del zase
ne vsebuje sosednjih vozliˇ sˇ c, tj. graf G mora biti dvodelen.
Za vozliˇ sˇ ci v
+
in v
−
iz zgornjega dokaza bomo rekli, da sta antipodni,
saj sestavljata antipodni razred. Mimogrede, tudi 1-skeleti Platonovih teles
so razdaljno-regularni 2-krovi.
Konstrukcija. Naj bo G Hadamardov graf reda 2n. Ker je G dvodelen
graf, obstaja delitev njegovih vozliˇ sˇ c na mnoˇ zici A in B, od katerih nobena
ne vsebuje sosednjih vozliˇ sˇ c. Potem je|A|=|B|=k
1
+k
3
=1+k
2
+k
4
=4n.
Ker sta antipodni vozliˇ sˇ ci na medsebojni razdalji 4, morata obe leˇ zati bodisi
v mnoˇ zici A bodisi v mnoˇ zici B. V posamezni mnoˇ zici A oziroma B imamo
torej 2n parov antipodnih vozliˇ sˇ c. Pare iz A oznaˇ cimo z a
1
,a
2
,...,a
2n
, iz
B pa z b
1
,b
2
,...,b
2n
. Potem je vsako vozliˇ sˇ ce para a
i
={a
+
i
,a
−
i
} sosednje
natanko enemu izmed vozliˇ sˇ c para b
j
= {b
+
j
,b
−
j
}. Naj bo H (2n× 2n)-
razseˇ zna matrika, za katero je H
ij
= 1, ˇ ce je vozliˇ sˇ ce a
+
i
sosednje vozliˇ sˇ cu
b
+
j
in H
ij
=−1 sicer.
Opomba. Naj bo G antipoden graf. Potem dobimo antipodni kvocient
grafa G tako, da vzamemo za njegova vozliˇ sˇ ca antipodne razrede, dva ra-
zreda pa sta sosednja,ˇ ce je vG med njima kakˇ sna povezava. Iz priprave na
zgornjo konstrukcijo je razvidno, da je antipodni kvocient Hadamardovega
grafa reda 2n res poln dvodelen graf K
2n,2n
. Kaj pa so antipodni kvocienti
1-skeletov Platonovih teles?
Trditev. Matrika H iz zgornje konstrukcije je Hadamardova.
Dokaz. Ker je skalarni produkt vsake vrstice te matrike s seboj enak k
1
=
2n, je dovolj pokazati, da sta poljubni razliˇ cni vrstici, npr.i6=i
0
, med seboj
pravokotni. Vrednosti, ki jih imata ti vrstici vj-tem stolpcu, se ujemata,ˇ ce
sta para vozliˇ sˇ ca
i
ina
i
0 povezana s paromb
j
na enak naˇ cin, se pravi,ˇ ce je z
obemavozliˇ sˇ cemaa
+
i
ina
+
i
0
povezanobodisivozliˇ sˇ ceb
+
j
bodisib
−
j
. Ujemanje
vrednosti vrstic v j-tem stolpcu torej pomeni, da imata vozliˇ sˇ ci a
+
i
in a
+
i
0
skupnega soseda (ˇ ce pa ga nimata, ga morata imeti a
+
i
in a
−
i
0
). Skalarni
produkt dveh razliˇ cnih vrstic je zato enak c
2
−(2n−c
2
)=2(c
2
−n)=0.
Priˇ sli smo na pol poti do naslednjega izreka.
121–135 125
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 126 — #6
i
i
i
i
i
i
Aleksandar Juriši´ c
Izrek (Darke, Shad, Delorme). Zan∈N obstaja Hadamardov graf reda
2n natanko tedaj, ko obstaja Hadamardova matrika reda 2n.
Pri drugem delu dokaza tega izreka pa nam pomaga konstrukcija iz na-
slednje trditve:
Trditev. Naj bo H Hadamardova matrika reda 2n, n ∈N. Potem je graf
G(H) z vozliˇ sˇ ci a
+
i
,a
−
i
,b
+
i
,b
−
i
, i ∈ {1,...,2n} in povezavami {a
ε
i
,b
η
j
}, kjer
je ε=η, ˇ ce je H
ij
=1 in ε6=η, ˇ ce je H
ij
=−1, Hadamardov graf.
Dokaz. Zaradi oˇ citne simetrije v deﬁniciji grafa G(H) med vozliˇ sˇ ci a
+
i
, a
−
i
,
b
+
i
in b
−
i
je dovolj opazovati vozliˇ sˇ ca glede na njihovo razdaljo od vozliˇ sˇ ca
u=a
+
i
. Potem je {b
ε
j
| ε=sgn(H
ij
)} mnoˇ zica sosedov vozliˇ sˇ ca u, {a
ε
j
| i6=
j} mnoˇ zica vozliˇ sˇ c na razdalji 2 od u,{b
ε
j
| ε=−sgn(H
ij
)} mnoˇ zica vozliˇ sˇ c
na razdalji 3 od u, edino preostalo vozliˇ sˇ ce a
−
i
pa je potem na razdalji 4 od
u.
Torej je G(H) antipoden graf premera 4 s preseˇ cnimi ˇ stevili b
0
(G) =
2n=c
4
, c
1
(G)=1=b
3
, b
1
(G)=2n−1=c
3
in c
2
(G)=n=b
2
.
Iz Hadamardovih grafov je Nomura [10] skonstruiral objekte, ki se ime-
nujejo spin modeli in so povezani tako s ﬁziko kot tudi s teorijo vozlov, glej
npr. [4].
Na kratko omenimoˇ se eno karakterizacijo Hadamardovih matrik. Le-ta
je povezana s konˇ cnimi geometrijami. Naj bo H Hadamardova matrika, ki
smo jo normalizirali tako, da so v prvem stolpcu in prvi vrstici same enice.
ˇ
Ce zbriˇ semo prvi stolpec in prvo vrstico, dobimo kvadratno matrikoN reda
4n−1, ki je (−1,1) toˇ cka/premica incidenˇ cna matrika Hadamardovega 2-
naˇ crta. Predstavlja kvadratni 2-(4n− 1,2n− 1,n− 1) naˇ crt, tj. konˇ cno
geometrijo, sestavljeno iz
• mnoˇ zice 4n−1 toˇ ck in enako velike mnoˇ zice blokov (premic),
• velikost vsakega bloka je 2n− 1, kar je hkrati tudi ˇ stevilo blokov, ki
vsebujejo poljubno toˇ cko,
• poljubni dve toˇ cki leˇ zita v n−1 blokih (toˇ stevilo pa hkrati pomeni tudi
velikost preseka poljubnih dveh blokov).
Naj bo I relacija incidenˇ cnosti med toˇ ckami in bloki. Paleyjev naˇ crt
deﬁniramo takole: ˇ ce je 4n−1 =q potenca praˇ stevila, potem vzamemo za
toˇ cke in bloke elemente konˇ cnega obsega s q elementi, tj. GF(q), ter xIy
126 Obzornik mat. ﬁz. 56 (2009) 4
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 127 — #7
i
i
i
i
i
i
Hadamardove matrike in misija Mariner 9
Slika 3. Fanova ravnina
natanko tedaj, ko x+y ni popoln kvadrat. Za q =7 dobimo znano Fanovo
ravnino (glej sliko 3), iz nje pa H
8
.
Geometrija, ki jo dobimo za q =11, pa je povezana z enostavno konˇ cno
grupo M
12
, znano pod imenom Mathieujeva grupa, in ˇ ze smo pri Hadamar-
dovi matriki reda 12. Omenimo ˇ se, da lahko tedaj, ko je q praˇ stevilo, za
incidenˇ cno matriko izberemo cirkulant, tj. matriko, katere vrstice dobimo s
cikliˇ cnim zamikom prve.
Konstrukcije in Hadamardova matriˇ cna domneva
Izn-razseˇ zne Hadamardove matrikeU inm-razseˇ zne Hadamardove ma-
trike V lahko s tenzorskim produktom matrik, ki je deﬁniran z
U⊗V =



u
11
V u
12
V ...
u
21
V u
22
V
.
.
.
.
.
.


=










u
11
v
11
u
11
v
12
... u
12
v
11
u
12
v
12
...
u
11
v
21
u
11
v
22
u
12
v
21
u
12
v
22
.
.
.
.
.
.
u
21
v
11
u
21
v
12
u
21
v
21
u
21
v
22
.
.
.










,
sestavimo (nm)-razseˇ zno Hadamardovo matriko (namig: uporabi identiteti
(A⊗B)(C⊗D) = (AC)⊗(BD) in (A⊗B)
T
= A
T
⊗B
T
). Bralec lahko
hitro preveri, da velja H
4
=H
2
⊗H
2
in H
8
=H
2
⊗H
4
, ter rekurzivno kon-
struira ˇ se Hadamardovo matriko H
n
reda n = 2
k
za vsak k∈N. Omenimo
ˇ se, da je vsaka Hadamardova matrika velikosti n, n ≤ 8, ekvivalentna H
1
,
H
2
, H
4
ali H
8
. Tudi Hadamardova matrika reda 12 je enoliˇ cno doloˇ cena
(do ekvivalentnosti), po drugi strani pa obstaja natanko pet neekvivalen-
tnih Hadamardovih matrik reda 16, tri reda 20, 60 reda 24 in 487 reda 28.
Dobljeno zaporedje 1,1,1,5,3,60,487,... ima oznako Sloan A007299.
ZakonstrukcijoHadamardovihmatriklahkouporabimotudikonferenˇ cne
matrike, ki jih je leta 1950 vpeljal Belevitch [1] (za uporabo v telefoniji).
121–135 127
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 128 — #8
i
i
i
i
i
i
Aleksandar Juriši´ c
Drugaˇ ce od Hadamardovih matrik ima n-razseˇ zna konferenˇ cna matrika C
na diagonali same niˇ cle in velja CC
T
= (n−1)I. Posebno enostavni sta
konstrukciji, ˇ ce je C
• antisimetriˇ cna: v tem primeru vzamemo H =I +C, ali pa
• simetriˇ cna: dvakrat veˇ cja matrika H je v tem primerub sestavljena iz
ˇ stirih blokov, na diagonaliI+C in−I−C, preostala bloka pa sta enaka
I−C.
Slika 4. (428×428)-razseˇ zna Hadamardova matrika, tj. matrika s paroma pravokotnimi
stolpci in elementi, enakimi bodisi +1 (svetli piksli) bodisi−1 (temnni piksli). Ta primer
staodkrilaH.KharaghaniinB.Tayfeh-Rezaieleta2004kotprvotakomatrikotevelikosti.
ˇ
Se vedno pa ne vemo, ali obstaja (668×668)-razseˇ zna Hadamardova matrika, ˇ ceprav je
bila postavljena domneva, da (4n×4n)-razseˇ zni primeri obstajajo za vsak n∈N.
Konferenˇ cne matrike redaq+1 (oziroma 2(q+1)), kjer jeq potenca praˇ ste-
vila in je q ≡ 3 (mod 4) (oziroma q ≡ 1 (mod 4)), pa je konstruiral Paley
leta 1933 [11] iz konˇ cnih obsegov (in popolnih kvadratov, ki jih je ravno
polovica med neniˇ celnimi elementi).
ˇ
Ze samo pravkar opisane konstrukcije
so dovolj, da skonstruiramo Hadamardove matrike do reda 100, z izjemo
n = 92.
1
V slednjem primeru pa so L. Baumert, S. W. Golomb in M. Hall
1
Bolj natanˇ cno znamo s Paleyjevim izrekom skonstruirati Hadamardovo matriko reda
n, ko 2
e
| n za e > 1 in je (n/2
e
)−1 potenca lihega praˇ stevila. Za n < 1000 nam potem
128 Obzornik mat. ﬁz. 56 (2009) 4
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 129 — #9
i
i
i
i
i
i
Hadamardove matrike in misija Mariner 9
leta 1962 poleg Williamsonove bloˇ cne metode [12], ta je prvi skonstruiral
Hadamardovo matriko reda 172, ˇ ze uporabili raˇ cunalnike. Slavna Hada-
mardova matriˇ cna domneva iz leta 1893 pravi, da obstaja Hadamardova
matrika reda 4n za vsako naravno ˇ stevilo n. Leta 2004 sta iranska mate-
matika H. Kharaghani in B. Tayfeh-Rezaie [7] konstruirala Hadamardovo
matriko reda 428 (na sliki 4 je lepo razvidna tudi Williamsonova bloˇ cna
metoda). Najmanjˇ si odprti primeri obstoja Hadamardove matrike so sedaj
matrike reda 668, 716, 876, 892. Najnovejˇ so konstrukcijo (Hadamardova
matrika reda 764) pa je lansko leto odkril Djokovi´ c [3].
Hadamardove kode in ekspedicija Mariner 9
Deﬁnicija Hadamardovih matrik nam zagotavlja nekakˇ sno
”
uravnoteˇ ze-
nost“, zato jih lahko uporabimo na ˇ stevilnih podroˇ cjih. Tu predstavljamo
sestavljanje uˇ cinkovitih kod za odpravljanje napak. Spomnimo se, da je
koda podmnoˇ zica nekega prostora, v katerem je deﬁnirana razdalja [6]. Na
prostoru m-teric najbolj pogosto uporabljamo Hammingovo razdaljo, ki je
enakaˇ stevilurazliˇ cnihkoordinatmeddveman-tericama. Morebitnenapake
v tem primeru odpravljamo po principu najbliˇ zjega soseda, ki dani m-terici
izbere najbliˇ zji element kode.
Slika 5. H-koda
ostanejo ˇ se naslednje velikosti: 92, 116, 156, 172, 184, 188, 232, 236, 260, 268, 292, 324,
356, 372, 376, 404, 412, 428, 436, 452, 472, 476, 508, 520, 532, 536, 584, 596, 604, 612,
652, 668, 712, 716, 732, 756, 764, 772, 808, 836, 852, 856, 872, 876, 892, 904, 932, 940,
944, 952, 956, 964, 980, 988, 996.
121–135 129
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 130 — #10
i
i
i
i
i
i
Aleksandar Juriši´ c
Naj bo H Hadamardova matrika reda 4m. Vzemimo vrstice matrike H
in matrike −H ter zamenjajmo vse
”
−1“ z
”
0“, glej sliko 5. Tako dobimo
8m vektorjev dolˇ zine 4m nad binarnim obsegomZ
2
(pri dolˇ zini mislimo na
ˇ stevilo koordinat in ne evklidske razdalje). Neposredno iz deﬁnicije Hada-
mardove matrike sledi, da je Hammingova razdalja med poljubnima razliˇ c-
nima vektorjema bodisi 2m ali 4m (razdalja do svojega negativa je 4m, do
vseh drugih pa 2m). Te vrstice generirajo vektorski podprostor v (Z
2
)
4m
,
ki predstavlja kodo. Potem je njena najmanjˇ sa razdalja 2m, koda pa lahko
popravi do (m−1)-napak.
Tako dobljenim kodam pravimo Hadamardove kode.
ˇ
Ce pa dobimo iz
Hadamardove matrike reda 2 Hadamardovo matriko s tenzorskim produk-
tom, potem kodo imenujemo tudi Reed-Mullerjeva koda prve vrste.
Proces uporabe kod bomo preverili na aplikaciji iz realnega sveta. Ma-
riner 9 je bila vesoljska sonda iz leta 1971, katere namen je bil leteti do
Marsa in poˇ siljatiˇ crno-bele slike na Zemljo (prva sonda, ki je letela v orbiti
drugega planeta).
ˇ
Cez vsako sliko je bila nameˇ sˇ cena podrobna mreˇ za in za
vsak kvadratek v tej mreˇ zi (piksel) je bila izmerjena sivina na skali od 0
do 63 (tj. 2
6
moˇ znosti oziroma 6 bitov informacije). Ta ˇ stevila, zapisana v
binarni obliki, so bili podatki, ki so bili poslani na Zemljo (bolj natanˇ cno v
laboratorij kalifornijskega instituta za tehnologijo v Pasadeni). Ob prihodu
jebilsignalˇ sibekinjemoralbitiojaˇ can. Motnjeizvesoljatertermiˇ cnemo-
tnje iz ojaˇ cevalca povzroˇ cijo, da vˇ casih poslano enico preberemo kot niˇ clo
(in obratno niˇ clo kot enico).
ˇ
Ze ˇ ce je verjetnost napake le 5 %, bo ob pred-
postavki, da ne bomo uporabili nobenih kod, kvaliteta slik izredno slaba
(le 26 % pravilna, velja namreˇ c 1− 0,95
6
≈ 0,26). Torej ni dvoma, da
moramo uporabiti kode za odpravljanje napak. Vpraˇ samo pa se lahko tudi,
katere kode naj uporabimo. Vsaka koda bo poveˇ cala velikost podatkov, ki
jih moramo poslati.
Mariner 9 je bilo majhno vozilo, ki ni moglo nositi velikega oddajnika,
tako da je moral biti signal usmerjen, vendar je na velikih razdaljah signal
teˇ zko uspeˇ sno usmeriti. Poleg tega pa je bila omejena tudi maksimalna
velikost podatkov, ki se jih da poslati v danem trenutku (ko je oddajnik
naravnan). Le-ta je bila enaka petkratni velikosti originalnih podatkov.
Ker so bili podatki sestavljeni iz ˇ sestih bitov, so bile lahko kodne besede
sestavljene iz tridesetih bitov.
Kode s ponavljanjem smo predstavili ˇ ze v [5] (ˇ ce vsak simbol ponovimo
m-krat, lahko z veˇ cinskim pravilom odkodiramo pravilno, ˇ ce je pri prenosu
priˇ slodomanjkotm/2napak). Kodaspetimiponovitvamijebilaenaizmed
130 Obzornik mat. ﬁz. 56 (2009) 4
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 131 — #11
i
i
i
i
i
i
Hadamardove matrike in misija Mariner 9
moˇ znosti, saj jo je enostavno implementirati, vendar pa le-ta lahko popravi
le 2 napaki. Hadamardova koda, ki je zasnovana na Hadamardovi matriki
reda 32, pa je lahko popravila 7 napak, tako da je bila vredna nekoliko bolj
zapletene implementacije. Z uporabo te kode je verjetnost napake na sliki
zreducirana na samo 0,01 % (v primeru kode s petimi ponovitvami pa bi
bila verjetnost pribliˇ zno 1 %).
Predpostavimo, da je verjetnost, da se spremeni en bit, enaka p=0,01.
Potem je verjetnost, da je sprejeti piksel napaˇ cen 1−0,99
6
≈ 0,06. Verje-
tnost v primeru kode s ponavljanjem pa je:
1−
   5
0
  (1−p)
5
+
  5
1
  p(1−p)
4
+
  5
2
  p
2
(1−p)
3
  6
in v naˇ sem primeru verjetnost 6· 10
−5
, da bo prejeti piksel napaˇ cen. V
primeru Hadamardove kode pa imamo:
1−
7
X
i=0
  32
i
  p
i
(1−p)
32−i
=
32
X
i=8
  32
i
  p
i
(1−p)
32−i
,
kar nam da bistveno boljˇ so verjetnost 8·10
−10
. Reed-Mullerjeva koda sicer
res potrebuje pribliˇ zno enako koliˇ cino dodane informacije, je pa zato skoraj
70000-krat zanesljivejˇ sa.
Sedaj pa preusmerimo naˇ so pozornost k problemu kodiranja in odkodi-
ranja z uporabo Hadamardove kode. Na prvi pogled kodiranje ne bi smelo
povzroˇ cati teˇ zav. Imamo namreˇ c 64 razliˇ cnih podatkov in 64 kodnih besed,
karpomeni, da bimorala delovatiˇ ze poljubna bijekcija. Teˇ zava pa je vtem,
da je Mariner 9 majhna naprava, ta naˇ cin pa bi zahteval hranjenje vseh 64
32-bitnih kodnih besed. Veliko bolj ekonomiˇ cno v smislu prostora in laˇ zje
je bilo narediti hardware, ki dejansko izraˇ cuna kodno besedo, namesto da
jo prebere iz pomnilnika.
S pravilno izbiro Hadamardove matrike postane Hadamardova koda li-
nearna (o linearnih kodah si lahko preberete veˇ c v [8]), tako da je ta izraˇ cun
v resnici mnoˇ zenje podatkov z generatorsko matriko kode. Prava izbira za
Hadamardovo matriko je tista, ki jo dobimo iz tenzorskega produkta Ha-
damardove matrike reda 2. Z matematiˇ cno indukcijo lahko preverimo, da
je taka koda linearna. Sedaj pa si oglejmo pobliˇ ze ˇ se problem odkodiranja.
Prejetisignal,tj.zaporedje32-ihniˇ celinenic,jenajprejspremenjenvobliko
±1 (tako da zamenjamo
”
0“ z
”
−1“). Tako dobimo vektor x, in ˇ ce ni bilo
napak, potem jexH
T
, kjer je H originalna Hadamardova matrika, vektor z
31-imi koordinatami enakimi 0 in eno koordinato enako ±32.
121–135 131
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 132 — #12
i
i
i
i
i
i
Aleksandar Juriši´ c
Slika 6. Povrˇ sina Marsa
ˇ
Ce pa nastanejo napake, potem se taˇ stevila spremenijo. Vendar pa naj-
veˇ c 7 napak poveˇ ca vrednost z 0 na najveˇ c 14, vrednost 32 pa se zmanjˇ sa
kveˇ cjemu do 18 (v tem primeru prejeta beseda spominja na poslano kodno
boljkotkaterakoliizmedpreostalih63kodnihbesed). Torejnammesto, na
katerem se pojavi po absolutni vrednosti najveˇ cja vrednost vektorja xH
T
,
pove,kateravrsticamatrikeH (oziroma−H,ˇ cejeoriginalnavrednostnega-
tivna)jebilaposlana. Kerjebiloriginalnialgoritemzaodkodiranjesignalov
sonde Mariner 9 poˇ casen (potreboval je 322 mnoˇ zenj in ustrezna seˇ stevanja
za vsako kodno besedo), so na Zemlji uporabili ˇ stevilne raˇ cunske trike in
tako zreducirali raˇ cunanje na vsega eno tretjino.
Hadamardove matrike v kemiji in statistiki
Hadamardove matrike se uporabljajo tudi za izboljˇ savo natanˇ cnosti pri
merjenjih podobnih objektov. Problem kemijskega ravnoteˇ zja, pri katerem
lahko objekte postavimo na katero koli stran tehtnice, glej sliko 7, je skoraj
popolnoma reˇ sen s Hadamardovimi naˇ crti, ki jih lahko dobimo iz Hadamar-
dovih matrik [9].
Brez tega postopka bi morali v nekaterih primerih tehtati tudi do
  n
n/2
  -
krat oziroma
  n
(n+1)/2
  -krat, pri ˇ cemer je n ˇ stevilo objektov. Npr. stolpce
lahko interpretiramo kot uteˇ zi na inˇ strumentu z dvema skalama, vrstice pa
kot objekte, ki jih ˇ zelimo tehtati. Med vsakim izmed n tehtanj uporabimo
vseh n objektov. Ko merimo j, postavimo i-ti objekt na levo stran, ˇ ce
je H
ij
= 1, sicer pa na desno. Ta naˇ cin merjenja bo natanˇ cnejˇ si (manjˇ sa
varianca/sprememba), kot ˇ ce bi merili vsak objekt posebej.
132 Obzornik mat. ﬁz. 56 (2009) 4
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 133 — #13
i
i
i
i
i
i
Hadamardove matrike in misija Mariner 9
Slika 7
Kompleksne Hadamardove matrike
ˇ
Ce namesto H
ij
= ±1 zahtevamo pri deﬁniciji Hadamardove matrike
raje |H
ij
| = 1, transponiranje pa pomeni hermitsko transponiranje, do-
bimo kompleksne Hadamardove matrike. Podobno kot pri obiˇ cajnih Hada-
mardovih matrikah imamo v bistvu natanko eno kompleksno Hadamardovo
matriko reda 3 (t. i. Butson-Hadamardovo matriko) in jo sestavimo s pri-
mitivnim kubiˇ cnim korenom ˇ stevila 3, ki ga oznaˇ cimo z w:


1 1 1
1 w w
2
1 w
2
w


.
Kompleksne Hadamardove matrike obstajajo za vsako naravno ˇ stevilo
n (medtem ko pri realnih ni tako). Npr. Fourierove matrike (F
n
)
jk
:=
e
2πi(j−1)(k−1)/n
, za j,k =1,2,...,n, pripadajo temu razredu.
Za konec pa postavimo bralcem ˇ se nekaj zanimivih nalog:
Naloga 1. Za n = 2
m
in 1 ≤ i ≤ m deﬁniramo matriko M
(i)
n
z M
(i)
n
:=
I
2
m−i ⊗H
2
⊗I
2
i−1. Dokaˇ zi, da je produkt M
(1)
n
M
(2)
n
...M
(m)
n
enak Hada-
mardovi matriki H
n
, ki smo jo skonstruirali s tenzorskim produktom.
Naloga 2. V primeru Reed-Mulerjeve kode prve vrste je sprejeta besedax
odkodirana tako, da izraˇ cunamo xH
T
n
.
ˇ
Ce ni priˇ slo do prevelikega ˇ stevila
napak, potem bodo vse vrednosti vseh koordinat tega produkta blizu 0,
z izjemo tiste, katere absolutna vrednost bo blizu n. Tako bomo vedeli,
kateri vektor je bil v resnici poslan. Mnoˇ zenje s ±1 imenujemo operacija.
Primerjaj ˇ stevilo operacij, ki so potrebne za odkodiranje, ˇ ce
(a) uporabimo matriko H
n
, (b) uporabimo reprezentacijo iz prve na-
loge.
121–135 133
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 134 — #14
i
i
i
i
i
i
Aleksandar Juriši´ c
Drugi primer je poznan kot hitra Fourierova transformacija.
Slika 8.
ˇ
Se nekaj predstavitev Hadamardovih matrik iz razliˇ cnih rekurzivnih konstrukcij
(nakljuˇ cne, Walshove in Paleyjeve Hadamardove matrike). Veˇ c o Hadamardovih matri-
kah lahko najdete v priroˇ cniku [2] (v katerem je 5. del posveˇ cen prav Hadamardovim
matrikam) ter na Wikipediji in Wolframovem raziskovalnem centru.
Naloga 3. Naj bo M (m×n)-razseˇ zna binarna matrika, v kateri je Ham-
mingova razdalja med poljubnima dvema razliˇ cnima vrsticama vsaj d (ˇ ce
postavimoHadamardovomatrikoH nadmatriko−H inzamenjamosimbole
134 Obzornik mat. ﬁz. 56 (2009) 4
i
i
“Hadamard-novi” — 2009/10/15 — 15:01 — page 135 — #15
i
i
i
i
i
i
Hadamardove matrike in misija Mariner 9
±1 v niˇ cle in enice, dobimo primer z m = 2n in d = n/2). Preˇ stej ˇ stevilo
urejenih trojic (i,j,k), za katere sta i in j (indeksa) razliˇ cni vrstici, k pa je
tak stolpec, da je M(i,k) 6= M(j,k), na dva naˇ cina – tako da nam en da
neenakost,kivsebujed,drugipastolpˇ cnevsotematrikeM.
ˇ
Ceprivzamemo
2d>n, potem dokaˇ zi oceno
m≤
2d
2d−n
,
ki ji pravimo v teoriji kodiranja tudi Plotkinova ocena. Kateri pogoj nam
zagotovi enakost?
Naloga 4. V prejˇ snji nalogi privzemi d =n/2 in dokaˇ zi, da je potem m≤
2n ter da enakost implicira eksistenco Hadamardove matrike reda n.
LITERATURA
[1] V. Belevitch, Theory of 2n-terminal networks with applications to conference tele-
phony, Electrical Communication 27 (1950), str. 231–244.
[2] C. J. Colbourn in J. H. Dinitz, Handbook of Combinatorial designs, druga izdaja,
Chapman&Hall/CRC, 2007.
[3] D.
ˇ
Z. Djokovi´ c, Hadamard matrics of order 764 exist, Combinatorica 28 (2008),
str. 487–489.
[4] P.delaHarpe, Spin models for link polynomials, strongly regular graphs and Jaeger’s
Higman-Sims model, Paciﬁc J. Math. 162 (1994) 1, str. 57–96.
[5] A. Juriˇ si´ c, Napake niso veˇ cne – Presek, zgoˇ sˇ cenke, planeti in kode, Presek 30
(2002/2003) 6, str. 361–366.
[6] A. Juriˇ si´ c in A.
ˇ
Zitnik, Reed-Solomonove kode, Obzornik mat. ﬁz. 51 (2004) 5,
str. 129–143.
[7] H. Kharaghani, A Hadamard matrix of order 428, J. Combin. Des. 13 (2005),
str. 435–440.
[8] S. Klavˇ zar, O teoriji kodiranja, linearnih kodah in slikah z Marsa, Obzornik mat.
ﬁz. 45 (1998) 4, str. 97–106.
[9] A. M. Mood, On Hotelling’s Weighing Problem, Ann. Math. Statist. 17 (1946),
str. 432–446.
[10] K. Nomura, Spin models constructed from Hadamard matrices, J. Combin. Th.
Ser. A 68 (1994), str. 251–261.
[11] R. E. A. C. Paley, On orthogonal matrices, J. Math. Phys. 12 (1933), str. 311–320.
[12] J. Williamson, Hadamard’s determinant theorem and the sum of 4 squares, Duke
Math. J. 11 (1944), str. 65–81.
121–135 135