KEITINIAI. SIMETRINĖ GRUPĖ S_{n}. Paskaitos konspektas

Tegu V = {v_{1}, v_{2}, ..., v_{n}} - baigtinė, visiškai sutvarkyta aibė: v_{1} < v_{2} < ... < v_{n} ir π - šios aibės keitinys (w_{1}, w_{2}, ..., w_{n}) . Tuo pačiu žymeniu π žymėsime ir funkcija̧

π : V → V, π (v_{1}) = w_{1}, π (v_{2}) = w_{2}, ..., π (v_{n}) = w_{n}. Žinome, kad keitiniai yra abipus vienareikšmės funkcijos ir ju̧ yra n! . Pateiksime keitiniu̧ reiškimo būdus.

1. Keitinio, kaip funkcijos apibrėžtos baigtinėje aibėje, reiškimas lentele:

( \begin{matrix}v_{1} & v_{2} & ... & v_{n} \\ w_{1} & w_{2} & ... & w_{n} \end{matrix} ) .

2. Reiškimas grafu. Grafas sudarytas iš viršūniu̧ v_{i} ir orientuotu̧ briaunu̧ ⟨v_{i}, π (v_{i})⟩ , 1 ≤ i ≤ n .

Pavyzdys. V = {1, 2, 3, 4, 5, 6, 7}

π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 4 & 5 & 2 & 1 & 6 & 7 \end{matrix} )

\begin{aligned}& & 1 \\ & ↗ & & ↘ \\ 5 & & ⟵ & & 3 \end{aligned} 2 ⟷ 4 6 7

3. Reiškimas nepriklausomais ciklais. Tegu v_{i} ∈ V . Tada turime aibės V elementu̧ seka̧ v_{i}, π (v_{i}) , π^{2} (v_{i}) = π (π (v_{i})) , ..., π^{k−1} (v_{i}) , π^{k} (v_{i}) = v_{i.}. Gauname k ilgio cikla̧ (v_{i}, π (v_{i}) , π^{2} (v_{i}) = π (π (v_{i})) , ..., π^{k−1} (v_{i})) . Jeigu k = n , tai visi aibės V elementai yra šiame cikle. Kitu atveju, egzis-

tuoja v_{j} ∉ (v_{i}, π (v_{i}) , π^{2} (v_{i}) = π (π (v_{i})) , ..., π^{k−1} (v_{i})) , kuriam konstruojame savo cikla̧:

(v_{j}, π (v_{j}) , π^{2} (v_{j}) = π (π (v_{j})) , ..., π^{l−1} (v_{j})) . Cikluose yra skirtingi elementai. Jeigu π^{r} (v_{j}) = π^{s} (v_{i}) , tai π^{r+1} (v_{j}) = π^{s+1} (v_{i}) , …, v_{j} = π^{l} (v_{j}) = π^{s+(l−r)} (v_{i}),

tai elementas v_{j} priklausytu̧ pirma̧jam ciklui, o tai prieštarautu̧ sa̧lygai.

Taigi, visi aibės V elementai suskyla i̧ nepriklausomus ciklus keitinio π atžvilgiu. Mes jau buvome susidūrȩ su ekvivalentumo sa̧ryši̧ atitinkančiu aibės skaidiniu (sveikieji skaičiai kuriuo nors moduliu).

Keitini̧ π atitinka baigtinės aibės V skaidinys S_{π}. v_{i} ≡ v_{j} (mod π) ⟺ v_{j} = π^{s} (v_{i}) , s ∈ N . Tai ekvivalentumo sa̧ryšis :

1) v_{i} ≡ v_{i} (mod π) .

2) v_{i} ≡ v_{j} (mod π) ⟺ v_{j} ≡ v_{i} (mod π) v_{j} = π^{s} (v_{i}) ⟹ π^{k−s} (v_{j}) = v_{i}.

3) v_{i} ≡ v_{j} (mod π) , v_{j} ≡ v_{k} (mod π) ⟹ v_{i} ≡ v_{k} (mod π) v_{j} = π^{s} (v_{i}) , v_{k} = π^{t} (v_{j}) = π^{t} (π^{s} (v_{i})) = π^{t+s} (v_{i}) . Parodėme, kad bet kuri̧ keitini̧ galima užrašyti kaip poromis nepriklausomu̧

ciklu̧ ”sandauga”. Šis skaidinys yra vienintėlis ciklu̧ išsidėstymo tikslumu. Paaiškinsime ”sandaugos” sa̧voka̧. Apibrėžimas.Tegu π , ρ - keitiniai aibėje V. Keitiniu̧ sandauga σ = π ∘ ρ

vadinsime keitini̧, apibrėžta̧ lygybe

σ (v_{i}) = ρ (π (v_{i})) , ∀v_{i} ∈ V.

Pastebėsime, kad taip apibrėžta sandauga yra funkciju̧ kompozicija. Ji nėra komutatyvi.

Pavyzdys. Kai π = ( \begin{matrix}v_{1} & v_{2} & v_{3} \\ v_{3} & v_{2} & v_{1} \end{matrix} ), o ρ = ( \begin{matrix}v_{1} & v_{2} & v_{3} \\ v_{3} & v_{1} & v_{2} \end{matrix} ), tai

π ∘ ρ = ( \begin{matrix}v_{1} & v_{2} & v_{3} \\ v_{2} & v_{1} & v_{3} \end{matrix} ) ≠ ( \begin{matrix}v_{1} & v_{2} & v_{3} \\ v_{1} & v_{3} & v_{2} \end{matrix} ) = ρ ∘ π .

Tačiau, keitinio π kanoniniame skaidinyje esantys nepriklausomi ciklai komutuoja poromis.

Teiginys.Tegu S(V) - visu̧ keitiniu̧ aibė aibėje V. Tada (S (V) , ∘) - grupė. I̧rodymas. 1) Operacijos korektiškumas: jei π, ρ ∈ S(V) , tai π ∘ ρ ∈ S(V) .

2) Asosiatyvumas: (π ∘ ρ) ∘ τ = π ∘ (ρ ∘ τ) . ((π ∘ ρ) ∘ τ) (v_{i}) = τ ((π ∘ ρ) (v_{i})) = τ (ρ (π (v_{i}))) = (ρ ∘ τ) (π (v_{i})) = (π ∘ (ρ ∘ τ)) (v_{i}) .

3) Neutralaus elemento egzistavimas : id (v_{i}) = v_{i} , ∀v_{i} ∈ V , todėl id ∘ π = π ∘ id = π , π ∈ S(V).

4) Atvirkštinio elemento egzistavimas: jei π (v_{i}) = w_{i} , tai π^{−1} (w_{i}) = v_{i} . I̧rodyta. Apibrėžimas. Ciklas (v_{i}, v_{j}) vadinamas transpozicija. Teiginys. Kai |V | ≥ 2 ,tai bet kuri̧ keitini̧ galima užrašyti transpoziciju̧ san-

dauga.

I̧rodymas. Ši̧ teigini̧ pakanka i̧rodyti k ilgio ciklui.

Indukcija pagal k . Kai k = 1, (v) = (u, v) ∘ (u, v) . Kai k = 2, (u, v) = (u, v) , o k ≥ 3, (v_{1}, v_{2}, ..., v_{k}) = (v_{1}, v_{2}) ∘ (v_{1}, v_{3}) ∘ ⋯ ∘ (v_{1}, v_{k}). Sandaugoje yra k − 1

transpozicija.

I̧rodyta. Pastebėsime, kad keitinio reiškimas transpoziciju̧ sandauga yra nevienareikšmiškas. Pavyzdžiui, (v, u) = (v, u) ∘ (v, u) ∘ (v, u) . Pastovus dydis šiame reiškime visdėlto yra: tai transpoziciju̧ skaičius mod 2. Apibrėžimas. Tegu π ∈ S(V). Pora (v_{i}, v_{j}), kai v_{i} < v_{j}, bet π (v_{i}) > π (v_{j})

vadinama keitinio π inversija. π vadinamas lyginiu keitiniu, jeigu π inversiju̧ skaičius yra lyginis. π vadinamas nelyginiu keitiniu, jeigu π inversiju̧ skaičius yra nelyginis. Keitinio π inversiju̧ skaičiu̧ žymėsime |π|, o ženkla̧ sgnπ = (−1)^{|π|} . Pastebėsime, kad id yra lyginis keitinys. Jei π− lyginis, tai sgnπ = 1, jei π−

nelyginis, tai sgnπ = −1.

Pavyzdys.[..........] . Teiginys. |π ∘ (a, b)| ≡ |π| + 1 (mod 2) . I̧rodymas.

π = ( \begin{matrix}v_{1} & ... & v_{k} & v_{k+1} & v_{k+2} & ... & v_{k+l+1} & v_{k+l+2} & v_{k+l+3} & ... & v_{n} \\ a_{1} & ... & a_{k} & a & b_{1} & ... & b_{l} & b & c_{1} & ... & c_{m} \end{matrix} ) ,

π ∘ (a, b) = ( \begin{matrix}v_{1} & ... & v_{k} & v_{k+1} & v_{k+2} & ... & v_{k+l+1} & v_{k+l+2} & v_{k+l+3} & ... & v_{n} \\ a_{1} & ... & a_{k} & b & b_{1} & ... & b_{l} & a & c_{1} & ... & c_{m} \end{matrix} ) .

Pažymėkime. p_{a} = |{a_{1}, ..., a_{k}|a_{i} > a}| , q_{a} = |{a_{1}, ..., a_{k}|a_{i} > b}| p_{b} = |{b_{1}, ..., b_{l}|b_{i} > a}| , q_{b} = |{b_{1}, ..., b_{l}|b_{i} > b}| p_{c} = |{c_{1}, ..., c_{m}|c_{i} > a}| , q_{c} = |{c_{1}, ..., c_{m}|c_{i} > b}| . Tegu r - keitinio

( \begin{matrix}v_{1} & ... & v_{k} & v_{k+2} & ... & v_{k+l+1} & v_{k+l+3} & ... & v_{n} \\ a_{1} & ... & a_{k} & b_{1} & ... & b_{l} & c_{1} & ... & c_{m} \end{matrix} )

inversiju̧ skaičius. Tada , kai a < b turime |π| = p_{a} + (l − p_{b}) + (m − p_{c}) + q_{a} + q_{b} + (m − q_{c}) + r, |π ∘ (a, b)| = p_{a} + p_{b} + (m − p_{c}) + q_{a} + (l − q_{b}) + (m − q_{c}) + 1 + r. Todėl |π| − |π ∘ (a, b)| = 2 (q_{b} − p_{b}) + 1 ≡ 1 (mod 2) . Atvejis a > b nagrinėjamas analogiškai. I̧rodyta.

Turime, kad sgn (id) = 1 ir sgn ((a, b)) = −1 . Transpoziciju̧ skaičius keitinyje π yra pastovus dydis mod 2 . Jeigu turime du

keitinio π reiškimus transpoziciju̧ snadauga ;

π = σ_{1} ⋯ σ_{k} = τ_{1} ⋯ τ_{l} ,

tai sgnπ = sgn (σ_{1} ⋯ σ_{k}) = sgn (τ_{1} ⋯ τ_{l}) ir sgnπ = (−1)^{k} = (−1)^{l} ⟹ (−1)^{k−l} = 1 ⟹ k − l ≡ 0 (mod 2) ⟹ k ≡ l (mod 2.)

Išvados.1. Keitinys yra lyginis tada ir tik tada, kai jis yra lyginio skaičiaus transpozicijiu̧ sandauga.

2. Keitinys yra nelyginis tada ir tik tada, kai jis yra nelyginio skaičiaus transpozicijiu̧ sandauga.

3. k-ciklas yra lyginis tada ir tik tada, kai k yra nelyginis ir atvirkščiai.

4. (lyginis) ∘ (lyginis) = (lyginis) . (nelyginis) ∘ (nelyginis) = (lyginis) . (nelyginis) ∘ (lyginis) = (nelyginis) .

5. sgn (π ∘ ρ) = sgn (π) · sgn (ρ) . Lyginiu̧ keitinu̧ aibȩ žymėsime A_{n} . Teiginys. A_{n} yra grupė. I̧rodymas. Akivaizdu. Šia̧ grupȩ vadina alternuojančia grupe.

Teiginys. Lyginiu̧ ir nelyginiu̧ keitiniu̧ yra po lygiai \frac{n!}{2} . I̧rodymas. Nagrinėjama alternuojanti grupė A_{n}. Apibrėžiama aibė

U_{(a,b)} = {π ∈ S_{n}|π = σ ∘ (a, b) , σ ∈ A_{n}} ⊆ S_{n} − A_{n}.

Tegu |A_{n}| = m_{1} , |S_{n} − A_{n}| = m_{2}. Tada aibės U_{(a,b)} visi elementai skirtingi: σ_{1} ∘ (a, b) = σ_{2} ∘ (a, b) ⟺ σ_{1} ∘ (a, b) ∘ (a, b) = σ_{2} ∘ (a, b) ∘ (a, b) ⟺ σ_{1} = σ_{2}. Taigi, |U_{(a,b)}| = |A_{n}| = m_{1} ≤ m_{2}. Analogiškai, tegu turime aibȩ

W_{(a,b)} = {π ∈ S_{n}|π = ρ ∘ (a, b) , ρ ∈ S_{n} − A_{n}} ⊆ A_{n}.

Kaip ir aibės U_{(a,b)} taip ir aibės W_{(a,b)} visi elementai skirtingi. Tada |W_{(a,b)}| = |S_{n} − A_{n}| = m_{2} ≤ m_{1}.

Taigi, m_{1} = m_{2} = \frac{n!}{2} .

I̧rodyta.

Teorema(A.Cayley). Tegu (G, ·) yra baigtinė grupė, turinti n elementu̧. Tada egzistuoja funkcija

f : G → S(G) = S_{n},

tenkinanti savybes

f (g_{1}) = f (g_{2}) ⟺ g_{1} = g_{2}, (injektyvumas)
f (g · h) = f (g) ∘ f (h) . (homomorfizmas)

I̧rodymas.∀a ∈ G konstruojame keitini̧ L_{a} : G → G , L_{a}(g) = g · a . Taigi L_{a} ∈ S_{n}.

Turime aibiu̧ lygybȩ

{g_{1}, g_{2}, ..., g_{n}} = {g_{1} · a, g_{2} · a, ..., g_{n} · a} = G.

Turime

1) L_{a} ∈ S_{n},

2) L_{a}^{−1} = L_{a^{−1}},

3) L_{a·b} (g) = g · (a · b) = (g · a) · b = L_{b} (L_{a} (g)) = (L_{a} ∘ L_{b}) (g) , taigi, L_{a·b} = L_{a} ∘ L_{b}.

Gavome, kad keitiniai L_{g_{1}}, L_{g_{2}}, ..., L_{g_{n}} sudaro grupȩ H ⊂ S (G) = S_{n}. Funkcija f : G → H ⊂ S_{n} apibrėžta formule f (g) = L_{g} . I̧rodyta. Pavyzdys1. Rombo simetriju̧ grupės i̧dėjimas i̧ simetrinȩ grupȩ. Tegu G = {e, a, b, c} - rombo simetriju̧ grupė. Čia e ir a posūkiai atitinkamai

0^{∘} ir 180^{∘} kampu, o b ir c simetrijos i̧strižainiu̧ atžvilgiu. Tada veiksmu̧ lentelė šioje grupėje

\begin{matrix}· & e & a & b & c \\ e & e & a & b & c \\ a & a & e & c & b \\ b & b & c & e & a \\ c & c & b & a & e \end{matrix}

ir L_{e} = ( \begin{matrix}e & a & b & c \\ e & a & b & c \end{matrix} ) = id , L_{a} = ( \begin{matrix}e & a & b & c \\ a & e & c & b \end{matrix} ) = (ea) (bc) , L_{b} =

( \begin{matrix}e & a & b & c \\ b & c & e & a \end{matrix} ) = (eb) (ac) , L_{c} = ( \begin{matrix}e & a & b & c \\ c & b & a & e \end{matrix} ) = (ec) (ab) .

Pavyzdys2. Ciklinės grupės ( pvz. n-ojo laipsnio šaknu̧ iš 1 multiplikacinės grupės) i̧dėjimas i̧ simetrinȩ grupȩ.

Tegu ε - primityvioji n-ojo laipsnio šaknis iš vieneto. Tada visos n-ojo laipsnio šaknis iš vieneto yra primityviosios šaknies ε laipsniai : ε, ε^{2}, ..., ε^{n−1}, ε^{n} = 1 ir

L_{ε} = ( \begin{matrix}ε & ε^{2} & ε^{3} & ⋯ & ε^{n−1} & ε^{n} \\ ε^{2} & ε^{3} & ε^{4} & ⋯ & ε^{n} & ε \end{matrix} )

L_{ε^{2}} = ( \begin{matrix}ε & ε^{2} & ε^{3} & ⋯ & ε^{n−1} & ε^{n} \\ ε^{3} & ε^{4} & ε^{5} & ⋯ & ε^{n+1} & ε^{n+2} \end{matrix} )

ir t.t. Pavyzdžiui, kai n = 6 turime reiškima̧ keitiniais:

L_{1} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 4 & 5 & 6 & 1 \end{matrix} ) = (123456)

L_{2} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 5 & 6 & 1 & 2 \end{matrix} ) = (135) (246)

L_{3} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 5 & 6 & 1 & 2 & 3 \end{matrix} ) = (14) (25) (36)

L_{4} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 6 & 1 & 2 & 3 & 4 \end{matrix} ) = (153) (264)

L_{5} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 & 2 & 3 & 4 & 5 \end{matrix} ) = (165432)

L_{6} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{matrix} ) = id.