Podpis permutace
V matematice , je permutace z médií hotových se nazývá dvojice , pokud má sudý počet inverze , odd jinak. Podpis obměny je hodnota 1, pokud je to ještě, -1, pokud je liché.
Podpis mapování , ze symetrické skupiny do skupiny ({-1, 1}, x), je morfismus , to znamená, že splňuje vlastnost analogické k pravidlu znamení .
Sne{\ displaystyle {\ mathfrak {S}} _ {n}}
Jakákoli obměna se rozpadá na produkt transpozic. Transpozice, která je lichá , pochází z tohoto pravidla znaků , že parita počtu transpozic takového rozkladu se shoduje s paritou permutace (a proto nezávisí na zvoleném rozkladu).
Jakýkoli morfismus v abelianské skupině je zohledněn podpisovým morfismem.
Sne{\ displaystyle {\ mathfrak {S}} _ {n}}
Podpis zasahuje zejména do lineární algebry , do Leibnizova vzorce, což je způsob, jak definovat determinant čtvercové matice .
Definice podpisu
V tomto článku definujeme paritu permutace počítáním jejích inverzí (in) .
Definice
Nechť i < j jsou dvě
celá čísla mezi 1 a n . Říkáme, že
dvojice { i , j } je v inverzi pro
σ, pokud
σ ( i )> σ ( j ) .
Permutace se říká pár, pokud má sudý počet inverzí, jinak lichý . Podpis sudého permutace je 1; lichá permutace je –1.
Jinými slovy, podpis permutace σ , označený ve zbytku tohoto článku ε ( σ ) , ověří, zda označíme funkcí sgn funkci znaménka :
ε(σ)=∏1≤i<j≤nesgn(σ(j)-σ(i)){\ displaystyle \ varepsilon (\ sigma) = \ prod _ {1 \ leq já <j \ leq n} \ operatorname {sgn} (\ sigma (j) - \ sigma (i))}.
Příklady
- Zvažte permutaciσ: =(1234513542){\ displaystyle \ sigma: = {\ začátek {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 5 & 4 & 2 \ end {pmatrix}}}který opraví 1 a 4 a odešle 2 ze 3, 3 z 5 a 5 ze 2.
Počítání počtu inverzí se rovná počítání počtu poruch ve druhém řádku. Jsou čtyři: 3 je před 2, 5 před 4, 5 před 2 a 4 před 2. To znamená, že páry vytvořené z jejich předchůdců jsou podle definice inverze, to znamená páry {2 , 5}, {3.4}, {3.5}, {4.5}.
Jelikož existují čtyři, σ je sudé a ε ( σ ) = 1 .
- Zvažte k -cyklusσ: =(12...k-1kk+1...ne23...k1k+1...ne){\ 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}}}který pošle 1 na 2, 2 na 3,…, k - 1 na k , k na 1 a který opraví všechna ostatní celá čísla.
Jeho obrácené páry jsou { i , k }, pro i < k .
Existuje k - 1, takže ε ( σ ) = (–1) k –1 a σ je sudé právě tehdy, je-li k liché.
Vzorec pro podpis
Permutace má pro podpis:
σ∈Sne{\ displaystyle \ sigma \ in {\ mathfrak {S}} _ {n}}
ε(σ)=∏1≤i<j≤neσ(j)-σ(i)j-i=∏{i,j}∈Pσ(j)-σ(i)j-i{\ 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}}},
kde označuje množinu párů odlišných celých čísel mezi 1 a n .
P={{i,j}∣1≤i≤ne a 1≤j≤ne a i≠j}{\ displaystyle {\ mathcal {P}} = \ {\ {i, \, j \} \ střední 1 \ leq já \ leq n {\ mbox {a}} 1 \ leq j \ leq n {\ mbox {a }} i \ neq {j} \}}
Demonstrace
Podle definice,
ε(σ)=∏1≤i<j≤nesgn(σ(j)-σ(i))=∏1≤i<j≤neσ(j)-σ(i)|σ(j)-σ(i)|=∏1≤i<j≤ne(σ(j)-σ(i))∏1≤i<j≤ne|σ(j)-σ(i)|{\ displaystyle \ varepsilon (\ sigma) = \ prod _ {1 \ leq já <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) \ vpravo |}}}}a můžeme transformovat jmenovatele pomocí bijectivity z å :
∏1≤i<j≤ne|σ(j)-σ(i)|=∏{i,j}∈P|σ(j)-σ(i)|=∏{k,l}∈P|k-l|=∏1≤i<j≤nej-i{\ Displaystyle \ prod _ {1 \ leq i <j \ leq n} \ left | \ sigma (j) - \ sigma (i) \ right | = \ prod _ {\ {i, j \} \ v {\ mathcal {P}}} \ left | \ sigma (j) - \ sigma (i) \ right | = \ prod _ {\ {k, l \} \ in {\ mathcal {P}}} \ left | kl \ vpravo | = \ prod _ {1 \ leq i <j \ leq n} {ji}}.
Podpis produktu
Permutace kontrolují pravidlo značek pro produkt :
- součin dvou sudých permutací je sudý;
- součin dvou lichých permutací je sudý;
- součin sudé a liché permutace je lichý.
Pomocí podpisu jde o vzorec:
ε(σ1∘σ2)=ε(σ1)ε(σ2){\ displaystyle \ varepsilon (\ sigma _ {1} \ circ \ sigma _ {2}) = \ varepsilon (\ sigma _ {1}) \ varepsilon (\ sigma _ {2})}.
Demonstrace
Být . Takže ( viz výše ):
σ1,σ2∈Sne{\ displaystyle \ sigma _ {1}, \ sigma _ {2} \ in {\ mathfrak {S}} _ {n}}
ε(σ1∘σ2)=∏{i,j}∈P(σ1∘σ2)(j)-(σ1∘σ2)(i)j-i=∏{i,j}∈Pσ1(σ2(j))-σ1(σ2(i))σ2(j)-σ2(i)∏{i,j}∈Pσ2(j)-σ2(i)j-i.{\ displaystyle {\ begin {aligned} \ 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 \} \ v {\ mathcal {P}}} {\ frac {\ sigma _ {2} (j) - \ sigma _ {2} (i)} {ji}}. \ end {zarovnáno}}}Ve druhém faktoru posledního výrazu poznáváme přímo .
ε(σ2){\ displaystyle \ varepsilon (\ sigma _ {2})}
Pro první musíme nejprve reindexovat (díky bijektivitě σ 2 ) pózováním :
{k,l}={σ2(i),σ2(j)}{\ displaystyle \ {k, l \} = \ {\ sigma _ {2} (i), \ sigma _ {2} (j) \}}
∏{i,j}∈Pσ1(σ2(j))-σ1(σ2(i))σ2(j)-σ2(i)=∏{k,l}∈Pσ1(k)-σ1(l)k-l=ε(σ1){\ displaystyle \ prod _ {\ {i, j \} \ v {\ mathcal {P}}} {\ frac {\ sigma _ {1} (\ sigma _ {2} (j)) - \ sigma _ { 1} (\ sigma _ {2} (i))} {\ sigma _ {2} (j) - \ sigma _ {2} (i)}} = \ prod _ {\ {k, l \} \ v {\ mathcal {P}}} {\ frac {\ sigma _ {1} (k) - \ sigma _ {1} (l)} {kl}} = \ varepsilon (\ sigma _ {1})}.
V algebraických termínech: podpis je morfismus ze symetrické skupiny do skupiny dvou prvků ({–1, 1}, ×).
Sne{\ displaystyle {\ mathfrak {S}} _ {n}}
Zejména jakákoli konjugovaná permutace σ má stejný podpis jako σ (auto ).
ε(ρσρ-1)=ε(ρ)ε(σ)ε(ρ)-1=ε(σ){\ displaystyle \ varepsilon (\ rho \ sigma \ rho ^ {- 1}) = \ varepsilon (\ rho) \ varepsilon (\ sigma) \ varepsilon (\ rho) ^ {- 1} = \ varepsilon (\ sigma)}
Transpozice je zvláštní
Podpis k -cyklu je (–1) k –1 . Zejména podpis transpozice (2-cyklus) je –1 .
Z poslední výše uvedené vlastnosti a skutečnosti, že jsou konjugovány dva cykly stejné délky , stačí ji zkontrolovat pouze na jeden cyklus na délku, což bylo provedeno v příkladu 2 výše .
Výpočet podpisu
Podle dvou předcházejících sekcí a rozkladu na produkt transpozic přichází, že jakákoli permutace je sudá nebo lichá, s:
σ{\ displaystyle \ sigma}
-
σ{\ displaystyle \ sigma}je sudé (jinými slovy :) právě když je možné jej rozložit na sudý počet provedení;ε(σ)=+1{\ displaystyle \ varepsilon (\ sigma) = + 1}
-
σ{\ displaystyle \ sigma}je liché (jinými slovy :) právě když je možné jej rozložit na lichý počet transpozic.ε(σ)=-1{\ displaystyle \ varepsilon (\ sigma) = - 1}
To umožňuje určit paritu (nebo podpis) permutace efektivněji než pouhým počítáním inverzí; skutečně, pro permutaci , takový rozklad vyžaduje maximálně n - 1 operací, proti n ( n - 1) / 2, pokud je definice použita přímo ( viz výše ).
Sne{\ displaystyle {\ mathfrak {S}} _ {n}}
Příklady
Toto poslední pozorování umožňuje vypočítat podpis permutace rozdělené do cyklů . Podpis permutace z je hodnota , kde m je počet cyklů rozkladu (počítání pevných bodů jako cykly o délce 1) v a p počet cyklů i délky ve stejném rozkladu.
σ{\ displaystyle \ sigma}Sne{\ displaystyle {\ mathfrak {S}} _ {n}}(-1)ne-m=(-1)p{\ displaystyle (-1) ^ {nm} = (- 1) ^ {p}}σ{\ displaystyle \ sigma}
Morfismus
S1{\ displaystyle {\ mathfrak {S}} _ {1}}být triviální skupinou , předpokládejme .
ne≥2{\ displaystyle n \ geq 2}
Podle vzorce pro výrobek a disproporcí z transpozic , podpis je pak surjektivní morfismus o v ({-1, 1}, x), a jeho jádro je střídavý skupina sudých permutací.
Sne{\ displaystyle {\ mathfrak {S}} _ {n}} NAne{\ displaystyle {\ mathfrak {A}} _ {n}}
Tato podskupina bytí skupina odvozená od , podpis je tedy realizace kanonické morfismu z v jeho abelianized , na skupinu kvocient . To znamená, že jakýkoliv Morfizmus f ze v abelian skupiny zohledněn prostřednictvím e, nebo znovu: v případě, že obraz z f není triviální skupina pak je to skupina řádu 2 a f shoduje, přes unikátní izomorfismus mezi touto skupinou a ( {–1, 1}, ×), s ε.
NAne{\ displaystyle {\ mathfrak {A}} _ {n}}Sne{\ displaystyle {\ mathfrak {S}} _ {n}}Sne{\ displaystyle {\ mathfrak {S}} _ {n}} Sne/NAne≃({-1,1},×){\ displaystyle {\ mathfrak {S}} _ {n} / {\ mathfrak {A}} _ {n} \ simeq (\ {- 1,1 \}, \ krát)}Sne{\ displaystyle {\ mathfrak {S}} _ {n}}
Přímá ukázka
Tento důkaz používá výše uvedené a rozklad permutací na produkt transpozic .
Nechť f je nediskriminačním triviální morfismus z v abelian skupině G , označené násobení.
Sne{\ displaystyle {\ mathfrak {S}} _ {n}}
Existuje permutace taková, že , a protože je produktem transpozice, zde se o transpozici taková, že .
σ{\ 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}
Zdůvodnění provedené výše pro ε platí také pro f : všechny konjugované transpozice , mají stejný obraz pomocí f . Pro jakoukoli transpozici tedy máme .
τ{\ displaystyle \ tau}F(τ)=F(τ0)=λ{\ displaystyle f (\ tau) = f (\ tau _ {0}) = \ lambda}
Proto by jakákoli permutace , rozkládající se do v produktu z m transpozice, splňuje: .
σ{\ displaystyle \ sigma}τ1τ2...τm{\ displaystyle \ tau _ {1} \ tau _ {2} \ tečky \ tau _ {m}}F(σ)=F(τ1)F(τ2)...F(τm)=λm{\ displaystyle f (\ sigma) = f (\ tau _ {1}) f (\ tau _ {2}) \ tečky f (\ tau _ {m}) = \ lambda ^ {m}}
Zejména je řádu 2, protože proto .
λ{\ displaystyle \ lambda}Jád=τ02{\ displaystyle \ mathrm {Id} = \ tau _ {0} ^ {2}}λ2=F(Jád)=1{\ displaystyle \ lambda ^ {2} = f (\ mathrm {Id}) = 1}
Podle parity m tedy :
F(σ)=λm={λ-li ε(σ)=-11-li ε(σ)=1.{\ displaystyle f (\ sigma) = \ lambda ^ {m} = {\ začít {případy} \ lambda & {\ text {si}} \ varepsilon (\ sigma) = - 1 \\ 1 & {\ text {si }} \ varepsilon (\ sigma) = 1. \ end {případy}}}
Podívejte se také
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">