Underskrift av en permutasjon

I matematikk kalles en permutasjon av ferdige medier par hvis den har et jevnt antall inversjoner , rart ellers. Den underskrift av en permutasjon er verdt en om det er enda, -1 hvis det er rart.

Den signatur kartlegging , fra den symmetriske gruppen inn i den gruppe ({-1, 1}, x), er en morphism , det vil si det tilfredsstiller en egenskap som er analoge med de tegn regel . $\ mathfrak S_n$

Enhver permutasjon brytes ned til et produkt av transposisjoner. En transposisjon som er merkelig , kommer fra denne regelen om tegnene på at pariteten til antall transposisjoner av en slik nedbrytning sammenfaller med pariteten til permutasjonen (og derfor ikke avhenger av den valgte nedbrytningen).

Enhver morfisme i en abelsk gruppe blir tatt med av signaturmorfismen. $\ mathfrak S_n$

Signaturen griper spesielt inn i lineær algebra , i formelen til Leibniz, som er en måte å definere determinanten til en firkantmatrise .

Definisjon av signatur

I denne artikkelen definerer vi pariteten til en permutasjon ved å telle inversjonene (in) .

Definisjon La jeg < j være to heltall mellom 1 og n . Vi sier at paret { i , j } er i inversjon for

σ

hvis

σ ( i )> σ ( j )

En permutasjon blir sagt par hvis den har et jevnt antall inversjoner, ellers rart . Den underskrift av en enda permutasjon er 1; den for en merkelig permutasjon er –1.

Med andre ord, signaturen til en permutasjon $σ$ , betegnet i resten av denne artikkelen $ε ( σ )$ , kontrollerer om vi betegner ved $SGN$ den Signum :

{\ displaystyle \ varepsilon (\ sigma) = \ prod _ {1 \ leq i <j \ leq n} \ operatorname {sgn} (\ sigma (j) - \ sigma (i))}

. Eksempler

Vurder permutasjonen ${\ displaystyle \ sigma: = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 5 & 4 & 2 \ end {pmatrix}}}$ som fikser 1 og 4 og sender 2 av 3, 3 av 5 og 5 av 2. Å
telle antall inversjoner betyr å telle antall lidelser i andre linje. Det er fire av dem: 3 er før 2, 5 før 4, 5 før 2, og 4 før 2. Dette betyr at parene som er dannet fra deres fortilfeller, ifølge definisjonen er inversjoner, det vil si parene {2 , 5}, {3.4}, {3.5}, {4.5}.
Siden det er fire, er $σ$ jevn og $ε ( σ ) = 1$ .
Tenk på k- sykkelen ${\ displaystyle \ sigma: = {\ begin {pmatrix} 1 & 2 & \ prikker & k-1 & k & k + 1 & \ prikker & n \\ 2 & 3 & \ prikker & k & 1 & k + 1 & \ dots & n \ end {pmatrix}}}$ som sender 1 på 2, 2 på 3,…, k - 1 på k , k på 1 og som fikser alle de andre heltallene.
Dens omvendte par er { i , k }, for i < k .
Det er k - 1 så $ε ( σ ) = (-1) k -1$ , og $σ$ er selv om og bare hvis k er merkelig.

En formel for signaturen

En permutasjon har for signatur: ${\ displaystyle \ sigma \ i {\ mathfrak {S}} _ {n}}$

{\ displaystyle \ varepsilon (\ sigma) = \ prod _ {1 \ leq i <j \ leq n} {\ frac {\ sigma (j) - \ sigma (i)} {ji}} = \ prod _ {\ {i, j \} \ i {\ mathcal {P}}} {\ frac {\ sigma (j) - \ sigma (i)} {ji}}}

hvor betegner settet med par med forskjellige heltall mellom $1$ og $n$ . ${\ displaystyle {\ mathcal {P}} = \ {\ {i, \, j \} \ mid 1 \ leq i \ leq n {\ mbox {and}} 1 \ leq j \ leq n {\ mbox {og }} i \ neq {j} \}}$

Demonstrasjon

Per definisjon,

{\ displaystyle \ varepsilon (\ sigma) = \ prod _ {1 \ leq i <j \ leq n} \ operatorname {sgn} (\ sigma (j) - \ sigma (i)) = \ prod _ {1 \ leq i <j \ leq n} {\ frac {\ sigma (j) - \ sigma (i)} {\ left | \ sigma (j) - \ sigma (i) \ right |}} = {\ frac {\ prod _ {1 \ leq i <j \ leq n} {\ left (\ sigma (j) - \ sigma (i) \ right)}} {\ prod _ {1 \ leq i <j \ leq n} {\ left | \ sigma (j) - \ sigma (i) \ right |}}}}

og vi kan transformere nevneren ved hjelp av bijektiviteten til $σ$ :

{\ displaystyle \ prod _ {1 \ leq i <j \ leq n} \ left | \ sigma (j) - \ sigma (i) \ right | = \ prod _ {\ {i, j \} \ in {\ mathcal {P}}} \ left | \ sigma (j) - \ sigma (i) \ right | = \ prod _ {\ {k, l \} \ in {\ mathcal {P}}} \ left | kl \ høyre | = \ prod _ {1 \ leq i <j \ leq n} {ji}}

Produktets signatur

Permutasjonene kontrollerer en skiltregel for produktet :

produktet av to jevne permutasjoner er jevnt;
produktet av to rare permutasjoner er jevnt;
produktet av en jevn og en merkelig permutasjon er merkelig.

Ved hjelp av signaturen kommer det ned til formelen:

{\ displaystyle \ varepsilon (\ sigma _ {1} \ circ \ sigma _ {2}) = \ varepsilon (\ sigma _ {1}) \ varepsilon (\ sigma _ {2})}

. Demonstrasjon

Vær . Så ( se ovenfor ): ${\ displaystyle \ sigma _ {1}, \ sigma _ {2} \ i {\ mathfrak {S}} _ {n}}$

{\ displaystyle {\ begin {align} \ varepsilon (\ sigma _ {1} \ circ \ sigma _ {2}) & = \ prod _ {\ {i, j \} \ in {\ mathcal {P}}} {\ frac {(\ sigma _ {1} \ circ \ sigma _ {2}) (j) - (\ sigma _ {1} \ circ \ sigma _ {2}) (i)} {ji}} \\ & = \ prod _ {\ {i, j \} \ i {\ mathcal {P}}} {\ frac {\ sigma _ {1} (\ sigma _ {2} (j)) - \ sigma _ {1 } (\ sigma _ {2} (i))} {\ sigma _ {2} (j) - \ sigma _ {2} (i)}} \ prod _ {\ {i, j \} \ in {\ matematisk {P}}} {\ frac {\ sigma _ {2} (j) - \ sigma _ {2} (i)} {ji}}. \ slutt {justert}}}

I den andre faktoren til det siste uttrykket, kjenner vi direkte igjen . ${\ displaystyle \ varepsilon (\ sigma _ {2})}$

For det første må vi først reindexere (takket være ect 2's bijektivitet ) ved å sette : ${\ displaystyle \ {k, l \} = \ {\ sigma _ {2} (i), \ sigma _ {2} (j) \}}$

{\ displaystyle \ prod _ {\ {i, j \} \ i {\ mathcal {P}}} {\ frac {\ sigma _ {1} (\ sigma _ {2} (j)) - \ sigma _ { 1} (\ sigma _ {2} (i))} {\ sigma _ {2} (j) - \ sigma _ {2} (i)}} = \ prod _ {\ {k, l \} \ in {\ mathcal {P}}} {\ frac {\ sigma _ {1} (k) - \ sigma _ {1} (l)} {kl}} = \ varepsilon (\ sigma _ {1})}

I algebraiske termer: signaturen er en morfisme fra den symmetriske gruppen til toelementgruppen ({–1, 1}, ×). $\ mathfrak S_n$

Spesielt har enhver konjugatpermutasjon av σ samme signatur som σ (bil ). ${\ displaystyle \ varepsilon (\ rho \ sigma \ rho ^ {- 1}) = \ varepsilon (\ rho) \ varepsilon (\ sigma) \ varepsilon (\ rho) ^ {- 1} = \ varepsilon (\ sigma)}$

En transponering er merkelig

Signaturen til en k- sykkel er $(-1) k -1$ . Spesielt er signaturen til en transponering (en 2-syklus) $-1$ .

Fra den siste egenskapen ovenfor og det faktum at to sykluser av samme lengde er konjugert , er det tilstrekkelig å kontrollere den for bare en syklus per lengde, noe som ble gjort i eksempel 2 ovenfor .

Beregning av en signatur

I henhold til de to foregående seksjonene og nedbrytningen til produktet av transposisjoner kommer det at enhver permutasjon er enten jevn eller merkelig, med: $\ sigma$

$\ sigma$ er jevn (med andre ord :) hvis og bare hvis den kan spaltes til et jevnt antall transposisjoner; ${\ displaystyle \ varepsilon (\ sigma) = + 1}$
$\ sigma$ er merkelig (med andre ord :) hvis og bare hvis det kan spaltes til et oddetall transposisjoner. ${\ displaystyle \ varepsilon (\ sigma) = - 1}$

Dette gjør det mulig å bestemme pariteten (eller signaturen) til en permutasjon mer effektivt enn ved ganske enkelt å telle inversjonene; faktisk, for en permutasjon av , krever en slik nedbrytning maksimalt $n$ $- 1$ operasjoner, mot $n$ $($ $n$ $- 1) / 2$ hvis definisjonen brukes direkte ( se ovenfor ). ${{\ mathfrak S}} _ {n}$

Eksempler

Den identiteten av {1, ..., n } er jevn.
Den omvendte permutasjonen av σ har samme paritet som σ.
En sirkulær permutasjon er selv om og bare hvis støtten inneholder et ulikt antall elementer ( se ovenfor ).

Denne siste observasjonen gjør det mulig å beregne signaturen til en permutasjon fordelt på sykluser . Signaturen til en permutasjon av er verdt , hvor $m$ er antall nedbrytningssykluser (teller de faste punktene som sykluser med lengde 1) i og $p$ antall sykluser med jevn lengde i samme nedbrytning. $\ sigma$ ${{\ mathfrak S}} _ {n}$ ${\ displaystyle (-1) ^ {nm} = (- 1) ^ {p}}$ $\ sigma$

Morfisme

${\ displaystyle {\ mathfrak {S}} _ {1}}$ å være den trivielle gruppen , antar . $n \ ge2$

I henhold til formelen for et produkt og impariteten til transposisjonene , er signaturen da en surjectiv morfisme av in ({–1, 1}, ×), og kjernen er den vekslende gruppen med jevne permutasjoner. $\ mathfrak S_n$ ${\ displaystyle {\ mathfrak {A}} _ {n}}$

Denne undergruppe er den gruppe avledet fra , er signaturen derfor en realisering av den kanoniske morphism av i sin abelianized , den kvotient gruppe . Dette betyr at enhver morphism f av i en abelsk gruppe er tatt ved ε, eller igjen: hvis bilde av f er ikke triviell gruppe, så det er en gruppe av orden 2 og f faller sammen, via det unike isomorfi mellom denne gruppe og ( {–1, 1}, ×), med ε. ${\ displaystyle {\ mathfrak {A}} _ {n}}$ $\ mathfrak S_n$ $\ mathfrak S_n$ ${\ displaystyle {\ mathfrak {S}} _ {n} / {\ mathfrak {A}} _ {n} \ simeq (\ {- 1,1 \}, \ times)}$ $\ mathfrak S_n$

Direkte demonstrasjon

Dette beviset bruker ovennevnte og spaltning av permutasjoner til et produkt av transposisjoner .

La f være en ikke- triviell morphism av i en abelsk gruppe G , betegnet med multiplikasjon. $\ mathfrak S_n$

Det er en permutasjon slik at , og siden er et produkt av transposisjoner, er det en transponering slik at . $\ sigma$ ${\ displaystyle f (\ sigma) \ neq 1}$ $\ sigma$ $\ tau _ {0}$ ${\ displaystyle \ lambda: = f (\ tau _ {0}) \ neq 1}$

Resonnementet som er gjort ovenfor for ε gjelder også f : alle transposisjonene blir konjugert , de har samme bilde av f . For enhver transponering har vi derfor . $\ tau$ ${\ displaystyle f (\ tau) = f (\ tau _ {0}) = \ lambda}$

Derved kan enhver permutasjon som dekomponerer til i produktet av m transponering, tilfredsstiller: . $\ sigma$ ${\ displaystyle \ tau _ {1} \ tau _ {2} \ dots \ tau _ {m}}$ ${\ displaystyle f (\ sigma) = f (\ tau _ {1}) f (\ tau _ {2}) \ dots f (\ tau _ {m}) = \ lambda ^ {m}}$

Spesielt er av orden 2 fordi derfor . $\ lambda$ ${\ displaystyle \ mathrm {Id} = \ tau _ {0} ^ {2}}$ ${\ displaystyle \ lambda ^ {2} = f (\ mathrm {Id}) = 1}$

I henhold til pariteten til m :

{\ displaystyle f (\ sigma) = \ lambda ^ {m} = {\ begin {cases} \ lambda & {\ text {si}} \ varepsilon (\ sigma) = - 1 \\ 1 & {\ text {si }} \ varepsilon (\ sigma) = 1. \ end {cases}}}

Se også