Paritet för en permutation

Permutationer av 4 element Udda permutationer har en grön eller orange bakgrund. Siffrorna i den högra kolumnen är inversionstalen (sekvens A034968 i OEIS ), som har samma paritet som permutationen.

I matematik , när X är en finit mängd med minst två element, faller permutationerna av X (dvs. de bijektiva funktionerna från X till X ) in i två lika stora klasser: de jämna permutationerna och de udda permutationerna . Om någon total ordning av X är fixerad, kan pariteten ( udda eller jämnhet ) för en permutation $\sigma$ av X definieras som pariteten av antalet inversioner för σ , dvs. av par av element x , y av X så att x < y och σ ( x ) > σ ( y ) .

Tecknet , signaturen eller tecknet för en permutation σ betecknas sgn( σ ) och definieras som +1 om σ är jämnt och −1 om σ är udda. Signaturen definierar den alternerande karaktären hos den _symmetriska gruppen Sn . En annan notation för tecknet på en permutation ges av den mer allmänna Levi-Civita-symbolen ( ε _σ ), som är definierad för alla kartor från X till X , och har värdet noll för icke-bijektiva kartor .

Tecknet på en permutation kan uttryckligen uttryckas som

sgn(σ) = (-1) N (σ)

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

Alternativt kan tecknet för en permutation σ definieras från dess nedbrytning till produkten av transpositioner som

sgn(σ) = (-1) m

där m är antalet transpositioner i nedbrytningen. Även om en sådan nedbrytning inte är unik, är pariteten för antalet transpositioner i alla nedbrytningar densamma, vilket antyder att tecknet på en permutation är väldefinierat .

Exempel

Betrakta permutationen σ för mängden {1, 2, 3, 4, 5} definierad av $\sigma (1)=3,$ $\ sigma (2)=4,$ $\sigma (3)=5,$ $\sigma (4)=2,$ och $\sigma (5)=1.$ I enradsnotation betecknas denna permutation 34521. Den kan erhållas från identitetspermutationen 12345 genom tre transpositioner: byt först ut siffrorna 2 och 4, sedan utbyte 3 och 5, och slutligen utbyte 1 och 3. Detta visar att den givna permutationen σ är udda. Enligt metoden i för cykelnotation kan detta skrivas, från vänster till höger, som

\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&3\end{pmatrix}}{\begin{pmatrix}3&5\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

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

,

men det är omöjligt att skriva det som en produkt av ett jämnt antal transponeringar.

Egenskaper

Identitetspermutationen är en jämn permutation. En jämn permutation kan erhållas som sammansättningen av ett jämnt antal och endast ett jämnt antal utbyten (kallade transpositioner ) av två element, medan en udda permutation kan erhållas genom (endast) ett udda antal transpositioner.

Följande regler följer direkt av motsvarande regler om addition 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

Av dessa följer att

inversen av varje jämn permutation är jämn
inversen av varje udda permutation är udda

Med tanke på den symmetriska gruppen S _n för alla permutationer i mängden {1, ..., n } kan vi dra slutsatsen att kartan

sgn: S n \to {-1, 1}

som tilldelar varje permutation dess signatur är en grupphomomorfism .

Vidare ser vi att de jämna permutationerna bildar en undergrupp av S _n . Detta är den alternerande gruppen på n bokstäver, betecknad med A _n . Det är kärnan i homomorfismen sgn. De udda permutationerna kan inte bilda en undergrupp, eftersom sammansättningen av två udda permutationer är jämn, men de bildar en coset av A _n (i S _n ).

Om n > 1 så finns det lika många jämna permutationer i S _n som det finns udda; följaktligen innehåller A _n n ! /2 permutationer. (Anledningen är att om σ är jämnt då (1 2) är σ udda, och om σ är udda så är (1 2) σ jämnt, och dessa två kartor är inversa till varandra.)

En cykel är jämn om och endast om dess längd är udda. Detta följer av formler som

(a\ b\ c\ d\ e)=(d\ e)(c\ e)(b\ e)(a\ e){\text{ eller }}(a\ b)(b\ c)(c\ d)(d\ e).

I praktiken, för att avgöra om en given permutation är jämn eller udda, skriver man permutationen som en produkt av osammanhängande cykler. Permutationen är udda om och endast om denna faktorisering innehåller ett udda antal cykler med jämn längd.

En annan metod för att bestämma om en given permutation är jämn eller udda är att konstruera motsvarande permutationsmatris och beräkna dess determinant. Värdet på determinanten är detsamma som permutationens paritet.

Varje permutation av udda ordning måste vara jämn. Permutationen (1 2)(3 4) i A ₄ visar att det omvända inte är sant i allmänhet.

Likvärdighet mellan de två definitionerna

Detta avsnitt presenterar bevis på att pariteten för en permutation σ kan definieras på två ekvivalenta sätt:

som pariteten för antalet inversioner i σ (under valfri ordning); eller
som pariteten av antalet transpositioner som σ kan dekomponeras till (hur vi än väljer att dekomponera det).

Bevis 1

Låt σ vara en permutation på en rankad domän S . Varje permutation kan produceras av en sekvens av transpositioner (2-elementutbyten). Låt följande vara en sådan sönderdelning

σ = T ₁ T ₂ ... T _k

Vi vill visa att pariteten för k är lika med pariteten för antalet inversioner av σ .

Varje transponering kan skrivas som en produkt av ett udda antal transponeringar av intilliggande element, t.ex

(2 5) = (2 3) (3 4) (4 5) (4 3) (3 2).

Generellt kan vi skriva transpositionen ( i i+d ) på mängden {1,..., i ,..., i+d ,...} som sammansättningen av 2 d −1 angränsande transpositioner genom rekursion på d :

Basfallet d=1 är trivialt.

I det rekursiva fallet, skriv först om ( i , i+d ) som ( i , i +1) ( i +1, i+d ) ( i , i +1). Skriv sedan rekursivt om ( i +1, i+d ) som intilliggande transpositioner.

Om vi sönderdelar på detta sätt var och en av transpositionerna T ₁ ... T _k ovan, får vi den nya sönderdelningen:

σ = A ₁ A ₂ ... A _m

där alla A ₁ ... A _m är intilliggande. Dessutom är pariteten för m densamma som den för k .

Detta är ett faktum: för all permutation τ och intilliggande transposition a, har aτ antingen en mindre eller en mer inversion än τ . Med andra ord växlas pariteten för antalet inversioner av en permutation när den är sammansatt med en intilliggande transponering.

Därför är pariteten för antalet inversioner av σ just pariteten av m , som också är pariteten av k . Detta är vad vi ville bevisa.

Vi kan alltså definiera pariteten för σ att vara den för dess antal ingående transpositioner i vilken sönderdelning som helst. Och detta måste överensstämma med pariteten för antalet inversioner under vilken ordning som helst, som ses ovan. Därför är definitionerna verkligen väldefinierade och likvärdiga.

Bevis 2

Ett alternativt bevis använder Vandermonde-polynomet

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

Så till exempel i fallet n = 3 har vi

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

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

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

Eftersom polynomet $har {\displaystyle P(x_{\sigma (1)},\dots ,x_{\sigma (n)})}$ samma faktorer som $P(x_{1},\dots ,x_{n})$ förutom deras tecken, följer att sgn( σ ) är antingen +1 eller −1. Dessutom, om σ och τ är två permutationer, ser vi det

{\begin{aligned}\operatörsnamn {sgn}(\sigma \tau )&={\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\ tau (n))})}{P(x_{1},\ldots ,x_{n})}}\\[4pt]&={\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)})}}\\[4pt]&= \operatörsnamn {sgn}(\sigma )\cdot \operatornamn {sgn}(\tau ).\end{aligned}}

Eftersom det med denna definition dessutom är tydligt att varje transponering av två element har signaturen −1, gör vi det verkligen återställa signaturen enligt tidigare definition.

Bevis 3

En tredje metod använder presentationen av gruppen S _n i termer av generatorer τ ₁ , ..., τ _{n −1} och relationer

$\tau _{i}^{2}=1$ för alla i
$\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{ i+1}\tau _{i}\tau _{i+1}$ för alla i < n − 1
$\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ om $|ij|\geq 2.$

[Här representerar generatorn

\tau _{i}

transpositionen ( i , i + 1) .] Alla relationer håller ett ords längd lika eller ändrar det med två. Att börja med ett ord med jämn längd kommer alltså alltid att resultera i ett ord med jämn längd efter användning av relationerna, och likaså för udda ord. Det är därför otvetydigt att kalla elementen i S _n representerade av ord med jämn längd "jämna", och elementen som representeras av ord med udda längd "udda".

Bevis 4

Kom ihåg att ett par x , y så att x < y och σ ( x ) > σ ( y ) kallas en inversion. Vi vill visa att antalet inversioner har samma paritet som antalet 2-elementsbyten. För att göra det kan vi visa att varje swap ändrar pariteten för antalet inversioner, oavsett vilka två element som byts ut och vilken permutation som redan har tillämpats. Anta att vi vill byta det i: te och det j: te elementet. Uppenbarligen kommer inversioner som bildas av i eller j med ett element utanför [ i , j ] inte att påverkas. För n = j − i − 1 inom intervallet ( i , j ) , antag att v _i av dem bildar inversioner med i och v _j av dem bildar inversioner med j . Om i och j byts om, är de v _i- inversioner med i borta, men n − v _i -inversioner bildas. Antalet inversioner i vunnit är alltså n − 2 v _i , vilket har samma paritet som n .

På liknande sätt har antalet inversioner j som erhållits också samma paritet som n . Därför har antalet inversioner som erhålls av båda kombinerat samma paritet som 2 n eller 0. Om vi nu räknar de inversioner som erhållits (eller förlorat) genom att byta det i: te och det j: te elementet, kan vi se att detta utbyte ändrar paritet för antalet inversioner, eftersom vi också adderar (eller subtraherar) 1 till antalet inversioner som erhållits (eller förlorats) för paret ( i,j) .

Observera att till en början när ingen swap tillämpas är antalet inversioner 0. Nu får vi ekvivalens mellan de två definitionerna av paritet för en permutation.

Bevis 5

Betrakta de element som är inklämda av de två elementen i en transponering. Var och en ligger helt ovanför, helt under eller mellan de två transponeringselementen.

Ett element som är antingen helt över eller helt under bidrar inte till inversionsräkningen när transponeringen tillämpas. Element däremellan bidrar med $2$ .

Eftersom själva transponeringen ger

\pm 1

inversion, och alla andra ger 0 (mod 2) inversioner, ändrar en transponering pariteten för antalet inversioner.

Andra definitioner och bevis

Pariteten för en permutation av $n$ punkter är också kodad i dess cykelstruktur .

Låt σ = ( i ₁ i ₂ ... i _{r +1} )( j ₁ j ₂ ... j _{s +1} )...( ℓ ₁ ℓ ₂ ... ℓ _{u +1} ) vara den unika nedbrytningen av σ till disjunkta cykler , som kan sammansättas i valfri ordning eftersom de pendlar. En cykel ( a b c ... x y z ) som involverar k + 1 poäng kan alltid erhållas genom att komponera k transpositioner (2-cykler):

(a\ b\ c\dots x\ y\ z)=(a\ b )(b\ c)\prickar (x\ y)(y\ z),

så kalla k storleken på cykeln och observera att under denna definition är transpositioner cykler av storlek 1. Från en sönderdelning till m osammanhängande cykler kan vi få en sönderdelning av σ till k ₁ + k ₂ + ... + k _m transpositioner, där k _i är storleken på den i: te cykeln. Talet N ( σ ) = k ₁ + k ₂ + ... + k _m kallas diskriminanten för σ , och kan också beräknas som

n{\text{ minus antalet disjunkta cykler i sönderdelningen av }}\sigma

om vi ser till att inkludera fixpunkterna för σ som 1-cykler.

Antag att en transposition ( a b ) tillämpas efter en permutation σ . När a och b är i olika cykler av σ då

(a\ b )(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{ 2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})

,

och om a och b är i samma cykel av σ då

(a\ b )(ac_{1}c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})

.

I båda fallen kan det ses att N (( a b ) σ ) = N ( σ ) ± 1 , så pariteten för N (( a b ) σ ) kommer att skilja sig från pariteten för N ( σ ).

Om σ = t ₁ t ₂ ... t _r är en godtycklig nedbrytning av en permutation σ till transpositioner, genom att tillämpa r -transpositionerna $t_{1}$ efter t ₂ efter ... efter t _r efter identitet (vars N är noll) observera att N ( σ ) och r har samma paritet. Genom att definiera pariteten för σ som pariteten av N ( σ ), är en permutation som har en jämn sönderdelning en jämn permutation och en permutation som har en sönderdelning med en udda längd är en udda permutation.

Anmärkningar

En noggrann undersökning av ovanstående argument visar att r ≥ N ( σ ) , och eftersom all nedbrytning av σ i cykler vars storlekar summa till r kan uttryckas som en sammansättning av r transpositioner, är talet N ( σ ) den minsta möjliga summan av storleken på cyklerna i en sönderdelning av σ , inklusive de fall där alla cykler är transpositioner.
Detta bevis introducerar inte en (möjligen godtycklig) ordning i den uppsättning punkter som σ verkar på.

Generaliseringar

Paritet kan generaliseras till Coxeter-grupper : man definierar en längdfunktion ℓ( v ), som beror på ett val av generatorer (för den symmetriska gruppen, närliggande transpositioner ), och sedan ger funktionen v ↦ (−1) ^{ℓ( v )} en generaliserad teckenkarta.

Se även

Femtonpusslet är en klassisk applikation
Zolotarevs lemma

Anteckningar

Weisstein, Eric W. "Even Permutation" . MathWorld .
Jacobson, Nathan (2009). Grundläggande algebra . Vol. 1 (andra upplagan). Dover. ISBN 978-0-486-47189-1 .
Rotman, JJ (1995). En introduktion till gruppteori . Examentexter i matematik. Springer-Verlag. ISBN 978-0-387-94285-8 .
Goodman, Frederick M. Algebra: Abstrakt och konkret . ISBN 978-0-9799142-0-1 .
Meijer, Paul Herman Ernst; Bauer, Edmond (2004). Gruppteori: tillämpningen till kvantmekanik . Dover klassiker inom vetenskap och matematik. Dover Publikationer. ISBN 978-0-486-43798-9 .