Paritet (permutationer)

Inom matematiken, när X är en ändlig mängd med minst två element, delas permutationerna av X (det vill säga de bijektiva funktionerna från X till X) i två klasser av lika storlek: de jämna permutationerna och de udda permutationerna. Om en linjär ordning av X föreligger så kan pariteten för en permutation σX definieras som antalet inversioner för σ, det vill säga antalet par av element  i X sådana att  och .

Tecknet eller signaturen för en permutation σ betecknas sgn(σ) och definieras som +1 om σ är jämnt och som -1 om σ är udda. Signaturen bestämmer den alternerande karaktären för den symmetriska gruppen Sn. En annan notation för permutationens tecken ges av den mera allmänna Levi-Civita-tensorn (), som definieras för alla avbildningar från X till X, och har värdet noll för icke -bijektiva avbildningar.

En permutations tecken kan explicit uttryckas som 

där inversionstalet N(σ) är antalet inversioner i σ.

En permutations σ tecken kan också definieras som den sammansatta produkten av transpositioner som

där  är antalet transpositioner i sammansättningen. Fastän en sådan sammansättning inte är unik är pariteten för antalet transpositioner alltid densamma, vilket medför att en permutations tecken är väldefinierat.

En enkel beskrivning
Om vi har ett antal ordnade objekt, som exempelvis de tre bokstäverna ABC kan vi ändra ordningen på dem genom att byta plats på två av dem. Till exempel kan vi byta plats på A och B och få ordningen BAC. Det finns sex olika sätt (permutationer) på vilka vi kan ordna A, B och C: ABC, ACB, BAC, BCA, CAB och CBA. Genom att byta plats på två bokstäver (utföra en transposition) kan vi från ABC få ACB, BAC och CBA, men ingen av de andra tre. Genom ytterligare en transposition kan vi däremot få dessa tre: ABC (som vi ju hade från början), BCA och CAB. Sålunda kan de sex permutationerna indelas i två "grupper" - de som går att åstadkomma genom ett jämnt antal transpositioner från utgångsläget och de som går att åstadkomma genom ett udda antal transpositioner. Precis samma sak gäller för fler objekt än tre, vilket man enkelt inser genom att lägga till ytterligare ett objekt och flytta detta till "rätt" plats sist. Exempel: Med en transposition går vi från ABCD till ACBD och med ytterligare en transposition kommer vi till DCBA, ADBC eller ACDB. Och så vidare för fem, sex, sju eller hur många som helst objekt... Antingen ett jämnt antal transpositioner eller ett udda.

Exempel 
Betrakta permutationen σ av mängden  som omvandlar begynnelseordningen 12345 till 34521.
Denna kan erhållas genom tre transpositioner: byt först plats på 1 och 5, sedan på 1 och 3, och till sist på 2 och 4. Detta visar att σ är udda.
 
Det finns många andra sätt att skriva σ som en sammansättning av transpositioner, till exempel
,
men det är omöjligt att skriva den som ett jämnt antal transpositioner.

Egenskaper 
Identitetspermutationen är en jämn permutation. En jämn permutation kan erhållas endast som en sammansättning av, och endast av, ett jämnt antal transpositioner, medan en udda permutation endast kan erhållas av ett udda antal transpositioner.

Följande regler följer direkt ur motsvarande regler för additioner av heltal:
 sammansättningen av två jämna permutationer är jämn
 sammansättningen av två udda permutationer är jämn
 sammansättningen av en udda och en jämn permutation är udda
Från dessa följer:
 inversen av varje jämn permutation är jämn
 inversen av varje udda permutation är udda.

Vad beträffar den symmetriska gruppen S av alla permutationer på mängden {1, ..., }, kan vi dra slutsatsen att avbildningen
,
som tilldelar vaje permutation dess signatur, är en grupphomomorfism.

Vidare ser vi att de jämna permutationerna bildar en undergrupp till S. Detta är den alternerande gruppen över  tecken, betecknad med A. Detta är nollrummet till homomorfismen sgn. De udda permutationerna kan inte bilda en undergrupp eftersom produkten (sammansättningen) av två udda permutationer är jämn, men de udda permutationerna bildar en sidoklass till A (in S).

Om  > 1, så finns det precis lika många udda permutationer som jämna i S - följaktligen innehåller då A !/2 permutationer. Anledningen härtill är att om  är jämn så är multiplikationen  =  udda och om  är udda så är  =  jämn; de två avbildningarna är varandras inverser.

En cyklisk permutation är jämn om och endast om dess längd är udda. Detta följer från uttryck som
(a b c d e) = (d e) (c e) (b e) (a e)
I praktiken skriver man en permutation som en produkt av disjunkta cykler för att bestämma dess paritet. Permutationen är udda om och endast om denna faktorisering innehåller ett udda antal lika långa cykler.

En annan metod för att avgöra huruvida en permutation är jämn eller udda är att konstruera dess permutationsmatris och beräkna dess determinant. Värdet på determinaten är detsamma som permutationens paritet.

Varje permutation av udda ordning måste vara jämn. Permutationen (12)(34) i A4 visar att det motsatta i allmänhet inte gäller.

Bevis för att de två definitionerna är ekvivalenta

Bevis 1 

Varje permutation kan åstadkommas genom en sekvens av transpositioner (byte av två element mot varandra), eftersom vi med den första transpositionen kan placera det första (felaktigt placerade) elementet på rätt plats, med nästa transposition kan vi placera nästa element rätt, och så vidare. Om vi har en permutation σ, kan vi skriva den som en produkt av transpositioner på många olika sätt. Vi skall visa att antingen består alla dessa sammansättningar ett jämnt antal transpositioner, eller så består alla av ett udda antal.

Antag att vi har två sådana sammansättningar:
σ = T1 T2 ... Tk
σ = Q1 Q2 ... Qm.
Vi vill visa att antingen är både k och m jämna, eller så är båda udda.

Varje transposition kan skrivas som en produkt av ett udda antal transpositioner av intilliggande element.
Exempel: Om vi har permutationen (2 5) = (2 3)(3 4)(4 5)(4 3)(3 2) [=(2 3)(3 4)(4 5)(3 4)(2 3)]
som permuterar "abcde(f...)" till "aecdb(f...)": De två första transpositionerna, (2 3)(3 4), flyttar bak "b" så att det hamnar strax före "e", den tredje (4 5) byter plats på dem ("be" blir "eb"), och sedan har "e" två transpositioner framåt (4 3)(3 2) till utgångsläget för "b". Sålunda får vi ju generellt: n "hopp" bakåt, ett byte, och n "hopp" framåt, alltså 2n+1=udda! Hela processen är, som framgår av skrivningen inom hakparenteser ovan, symmetrisk kring den mittersta transpositionen.
Om vi på detta sätt bryter ner alla transpositionerna T1...Tk och Q1...Qm till ett udda antal transpositioner av intilliggande element får vi de nya sammansättningarna:
σ = T1′ T2′ ... Tk′
σ = Q1′ Q2′ ... Qm′
där alla T1′...Tk′ och Q1′...Qm′ är intilliggande; vidare är k − k′ är jämnt, liksom m − m′.<ref>Om k är jämnt och varje Ti (1 ≤ i ≤ k) bryts ner i ett udda antal transpositioner av intilliggande element, kommer ju k′ att bli summan av ett jämnt antal (d.v.s. k) udda termer, vilken ju är jämn. På motsvarande sätt, om k är udda, kommer k′ att bli summan av ett udda antal udda termer, vilken ju är udda. k − k′, skillnaden antingen mellan två jämna tal eller mellan två udda, blir alltså i båda fallen ett jämnt tal. Självklart är förhållandet detsamma för m och ''m</ref>

Sätt nu samman inversen av T1' med σ. T1' är transpositionen (i, i + 1) av två intilliggande tal, så i förhållande till σ kommer den nya permutationen σ (i, i + 1) att ha exakt en inversion mer (om (i, i + 1) inte var en inversion) eller mindre (om (i, i + 1) var en inversion).Exempel: Om vi transpositionerar de intilliggande 2 och 5 i "xxxx25yyyy" får vi "xxxx52yyyy" medför detta en, och endast en, inversion mer (antalet inversioner för "xxxx" och "yyyy" påverkas ju ej och ej heller de inversioner som beror av "xxxx" i förhållande till 5 och 2). Inversionstalet ökar alltså med ett. Transpositionerar vi "xxxx52yyyy" till "xxxx25yyyy" får vi en inversion mindre och inversionstalet minskar med ett. Var inversionstalet jämnt före transpositionen blir det udda efter och vice versa - inversionstalet byter alltså paritet, när antalet transpositioner byter paritet.
Fortsätt på samma sätt med T2', T3', ... Tk' så att σ "vecklas upp". Till slut kommer vi att ha identitetspermutationen vars inversionstal N är noll. Detta betyder att det ursprungliga N(σ) minus k är jämnt och också att N(σ) minus k' är jämnt.

Vi kan göra samma sak med den andra sammansättningen, Q1'...Qm', och på samma sätt är det ursprungliga N(σ) minus m är jämnt.

Sålunda är m − k jämnt, vilket medför att antingen är båda jämna eller så är båda udda, vilket vi skulle visa.

Vi kan nu definiera permutationen σ att vara jämn om dess inversionstal N(σ) är jämnt, och som udda om dess inversionstal N(σ) är udda. Detta sammanfaller med definitionen ovan, men det är nu också klart att varje permutation verkligen antingen är jämn eller så är den udda.

 Bevis 2 

Ett alternativt bevis utnyttjar polynomet

Så har vi exempelvis för fallet  = 3,

Nu definierar vi, för en given permutation σ av talen {1, ..., }Exempel:''' För den ordnade mängden {1,2,3} och permutationen σ{1,2,3} = {3,1,2} får vi 
P = (1-2)(2-3)(1-3) = (-1)(-1)(-2) = 2⋅(-1)3 = -2 och 
Pσ = (3-1)(1-2)(3-2) = (1-2)(3-2)(3-1) = (-1)(+1)(+2) = 2⋅(-1) = -2. 
Eftersom |(1-2)(2-3)(1-3)| = |(1-2)(3-2)(3-1)| är |P| = |Pσ| och bara tecknet skiljer eventuellt (så ej i detta fall eftersom σ är jämn). Vi får alltså: sgn(σ) = Pσ/P = -2/-2 = 1. 
Den udda permutationen σ´{1,2,3} = {2,1,3} ger 
Pσ´ = (2-1)(1-3)(2-3) = (2-1)(2-3)(1-3) = (+1)(-1)(-2)=+2 
och alltså är Pσ´/P = 2/-2 = -1, och sålunda är σ´ udda.

Eftersom polynomet  består av samma faktorer som , bortsett från deras tecken, följer det att sgn(σ) antingen är +1 eller -1. Vidare, om σ och τ är två permutationer, ser vi att
 

Eftersom det med denna definition ytterligare är klarlagt att varje transposition av två element har signaturen -1, får vi såklart samma signatur som definierats ovan.

Se även 
 Femtonspelet, som är en klassisk tillämpning, fastän det egentligen innehåller en gruppoid.

Noter

Referenser
 
 
  
 
 

Gruppteori
Permutationer
Paritet