Matematick´y ustav ´ Slezske´ univerzity v Opaveˇ Uˇcebn´ı texty k pˇrednaˇ ´ sce ALGEBRA I, zimní semestr 2000/2001 Michal Marvan
4. Permutace Definice. Bud’ M koneˇcn´a mnoˇzina. Bijekce M → M se naz´yv´a permutace na mnoˇzinˇe M. Je-li p : M → M permutace a je-li m ∈ M libovoln´y prvek, pak obraz p(m) prvku m obvykle znaˇc´ıme pm . Pˇr´ıklad. V kr´al´ık´arnˇe o cˇ tyˇrech kotc´ıch zˇ ij´ı cˇ tyˇri kr´al´ıci, po jednom v kaˇzd´em kotci. Majitel v p´atek pˇrestˇehoval kr´al´ıky z horn´ıho patra do spodn´ıho a naopak: p=
✻ ✻ ❄ ❄
Bud’ M cˇ tyˇrprvkov´a mnoˇzina kotc˚u. Stˇehov´an´ı kr´al´ık˚u je permutace na M pr´avˇe tehdy, kdyˇz po nˇem nebudou v zˇ a´ dn´em kotci dva kr´al´ıci (injektivita) a zˇ a´ dn´y kotec nez˚ustane pr´azdn´y (surjektivita).
Oznaˇcme S(M) mnoˇzinu vˇsech permutac´ı na mnoˇzinˇe M. Jsou-li p, s : M → M dvˇe permutace, pak jejich sloˇzen´ı je permutace s ◦ p : M → M dan´a zn´amou formul´ı (s ◦ p)(m) = s( p(m)). Sloˇzen´ı permutac´ı je opˇet permutace, protoˇze sloˇzen´ı bijekc´ı je bijekce. Na mnoˇzinˇe S(M) tak vznik´a asociativn´ı bin´arn´ı operace S(M) × S(M) → S(M) skl´ad´an´ı permutac´ı. Pˇr´ıklad. Majitel kr´al´ık´arny z pˇredchoz´ıho pˇr´ıkladu v sobotu opˇet stˇehoval kr´al´ıky: s=
✒ ✠
(dva kr´al´ıci z˚ustali na m´ıstˇe). Ovˇeˇrte, zˇ e s◦p=
✲ ✻ ✛ ❄
Permutace s ◦ p vyjadˇruje rozm´ıstˇen´ı kr´al´ık˚u v sobotu ve srovn´an´ı s rozm´ıstˇen´ım kr´al´ık˚u ve cˇ tvrtek.
Mnoˇzina S(M) je grupa vzhledem k bin´arn´ı operaci ,,◦“. Jednotkov´ym prvkem je identick´e zobrazen´ı id M : M → M. Inverzn´ı prvky jsou inverzn´ı zobrazen´ı. (Ovˇerˇte jako cviˇcen´ı.) Pro zjednoduˇsen´ı dalˇs´ıch u´ vah zvolme pevnou mnoˇzinu o n prvc´ıch, In = { 1, . . . , n } ⊂ N. Mnoˇzinu vˇsech permutac´ı na mnoˇzinˇe In oznaˇcme prostˇe Sn . Prvky libovoln´e n-prvkov´e mnoˇziny M m˚uzˇ eme oznaˇcit indexy 1, . . . , n, takˇze M = { m 1 , . . . , m n }. M´ısto o permutaci prvk˚u m i mnoˇziny M pak m˚uzˇ eme uvaˇzovat o permutaci odpov´ıdaj´ıc´ıch index˚u i, tj. o permutaci na mnoˇzinˇe In = { 1, . . . , n }. Pˇrechod k mnoˇzinˇe In proto nen´ı na u´ kor obecnosti.
4. Permutace
Permutaci t : In → In m˚uzˇ eme zapsat r˚uzn´ymi zp˚usoby. Bˇezˇ nˇe ji zapisujeme
1 2 ··· n t1 t2 · · · tn
[anebo, pro jednoduchost, jen (t1 , t2 , . . . , tn ), protoˇze prvn´ı ˇra´ dek (1, 2, . . . , n) je vˇzdy stejn´y]. M˚uzˇ eme tak´e kreslit n´azorn´e diagramy, napˇr´ıklad tak, zˇ e se mnoˇzina In zobraz´ı dvakr´at vedle sebe a vedou se spojnice mezi prvky i a ti (viz n´asleduj´ıc´ı pˇr´ıklad). Pˇr´ıklad. Oˇc´ıslujme kotce: 1 2 3 4 Permutace p, s a s ◦ p z pˇredchoz´ıho pˇr´ıkladu jsou po ˇradˇe p=
1 3
2 4
3 1
4 , 2
s=
1 1
2 3
4 , 4
3 2
s◦p=
1 2
2 4
3 1
4 . 3
Tot´ezˇ vyj´adˇreno diagramy: 1❜ ✧ ✧ 2 ❜❜ ✧❜ ✧ ✧ ❜ ✧ 3 ❜ ✧❜ ❜ ✧ 4 p
1 2 3 4
1 ✏ 2 PP ✏✏ P 3✏ P 4 s
1 PP ✧ ✧ P 2 ❜✧P ✧ 3 ❜✏ ✏ ✏❜ 4✏ ❜ s◦p
1 2 3 4
1 2 3 4
Pˇri nav´az´an´ı diagram˚u je n´azornˇe vidˇet, jak se permutace skl´adaj´ı: 1❜ ✧ ✧ 2 ❜❜ ✧❜ ✧ ✧ ❜ ✧ ❜ 3 ✧❜ ❜ ✧ 4 p
1 1 ✏ 2 P✏ ✏ P P 2 3 3 ✏ P 4 4 s
=
1 PP ✧ P P 2 ❜✧✧ 3 ✧❜❜ ✏ ✏✏ 4✏ ❜ s◦p
1 2 3 4
Definice. Bud’ t permutace na mnoˇzinˇe In = { 1, . . . , n }. Necht’ i, j ∈ In , pˇriˇcemˇz i < j a z´aroveˇn ti > t j . Pak ˇrekneme, zˇ e p´ar (ti , t j ) tvoˇr´ı inverzi. Poˇcet inverz´ı (tj. p´ar˚u ti > t j kde i < j) oznaˇc´ıme inv t. Dost´av´ame zobrazen´ı inv : Sn → N ∪ { 0 }. Pˇr´ıklad. Vyjmenujme inverze v pˇredchoz´ım pˇr´ıkladu: p : (3, 1), (3, 2), (4, 1), (4, 2),
inv s = 4;
s : (3, 2),
inv p = 1;
s ◦ p : (2, 1), (4, 1), (4, 3),
inv(s ◦ p) = 3.
Poˇcty inverz´ı lze tak´e snadno urˇcit z diagram˚u jako poˇcty pr˚useˇc´ık˚u cˇ ar.
2
4. Permutace
Obecnˇe plat´ı: inv(s ◦ p) = inv s + inv p − sud´e cˇ´ıslo: Tvrzen´ı. Bud’te p, q permutace na mnoˇzinˇe In . Pak existuje cel´e cˇ´ıslo k takov´e, zˇe plat´ı inv(q ◦ p) = inv q + inv p + 2k. Dukaz. ˚ Pro kaˇzdou dvouprvkovou podmnoˇzinu { i, j } ⊆ In oznaˇcme i menˇs´ı z obou prvk˚u, takˇze i < j. Vˇzdy nastane pr´avˇe jeden ze cˇ tyˇr pˇr´ıpad˚u: (i)
p(i) < p( j),
q( p(i)) < q( p( j)) :
i j
p( i) p( j)
q( p( i)) q( p( j))
(ii)
p(i) > p( j),
q( p(i)) > q( p( j)) :
i PP✏✏ p( j) ✏PP j✏ p( i)
q( p( j)) q( p( i))
(iii)
p(i) < p( j),
q( p(i)) > q( p( j)) :
i j
(iv)
p(i) > p( j),
q( p(i)) < q( p( j)) :
i PP✏✏ p( j) PP✏✏ q( p( i)) ✏PP ✏PP j✏ p( i) ✏ q( p( j))
p( i) PP✏✏ q( p( j)) ✏PP p( j) ✏ q( p( i))
Oznaˇcme po ˇradˇe N(i) , N(ii) , N(iii) , N(iv) poˇcet v´yskyt˚u dvojice { i, j } ⊆ In uveden´eho druhu. P´ar { i, j } pˇrisp´ıv´a jednou inverz´ı k inv p v pˇr´ıpadech (ii) a (iv), protoˇze pr´avˇe v tˇechto pˇr´ıpadech jdou p( j), p(i) v opaˇcn´em poˇrad´ı neˇz i, j. Proto plat´ı inv p = N(ii) + N(iv) . Podobnˇe p´ar { i, j } pˇrisp´ıv´a jednou inverz´ı k inv q v pˇr´ıpadech (iii) a (iv), protoˇze pr´avˇe v tˇechto pˇr´ıpadech jdou q( p(i), q( p( j)) v opaˇcn´em poˇrad´ı neˇz p(i), p( j): inv q = N(iii) + N(iv) . A koneˇcnˇe { i, j } pˇrisp´ıv´a jednou inverz´ı k inv(q ◦ p) v pˇr´ıpadech (ii) a (iii), protoˇze pr´avˇe v tˇechto pˇr´ıpadech jdou q( p(i), q( p( j)) v opaˇcn´em poˇrad´ı neˇz i, j: inv(q ◦ p) = N(ii) + N(iii) . Pak
inv(q ◦ p) = N(ii) + N(iii) = (N(ii) + N(iv) ) + (N(iii) + N(iv) ) − 2N(iv) = inv p + inv q − 2N(iv) .
Vid´ıme, zˇ e tvrzen´ı plat´ı, pˇriˇcemˇz k = −N(iv) ∈ Z. Definice. Definujme signum (znam´enko) permutace s ∈ Sn pˇredpisem sgn s = (−1)inv s . Vid´ıme, zˇ e sgn je zobrazen´ı Sn → { −1, 1 }. Pro signum sloˇzen´e permutace odvod´ıme vztah, kter´y jiˇz neobsahuje neurˇcit´e sud´e cˇ´ıslo 2k: 3
4. Permutace
Tvrzen´ı. Pro libovoln´e permutace p, q ∈ Sn plat´ı sgn(q ◦ p) = sgn q · sgn p. Dukaz. ˚ sgn(q ◦ p) = (−1)inv(q◦ p) = (−1)inv q inv q (−1) · (−1)inv p = sgn q · sgn p.
+ inv p + 2k
= (−1)inv q · (−1)inv p · (−1)2k =
T´ım je ovˇeˇreno, zˇ e sgn je homomorfismus pologrup, ale kaˇzd´y pologrupov´y homomorfismus mezi grupami je homomorfismus grup. Tud´ızˇ , sgn je homomorfismus grup (Sn , ◦, id,−1 ) → ({ −1, 1 }, · , 1,−1 ). Zbavit se neurˇcit´eho sˇc´ıtance 2k m˚uzˇ eme i tak, zˇ e pˇrejdeme ke sˇc´ıt´an´ı v poli Z2 . Tvrzen´ı. Pro libovoln´a k, l ∈ Z plat´ı [k + l]2 = [k]2 + [l]2 (sˇc´ıt´an´ı vpravo je v Z2 ). Dukaz. ˚ Cviˇcen´ı. Definice. Bud’ s : In → In permutace. Prvek |s| = [inv s]2
∈ Z2
se naz´yv´a parita permutace s. Tvrzen´ı. Bud’te p, q permutace na mnoˇzinˇe In . Pak (1) |q ◦ p| = |q| + | p| v Z2 . (2) |id| = 0 v Z2 . (3) |q −1 | = |q| v Z2 . Dukaz. ˚ Cviˇcen´ı. N´avod: viz analogick´e formule pro sgn. Mezi paritou a signem je jednoznaˇcn´y vztah, kter´y v´ystiˇznˇe zapisujeme sgn s = (−1)|s| . Parita 0 se naz´yv´a ,,sud´a,“ parita 1 se naz´yv´a ,,lich´a.“ Vrat’me se k permutac´ım na obecn´e mnoˇzinˇe M. Poˇcet inverz´ı a tedy i signum a paritu takov´e permutace stanov´ıme tak, zˇ e oˇc´ıslujeme prvky v M a stanov´ıme paritu odpov´ıdaj´ıc´ı permutace na mnoˇzinˇe In . Vznik´a ovˇsem ot´azka, zda potom parita nez´avis´ı na volbˇe oˇc´ıslov´an´ı. Pˇr´ıklad. V naˇsem pˇr´ıkladu s kr´al´ıky m˚uzˇ eme prvky mnoˇziny M (kotce) oˇc´ıslovat i jinak, napˇr´ıklad 1 3 2 4 P´ateˇcn´ı permutace p potom m´a jen dvˇe inverze 4 PP✏ ✏ ✏ P 3✏ P 2 PP✏ ✏ ✏ P 1✏ P
4 3 2 1
oproti cˇ tyˇrem v p˚uvodn´ım oˇc´ıslov´an´ı. Parita ovˇsem z˚ust´av´a sud´a.
4
4. Permutace
Tvrzen´ı. Parita a signum permutace s ∈ S(M) nez´avis´ı na oˇc´ıslov´an´ı prvk˚u mnoˇziny M. Dukaz. ˚ Oˇc´ıslov´an´ı prvk˚u mnoˇziny M je vlastnˇe bijekce u
In −→ M,
i → u i ∈ M,
takov´a, zˇ e M = { u 1 , u 2 , . . . , u n }. Bud’ s permutace na mnoˇzinˇe M. Bud’ s u ∈ Sn permutace, kter´a pˇri oˇc´ıslov´an´ı u odpov´ıd´a permutaci s. M´ame s u = u −1 ◦ s ◦ u :
u
u −1
s
In −→ M −→ M −→ In .
[Vskutku, prvek s cˇ´ıslem i se pˇri permutaci u zobraz´ı na prvek s cˇ´ıslem s u (i). To ale znamen´a, zˇ e u(s u (i)) = s(u(i)) pro kaˇzd´e cˇ´ıslo i ∈ In , a tedy u ◦ s u = s ◦ u; odtud s u = u −1 ◦ s ◦ u.] Parita permutace s : M → M v oˇc´ıslov´an´ı u pak je |s u | = |u −1 ◦s ◦u|, parita t´ezˇ e permutace v jin´em oˇc´ıslov´an´ı v : In → M je |s v | = |v −1 ◦ s ◦ v|. Snadno najdeme vztah mezi s v a s u : s v = v −1 ◦ s ◦ v = v −1 ◦ u ◦ u −1 ◦ s ◦ u ◦ u −1 ◦ v = v −1 ◦ u ◦ s u ◦ u −1 ◦ v = (v −1 ◦ u) ◦ s u ◦ (v −1 ◦ u)−1 . Pˇritom zobrazen´ı v −1 ◦ u : In → In je bijekce, a tedy permutace na In , a proto m˚uzˇ eme pouˇz´ıt zn´am´y vztah | p ◦ q| = | p| + |q|. Dostaneme |s v | = |v −1 ◦ u| + |s u | + |(v −1 ◦ u)−1 | = |v −1 ◦ u| + |s u | + |v −1 ◦ u| = |s u |, coˇz se mˇelo dok´azat. Nejjednoduˇssˇ´ı netrivi´aln´ı permutace jsou transpozice. Definice. Transpozice je permutace, pˇri n´ızˇ se vymˇen´ı dva prvky a ostatn´ı z˚ustanou na m´ıstˇe. Cviˇcen´ı. Ukaˇzte, zˇ e libovoln´a transpozice m´a lichou paritu. Probl´em k rˇ eˇsen´ı. Ukaˇzte, zˇ e libovoln´a permutace je sloˇzen´ım koneˇcn´eho poˇctu transpozic; pˇritom sud´a (lich´a) permutace je sloˇzen´ım sud´eho (lich´eho) poˇctu transpozic.
Parity permutac´ı se pouˇz´ıv´a pˇri nˇekter´ych d˚ukazech neexistence cˇ i nemoˇznosti. Cviˇcen´ı. V tabulce o 4×4 pol´ıcˇ k´ach se pohybuje 15 kostek a jedna d´ıra. Je dovoleno pˇresunout kostku na m´ısto d´ıry, pokud s n´ı soused´ı. Ukaˇzte, zˇ e z poˇca´ teˇcn´ıho rozestaven´ı Z nelze doj´ıt k rozestaven´ı K , je-li
Z=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
K =
5
1
2
3
4
5
6
7
8
9
10
11
12
13
15
14
4. Permutace
N´avod: 1) Jednotliv´e pozice v tabulce oznaˇcujme dvojicemi (i, j), i = 1, . . . , 4, j = 1, . . . , 4. Bud’ M = { 1, 2, 3, 4 } × { 1, 2, 3, 4 } mnoˇzina vˇsech pozic. Pˇresouv´an´ım kostek vytv´aˇr´ıme permutace na mnoˇzinˇe M. Rozestaven´ı Z povaˇzujme za identickou permutaci. Dokaˇzte, zˇ e kaˇzd´y tah ve shodˇe s pravidly je transpozic´ı. 2) Zaved’me zobrazen´ı d : S(M) → { 0, 1 } pˇredpisem: Je-li pˇri permutaci s d´ıra na pozici (i, j) ∈ M, pak d(s) = [i + j]2 . Dokaˇzte, zˇ e pro kaˇzdou permutaci s dosaˇzenou ve shodˇe s pravidly plat´ı |s| = d(s) [pˇredpokl´ad´ame, zˇ e d´ıra p˚uvodnˇe stoj´ı na pozici (4, 4), takˇze d(id) = 0]. 3) Nakonec ukaˇzte, zˇ e |K | = d(K ). Cviˇcen´ı. Z pohledu matematika, Rubikova kostka sest´av´a z 20 krychliˇcek, rozloˇzen´ych ve vrcholech krychle (8 vrcholov´ych krychliˇcek) a ve stˇredech hran krychle (12 hranov´ych krychliˇcek). Je dovoleno ot´acˇ et jednotliv´ymi stˇenami krychle. Ukaˇzte, zˇ e pˇri dovolen´e manipulaci s Rubikovou kostkou nelze vymˇenit mezi sebou dva vrcholy tak, aby vˇsechny ostatn´ı krychliˇcky z˚ustaly na m´ıstˇe. (K obarven´ı nepˇrihl´ızˇ´ıme.) N´avod: Jelikoˇz se pˇri manipulaci s kostkou nem´ıs´ı vrcholov´e a hranov´e krychliˇcky, jde o souˇcasnˇe prov´adˇen´e permutace na mnoˇzinˇe V vrcholov´ych krychliˇcek a na mnoˇzinˇe H hranov´ych krychliˇcek. Ukaˇzte, zˇ e otoˇcen´ı jednou stˇenou je permutace lich´e parity jak na V , tak na H . Ukaˇzte, zˇ e bˇehem dovolen´e manipulace s kostkou jsou parita permutace na V a parita permutace na H st´ale stejn´e. Cviˇcen´ı. (a) Ukaˇzte, zˇ e na n-prvkov´e mnoˇzinˇe je n! permutac´ı. (b) Je-li n > 1, pak pr´avˇe polovina z nich je sud´ych a polovina je lich´ych. Dokaˇzte. N´avod: (a) Indukc´ı vzhledem k n. (b) Sloˇzen´ı s libovolnou pevnˇe zvolenou transpozic´ı d´av´a bijekci mezi mnoˇzinou sud´ych a mnoˇzinou lich´ych permutac´ı.
6
