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 $x$ , $y$ i X sådana att $x<y$ och $\sigma (x)>\sigma (y)$ .

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 S_n. En annan notation för permutationens tecken ges av den mera allmänna Levi-Civita-tensorn ( $\epsilon _{\sigma }$ ), 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

sgn(σ) = (−1)^N(σ)

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

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

sgn(σ) = (−1)^$m$

där $m$ ä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.^[1]

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 {1, 2, 3, 4, 5} 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.

\sigma ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}={\begin{pmatrix}1&3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}={\begin{pmatrix}1&5\end{pmatrix}}{\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}.

Det finns många andra sätt att skriva σ som en sammansättning av transpositioner, till exempel

σ = (2 3) (1 2) (2 4) (3 5) (4 5),

men det är omöjligt att skriva den som ett jämnt antal transpositioner.

Egenskaper

Identitetspermutationen är en jämn permutation.^[1] 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:^[1]

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_$n$ av alla permutationer på mängden {1, ..., $n$ }, kan vi dra slutsatsen att avbildningen

sgn: S_$n$ → {−1, 1} ,

som tilldelar vaje permutation dess signatur, är en grupphomomorfism.^[2]

Vidare ser vi att de jämna permutationerna bildar en undergrupp till S_$n$.^[1] Detta är den alternerande gruppen över $n$ tecken, betecknad med A_$n$.^[3] Detta är nollrummet till homomorfismen sgn.^[4] 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_$n$ (in S_$n$).^[5]

Om $n$ > 1, så finns det precis lika många udda permutationer som jämna i S_$n$^[3] - följaktligen innehåller då A_$n$ $n$ !/2 permutationer. Anledningen härtill är att om σ är jämn så är multiplikationen σ´ = (1 2) σ udda och om σ´ är udda så är σ = (1 2) σ´ jämn; de två avbildningarna är varandras inverser.^[3]

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 A₄ 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:

σ = T₁ T₂ ... T_k

σ = Q₁ Q₂ ... Q_m.

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 T₁...T_k och Q₁...Q_m till ett udda antal transpositioner av intilliggande element får vi de nya sammansättningarna:

σ = T_1′ T_2′ ... T_k′

σ = Q_1′ Q_2′ ... Q_m′

där alla T_1′...T_k′ och Q_1′...Q_m′ är intilliggande; vidare är k − k′ är jämnt, liksom m − m′.^[6]

Sätt nu samman inversen av T_1' med σ. T_1' ä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 T_2', T_3', ... T_k' 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, Q_1'...Q_m', 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

P(x_{1},\ldots ,x_{n})=\prod _{i<j}(x_{i}-x_{j})\;

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

P(x_{1},x_{2},x_{3})=(x_{1}-x_{2})(x_{2}-x_{3})(x_{1}-x_{3})\;

Nu definierar vi, för en given permutation σ av talen {1, ..., $n$ }

\operatorname {sgn} (\sigma )={\frac {P_{\sigma }}{P}}={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}

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)³ = -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 $P(x_{\sigma (1)},\dots ,x_{\sigma (n)})$ består av samma faktorer som $P(x_{1},\dots ,x_{n})$ , bortsett från deras tecken, följer det att sgn(σ) antingen är +1 eller -1. Vidare, om σ och τ är två permutationer, ser vi att

\operatorname {sgn} (\sigma \tau )={\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{1},\ldots ,x_{n})}}

={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}\cdot {\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}}

=\operatorname {sgn} (\sigma )\cdot \operatorname {sgn} (\tau )

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

^ [a b c d] Jacobson (2009), p. 50.
^ Rotman (1995), sid. 9, Theorem 1.6.
^ [a b c] Jacobson (2009), p. 51.
^ Goodman, sid. 116, definition 2.4.21
^ Meijer & Bauer (2004), "these permutations do not form a subgroup since the product of two odd permutations is even", sid. 72
^ Om k är jämnt och varje T_i (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'

Referenser

Weisstein, Eric W., "Even Permutation", MathWorld. (engelska)
Jacobson, Nathan (2009). Basic algebra. "1" (2nd). Dover. ISBN 978-0-486-47189-1
Rotman, J.J. (1995). An introduction to the theory of groups. Graduate texts in mathematics. Springer-Verlag. ISBN 978-0-387-94285-8. Arkiverad från originalet den 7 mars 2016. https://web.archive.org/web/20160307181230/http://shi.matmor.unam.mx/algebra/Rotman%20J.J.%20Introduction%20to%20the%20theory%20of%20groups.pdf. Läst 7 november 2014 Arkiverad 7 mars 2016 hämtat från the Wayback Machine.
Goodman, Frederick M. (2012). Algebra: Abstract and Concrete. ISBN 978-0-9799142-0-1. http://homepage.math.uiowa.edu/~goodman/algebrabook.dir/bookmt.pdf
Meijer, Paul Herman Ernst; Bauer, Edmond (2004). Group theory: the application to quantum mechanics. Dover classics of science and mathematics. Dover Publications. ISBN 978-0-486-43798-9

[Jacobson-1] [a b c d] Jacobson (2009), p. 50.

[2] Rotman (1995), sid. 9, Theorem 1.6.

[Jacobson_a-3] [a b c] Jacobson (2009), p. 51.

[4] Goodman, sid. 116, definition 2.4.21

[5] Meijer & Bauer (2004), "these permutations do not form a subgroup since the product of two odd permutations is even", sid. 72

[6] Om k är jämnt och varje T_i (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'

[1]

[2]

[3]

[4]

[5]

[6]