18 ...~ N
DISCRETE
WISKUNDE
J .R. van Lint en J.J. Seidel
Rerorienteringscursus 1973 te Eindhoven
Commissie Modernisering Leerplan Wiskunde Instituut voor Ontwikkeling van het Wiskunde Onderwijs
Cu~sus
Discrete
Wiskund~
Eindhoven, 26, 27, 28 april 1973. Docenten: Prof. Dr. J.H. van Lint en Prof. Dr. J.J.
Seidel~
t.H. Eindhoven.
,.,
Programma Donderdag 26 april Ontvangst met koffie
9.30 - 10.00 uur 10.00 "- 11.00
1•
11.15 - 12. 15
2. Galois lichamert
Inleiding
12.15 - 13.30
Lunchpauze
13.30 - 15.30
Oefeningen
15.30 - 16.00
Theepauze
Seidel Van Lint
3. Latijnse vierkanten
Seidel
9.00 - 10. 15 uur 10.15 - 10.45
4. Orthogonale matrices
Van Lint
10.45 - 12. 15
5. Block designs
12.15- 13.30
Lunchpauze
13.30 - 15.30
Oefeningen
15.30 - 16.00
Theepauze
16.00 - 17.00 Vrijdag 27 april
..
16.00 - 17.00
Koffiepauze Seidel
6. Codes
Van Lint
7. Eindige meetkunde Koffiepauze
Seidel
8. Toepassingen
Van Lint
Zaterdag 28 april 9.00 - 10.00 uur 10.00 - 10.30 10.30 - 12.30 ,~
12.35
Sluiting.
Hoofdstuk 1. Inleiding.
1.1. Hadamard matrices
Uit de 8 hoekpunten van een kubus kan men er vier kiezen die de hoekpunten zijn van een regelmatig vierv1ak. Indetdaad, neem de oorsprong van een coordinatenste1se1 in het middelpunt van een kubus met ribbe 2, neem de assen evenwijdig aan de ribben, dan voldoen de punten (1,1,1) ( ],-1,-1)
-1 -I
(-1, 1,-1)
De matrix
(-1,-1, 1) •
-)
-1 -1
-)
bevat slechts de getallen I en -I en is orthogonaal. Zo'n matrix heet een Hadamard matrix van de orde 4. Definitie.
Een Hadamard matrix H is een vierkante matrix van de orde r, r
waarvan a1le elementen I of -1 zijn, die voldoet aan HT r
H
r
=r
I
r
Nodige voorwaarden voor het bestaan van Hadamard matrices H zijn r
r
=
)
of r
=
2 of r ::
a
(mod 4).
Men vermoedt dat deze voorwaarden ook vo1doende zijn. Er bestaan Hr voor a1le r Opgave I.
< 188
en voor oneindig vee1 andere waarden van
r.
Bewijs de nodige voorwaarden. Maak daartoe van een rij alle e1ementen I, en bekijk nog ewee rijen.
2.
1.2. De meetkunde van Fano 2
...
De meetkunde van Fano, aangeduid door PG(2,2), het binaire proie.ctie'l)'e vlak, bevat zeven punten I, 2, 3, 4; 5, 6; 7 en zeven lijnen
a, b J c,
d, e, f, g. Elke lijn bevat drie punten, door elk punt gaan dtie l{jnen. Door elk tweetal punten gaat een lijn, en elk tweetal lijneh sn{jdt in een punt. De meetkunde wordt beschreveu door de pUnt~lijrt irtcidentie "
matrix N, . met elementen n. .
als punt i op lijh J,
~J
=
N
0 als pUnt i niet op lijn J;
= circul (I I 0 } 0 00 ) •
De verzameling {I, 2, 4} is eert" (perfect) difference set. Dit betekent, dat elke a 1. 0 (mod 7)op precies een manier te schrijven is.als a ::: x - y(mod. : 7), met x, y
E
{I, 2, 4} •
~
Opgave 2.
.Construeer eenHadamard matrix Van de. orde 8, tiitgaande van
b~venstaande
matrix N•.
1. 3. Latijnse vierkanten 2
3
2
3
4
3
4
4
2
2
4 2
2
3
4
3
4
3
3
4
4
3 2
2
Beide vierkanten hebbeh de eigenschap dat elk cijfer in elke rij en elke kolom slechts eenmaal voorkomt.
..
~n
3.
Een Latijns vierkant van de orde 4 bestaat uit 16 geordende drietallen uit4 symbolen, zodat voor elk paar coordinaten elk paar symbolen precies eenmaal voorkomt. Er zijn twee (niet-isomorfe) Latijnse vierkanten van de orde 4, namelijk de hiervoren gegeven vierkanten. Maak twee (niet-isomorfe) Latijnse vierkanten van de orde 5.
Opgave 3.
1.4. Error correcting codes Zij V(4,3) de vectorruimte van dimensie 4 over GF(3). Ret Galois lichaam (GF(3) is de verzameling {O, I, -J} met als afwijkende rekenregels 1 +
J = -1,
-1-1
==
1. Schrijf + voor I en - voor -I.
De vectoren
(0, +, +, +)
en
(+, 0, +, -)
spannen een vlak op, dat 9 vectoren bevat: (0, +, +, +)
(0, -
-)
(+, 0, +, -)
(-, 0, -
+)
(+, +, -
0)·
(-, +, 0, -)
(-, -
+, 0)
(+, -
0, +)
(0, Ot 0, 0).
Deze 9 vectoren hebben de eigenschap dat elk paar de afstand 3 heeft. Daarbij wordt onder de afstand van twee vectoren verstaan het aantal coordinaten waarin de vectoren verschillen. V(4,3) heeft 81 vectoren, genaamd woorden. Ret vlak heet een lineaire code, en zijn 9 vectoren heten codewoorden.Onze code heeft de eigenschap dat hij een fout kan corrigeren,
single-err~r-co~rec;ing
is.
Onze code is perfect, omdat de bollen met straal 1 om de 9 codewoorden disjunct zijn en de gehele V(4,3) uitputten. Opgave 4.
Construeer 16 vectoren in V(8,2), waarvan elk paar afstand ~
4 heeft, uitgaande van de Hadamard matrix H8 van opgave 2.
1.5. Gelijkhoekige rechten en grafen Een stelsel rechten heet gelijkhoekig als de hoek tussen elk paar rechten dezelfde is. De vier diagonal en van een kubus vormen een gelijk-
4.
hoekig stelsel met, hoek arccos
1 3'
De zes diagonalen van een icosaeder
vormen een gt;lijkhoekig stelsel met hoek arccos 1/15.
1
I .;
/'-
-
Neem eenheidsvectoren p. langs de rechten en beschouw de matrix der 1.
inproducten P A
= [(p.,p.)J. 1. J
= ~..:.-cos q>
Voor
[P-I]
..
hebben wij in de voorbeelden:
0 0
A4 =
+'
+
+
+
+
+
+
+
0
+
+
0
+
0 0
+
+
+
o
+
A6 =
+
+
+
+
+
+
+
o
+ +
o
+
+
+
+
o
Voor deze matrices geldt:
(A -I) (A +31) = 0, A4J 4 4
= J; A62 = 5I.
Opgave 5.
Bepaal de eigenwaarden van A4 en A6 ·
Opgave 6.
C'onstrueer 28 gelijkhoekige rechten
l.U
de 7-dimensionale
ruimte. Gebruik hiertoe de matrix N van 1.2 en de vier punten van 1. 1. Opgave 7.
Construeer een Hadamard matrix H , door gebruik te maken 12 van de matrix A6'
5.
Hoofdstuk 2. Galoislichamen. We beschouwen verzamelingen V waarop een bewerking is gedefinieerd. dat is een voorschrift dat aan ieder geordend paar elementen (a,b) van V een element van V toevoegt. We schrijven het aan (a,b) toegevoegde element vaak als ab of a+b en spreken van product resp. som van a en h. 2.1
Definitie: Een verzameling met productoperatie (G, ) heet een groep als GI
VaEG VbEG
~CEG [(ab)c
G2
= a(bc)], a]
G3 : 'VaEG 3bEG lab
= ba =
eJ •
Het element e heet de eenheid. Er is een eenheid. Als we de bewerking aanduiden met+spreken we van een additieve groep.We schrijveu dan Lp.v. e meestal 0 en noemen dit het nulelement. Het is eenvoudig in te zien dat er bij iedere a precies een b is met ab
= e.
We schrijven vaak
b = a-I. Als de groep additief geschreven wordt dan noemen we dit element b de tegengestelde en schrijven (-a). 2.2
Definitie: Een groep (G, ) heet abels of commutatief als
VaEG ~bEG Cab 2.3
= ba]
•
Definitie: Is (G, ) een groep en H
c
G en (H, ) een groep dan noemen
we (H, ) een ondergroep van (G, ). 2.4
Definitie: Is (G, ) een groep en het aantal elementen van G eindig dan noemen we dit aantal de or de van de groep.
Voorbeelden: a) CR, +) is een (additieve) groep. b) (lR \{O}, ) is een (multiplieatieve) groep. e) (I;, +) is een groep. Deze groep is een ondergroep van (lR,+)' d) De matrices (: :) met ad - be ~ 0 en vermenigvuldiging als bewerking vormen een groep. Hierin is (~ ~) de eenheid. Deze groep is niet abels.
6.
e) De gehele getallen mod m met optelling als bewerking vormen een groep. De orde van deze groep is m. n met optelling als bewerking is een groep. In JR.3 is
f) De vectorruimte lt
.
2
.
l.edere lR een ondergroep. g) Het gereduceerde restklassensysteem mod 10, bestaande uit 1, 3, 7 en 9, met vermenigvuldiging mod 10 als bewerking is een groep. De orde Van de groep is 4. De vermenigvuldigingsregels kunnen in een tabel worden aangegeven: 1
3
7
9
1
1
3
7
9
3
3
9
1
7
7
7
1
9
3
9
9
7
3
I
h) Zij (G, ) een groep. De eenheid schrijven we als I. Ais a a2 , a 3,
•••
~
E
G dan ook
Als in deze rij een element meer dan een keer voorkomt is
er een kleinste n waarvoor an = 1 (de rij is periodiek). Dan vormen l,a,a 2 , ••• ,an-I een ondergroep van (G, ). Is dit (G, ) zelf dan noemen we (G,
.>
een cyclischegroep van de orde n.
Het in g) genoemde voorbeeld is een cyclische groep van de orde 4. We noemen a (in het voorbeeld g) kunnen we hiervoor 3 nemen) een voortbrenger van de groep. 2.5 Definitie:
Ais (G, ) een groep is, a
E
G, dan heet de kleinste posi-
tieve n waarvoor an = I (1 is de eenheid van de groep) de orde van het element a. Voorbeeld: 1,2,4,7,8,11,13,14 is een gereduceerd restklassensysteem mod 15. Ais we vermenigvuldiging mod IS als bewerking nemen dan is dit een groep (van de orde 8). Deze groep is niet cyclisch omdat voor alle elementen a geldt
= 1 (d.w.z. 15 ·heeft geen primitieve wortel). De groep heeft een aantal cyclische ondergroepen zoals bijv. (1,7,7 2 = 4,7 3 = 13) en (1,11).
a4
7. 2.6 Definitie: Een verzameling met twee bewerkingen (R,+, ) heet een ring als RI
(R,+) is een abelse groep,
R2
~a~R ~b~R VeER [a(be)
R3
~a~.R ~b ~ R ~e~ R [a(b+e)
= ab
va€R V
==
b~R
"'1
c~R
=
[(a+b)c
(ab)e], + aeJ en
ac + beJ.
2.7 Definitie: (R,+, ) heet commutatieve ring als 't:/a€R "Vb ~ R Cab = baJ.
We noemen (R,+) de additieve groep van de ring.
2.8 Definitie: Is (R,+, ) een ring en S
c
R, dan heet Seen ideaal in de
ring als [a - b ~ SJ
Cab
E
S & ba
en E
SJ.
Het ideaal heet echt als Seen eehte deelverzameling van R is. 2.9 Definitie: Een lichaam is een ring (R,+, ) waarvoor (R \ {a}, ) een abelse groep is. (Als we "abels" weglaten dan spreken we van een seheef lichaam.) (lnde engelse literatuur: field.) Voorbeelden: a) (lR,+, ) is een liehaam. b) (Il,+, ) is een (eommutatieve) ring. e) De 3-vouden vormen een ideaal in (L, +, ). d) De verzameling van aIle polynomen met gehele coefficienten met optelling en vermenigvuldiging als bewerkingen is een ring.
..
e) (E mod m,+, ) is een ring. Als m een priemgetal is dan is het een liehaam. Voor m = 2 hebben we een liehaam met 2 elementen (het kleinste liehaam) • Zij (G, ) een abelse groep, (H, ) een ondergroep. De verzamelingen {ah I h E H} heten nevenklassen van H. !wee nevenklassen van H zijn disjunct of identfek. Alle producten van elementen uit de nevenklasse aH met elementen uit bH behoren tot eenzelfde nevenklasse, namelijk de neven-
8.
klasse abH. We kunnen dus een vermenigvuldiging van nevenklassen definieren door abH het product van aH en bH te noemen. De nevenklassen vormen dan een groep met H, de nevenklasse van e,als eenheid. Deze groep wordt met
clH
aangegeven en heetfactorgroep van G naar H. Voorbeelden: a) (E,+) met ondergroep H bestaande uit aIle 5-vouden. Er zijn 5 nevenklassen namelijk 0 + H, 1 + H, 2 + H, 3 + H, 4 + H. De factorgroep is de groep
(E
mod 5, +) •
b) In het eerder gegeven voorbeeld van het gereduceerde restklassensysteem mod 15 met H = (1,4,7,J3) als ondergroep, is er naast H nog een nevenklasse, bestaande uit 2, 8, II en 14. De factorgroep is de cyclische groep van de orde 2. Is 8 een ideaal in de ring (R,+, ) dan is (8,+) een ondergroep van de additieve groep (R,+). We kunnen hier weer de factorgroep beschouwen. De nevenklassen noemen we restklassert mod 8. Voor deze restklassen kunnen we naast.de optelling oOk vermenigvuldiging definieren op analoge wijze. Het is eenvoudig na te gaan dat (Rls,+, ) een ring is. We noemen dit de quotientring of restklassenring mod S. Van deze methode hebben we al voorbeelden gezien waaraan ook de gebruikte namen ontleend zijn. 2.10 Stelling: Als peen priemgetal is dan is (L mod p,+, ) een lichaam. Bewijs: We weten reeds dat we met een commutatieve ring te maken hebben. Is a # 0 een element van deze ring, dan is (a,p) = I en dus is er een x met ax ::: 1 (mod p) .Dit wil zeggen dat
(E
mod p \ {O}, ) een abelse groep
is , hetgeen we moesten bewijzen. We noemen deze Iichamenpriemlichamen. Ais n niet een priemgetal is dan is de ring (L mod n,+, ) geen lichaam. Eindige lichamen, d.w.z. lichamen met eindig veel elementen, zijn het eerst bestudeerd door Galois en worden daarom ook Galois lichamen genoemd (engels: Galois fields) en aangegeven als GF(n) (Galois lichaam met n elementen). Laat (K,+, ) een eindig lichaam zijn. De eenheid noemen we J. Het element 1 + 1 noemen we 2, 2 + 1 noemen we 3, enz. Daar het lichaam eindig is vormen deze v"eelvouden van 1 een eindige cyclische ondergroep van (K,+, ). Dit is z~lfseen ii.chaam en weI een priemlichaam. Het lichaam K bevat dus
9.
een priemlichaam GF(p) als deellichaam. We beschouwen nu in Keen maximaal stelsel lineair onafhankelijke elementen (t.o.v. GF(p»
d.w.z. elementen
x ,x , ••• ,x uit K zo dat ctx + c x + ••• + cmx (0 ~ c i < p) aIleen 0 I 2 2 1 2 m m is als aIle c. = 0 zijn. Ieder element van K is eenduidig te schrijven als 1
lineaire combinatie van Xl tIm xm met coefficienten uit GF(p). Met x ,x , ••• ,x
als basisvectoren is Keen vectorruimte van dimensie mover m het lichaam GF(p). We hebben hiermee bewezen: 1
2
2.11 Stelling: Ret aantal elementen van een eindig lichaam is een macht van een priemgetal. m
We delen hier zonder bewijs mee dat er slechts een lichaam is met p
elementen. We geven het zoals eerder reeds gezegdis aan met GF(pm). (lets V~~r
beter gezegd: twee lichamen met evenveel elementen zijn isomorf.)
een
grondige behandeling van Galois lichamen verwijzen we naar: B.L. van der Waerden, Algebra. We volstaan hier met het vermelden van enige stellingen (zonder bewijs) en enige voorbeelden. 2.12 Stelling: AIle elementen f 0 van GF(q) zijn machten van een zelfde element (primitief element), d.w.z. de multiplicatieve groep van GF(q) is cyclisch (van de orde q-I). m
We geven nu een methode om GF(p ) te construeren. Laat f(x) een polynoom zijn van de graad m met coefficienten in GF(p) en laat f(x) irreducibel zijn (f(x) is niet het product van 2 polynomen van lagere graad met coefficienten in GF(p». Allepolynomen met coefficienten in GF(p) vormen een ring (R,+, ) (notatie: (GF(p)[x],+,
».
De veelvouden van f(x) vormen een
De restklassenring Rls is op te vatten als de verzameling polynomen Co + c1x + ••• + cm_Ixm-I (0 ~ c < p) met opi telling en vermenigvuldiging mod p en mod f(x) (notatie: (GF(p)[xJ(mod({f(x)D,+, ). ideaal S in R (notatie: S
Ais g(x) een element van
= {f(x)}).
Rls
is en c(x) doorloopt
g(x)c(x) de hele restklassenring daar g(x)cl(x)
Rls
dan doorloopt ook
g(x)c (x) zou impliceren dat 2
g(x){c1(x) - c 2 (x)} = r(x)f(x) en dit kan niet als f(x) irreducibel is. Uit bovenstaande voIgt dat er bij iedere g(x) in Rls een c(x) is zo dat g(x)c(x)
=
I, m.a.w.
Rls
is een lichaam. Dit is het lichaam GF(pm).
Ret volgende voorbeeld illustreert deze methode en tevens stelling 2.12. We construeren GF(24) door uit te gaan van een primitief element doet aan x4 + x +] = 0 (dan is xIS
=
I):
X
dat vol-
10.
(0 0 0 0)
0 xO
=
== (1
xl
=
x3
=
x4
=
x5
=
x6
:=
x7
x2 x3 )
+ x x + x2
=
x9
=
x lO
=
xll
=
xl2
=
= (0 0
0)
= (0 o 0
1)
= (J
0 0)
=
1 0)
x2 + x 3
(0 (0 0
+ x 3 = (l
+ x
x8
+ x2
= + x3
x
1 + x + x2
I)
0 1)
(1 0 I
= (0
xl4 =
0)
0 J)
=
()
0)
x + x2 + x3
=
(0
I)
+ x + x2 + x 3
=
(1
J)
+ x 2 + x 3 = (J 0
x 13
0)
= (0 1 0 0)
x
x2
o0
+ x 3 = (l
o0
1)
1)
De representatie als machten van x geeft de structuur van de multiplicatieve groep van GF(2 4 ) en de representatie als vectoren (4-dimensionale vectorruimte over GF(2»
geeft de structuur van de additieve groep.
We merken nog op dat we analoog aan het bovenstaande een vectorruimte kunnen maken van de n-tallen (a),a , ••• ,a ) waarbij aIle a uit een lichaam 2 i n K gekozen zijn. Dit heet een n-dimensionale vectorruimte over het lichaam K. Ais oefening kan men GF(3 3 ) construeren door bovenstaande constructie uit te voeren m.b.v. een polynoom x 3 + ax 2 + bx + c dat deler is van x 13 + I. Ais we dan de machten van x schrijven als lineaire combinatie van I, x en x 2 met coefficienten uit GF(3), dan is x 26 de kleinste macht die = I is, d.w.z. we vinden voor de multiplicatieve groep x als voortbrenger (x is primitie£ element) •
II.
Zij f(x)
n
= O.
Opgave 8.
GF(5)[x] en a een element van GF(5 ) zo dat f(a) Bewijs dat ook f(a s ) = O.
Opgave 9.
Beschouw de polynomen x2 + a x + a 2 met a = 0, I of 2 (i = 1,2). t i We rekenen mod 3. Welke van deze polynomen zijn niet in factoren
€
te ontbinden? Geef de ontbinding in irreducibele factoren van x8 -
I.
°
Opgave 10. Er zijn 16 matrices (~ ~) met elementen of 1. Als we mod 2 rekenen (gewone matrix-optelling en vermenigvuldiging) dan vormen deze matrices een ring (ga na!). Bewijs dat er in deze ring een matrix X is met X2 = X + I (hierin is I de eenheidsmatrix). Bewijs dat 0, I, X en X + I een lichaam met 4 elementen vormen. opgave 11. Toon aan dat x 2 + 1 in GF(3)[x] irreducibel is. We nemen (GF(3)[x] (mod({x2 + 0»,+, ) als model van GF(9). Bepaal in dit geval een primitief element a van GF(9). Toon aan dat in GF(3) [x] het polynoom x4 + 1 product is van twee irreducibele polynomen en dat a nul punt is van een van deze polynomen.
12.
Roofdstuk 3. Latijnse'vierkartten.
3. I. Definitie Een Latijns vierkant van de orde n is een vierkante matrix van de orde n, waarvan elke rij en elke kolom een permutatie is van n symbolen {1,2, ••. ,n}. Twee Latijnse vierkanten van de orde n zijn orthogonaal, als hun superpositie elk van de n 2 geordende paren (i,j) met i,j
E
{I ,2, ••• ,n} precies eenmaal be-
vat. Neern verder n > 2. Voorbeeld. orthogonaal wegens
[
I1
22
23
31
33J 12
32
13
21
Voorbeeld. Twee aan twee orthogonaal is het drietal 1
2
2 3
4
4
3
3
2
3
4
4
3
3
4
2
4
3
2
fl
4 2
l:
2
4
2
3
2
3
3
2
4 4
4
3 2
Ret volgende Latijnse vierkant echter bezit geen orthogonale collega: 2
3
2
3
4
3
4
4
2
:l 3J
3.2. Ret vermoeden van Euler Stelling: Bij elke eindige groep van oneven orde nkan een paar orthogonale Latijnse vierkanten van de orde n worden geconstrueerd. Bewij s.
Zij G
= {a 1 ,a2 , ••• ,an }
een multiplicatieve groep van orde n.
De matrices [a. a. ] 1 J
en
[a. J
-I
a. ] 1
a., a. 1
J
E
G
zijn Latijnse vierkanten van de orde n. Inderdaad, in elk der matrices komt elk der groepselementen in elke rij en in elke kolom eenmaal voor. Uit
13.
a 2 • Verhef in de macht i(n+l) dan k
voIgt echter a. 2 ~
a.
n+l
~
omdat de n
e
macht van elk groepselementgelijk is aan het eenheidselement
(waarom?) • Euler formuleerde in 1782 het volgende: Vermoeden. Er bestaat geen paar orthogonale Latijnse vierkanten van orde n
2 (mod 4), n > 2.
~
Dit vermoeden werd in 1900 voor n = 6 bevestigd door Tarry. Voor aIle andere n werd het echter in 1959 weerlegd door Bose, Shrikhande en Parker, die de volgende stelling bewezen: Stelling. Er bestaat een paar orthogonale Latijnse vierkanten van elke orde n '" 6. 3.3. Orthogonale Latijnse vietkanten Stelling. Er bestaan ten hoogste n-l twee aan twee orthogonale Latijnse vierkanten van de orde n Bewijs.
~
3.
Stel AI' A , ••• , At vormen t twee aan twee orthogonale Latijnse 2
vierkanten van de orde n. Arrangeer de symbolen van elk der Latijnse vierkanten zo, dat de eerste rij van elke A. bestaat uit de symbolen 1,2, ••• ,n, ~
in deze volgorde. De (2,1) plaatsen van de t Latijnse vierkanten zijn aIle verschillend, en bevatten niet het symbool J. Daarom is t S n-I.
= pm
Stelling. Als n
~ 3, p priem, dan bestaan er
n-l
twee aan twee ortho-
gonale Latijnse vierkanten van de orde n. Bewij s.
Zij GF(n)
= {aO
= 0, a
1 orde n. Definieer de n-l matrices
= [ae
Ae
= I, a , ••• ,an_I} het Galois lichaam van
2
a. + a.], i,j = O,J, ••• ,n-J, e = l, ••• ,n-I. J
~
Deze A zijn Latijnse vierkanten, wegens e (a a. + a. = a a. + a., ) =!> (a. = a. ,) e ~ e I. J J J J (a
e
V~~r
a
a. + a. = a a. , + a.) => .(a.I. I. e ~ J J e
"=
= a.I. ,)
f zijn A en Af orthogonaal omdat uit e
a. + a. eI. J
a
a., + a., , a a. + a. = a a., + a., voIgt dat a. f I. f I. eI. J J J I.
= a., I.
en a.= a'j. J
J
14.
Hoofdstuk 4. Orthogonale matrices.
4. I. Het Legendre symbool k
Het Galois lichaam GF (q), q == p , p :f. 2 priem, bev'at, behalve het hulelement 0, nog !(q-l) kwadraten en i(q-I) niet-kwadrateh. Dit is op twee manieren in te zien: GF(q) \ {oJ
(i)
=
? {w, w-, w3 , •• .,wq-I - I} , w primitief.
(ii) x 2 = y 2 ddan als x = ~ y in GF(q). Dei.
Het Legendre symbool x(a) van a
x(a) := [
~
IiO
GF(q) is
als a == 0, als a is kwadraat, als a is niet-kwadraat.
-)
Eigenschap I. x(ab)
==
x(a) X(b).
Bewijs: verifieer, voor a :f. 0, b (:. 0 met de primitieve w. Eigenschap 2. Voor q - I (mod 4) is XC-I)
I, voor q - -1 (mod 4) is X(-I) * -I. ==
Bewijs: zij w primitief in GF(q), dan wi(q-l) Eigenschap 3.
E x(a) aEGF(q)
= -1.
= O.
Bewijs: er zijn evenveel kwadraten als niet-kwadraten. Eigenschap 4.
L x(a) x(a+b) a€GF(q)
==
-I, voor b (:. O.
Bewijs: Stel a+b=ca. Als a doorloopt GF(q) \ {OJ; dan c doorloopt GF(q) \ a
l
+ b
dus a l L
a:f.O
{I}.
= ca, ==
Inderdaad, a
2
+ b == ca , dan (a -a )(I-c) * 0, t
2
2
a 2 , omdat c (:. 1 wegens b '" O. Nu is
x(a) X(a+b)
==
L
a:f.O
X (a 2 c)
=
1:
c1-J
x(c)
==
L X(c) - X(I) == c
o-
1 - -1.
15.
4.2. Paley-matrices ' Stelling. De q x q matrix S
= [X(ar-ak )],
waar a
en a
r
k
de elementen van
GF(q) doorlopen, voldoet aan
SST Bewijs. Elke
=q
I-J, Sj
= j
S
= o.
-
rij van S bevat een 0 en q-I elementen + I.
Het inproduct van de rijen r en s is wegens eig.4 E X(a -a ) x(a -~) ... ·1 k r k s k voor r ~ s en q-l voor r = s. Voorts is de som van elementen van elke rij nul, wegens eig.3. Dit bewijst de bewering, als we noemen: J
= de
matrix waarvan aIle elementen ) zijn,
j
= de
kolomvector waarvan aIle elementen I zijn.
I (:r_';/ ar,
Stelling. De (q+l) x (q+l) matrix
o
.T
c =[
X
j X (-1)
a
k
GF(q),
€
is symmetrisch voor q - I (mod 4), scheef voor q - -J (mod 4) en voldoet aan CC
T
== q I
•
Bewijs. Met eigenschap 2 en de vorige stelling. Voorbeeld. GF(5) ...
{o, 1, 2, 3, 4}
met x(a) ... 0, 1, -1, -1, 1 • GF(7)
= {O,
1,2,3,4,5, 6}
met )(a) .. 0, 1, I, -1, I, -1, .... 1 • Daarom zijn de volgende matrices orthogonaal: 0
0 -I
0
-I
-)
0
-I -)
0
C .. 6
-]
-I
-1
0 -I -)
-I
C 8
=
)
-I
-)
0
-I
0
-)
-I
1
0
-I
-1
0
-)
-1
0
-)
-I
0
"'1
1
-1
-)
0 -I
,
-)
-I
-I
-I
-1
J
-1
-)
-1
-1
1
-I
-1
I
-1
0
16.
4.3. Conferentie-matrices Een conferentie-matrix C van orde v is een vierkante matrix van or de v met diagonaal elementen 0 en overige elementen + 1, die voldoet aan T C C
III
(v-i) 1.
Stelling. Nodige voorwaarde voor het bestaan van een symmetrische [scheveJ C-matrix van de orde v is dat v :: 2 (mod 4) Bewijs. Voor v
=2
[v - 2 en v :: 0 (mod 4)J •
triviaal. Neem v > 3, normaliseer en permuteer rijen
en kolommen zodat de eerste drie rijen zijn
o
+
+
o
+
o met 1, I, 1, x, y, z, u kolommen. Uit de inproducten concluderen wij in het symmetrische en het scheve geval respectievelijk: + x + y +% + u ... + x + y - z - u ... + x - y + z - u ... + x - y - z + U ... 4(x+l) ... 4y ... 4z
a
+ x + y + z + u ... v - 2 + x + y - z - u ... 0 -J + x - y + Z - U = 0
v 0 0
1 + x - y - z + u '"" 0
0
4u ... v - 2 ,
4(x+t) ... 4(y+l) ... 4z ... 4(u+l)
c
v.
Stelling. Nodige voorwaarde voor het bestaan van een symmetrische C-matrix van de orde v is v -
... a 2 + b 2 , a en b geheel.
In 4.2 werden speciale C-matrices van de orde v
= I
k
+ p , p
~
2 priem,
geconstrueerd. Zij heten Paley-matrices, naar R.E.A.C. Paley (1933). Er bestaan ook andere C-matrices, bijv. van de orde v Het kleinste onopgeloste geval is v
= 226..
= 46.
4.4. Hadamard matrices Def. Een Hadamard matrix van de orde n is een vierkante matrix H, waarvan T
aIle elementen + 1 zijn en waarvoor geldt H H
=n
I.
17.
Stelling. Als Hn bestaat, dan is n - 1, n ,.. 2, n - 0 (mod 4). Bewijs: zie 1.1. Stelling. Als C een scheve conferentie matrix is, dan is H n n een Hadamard matrix.
= Cn.
+ I
n
Bewijs. CT ,.. -C, dus
(C+1)(CT+1) ,.. CCT + C + cT + I ,.. (n-l) I + 0 + I ,.. n I. Stelling. Als C een symmetrische conferentie matrix iS t dan is n
H ,.. 2n
cn
+ I
C
- In
n
n
C
- I
-cn
- I
n
n n
een Hadamard matrix van de orde 2n. Bewijs.
r
[C+I
C-1
C-1
-C-1
(C+I)(C-I) - (C-l)(C+1)
,.. fCC+I)2 + CC-I)2 (C-l) (C+1) - (C+l) (C-I)
(C-1)2 + (C+I)2
]
=
o 2C 2 + 21
4.5. Kronecker product Het Kronecker product A x B van de vierkante matrices A'" [a •• J van orde m, lJ en B = [bklJ van orde n, is de matrix van orde mn gedefinieerd door:
A
x
B
•
=
• a
mm
B
18.
Eigenschappen:
(A x B) x C = A x (B x C), (A x B)T = AT x BT, (A x B)(C x D)
~
(aA+SB) x (yC+OD)
(AC) x (Bb) ,
= ayA
x C + aoA x D
+ SyB x C + BoB
x D.
Stelling. Als H.m en Hn Hadamard matrices zijn; dart is Hm van de orde mn. Bewij s. (H x H )(H x H )T = (H x H )(H T m n m n m n m
= (H H T) m m
x
x
H T)
n
(H HT) = mn i x I '" Din I n n m n mn
=
x
Hn HAdamard matrix
19.
Hoofdstuk 5.
Block designs
5.1. Steiner tripel systemen zij V een verzameling van v elementen, zeg punten. Ren tripel is een deelverzameling van 3 punten. Bestaat er een col1ectie tripels zo, dat elk paar punten in preeies een tripel zit? Dan meet v aan voorwaarden voldoen. tnderdaad, elk punt zit met elk van de v-l andere punten in een tripel, dus zit in I(v-I) tripels; totaa I
.•
z~Jn
er
31
I v • -(v-l) 2
= -61
v(v-l) tripels •
Hieruit voIgt, dat v meet voldoen aan v
•
= J of
3 (mod 6).
Omgekeerd kan men bewijzen dat deze voorwaarde voldoende is. Zo'n collectie tripels heet een Steiner tripel systeem, naar Jacob Steiner (1853), en heeft de eigensehap: Er zijn v punten en b elk tripel bevat
k
=
=3
! v(v-I) tripels, punten, door elk punt gaan r *
2I
. (v-J) tripels,
elk paar punten ligt in A = J tripel. (v, k, b, r, A) ,.. (v, 3,
Existentie ddan als v
'6]
v(v-J) ,
= 1,3
]
'2
(v-J), 1).
(mod 6).
Voorbeeld 1. (v, k, b, r, A) ,.. (7, 3, 7, 3, I). Dit is de meetkunde van Fano, zie 1nleiding 1.2, met punt-tripel incidentie matrix N
= eire
(I I 0 I 0 0 0).
Deze matrix voldoet aan
Nj
=
3j , jT N = 3jT , NN
T
= 21
+ J •
20,
Voorbeeld 2. (v, k, b, r, i.) .. (9. 3, 12, 4, I). De punt-tripel ineidentie matrix N voldoet aan Nj .. 4j , jTN .. 3jT , NNT
= 3I
~
+ J.
Bieraan voldoet het tripel systeem aangegeven door de volgende 12 lijnen, later AG(2,3) te noemen.
Voorbeeld 3. (v, k, b, r, A) = (13, 3, 26, 6, I). T , 6' ,T 3,T NJ == J, J. N == J . , NN .. 5I + J • Bieraan voldoet N .. [N N)
.. eire
(I
0
1
N J met 2 0 0 0 0 0
eire
(0
0
0
0
N2 =
I
0
0
I
I
0 0
0
0)
0
0
J
0
0)
,
Voorbeeld 4. (v, k, b, r, A) .. (15, 3, 35, 7, I). Nj = 7j , jTN = 3jT , NNT = 6I + J • Bieraan voldoen de 15punten en 35 lijnen van PG(3,2), (zieBoofdstuk 7). Opllierking. Voorbeeld 3 heeft 2 oplossingen, voorbeeld 4 heeft80 oplossingen. 5.2. Block designs Lemma.
zij M een (rechthoekige of vierkante) matrix. Dan hebben 'M,MT en MTM dezelfde eigenwaarden'; O.metdezelfd~ ,tmiltipliieiteiten.
21.
Bewijs.
Zij ). ,. 0 eigenwaarde van MMT, met eigenvector ~; MMT ~
= A .! ,
Q.
MT !. ,. Q , MTMMT x .. A MT x
• MT x. Dus A\"1S e1genwaar devan MTM , met e1genvector Evenzo, als a~ + 8Z" Q in de eigenruimte bij de eigenwaarde A ; 0 van MMT, . a MT !. + 8MT Z rJ. _O·1n d ' . b"1J d ' de A van MTM. Q.e.d. dan 1S e e1genru1mte e e1genwaar zij V een eindige verzameling van v punten. De delen van V heten blokken. Een IBD, incomplete block design, is een verzameling van, zeg b, blokken. Een BIBD, balanced IBD, is een IBD met (1) elk biok heeft evenveel, zeg k, elementen, (2) elk paar punten ligt in evenveel, zeg A, blokken,
(3) 0 < ). en k < v-l.
Voor een BIBD gelden dan de volgende eigenschappen: (4) elk punt ligt in evenveel, zeg r, blokken, (5) r(k-I) • A(v-I), bk
= vr,
die wij weldra zullen bewijzen. Een BIBD, zeg block design, wardt beschreven door zijn v x b punt-blok incidentie matrix N = [n .. ] gedefinieerd door 1J I alB punt i ligt in blok j, n ij
=
t
.
0 als punt i niet ligt in blok J.
Volgens definitie geldt dat (I) elke kolom van N heeft k enen, (2) elk paar rijen van N heeft inproduct ).. e ~tel de i rij van N heeft r. enen. Tel het aantal paren {h,j} waarvoor geldt 1.
(n •• , n ·) .: (J, l) •
1J
hJ
Volgens (2) is dit aantal (v-l»)'. Volgens (J) is dit aantal r.(k-I). 1. Hieruit voIgt: (4) elke rij van N heeft evenveel, zeg r, enen, en r(k-l) .. A(V-J). Tel nu op twee manieren het totale aantal enen in N, dan voIgt vr • bk.
22,
In termen van de punt-blok incidentie matrix N wordt een block design dus gedefinieerd door NNT - (r-A ) I + 1\'J vr s bk
,
N'J . rJ, , J.TN· k'J , r(k-]) • l.(v~l) •
Voorbeeld I. Steiner tripet·systemen. Voorbeeld 2. N • circ (J
o
o
0)
definieert een block design met (v, le, b, r, A) • (7, 4. 7, 4, 2). Voorbeeld 3. Een block design met (v, k,b, r, A) • (8, 4, 14, 7, 3) wordt gegeven door de 8 hoekpunten van een kubuB en de volgende 14 blokken: de 6 zijvlakken, de 6 diagonaalvlakken, de 2 regelmatige viervlakken gevormd door de hoekpunten. Een betere voorstelling wordt verkregen door de 8 punt en van de vectorruimte van dimensie 3 over GF(2), en de ]4 vlakken x x
= 0, = 1,
y y
= 0,
z = 0, x+y - 0, x+z • 0, y+z • 0, x+y+z • 0, = I, z - I, x+y = 1, x+z • 1, y+z • I, x+y+z • I.
Stelling (Fisher). In een block design geldt v s b. Bewijs.
De eigenwaarden van de v x v matrix NNT _ (r-A) I + l,J zijn (v-]) maal (r-A) en eenmaal
r - l. + A v - rk. Deze eigenwaarden zijn ; O. Volgens het tenminste deze v eigenwaarden, benevens Daarom is b ~ v. Een BIBD met b - v heet een symmetrisch v~erkant, en r m k, en we hebben Nj = kj, jTN a kjT, NNT m NTN = (k-l.) I
Lemma heeft de b x b matrix NTN eventueel b-v eigenwaarden O. block design. De matrix N is dan + l.J
j
(det N)2 _ k2 (k_l.)v-l , dus k-A moet een kwadraat zijn. Een projectief vlak PG(2,n) van orde n met
> 1
is een symmetrisch block design
b = v = n 2 + n + I, r - k - n + 1, l. • I.
23.
Voorbeeld. De meetkunde van Fano, zie 1.2. Omtrent het bestaan van PG(2,n) is het volgende bekend. m
Stelling.
PG{2,p ). p priem, bestaat, zie 7.3.
Stelling.
Ais PG{2,n) bestaat. en n = 1 of 2 (mod 4), dan geldt n = a 2 + b2 , a en b geheel.
Een gevolg hiervan is, dat PG(2,6) niet bestaat. Het bestaan van PG(2,IO) is een open probleem.
5.3. Block designs en orthogonale matrices Stelling.
Een genormaliseerde Hadamard matrix van de orde 4t
~
8 i8 equi-
valent met een symmetrisch block design met parameters (v, k, A) = (4t-J, 2t-l, t-J). Bewijs.
Schrijf de Hadamard matrix volgens
' dan vo ldoet de v1erkante R van orde 4 t- J wegens BHT • 4 tl aan RRT ... 4 t I - J , R'J -
• • TR -J, J - -3•T •
De incidentie matrix N van het symmetrische block design voldoet aan NNT ... tI + (t-J) J, Nj • (2t-l) j, jTN _ (2t-J) jT. Het verband tussen R en N wordt gegeven door R = 2N - J • Voorbeeld: opgave 2 van de Inleiding. Stelling.
Als er een C-matrix van orde n bestaat, dan is er een block design met parameters (v, k, b, r, A) ... (n, In, 2n-2, n-l, In-I) •
Bewijs.
Normaliseer de C-matrix volgens
24.
dan voldoet de matrix S. van or de n-l, aan SST .. (n-J) I - J , Sj • 0, jTS • OT • Het gevraagde block design wordt nu gegeven doot .T N ..
[
J
OT
i (J-S-I)
i(J-S+I)
1
25. Hieronder volgen enkele opgaven betreffende de hoofdstukken 3, 4 en 5. Opgave· )2.
a) Bepaal 7
met hoekpunten uit {] ,2,3,4,5,6,7} zo,
dat elk paar driehoeken een hoekpunt gemeen heeft. b) Bepaal ]4 verschillende driehoeken met hoekpunten uit . {1,2,3,4,5,6,7} zo, dat elk paar punten in twee driehoeken ligt. Opgave ]3. Gegeven I
2
3
2
3
4
3
4
5
....
....
n-l
n
n
,
n
2
n-2
n-l
J
n
.... • . . .
2
2
A :=
n
n-l
B
3
2
I
4
3
2
5
4
3
:=
n-)
n-2
2
n
Bewijs dat A en B orthogonale Latijnse vierkanten zijn dan en alleen dan als n oneven is. Opgave 14. De 9 elementen van GF(9) worden voorgesteld door aile getallen van de vorm ax + b, waarbij a en b doorlopen GF(3) en x voldoet aan x 2 + 1 == O.
a) Welke elementen van GF(9) \ {OJ. zijn kwadraat? b) Construeer een Conferentie
~atrix
van de orde 10.
26.
Opgave 15. De (0,1) matrix N heeft afmeting 6 x 10. Elke rij bevat 5 enen en 5 nullen. De Hamming afstand van elk paar rijen is
~
6 (zie
1.4 of 6.1).
a) Bewijs dat elk paar rijen ten hoogs.te 2 enen g.emeen heeft. b) Bewijs dat elke kolom ten hoogste 3 enen heeft. c) Bewijs dat elke kolom precies 3 enen heeft. d) Bewijs dat N de incidentiematrix van een block design is en geef de parameters van dit block design. Opgave 16. Zijf(n) het maximum aantal tripels, dat kan worden g.ekozen uit een verzamelingvan n symbolen, zodat elk paar tripels een symbool gemeen heeft. a) Wat is f(7)?
b) Bereken fen) voor n c)
Ber~ken
fen) voor n
= 3,4,5,6. ~
7.
27.
Hoofdstuk 6. Codes. Beschouw een verzameling van q verschillende symbolen (alfabet) en vorm alle rijtjes van n van deze symbolen(wootden). We noemen deze verzameling V(n,q). Een deelverzameling C
c
V(n,q) heet een code.We definieren:
= (x1, ••• ,xn )
6.1. Definitie: Als x
E
V(n,q) en l = (Y1, ••• ,Y ) n
E
V(n,q)
dan is d(~,X) :=
het aantal indices i (I ::;; i ::;; n) zo dat xi :f Yi'
d(~,x)heet
Hamming-afstand van x en X (zie 1.4).
We beschouwen nu het volgende model van een communicatiekanaal: 6.2. Definitie: Eenbinair symmetrisch kanaal met kans p op fout (0 ::;; p ::;;
o
o
is een systeem met 2 mogelijke ingangssignalen (0 en 1) en dezelfde twee
uitgangss~gnalen
zo dat voor beide ingangs-
signalen de kans p is dat het verkeerde signaal uitgangssignaal is. 6.3. Voorbeeld van gebruik van codes: Stel dat we een binair symmetrisch kanaal met kans p
= 0.02
op fout overkomen ter beschikking hebben en dat
dit kanaal 2 signalen per tijdseenheid kan verwerken. Via dit kanaal willen we de resultaten overbrengen van een experiment waarbij met constante snelheid, nl. een maal per tijdseenheid, met een munt kruis of munt wordt geworpen. Als we nu bij iedere keer kruis een 0 zenden en bij iedere keer munt een 1 dan zal de ontvanger informatie ontvangen waarvan ongeveer 2% fout is. Stel dat we nu wachten tot twee keer is geworpen en steeds na elke twee worpen 4 signalen zenden als voIgt: - munt
-+
kruis - munt
-+
o0 0 1 o 0
munt
- kruis
-+
0
kruis - kruis
-+
munt
0
0
!)
28.
De ontvanger wordt opgedragen bij ontvangst van een ander vier tal een van de eerste drie plaatsen te veranderen zo dat een van de vier rijtjes ontstaat. Merk op dat we door zo het kanaal te gebruiken in de tijd het experiment precies bijhouden. We hebben nu de volgende kansen: P(4 symbolen goed)
= q4,
pel fout onder de eerste drie)
= 3pq 3,
en 1n beide geva.llen zal de ontvanger na "decoderen" 2 goede resultaten e hebben. Twee foute resultaten vindt de ontvanger als het 4 symbool goed ~
doorkomt en onder de eerste drie
2 fouten waren. De kans hierop is
p3 q + 3p2q2. Blijft over een kans p dat de ontvanger althans een van de experimenten goed doorgegeven krijgt. Gevolg is dat ongeveer 1,12% van de totale informatie onjuist is. Dit is veel beter dan eerst. Laten we nu wachten tot 3 worpen zijn voltooid en steeds na elke 3 zes signalen zenden. We kunnen weer
h~t
experiment in de tijd bijhouden! Nu
zenden we als voIgt: Laat (a ,a " ,a ) het resultaat van de worpen zijn. l Z 3 Neem a := a + a , as := a + aI' a = a + a (aIle optellingen in GF(Z». 4 2 Z 3 l 3 6 Zend nu (a ,a , ••• ,a ). De ontvanger decodeert als voIgt: Zoek een mogelijk l 2 6 signaal met zo klein mogelijke Hamming-afstand tot het ontvangen signaal. Dit noemt men maximum-likelihood-decoding. De lezer controlere nu zelf dat de ontvanger nu nog slechts 0,29% foute informatie ontvangt. Door steeds langere codes te gebruiken kan men de informatie willekeurig nauwkeurig over het als voorbeeld gekozen kanaal zenden! Het vinden van codes, de bestudering van deze codes en het ontwerpen van decodeerprocedures zijn de onderwerpen van de "coding theory". 6.4. Hadamard codes. Zij H een Hadamard matrix van de orde 4n. We construeren een code van 8n woorden van de lengte 4n met {O,I} als alfabet door (al, ••• ,a ) als coden woord te nemen als ! (2a -l, 2a -l, ••• ,2a -l) een rij van His. Nu is voor l Z n twee rijen van H het inproduct 0, dus hebben de door ons geconstrueerde woorden afstand Zn of 4n. Voorbeeld: 1
H =
[l -:] -)
-I
1 -) -1 -1 1
C
=
0 1 0 1 0
0 1 0 I 1
0 I
0 1
1
]
a a
J
a
0 I
a a
I
I 1
° )
0
a 1
29.
Als vorengenoemde code gebruikt wordt (bijv. voor een binair symmetrisch kanaal)en het kanaal introduceert e < n fouten dan leidt de reeds eerder genoemde maximum likelihood decoding tot een correcte interpretatie. Men spreekt nu van een e-fouten-verbeterende code.
T
Een decodeerprocedure kan als voIgt werken: We ontvangen ~ = (x , ••• ,x ). 1 4n T Bepaal nu H(2~-i) =: Z. Als er geen fouten in x zitten zijn aIle componenten van
Z op
een na 0 en de andere component is + 4n. Bij e
<
n fouten geeft op
analoge wijze het inproduct met de grootsteabsclute waarde eenduidig aan wat het gezonden woord geweest is •
•
30.
Hoofdstuk 7. Eindige meetkunde
6.1. Vectorruimten over Galois lichamen Definitie. V(n,q) is de vectorruimte van de dimensie n, waarbij de getallen worden genomen uit het Galois lichaam GF(q}. De lineaire algebra van V(n,q) heeft veel gemeen met de gewone lineaire algebra over R, het lichaam der reele getallen. Er zijn echter ook verschillen, bijvoorbeeld omdat het aantal vectoren van V{n,q) eindig is, ni. qn. Voorbeeld. V(3,2) heeft 8 binaire vectoren (x,y,z), met coordinaten 0 of I. Voorbeeld. V{2,3} heeft 9 ternaire vectoren (x,y), met coordinaten 0, I, -I.
Zij A(s,n; q) het aantal lineaire deelruimten V(s,q} van V(n,q}. n
Stelling.
a -I A(I,n; q} ... A(n-I ,n; q) • ..:L.-:q-I
s
A(s,n; q) -
q
II
n+l-i -1•
i-J
Bewijs.
•
i q -I
Elke rechte door
~bevat
er (qn_I}/{q_l) rechten door
«,
behalve Wnog q-I vectoren. Daarom zijn
en evenveel hypervlakken door 6. Het aantal
der V(s+l,q) in V(n,q), die een gegeven V(s,q) bevatten, is n-s n s q -q .. q -I. 8+1 s q-l q -q Daarom geldt A{s,s+l; q) A(s+l,n; q} • A(s,n; q) Wegens A(s,s+l; q) ... (q
s+1
q
n-s -1 q-l •
-1)/(q-l) voIgt het gestelde.
Voorbeeld. V{3,2) bevat 7 rechten en 1 vlakken door W. Elk vlak door W bevat 3 rechten door 8'. Voorbeeld. V(2,q} bevat q+1 rechten door
~.
Voorbeeld. V(3,q} bevat q2+q+1 rechten, en q2+ q + I vlakken door W. Voorbeeld. V(4,2) bevat 15 rechten, 35 vlakken, en 15 drie-ruimten door
d.
31.
7.2. Block designs uit V(n,q) :.
Stelling.
De V(l,q) en de V(s,q) van V(n,q). 1
<
s < n, vormen de punten en
de blokken van een block design met v • A(I,n; q), k r - A(s-I, n-l;
= A(I,s; q), b • A(s,n; q), A = A(s-2. n-2; q).
q),
Dit block design is symmetrisch ddan als s· n-l. Bewijs.
Elke V(s,q) bevat evenveel V(l,q), namelijk (qS_l)/(q_]).
Voorts liggen twee gegeven rechten door
~
in een aantal A deelruimten V(s,q),
dat onafhankelijk is van die rechten. Inderdaad, zo'n V(s,q) is bepaald door s van de n basisvectoren van V(n,q), waarvan er twee langs de gegeven rechten
kunnen worden gekozen. Er zijn dus s-2 basisvectoren vrij te kiezen uit de overige n-2 basisvectoren van V(n,q). Daarom is A = A(s-2, n-2; q). Voorbeeld. De 7 rechten en de 7 vlakken door Wvan V(3,2) vormen PG(2,2). Voorbeeld. De 15 rechten en de 15 drie-ruimten door Wvan V(4,2) vormen
(V,k,A)
= (15, 7, 3).
Voorbeeld. De 15 rechten en de 35 vlakken door d van V(4,2) vormen (v,k,b,r,A)
= (15,
3, 35, 7, J).
7.3. Het projectieve vlak PG(2,q) Stelling.
PG(2,q), q b
= v = q2
= pm,
p priem, met
+ q + I,
r - k • q + I,
A-I,
bestaat. Bewijs. Pas de stelling uit 7.2 toe op V(3,q), namelijk op de (q3-1)/(q-l) rechten door d en de (q3-1)/)q-l) vlakken door ~. Elk vlak door ~bevat
q+] rechten door
~
en door elk tweetal rechten door
~
gaat een vlak.
Bij projectieve vlakken is men gewend om, in plaats van over punten en blokken, te spreken over punten en lijnen. BIijkbaar geldt in PG(2,n) PI. Door elk paar punten gaat een Iijn. P2. Elk paar lijnen heeft een punt gemeen. P3. Er zijn 4 verschillende punt en waarvan geen drietal op een lijn ligt. Projectieve vlakken Iaten zich ook omgekeerd uit deze 3 axioma's opbouwen.
32.
Wanneer uit een projectief vlak een lijn £ en de punten van die lijn worden weggelaten, dan blijven er over n 2 punten en n(n+l) lijnen, die het z.g. affiene vlak AG(2,n) vormen. Twee lijnen heten evenwijdig, wanneer ze in de oorspronkelijke PG(2,n) een snijpunt op £ hebben. De eigenschappen PI, P2, P3 gaan over in de bekende axioma's van de vlakke meetkunde. Voorbeeld: Voor AG(2,3) zie voorbeeld 2 van 5.1. 7.4. Lineaire codes. Een lineaire (n,k) code over GF(q) is een lineaire deelruimte van dimensie k van de vectorruimte V(n,q) van dimensie n over GF(q). De codewoorden, dat zijn de vectoren van de lineaire deelruimte, hebben de volgende eigenschap: het verschil van twee codewoorden is weer eencodewoord. Daarom worden de Hamming-afstanden tussen de paren codewoorden bepaald door de Hammingafstanden van het codewoord 0 tot de andere codewoorden. Definitie: Het gewicht van een codewoord is het aantal coordinaten
~
0 van
het codewoord. Voorbeeld: Het vlak in V(4,3), opgespannen door f
=
(1,0,1,2)
.s
=
(0,1,1,1)
is een ternaire lineaire (4,2) code; n = 4, k AIle codewoorden
~
Q hebben
= 2, q = 3, zie Inleiding ].4.
gewicht 3, dus de onderlinge Hamming-afstanden
der 9 codewoorden zijn 3. Een lineaire code kan op verschillende manieren worden beschreven: Een generator matrix G van een lineaire (n,k) code is een k x n matrix, waarvan de rijen worden gevormd door k basisvectoren van de code. De qk co d ewoor d en ~
T
G, met
~
T
..
z~Jn
= (ul, ••• ,uk ),
u
E
i
GF(q).
Een parity check matrix H van een lineaire (n,k) code is een (n-k) k
matrix over GF(q) zo, dat de q x- = (xl' ••• ,x) n
T
met Hx
0
x
n
codewoorden zijn de vectoren
33.
Voorbeeld:
o
2 2
o
duiden aan de generator en de parity check matrix van het vorige voorbeeld. Inderdaad, er geldt GH
T
=0 •
Door geschikte basiskeuze kan de generator matrix van een lineaire (n,k) code worden gekozen als voIgt:
G
= [Ik
NJ , met k x (n-k) matrix N = [n ..
1J
J
Dan luidt de parity check matrix van die code: I n- kJ
T omdat GH
= O.
,
De codewoorden zijn nu eenvoudig op te schrijven, immers kies
x 1, ••• ,xk willekeurig, en
~+j
=
k E x. n ... 1 1J 1
Opmerking. x1"",xk heten de information symbols, xk+1"",x n heten de parity check symbols. 7.5. Hamming codes Binaire Hamming codes Z1Jn lineaire codes met de volgende parity check matrix H van afmeting m x (2 m - 1). De kolommen van H zijn 1 Q, verschillend, en bevatten slechts de elementen 0 en I van GF(2). Voorbeeld, voor m= 3,
H3 =
[~
0
0
]
0
0
0
0
]
0
m
De lengte van de binaire Hamming code is n = 2 - 1, en de dimensie is m k = 2 - ) - m. Het minimum gewicht van de codewoorden 1 0 is 3. Inderdaad, een codevector is een oplossing ~
=0
~
van
34.
T
enelke ~ = (xl' ••• ,xn ) ~ Q heeft tenminste 3 coordinaten ~ 0, omdat elk· tweetalkolommen van H een som ~ 0 mod 2 heeft. Daarom zijn de Hamming codes l-error-correcting. Het corrigeren van een fout geschiedt als voIgt. Stel y = x + e is het ontvangen wootd, afkomstig van een codewoord
•
~,
doch met een fout in de j-de coordinaat, e = (0 .• 0 J 0 •• O)T. Dan wordt door Hy
= H~
+ H~
=
H~
= j-de
kolom van H
de plaats van de fout aangeduid, omdat de j-de kolom van H juist de binaire representatie van het getal j is. Opmerking.
m is de parity check matrix van een lineaire code van lengte 2 en dimensie 2m - m - 1, met d ;;:: 4. Inderdaad, elk drietal kolommen van H* heeft som :/: 0 mod 2. Deze lineaire code is dus 2-error-detecting. Voorbeeld.
is de H van een lineaire (8,4) code met d ;;:: 4. Deze code, die 24 = 16 codewoorden van lengte 8 bezit, is een Hadamard code volgens 6.4. Hamming codes over GF(q) zijn lineaire codes met een m parity check matrix H. De kolommen van H zijn :/:
Q,
x
(q
m
- l)/(q - J)
twee aan twee onafhan-
kelijk, en bevatten de elementen van GF(q).
.
Voorbeeld.
o o o ]
a
1
0
2
a
a
0 2
2
a
2
2
o
is de parity check matrix van een lineaire code met 3 10 codewoorden van lengte 13, die l-error-correcting is.
35.
7
r
Opgave 17. Beschouw aIle polynomen
a.x
i
1
i=O
met a.
1
en reken daarmee mod 3 en mod (x 8 - 1) ({x 8 -
(GF(2)[x] (mod
J}»
= 0, ] of 2 (i = 0,1, •• ,7) (d.w.z. beschouw
».
,+,
In deze ring vormen aIle veelvouden van x 2 + x + 2 een ideaal S (ga na!). Beschouw nu de 8-dimensionale vectorruimte
Ra
bestaande
uit de vectoren (a ,a , •• ,a ) met a = 0,1,2 (i = 0, •• ,7) en opi O 1 7 telling etc. mod 3. Laat VcR gedefinieerd zijn door
7 (a ,a , •• ,a ) 7 O 1
€
V :
<=?
L
i=O
i
a.x 1
€
S.
Toon aan dat V eenlineaire deeIruimte van RS is (dimensie?). Toon aan dat uit (a ,a , •• ,a ) E V voIgt dat (a ,a ,a , •• ,a ) O l 7 7 O l 6 (dit heet een cyclische deelruimte). Opgave 18. Zij
~
€
V
een primitief element van GF(16). Beschouw de verzameling V
van aIle polynomen C(x)
= Co
+ clx + •• + c
14
x 14 met coefficienten
in GF(2) waarvoor geldt
-
Zij V de code bestaande uit de woorden (c 'c , •• ,c ) waarvoor O l I4 Co + ctx + •• + c x 14 E V. Toon aan dat V een lineaire code is. 14 Hoeveel information symbols bevat elk woord? Bewijs dat dit een , 3-error-correcting code is.
36.
Hoofdstuk 8. Toepassingen.
.. "
8. I. Proefvelden. Op een vierkant stuk bouwland wil men n soorten graan zaaien, en de oogst vergelijken. Hiertoe verdeelt men het stuk land in n 2 subvierkanten. We nemen aan dat (misschien) de grond niet overal even vruchtbaar is maar dat de afhankelijkheid zo is dat E(y .. ) = gemiddelde oogst per m2 voor het k-de ~J k soort graan gezaaid in i-de rij en j-de kolom = p + ~. + v. + P waarbij k ~ J E ~. = E v. = E P = 0. Hierin is p de gemiddelde oogst per m2 • Men wil k ~ J vragen van het type: "zijn de graansoorten verschi1lend in kwaliteit", "is er werkelijk verschil in vruchtbaarheid voor verschillende rijen resp. kolommen" enz. beantwoorden. Als men de k-de soort graan zo zaait dat in iedere rij en iedere kolom een subvierkant met deze soort voorkomt dan is de gemiddelde oogst over deze proefveldjes p + Pk omdat E
~i
= E Vj = 0.
D.w.z. de invloed van de plaats is geelimineerd. Om aIle soorten zo te zaaien moet men van het proefveld een Latijns vierkant maken. 8.2. Intensiteitsmetingen. Om de invloed van verschillen in lichtintensiteit op het oog te bestuderen heeft men proeven gedaan met een televisiescherm waarop n verschillende intensiteiten voorkwamen. Het scherm werd verdeeld in n 2 vierkantjes. Weer gebruikte men een Latijns vierkant. De experimentatoren wilden graag dat ieder geordend paar verschillende intensiteiten (a,b) eenmaal horizontaal en eenmaal verticaal voorkwam. Ais oefening kan de lezer proberen een dergelijk Latijns vierkant te construeren. 8.3. Statistische analyse van buizenfabricage. Dit voorbeeld is afkomstig van een plaatselijke fabriek waar radiobuizen worden gemaakt. Er zijn vier bewerkingen, te weten a) maken van de wolframdraad, b) maken van de spiraal, c) aanbrengen van de A1 0 -laag , d) buizen2 3 fabricage. De productie vertoonde een veel te grote spreiding in de gemiddelde gloeistroom. De 4 afdelingen gaven elkaar de schuld en door middel van een experiment moest worden uitgemaakt welke van de 4 factoren oorzaak van het verschijnsel was. I.v.m. tijd en kosten wilde men niet te veel buizen testen.
37.
Voor dit soort experimenten is een grieks-latijns vierkant het hulpmiddel.
.. I"
Beschouw een latijns vierkant van de orde 7 met elementen A, B, C, D, E, F, G en een met elementen a, b, c, d, e, f, g
zo dat deze twee orthogonaal
zijn. Op 7 verschillende dagen wordt een partij wolframdraad geinaakt en van elke partij maakt men op 7 verschillende dagen spiralen. Een steekproef van 15
spiralen uit elke partij geeft een groep van 49 keer 15 spiralen. Deze
plaatst men op het grieks-latijns vierkant en wei draad van de i-de dag in i-de rij, spiraal van j-de dag in j-de kolom. De 7 partijen op een A-plaats worden op een dag van de A1 0 -laag voorzien en teruggeplaatst etc. Daarna 2 3 worden de 7 partijen op een a-plaats op een dag in buizen gemonteerd, etc. Na 28 dagen heeft men 49 keer 15 buizen en aan elke groep worden dan gloeistroommetingen gedaan. Deze opzet heeft bereikt dat voor elke fase de productie van een dag voor iedere andere fase over 7 dagen is verspreid. Het experiment toonde duidelijk aan dat de spreiding (voor verschillende dagen)
.
bij de buizenmontage te groot was •
~'
8.4. Kleine experimenten. Het komt vaak voor dat men enkele factoren wil onderzoeken maar dat door tijdgebrek of hoge kosten het niet mogelijk is iedere mogelijkheid voor de eerste factor te koppelen met iedere mogelljkheid voor de tweede. We nemen als voorbeeld een object dat uit 7 verschillende soorten metaal kan worden gemaakt. Er zijn 7 verschillende processen mogelijk voor de fabricage. Het is te duur aile 49 combinaties te onderzoeken. Hoe nu het experiment op te zetten? Voorbeeld 1.2 op biz. 2 geeft een oplossing. De metalen nummeren we van 1 tIm 7 en aan ieder productieproces kennen we een blok toe. We bereiken dat het eindproduct door elk proces 3 keer is gemaakt, met elk metaal 3 keer is gemaakt en dat er voor ieder tweetal processen een metaal is dat met beide processen is verwerkt. Door middel van variantie-analyse bepaalt men daarna wat de beste keuze is. 8.5. Foto's van Mars. Voor het naar de aarde seinen van de foto's gemaakt door de Mariner Mars
1969 is een zg. (32,6) biorthogonale Reed-Muller code gebruikt. Dit komt neer op een speciale Hadamard code zoals in 6.4 behandeld. De code ontstaat uit (: ~) door vijf keer de stelling uit 4.5 toe te passen.
38.
8.6. Conferentietelefonie. De n directeuren van een concern wensen hun conferenties per telefoon te houden, zodanig dat elke directeur met elke collega kan spreken en dat de anderen hun discussies kunnen horen. De constructie van een daarvoor geschikt conferentie-netwerk (een lineaire, verliesvrije, frequentie-onafhankelijke, reciproke n-poort, met uniforme verdeling en zonder reflectie) is gelijkwaardig met de constructie van een symmetrische conferentie matrix. 8.7. Weegschema's. Stel dat v objecten gewogen moeten worden in v wegingen met een balans. We nemen aan dat aIle wegingen eenzelfde variantie hebben, onafhankelijk van de belasting van de schaal. We verlangen nu dat de wegingen zo worden uitgevoerd dat de gemiddelde variantievan de geschatte gewichten minimaal ~s.
We geven het schema als voIgt aan: als bij de i-de weging het j-de object op de linkerschaal ligt, dan is a .. a .. ~J
= -I en verder nemen we a .. ~J
~J
=
= I, terwijl voor de rechterschaal
0 als het j-de object bij de i-de weging
niet meedoet. Door Hotelling is bewezen dat als v weging gevonden wordt door te eisen dat A
=0
(mod 4) de beste
= (a .. ) een Hadamard matrix is. 1J
De geschatte gewichten hebben dan gelijke varianties en ze zijn niet gecorreleerd. Als v
=Z
(mod 4) is een C-matrix het beste weegschema.
8.8. De voetbalpool. Ret laatste voorbeeld in 7.5 geeft 3 10 kolommen van 13 getallen 0 (= 3), en Z die we kunnen insturen voor de Nederlandse voetbalpool. We weten dan vooraf (!) dat we de Ie of Ze prijs zullen winnen. 8.9. BCH-codes. Laat a een primitief element zijn van GF(16) (zie bIz. 10). De matrix H van 8 rijen en 15 kolommen gedefinieerd door
H waarin iedere a
[: i
:: .......... :::j een kolom van 4 elementen 0 resp. 1 voorstelt nemen we als
parity check matrix van een lineaire code C (dimensie 7, woordlengte 15, alfabet GF(2».
39.
.
Zij
£ = (c O,c 1' ••• ,c 14 )
€
C•
Dan geldt voor het polynoom c(x) :=
Co
+ c1x + ••• + c
. Stel dat we het woord r := c + e
=
(e , ••• ,e ) met e O k 14
= ~~
~
I4
x 14
ontvangen en dat hierin 2 fouten zitten;
=1, aIle andere coordinaten O.
Zij
reX) Dan is e(a) e(a 3)
= ak
+ a
~
= rea)
(bekend aan de ontvanger!)
"
"
"
tI
)
Oplossen van 2 vergelijkingen met twee onbekenden leert de ontvanger wat k en t zijn. Dus 2 fouten worden verbeterd!.
.,
~
40.
Literatuur M. Hall Jr., Combinatorial Theory, Blaisdell Comp., 1967. J.H. van Lint, Coding Theory, Lecture Notes in Mathematics 201, Springer, 1970. J.H. van Lint, J.J. Seidel, P.C. Baayen, Colloquium Discrete Wiskunde, M.C. Syllabus 5, Mathematisch Centrum; 1968. H.J. Ryser, Combinatorial Mathematics, Carus Monograph, Math. Assoc. Amer., Wiley, 1963.
'
..
•
