Underskrift af en permutation

I matematik kaldes en permutation af færdige medier par, hvis den har et lige antal inversioner , ellers uligt . Den underskrift en permutation er værd 1, hvis det er endda, -1 hvis det er ulige.

Den signatur kortlægning , fra den symmetriske gruppe i gruppen ({-1, 1}, x), er en morphism , dvs. det opfylder en egenskab analoge med tegnet regel . $\ mathfrak S_n$

Enhver permutation nedbrydes til et produkt af transpositioner. En transponering er mærkelig , det kommer fra denne regel af tegnene , at pariteten af antallet af transponeringer af en sådan nedbrydning falder sammen med permutationens paritet (og derfor ikke afhænger af den valgte nedbrydning).

Enhver morfisme i en abelsk gruppe tages med i signaturmorfismen. $\ mathfrak S_n$

Signaturen griber især ind i lineær algebra i formlen på Leibniz, som er en måde at definere determinanten for en kvadratmatrix på .

Definition af underskrift

I denne artikel definerer vi pariteten af en permutation ved at tælle dens inversioner (in) .

Definition Lad i < j være to heltal mellem 1 og n . Vi siger, at paret { i , j } er i inversion for

σ,

hvis

σ ( i )> σ ( j )

En permutation siges par, hvis den har et lige antal inversioner, ellers ulige . Den underskrift af et lige permutation er 1; den af en ulige permutation er –1.

Med andre ord, underskrift af en permutation $σ$ , betegnet i resten af denne artikel $ε ( σ )$ , kontrollerer, om vi betegne som $sgn$ den tegnet funktion :

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

. Eksempler

Overvej permutationen ${\ displaystyle \ sigma: = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 5 & 4 & 2 \ end {pmatrix}}}$ der løser 1 og 4 og sender 2 ud af 3, 3 ud af 5 og 5 ud af 2.
At tælle antallet af inversioner svarer til at tælle antallet af lidelser i anden linje. Der er fire af dem: 3 er før 2, 5 før 4, 5 før 2 og 4 før 2. Dette betyder, at parene dannet af deres fortilfælde ifølge definitionen er inversioner, det vil sige parene {2 , 5}, {3.4}, {3.5}, {4.5}.
Da der er fire, er $σ$ lige og $ε ( σ ) = 1$ .
Overvej k -cyklen ${\ 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 løser alle de andre heltal.
Dens omvendte par er { i , k }, for i < k .
Der er k - 1, så $ε ( σ ) = (-1) k -1$ , og $σ$ er lige, hvis og kun hvis k er ulige.

En formel til signaturen

En permutation har til underskrift: ${\ 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 sæt par af forskellige heltal mellem $1$ og $n$ . ${\ displaystyle {\ mathcal {P}} = \ {\ {i, \, j \} \ mid 1 \ leq i \ leq n {\ mbox {and}} 1 \ leq j \ leq n {\ mbox {and }} i \ neq {j} \}}$

Demonstration

Per definition,

{\ 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 nævneren ved hjælp af bijektiviteten af $σ$ :

{\ 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øjre | = \ prod _ {1 \ leq i <j \ leq n} {ji}}

Et produkts underskrift

Permutationerne kontrollerer en regel for tegn på produktet :

produktet af to jævne permutationer er jævnt;
produktet af to ulige permutationer er jævnt;
produktet af en jævn og en ulige permutation er ulige.

Ved hjælp af signaturen kommer det ned til formlen:

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

. Demonstration

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 \} \ i {\ 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}}. \ slut {justeret}}}

I den anden faktor i det sidste udtryk genkender vi direkte . ${\ displaystyle \ varepsilon (\ sigma _ {2})}$

For det første skal vi først reindexere (takket være ect 2 's bijektivitet ) ved at stille : ${\ 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 udtryk: underskriften er en morphism fra den symmetriske gruppe ind i to-element gruppe ({-1, 1}, ×). $\ mathfrak S_n$

Især enhver konjugatpermutation af σ har den samme signatur som σ (bil ). ${\ displaystyle \ varepsilon (\ rho \ sigma \ rho ^ {- 1}) = \ varepsilon (\ rho) \ varepsilon (\ sigma) \ varepsilon (\ rho) ^ {- 1} = \ varepsilon (\ sigma)}$

En gennemførelse er mærkelig

Signaturen på en k -cykel er $(-1) k -1$ . Især signaturen for en transponering (en 2-cyklus) er $-1$ .

Fra den sidste egenskab ovenfor og det faktum, at to cyklusser af samme længde er konjugeret , er det tilstrækkeligt at kontrollere det kun for en cyklus pr. Længde, hvilket blev udført i eksempel 2 ovenfor .

Beregning af en signatur

Ifølge de to foregående sektioner og nedbrydningen i et produkt af transpositioner kommer det, at enhver permutation er lige eller ulige med: $\ sigma$

$\ sigma$ er jævn (med andre ord :) hvis og kun hvis den kan nedbrydes til et lige antal transpositioner; ${\ displaystyle \ varepsilon (\ sigma) = + 1}$
$\ sigma$ er ulige (med andre ord :) hvis og kun hvis det kan nedbrydes til et ulige antal transpositioner. ${\ displaystyle \ varepsilon (\ sigma) = - 1}$

Dette gør det muligt at bestemme pariteten (eller signaturen) af en permutation mere effektivt end ved blot at tælle inversionerne; for en permutation af kræver en sådan nedbrydning højst $n$ $- 1$ operationer mod $n$ $($ $n$ $- 1) / 2,$ hvis definitionen anvendes direkte ( se ovenfor ). ${{\ mathfrak S}} _ {n}$

Eksempler

Den identitet af {1, ..., n } er endnu.
Den omvendte permutation af σ har den samme paritet som σ.
En cirkulær permutation er, selvom og kun hvis dens understøttelse indeholder et ulige antal elementer ( se ovenfor ).

Denne sidste observation gør det muligt at beregne signaturen for en permutation opdelt i cyklusser . Signaturen af en permutation er værd , hvor $m$ er antallet af cyklusser for nedbrydningen (tæller de faste punkter som cyklusser med længden 1) i og $p$ antallet af cykler af ens længde i denne samme nedbrydning. $\ sigma$ ${{\ mathfrak S}} _ {n}$ ${\ displaystyle (-1) ^ {nm} = (- 1) ^ {p}}$ $\ sigma$

Morfisme

${\ displaystyle {\ mathfrak {S}} _ {1}}$ er den trivielle gruppe , formoder . $n \ ge2$

I henhold til formlen for et produkt og impariteten ved transpositionerne er signaturen derefter en overvejende morfisme af in ({–1, 1}, ×), og dens kerne er den alternerende gruppe af lige permutationer. $\ mathfrak S_n$ ${\ displaystyle {\ mathfrak {A}} _ {n}}$

Denne undergruppe er den gruppe afledt fra , at signaturen er derfor en realisering af kanoniske morphism af i sin abelianized , den kvotient gruppe . Det betyder, at enhver morphism f af i en abelsk gruppe indregnes ved ε, eller igen: hvis billedet af f er ikke den triviel gruppe så er det en gruppe af orden 2 og f er sammenfaldende, via det unikke isomorfi mellem 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 demonstration

Dette bevis bruger ovenstående og nedbrydning af permutationer til et produkt af transpositioner .

Lad f være en ikke- triviel morfisme af i en abelsk gruppe G , betegnet med multiplikation. $\ mathfrak S_n$

Der er en sådan permutation , at og da den er et produkt af transpositioner, er der en sådan transponering . $\ sigma$ ${\ displaystyle f (\ sigma) \ neq 1}$ $\ sigma$ $\ tau _ {0}$ ${\ displaystyle \ lambda: = f (\ tau _ {0}) \ neq 1}$

Ræsonnementet, der er gjort ovenfor for ε , gælder også for f : alle transpositioner, der konjugeres , de har det samme billede af f . For enhver gennemførelse har vi derfor . $\ tau$ ${\ displaystyle f (\ tau) = f (\ tau _ {0}) = \ lambda}$

En hvilken som helst permutation , nedbrydes til i produkt af m gennemførelser, opfylder: . $\ sigma$ ${\ displaystyle \ tau _ {1} \ tau _ {2} \ dots \ tau _ {m}}$ ${\ displaystyle f (\ sigma) = f (\ tau _ {1}) f (\ tau _ {2}) \ dots f (\ tau _ {m}) = \ lambda ^ {m}}$

Især er af rækkefølge 2 fordi derfor . $\ lambda$ ${\ displaystyle \ mathrm {Id} = \ tau _ {0} ^ {2}}$ ${\ displaystyle \ lambda ^ {2} = f (\ mathrm {Id}) = 1}$

I henhold til pariteten m :

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

Se også