“ Ik ben Karel`` - BS de Cramignon Eijsden

Aanvullingen bij Hoofdstuk 13
Het teken van een permutatie
Ter herinnering. Een permutatie van een verzameling V is een bijectie van V naar V .
De verzameling van permutaties van V = {1, 2, 3, . . . , n − 1, n} noteert men met Sn .
Het aantal elementen van Sn is n! = n · (n − 1) · (n − 2) · . . . · 2 · 1.
Definitie. Een transpositie is een permutatie die twee elementen verwisselt en alle
andere elementen op zichzelf afbeeldt.
Bewering. Elke permutatie in Sn is een samenstelling van transposities.
Dit is (hopelijk) intu¨ıtief zeer aannemelijk. We zullen dit gebruiken zonder het exact te
bewijzen.
Voor de vrijwilligers : probeer eventueel per inductie op het aantal elementen van
{1, 2, . . . , n} die niet op zichzelf afgebeeld worden door de permutatie.
Definitie. Zij σ ∈ Sn .
(1) Zij i en j verschillende elementen uit {1, 2, 3, . . . , n − 1, n}. Het paar {i, j} is een
inversie van σ als i < j en σ(i) > σ(j).
(2) Het teken van σ, genoteerd sgn(σ), is +1 als het aantal inversies van σ even is,
en −1 als dat aantal oneven is. In formulevorm :
sgn(σ) = (−1)#{inversies van
σ}
.
Men zegt ook in het eerste geval dat σ even is, en in het tweede dat σ oneven is.
Voorbeeld. Zij σ de permutatie in S3 gegeven door σ(1) = 2, σ(2) = 3 en σ(3) = 1.
Deze heeft twee inversies en dus is sgn(σ) = +1.
Stelling. Zij σ een willekeurige permutatie en τ een transpositie in Sn . Dan geldt :
sgn(τ ◦ σ) = −sgn(σ) .
Anders gezegd : ‘samenstellen met een transpositie verwisselt het teken’.
Bewijs. Noteer voor elke ` in {1, 2, . . . , n} zijn beeld σ(`) als a` (∈ {1, 2, . . . , n}). We
stellen dit ook schematisch voor als
µ
¶
1 2 ... i i + 1 ... j ... n
σ:
.
a1 a2 . . . ai ai+1 . . . aj . . . an
1
De transpositie τ verwisselt twee elementen, zeg ai en aj (met i < j), en beeldt de
andere a` op zichzelf af.
Wat is nu het effect van ‘samenstellen met τ ’ op het aantal inversies ? Meer precies :
wat is het verband tussen het aantal inversies van σ en het aantal inversies van τ ◦ σ ?
Eerst een speciaal geval : j = i + 1. De schematische voorstelling van τ ◦ σ is dan
µ
1
a1
2
a2
...
...
i
ai+1
i+1
ai
...
...
j
aj
...
...
n
an
¶
.
Indien ai < ai+1 heeft τ ◦ σ dus ´e´en inversie meer dan σ. En als anderzijds ai > ai+1
heeft heeft τ ◦ σ ´e´en inversie minder dan σ. In beide gevallen verwisselt dus inderdaad
het teken bij overgang van σ naar τ ◦ σ.
Nu in het algemeen. We kunnen τ ◦ σ verkrijgen door 2(j − i) − 1 keer het vorige
speciale geval toe te passen. Inderdaad, als we eerst j − i keer ai wisselen met het
‘volgende element’ in de schematische voorstelling, verkrijgen we
µ
1
a1
2
a2
...
...
i
i+1
ai+2
ai+1
...
...
j−1 j
aj
ai
...
...
n
an
¶
.
En hierna j − i − 1 keer aj wisselen met het ‘vorige’ element levert
µ
τ ◦σ :
1
a1
2
a2
...
...
i
aj
i+1
ai+1
...
...
j−1
aj−1
j
ai
...
...
n
an
¶
.
Het besluit is dat bij overgang van σ naar τ ◦ σ het teken een oneven aantal keer wisselt,
en dat τ ◦ σ en σ dus een verschillend teken hebben. ¤
Voorbeeld–Oefening. Zij σ in S3 zoals in vorig voorbeeld en τ in S3 gegeven door τ (1) =
2, τ (2) = 1 en τ (3) = 3. Verifieer dat sgn(τ ◦ σ) = −1.
Als onmiddellijk gevolg van de vorige stelling verkrijgen we :
Stelling. Zij σ in Sn een samenstelling van m transposities. Dan is sgn(σ) = (−1)m .
Oefening. Voor elke σ in Sn geldt dat sgn(σ) = sgn(σ −1 ).
2

Download Report