Semnătura unei permutări
În matematică , o permutare a mediilor terminate se numește pereche dacă are un număr par de inversiuni , impare altfel. Semnătura unui permutare este în valoare de 1 dacă este chiar, -1 dacă este ciudat.
Semnătură mapare , din grupul simetric în grupul ({-1, 1}, x), este un morfism , adică, se constată că o proprietate analoage regula semn .
Snu{\ displaystyle {\ mathfrak {S}} _ {n}}
Orice permutare se descompune într-un produs al transpunerilor. O transpunere fiind ciudată , provine din această regulă a semnelor că paritatea numărului de transpuneri ale unei astfel de descompuneri coincide cu paritatea permutării (și, prin urmare, nu depinde de descompunerea aleasă).
Orice morfism dintr- un grup abelian este luat în considerare de morfismul de semnătură.
Snu{\ displaystyle {\ mathfrak {S}} _ {n}}
Semnătura intervine în special în algebra liniară , în formula lui Leibniz care este un mod de a defini determinantul unei matrice pătrate .
Definiția signature
În acest articol, definim paritatea unei permutări prin numărarea inversiunilor sale (în) .
Definiție
Fie i < j două
numere întregi între 1 și n . Spunem că
perechea { i , j } este în inversiune pentru
σ dacă
σ ( i )> σ ( j ) .
O permutare se spune pereche dacă are un număr par de inversiuni, impare altfel. Semnătura unui permutare chiar este 1; cea a unei permutări ciudate este –1.
Cu alte cuvinte, semnătura unui permutare σ , notat în restul acestui articol ε ( σ ) , verifică dacă notăm cu SGN funcția de conectare :
ε(σ)=∏1≤eu<j≤nusgn(σ(j)-σ(eu)){\ displaystyle \ varepsilon (\ sigma) = \ prod _ {1 \ leq i <j \ leq n} \ operatorname {sgn} (\ sigma (j) - \ sigma (i))}.
Exemple
- Luați în considerare permutațiaσ: =(1234513542){\ displaystyle \ sigma: = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 5 & 4 & 2 \ end {pmatrix}}}care fixează 1 și 4 și trimite 2 din 3, 3 din 5 și 5 din 2.
Numărarea numărului de inversiuni echivalează cu numărarea numărului de tulburări din a doua linie. Există patru dintre ele: 3 este înainte de 2, 5 înainte de 4, 5 înainte de 2 și 4 înainte de 2. Aceasta înseamnă că perechile formate din antecedentele lor sunt, conform definiției, inversiuni, adică perechile {2 , 5}, {3.4}, {3.5}, {4.5}.
Deoarece sunt patru, σ este egal și ε ( σ ) = 1 .
- Luați în considerare ciclul kσ: =(12...k-1kk+1...nu23...k1k+1...nu){\ displaystyle \ sigma: = {\ begin {pmatrix} 1 & 2 & \ dots & k-1 & k & k + 1 & \ dots & n \\ 2 & 3 & \ dots & k & 1 & k + 1 & \ dots & n \ end {pmatrix}}}care trimite 1 pe 2, 2 pe 3, ..., k - 1 pe k , k pe 1 și care fixează toate celelalte numere întregi.
Perechile sale inversate sunt { i , k }, pentru i < k .
Există k - 1 deci ε ( σ ) = (–1) k –1 , iar σ este chiar dacă și numai dacă k este impar.
O formulă pentru semnătură
O permutare are pentru semnătură:
σ∈Snu{\ displaystyle \ sigma \ in {\ mathfrak {S}} _ {n}}
ε(σ)=∏1≤eu<j≤nuσ(j)-σ(eu)j-eu=∏{eu,j}∈Pσ(j)-σ(eu)j-eu{\ displaystyle \ varepsilon (\ sigma) = \ prod _ {1 \ leq i <j \ leq n} {\ frac {\ sigma (j) - \ sigma (i)} {ji}} = \ prod _ {\ {i, j \} \ in {\ mathcal {P}}} {\ frac {\ sigma (j) - \ sigma (i)} {ji}}},
unde denotă mulțimea de perechi de numere întregi distincte între 1 și n .
P={{eu,j}∣1≤eu≤nu și 1≤j≤nu și eu≠j}{\ displaystyle {\ mathcal {P}} = \ {\ {i, \, j \} \ mid 1 \ leq i \ leq n {\ mbox {and}} 1 \ leq j \ leq n {\ mbox {și }} i \ neq {j} \}}
Demonstrație
Prin definitie,
ε(σ)=∏1≤eu<j≤nusgn(σ(j)-σ(eu))=∏1≤eu<j≤nuσ(j)-σ(eu)|σ(j)-σ(eu)|=∏1≤eu<j≤nu(σ(j)-σ(eu))∏1≤eu<j≤nu|σ(j)-σ(eu)|{\ 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 |}}}}și putem transforma numitorul folosind bijectivitatea lui σ :
∏1≤eu<j≤nu|σ(j)-σ(eu)|=∏{eu,j}∈P|σ(j)-σ(eu)|=∏{k,l}∈P|k-l|=∏1≤eu<j≤nuj-eu{\ 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 \ dreapta | = \ prod _ {1 \ leq i <j \ leq n} {ji}}.
Semnătura unui produs
Permutările verifică o regulă de semne pentru produs :
- produsul a două permutări uniforme este egal;
- produsul a două permutări ciudate este par;
- produsul unei permutări pare și impare este impar.
Folosind semnătura, se reduce la formula:
ε(σ1∘σ2)=ε(σ1)ε(σ2){\ displaystyle \ varepsilon (\ sigma _ {1} \ circ \ sigma _ {2}) = \ varepsilon (\ sigma _ {1}) \ varepsilon (\ sigma _ {2})}.
Demonstrație
Fii . Deci ( vezi mai sus ):
σ1,σ2∈Snu{\ displaystyle \ sigma _ {1}, \ sigma _ {2} \ in {\ mathfrak {S}} _ {n}}
ε(σ1∘σ2)=∏{eu,j}∈P(σ1∘σ2)(j)-(σ1∘σ2)(eu)j-eu=∏{eu,j}∈Pσ1(σ2(j))-σ1(σ2(eu))σ2(j)-σ2(eu)∏{eu,j}∈Pσ2(j)-σ2(eu)j-eu.{\ 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 \} \ in {\ mathcal {P}}} {\ frac {\ sigma _ {1} (\ sigma _ {2} (j)) - \ sigma _ {1 } (\ sigma _ {2} (i))} {\ sigma _ {2} (j) - \ sigma _ {2} (i)}} \ prod _ {\ {i, j \} \ in {\ mathcal {P}}} {\ frac {\ sigma _ {2} (j) - \ sigma _ {2} (i)} {ji}}. \ end {align}}}În al doilea factor al ultimei expresii, recunoaștem direct .
ε(σ2){\ displaystyle \ varepsilon (\ sigma _ {2})}
Pentru prima, trebuie mai întâi să ne reindexăm (datorită bijectivității lui σ 2 ) prin a prezenta :
{k,l}={σ2(eu),σ2(j)}{\ displaystyle \ {k, l \} = \ {\ sigma _ {2} (i), \ sigma _ {2} (j) \}}
∏{eu,j}∈Pσ1(σ2(j))-σ1(σ2(eu))σ2(j)-σ2(eu)=∏{k,l}∈Pσ1(k)-σ1(l)k-l=ε(σ1){\ displaystyle \ prod _ {\ {i, j \} \ in {\ 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})}.
În termeni algebrici: semnătura este un morfism din grupul simetric în grupul cu doi elemente ({–1, 1}, ×).
Snu{\ displaystyle {\ mathfrak {S}} _ {n}}
În special, orice permutare conjugată a lui σ are aceeași semnătură ca σ (car ).
ε(ρσρ-1)=ε(ρ)ε(σ)ε(ρ)-1=ε(σ){\ displaystyle \ varepsilon (\ rho \ sigma \ rho ^ {- 1}) = \ varepsilon (\ rho) \ varepsilon (\ sigma) \ varepsilon (\ rho) ^ {- 1} = \ varepsilon (\ sigma)}
O transpunere este ciudată
Semnătura unui k- ciclu este (–1) k –1 . În special, semnătura unei transpuneri (un 2-ciclu) este –1 .
Din ultima proprietate de mai sus și din faptul că două cicluri de aceeași lungime sunt conjugate , este suficient să o verificăm pentru un singur ciclu pe lungime, ceea ce a fost făcut în exemplul 2 de mai sus .
Calculul unei semnături
Conform celor două secțiuni precedente și descompunerii în produs a transpunerilor , se pare că orice permutare este fie pară, fie impară, cu:
σ{\ displaystyle \ sigma}
-
σ{\ displaystyle \ sigma}este par (cu alte cuvinte :) dacă și numai dacă poate fi descompus într-un număr par de transpuneri;ε(σ)=+1{\ displaystyle \ varepsilon (\ sigma) = + 1}
-
σ{\ displaystyle \ sigma}este impar (cu alte cuvinte :) dacă și numai dacă poate fi descompus într-un număr impar de transpuneri.ε(σ)=-1{\ displaystyle \ varepsilon (\ sigma) = - 1}
Acest lucru face posibilă determinarea parității (sau semnăturii) unei permutări mai eficient decât prin simpla numărare a inversiunilor; într-adevăr, pentru o permutare a , o astfel de descompunere necesită cel mult n - 1 operații, față de n ( n - 1) / 2 dacă definiția este aplicată direct (a se vedea mai sus ).
Snu{\ displaystyle {\ mathfrak {S}} _ {n}}
Exemple
Această ultimă observație face posibilă calcularea semnăturii unei permutări defalcate în cicluri . Semnătura unei permutări de merită , unde m este numărul de cicluri de descompunere (numărând punctele fixe ca cicluri de lungime 1) în și p numărul de cicluri de lungime pare în aceeași descompunere.
σ{\ displaystyle \ sigma}Snu{\ displaystyle {\ mathfrak {S}} _ {n}}(-1)nu-m=(-1)p{\ displaystyle (-1) ^ {nm} = (- 1) ^ {p}}σ{\ displaystyle \ sigma}
Morfism
S1{\ displaystyle {\ mathfrak {S}} _ {1}}fiind grupul banal , să presupunem .
nu≥2{\ displaystyle n \ geq 2}
Conform formulei unui produs și a impariității transpunerilor , semnătura este apoi un morfism surjectiv de in ({–1, 1}, ×), iar nucleul său este grupul alternativ de permutări uniforme.
Snu{\ displaystyle {\ mathfrak {S}} _ {n}} LAnu{\ displaystyle {\ mathfrak {A}} _ {n}}
Acest subgrup fiind grupul derivat din , semnătura este, prin urmare, o realizare a morfismului canonic din grupul său abelianizat , coeficient . Aceasta înseamnă că orice morfism f al unui grup abelian este luat în considerare de ε, sau din nou: dacă imaginea lui f nu este grupul trivial, atunci este un grup de ordinul 2 și f coincide, prin izomorfismul unic dintre acest grup și ( {–1, 1}, ×), cu ε.
LAnu{\ displaystyle {\ mathfrak {A}} _ {n}}Snu{\ displaystyle {\ mathfrak {S}} _ {n}}Snu{\ displaystyle {\ mathfrak {S}} _ {n}} Snu/LAnu≃({-1,1},×){\ displaystyle {\ mathfrak {S}} _ {n} / {\ mathfrak {A}} _ {n} \ simeq (\ {- 1,1 \}, \ times)}Snu{\ displaystyle {\ mathfrak {S}} _ {n}}
Demonstrație directă
Această dovadă folosește cele de mai sus și descompunerea permutărilor într-un produs al transpunerilor .
Fie f un morfism non- banal al unui grup abelian G , notat prin multiplicare.
Snu{\ displaystyle {\ mathfrak {S}} _ {n}}
Există o permutare astfel încât , și întrucât este un produs al transpunerilor, există o transpunere astfel încât .
σ{\ displaystyle \ sigma}f(σ)≠1{\ displaystyle f (\ sigma) \ neq 1}σ{\ displaystyle \ sigma}τ0{\ displaystyle \ tau _ {0}}λ: =f(τ0)≠1{\ displaystyle \ lambda: = f (\ tau _ {0}) \ neq 1}
Raționamentul făcut mai sus pentru ε se aplică și pentru f : toate transpunerile fiind conjugate , au aceeași imagine prin f . Prin urmare, pentru orice transpunere avem .
τ{\ displaystyle \ tau}f(τ)=f(τ0)=λ{\ displaystyle f (\ tau) = f (\ tau _ {0}) = \ lambda}
Astfel, orice permutare , se descompune într - în produs de m transpoziții, satisface: .
σ{\ displaystyle \ sigma}τ1τ2...τm{\ displaystyle \ tau _ {1} \ tau _ {2} \ dots \ tau _ {m}}f(σ)=f(τ1)f(τ2)...f(τm)=λm{\ displaystyle f (\ sigma) = f (\ tau _ {1}) f (\ tau _ {2}) \ dots f (\ tau _ {m}) = \ lambda ^ {m}}
În special, este de ordinul 2, deoarece, prin urmare .
λ{\ displaystyle \ lambda}Eud=τ02{\ displaystyle \ mathrm {Id} = \ tau _ {0} ^ {2}}λ2=f(Eud)=1{\ displaystyle \ lambda ^ {2} = f (\ mathrm {Id}) = 1}
Astfel, conform parității lui m :
f(σ)=λm={λdacă ε(σ)=-11dacă ε(σ)=1.{\ displaystyle f (\ sigma) = \ lambda ^ {m} = {\ begin {cases} \ lambda & {\ text {si}} \ varepsilon (\ sigma) = - 1 \\ 1 & {\ text {si }} \ varepsilon (\ sigma) = 1. \ end {cases}}}
Vezi și tu
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">