Тема 7

Симетрична група. Представяне на елементите като произведение на независими цикли, ред на елементите от Sn и спрягане. Алтернативна група.

Симетрична група

Нека $M$ е произволно множество.
Дефинираме множеството от всички биекции $\varphi : M \to M$:

(1)
\begin{align} S(M) = \{ \varphi : M \to M | \varphi - \mbox{bijection} \} \end{align}

Въвеждаме операцията композиция $\circ$ и ще проверим дали тя е подходяща операция за да превърне $S(M)$ в група:

Свойство 0: Композиция на две биекции е биекция - $\varphi, \psi \in S(M) \Rightarrow \varphi \circ \psi \in S(M)$

Свойство 1: Композицията е асоциативна - $\varphi, \psi, \tau \in S(M) \Rightarrow \varphi \circ (\psi \circ \tau) = (\varphi \circ \psi) \circ \tau$

Свойство 2: Съществува единичен елемент - $\exists id : M \to M : id \circ \varphi = \varphi \circ id = \varphi \quad \forall \varphi \in S(M)$

Свойство 3: За всеки елемент съществува противоположен: $\forall \varphi \in S(M) \Rightarrow \exists \varphi^{-1} : \varphi \circ \varphi^{-1} = \varphi^{-1}\circ\varphi = id$

Дефиниция: Ще наричаме множеството $S(M)$ с операция $\circ$ симетрична група за $M$.

Твърдение:

Групата $\langle S(M), \circ \rangle$ не е комутативна, при $|M| \ge 3$.

Дефиниция: Нека $|M| = n$, тогава $S_n$ наричаме симетрична група от степен $n$.
Забележка: Горната дефиниция важи само за крайни множества $M$.

Означение

За удобство при $|M| = n$ ще си обозначим елементите на $M$ с естествени числа :

(7)
\begin{align} M = \{ 1, 2, \cdots, n \} \end{align}

и ще записваме биекциите по следния начин (без стрелки)

(8)
\begin{align} \varphi = \begin{pmatrix} 1 & 2 & \cdots & n \\ i_1 & i_2 & \cdots & i_n \\ \end{pmatrix} \end{align}

което всъщност ще означава, че $\varphi(k) = i_k$.

Брой елементи

Очевидно една биекция се определя еднозначно от подредбата на елементите $i_1, i_2, \cdots, i_n$. Тогава броя на всички възможни пермутации $|S(M)| = |S_n| = n!$.

Обратен елемент

Обратна биекция на дадена се намира, като първо се напишат стълбовете на матрицата наопаки (т.е долния ред - отгоре) и после се сортират по горния ред (т.е той да стане $1, 2, \cdots n$). Ето така:

(9)
\begin{align} \varphi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 3 & 5 \end{pmatrix} \Rightarrow \varphi^{-1} = \begin{pmatrix} 2 & 4 & 1 & 3 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 4 & 2 & 5 \end{pmatrix} \end{align}

Представяне с цикли

Сега ще разгледаме един по-подходящ начин да записваме пермутациите.

Дефиниция: Нека $\{ i_1, i_2, \cdots, i_k \} \subseteq \{ 1, 2, \cdots, n \}$, и $i_1, i_2, \cdots, i_n$ са различни помежду си. Нека

(10)
\begin{eqnarray} \varphi(i_1) &=& i_2 \\ \varphi(i_2) &=& i_3 \\ \vdots & & \vdots \\ \varphi(i_{k-1}) &=& i_k \\ \varphi(i_k) &=& i_1 \\ \end{eqnarray}

и освен това останалите елементи са неподвижни, т.е $\varphi(j) = j \quad \forall j \notin \{ i_1, i_2, \cdots, i_k \}$.
Тогава $\varphi$ ще наричаме цикъл с дължина $k$ и ще записваме $\varphi = (i_1\ i_2\ \cdots\ i_k)$.

Т.е ако пермутацията изпълнява горните условия - наричаме я цикъл и я записваме като изредим елементите от цикъла подред. Ако пермутацията не изпълнява горните условия - значи не е цикъл (и не я записваме никак по-кратко). След малко ще представяме не-циклите като произведение на няколко цикъла.

Дефиниция: Нека $\varphi = (i_1\ \cdots\ i_k)$ и $\psi = (j_1\ \cdots\ j_s)$. Ще казваме, че $\varphi, \psi$ са независими, ако $\{ i_1, \cdots, i_k \} \cap \{ j_1, \cdots, j_s \} = \varnothing$, т.е нямат общ елемент помежду си.

Твърдение: Ако $\varphi, \psi$ са независими, то $\varphi \circ \psi = \psi \circ \varphi$, т.е независимите цикли комутират.

Представяне чрез произведение на независими цикли

Теорема:

Нека $\varphi \in S_n$ и $\varphi \ne id$. Тогава $\varphi$ може да се представи като произведение на независими цикли и това представяне е единствено с точност до наредбата на циклите.

Свойства

1. $\tau = (i_1\ \cdots\ i_k)$
$|\tau| = k$ - реда2 на цикъла е равен на дължината му.
2. $\tau, \sigma$ - независими цикли
$| \tau \circ \sigma | = lcm( |\tau|, |\sigma|)$ - реда на произведението на 2 цикъла е равен на НОК-а от редовете им.
3. $\varphi = \tau_1 \tau_2 \cdots \tau_k$ - разбиване на независими цикли
$|\varphi| = lcm(|\tau_1|, |\tau_2|, \cdots, |\tau_k|)$ - обощение на 2. за произведение на произволен брой цикли.

Спрегнати елементи

Дефиниция: Нека $G$ е група и $a, g \in G$. Ще казваме, че $a$ и $gag^{-1}$ са спрегнати и ще записваме $a \sim gag^{-1}$.

Свойства

  1. $a \sim a$ - рефлексивност (използваме $g = id$)
  2. $a \sim b \Rightarrow b \sim a$ - симетричност (ако $b = gag^{-1}$, тогава $a = g^{-1}bg$)
  3. $a \sim b \And b \sim c \Rightarrow a \sim c$ - транзитивност (ако $b = g_1ag^{-1}_1 \And c = g_2bg^{-1}_2 \Rightarrow c = g_2(g_1ag^{-1}_1)g^{-1}_2 = (g_2g_1)a(g_2g_1)^{-1}$)

Твърдение:

Нека $\sigma = (i_1\ \cdots\ i_k)$ и $\varphi \in S_n$. Тогава
а) $\tau = \varphi \sigma \varphi^{-1} = (\varphi(i_1)\ \varphi(i_2)\ \cdots\ \varphi(i_k))$
б) $\sigma = \tau_2 \cdots \tau_p$ - разбиване на независими цикли,
$\sigma = (i_1\ \cdots\ i_k)\cdots(j_1\ \cdots\ j_s)$
Тогава $\varphi \sigma \varphi^{-1} = (\varphi(i_1) \cdots \varphi(i_k)) \cdots (\varphi(j_1)\cdots \varphi(j_s))$.
в) $\sigma \sim \tau$ т.с.т.к. имат еднакъв цикличен строеж (т.е равен брой цикли от всеки ред)3

Четност на пермутации

При разглеждането на детерминанти по Линейна Алгебра се наложи да разбием пермутациите на 2 групи - четни и нечетни. Сега ще направим това по-формално и ще докажем някои свойства.

Транспозиция

Дефиниция: Цикъл от ред 2 ще наричаме транспозиция.

Свойства:

  1. $(x\ y)^2 = id$ - прилагайки последователно една и съща транспозиция получаваме идентитет.
  2. $(i\ j)(k\ l) = (k\ l)(i\ j)$ - независимите транспозиции комутират (защото са независими :)).
  3. $(i\ j)(i\ k) = (i\ k)(k\ j) = (k\ j)(j\ i)$ - просто разпишете коя да е композиция на транспозиции и ще получите $(j\ i\ k)$.
  4. $(i_1\ i_2\ \cdots\ i_k) = (i_1\ i_k)(i_1\ i_{k-1}) \cdots (i_1\ i_3)(i_1\ i_2)$ - всеки цикъл може да се представи като произведение на транспозиции (разпишете дясната страна и ще се получи ;)).

Четност

Теорема:
а) $id = \tau_1\tau_2\cdots\tau_k$, където $\tau_i$ са транспозиции и $k$ е четно;
б) Ако $\varphi = \tau_1\tau_2\cdots\tau_p = \sigma_1\sigma_2\cdots\sigma_r$, където $\tau_i, \sigma_j$ са транспозиции, тогава $p \equiv r \pmod{2}$ (т.е независимо от разбиването на цикли на дадена пермутация $\varphi$ броя на участващите транспозиции във всяко разбиване има една и съща четност - или всички са четни, или всички са нечетни);

Горната теорема позволява въвеждането на следната дефиниция:
Дефиниция: Нека $\varphi$ е пермутация.

  • Ще казваме, че тя е четна, ако може да бъде представена като произведение на четен брой транспозиции.
  • Ще казваме, че тя е нечетна, ако може да бъде представена като произведение на нечетен брой транспозиции.

Алтернативна група

Дефиниция:

  • $A_n = \{ \sigma \in S_n | \sigma$ - четна пермутация $\}$;
  • $B_n = \{ \sigma \in S_n | \sigma$ - нечетна пермутация $\}$;

Ще наричаме $A_n$ алтернативна група от степен n.

За да докажем, че $A_n$ е група трябва да покажем, че произведение на два елемента от $A_n$ е вътре в $A_n$ и противоположния на всеки елемент също е вътре:

  • $\sigma_1, \sigma_2 \in A_n$. Тогава всяка една от тях се представя като произведение на четен брой транспозиции, следователно тяхното произведение също се представя като произведение на четен брой транспозиции. Следователно $\sigma_1\sigma_2 \in A_n$
  • $\sigma\sigma^{-1} = id$ - тъй като $\sigma$ е четна и идентитета също е четен, то следователно и $\sigma^{-1}$ също е четна (иначе излиза, че идентитета има представяне с нечетен брой транспозиции).

Ще покажем, че съществува биекция между $A_n$ и $B_n$ с което ще покажем, че четните пермутации са точно колкото са нечетните пермутации.
Нека $\varphi : S_n \to S_n$ е такава, че $\varphi(\sigma) = (1\ 2)\circ \sigma$. Т.е добавяме транспозицията $(1\ 2)$ след пермутацията. Очевидно, тази функция праща всички четни пермутации в нечетни и обратно (защото добавянето на една транспозиция променя четността). Това означава, че функцията $\varphi$ разгледана като функция $\varphi : A_n \to B_n$ или $\varphi : B_n \to A_n$ е сама на себе си обратна - защото $\varphi(\varphi(\sigma)) = \sigma$. Следователно $|A_n| = |B_n| = \frac{|S_n|}{2} = \frac{n!}{2}$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License