#abstract_algebra #computer_science

חבורת התמורות

לכל $n \in N$ נגדיר את חבורת התמורות $S_{n}$ להיות אוסף כל הפונקציות ההפיכות מ $[n] \to [n]$ כאשר הפעולה של $S_{n}$ היא $\circ$ כלומר הרכבה.
באופן כללי נוכל לסמן $S_{X}$ להיות קבוצת הפונקציות ההפיכות ב $X^{X}$ .

למשל התמורה

f = (\begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \end{matrix})

היא תמורה השייכת לחבורה $S_{4}$ .

משפט:
תהי $S_{n}$ ותהיינה $f, g \in S_{n}$ אזי

s i g n (f \circ g) = s i g n (f) \cdot s i g n (g)

הוכחה:

\begin{matrix} s i g n (f \circ g) = \prod_{i \neq j} \frac{f (g (i)) - f (g (j))}{i - j} \\ = \prod_{i \neq j} \frac{f (g (i)) - f (g (j))}{i - j} \cdot \frac{g (i) - g (j)}{g (i) - g (j)} \\ = \prod_{i \neq j} \underset{s i g n (f)}{\underset{⏟}{\frac{f (g (i)) - f (g (j))}{g (i) - g (j)}}} \cdot \underset{s i g n (g)}{\underset{⏟}{\frac{g (i) - g (j)}{i - j}}} = s i g n (f) \cdot s i g n (g) \end{matrix}

משפט
הסדר של $S_{n}$ הוא $n!$ שכן מ קומבינטוריה נוכל לבחור לכל ערך ב $[n]$ בהתחלה $n$ איברים ולאחר מכן $n - 1$ וכן הלאה..

מחזור

יהי $n \in N$ ויהיו $a_{1}, \dots, a_{k} \in [n]$ כך ש $\forall_{i \neq j \in [k]} : a_{i} \neq a_{j}$ . נגדיר את המחזור $f = (a_{1} a_{2} a_{3} \dots a_{k}) \in S_{n}$ להיות:

\forall_{i \in [k - 1]} : f (x) = {\begin{cases} x & x \neq a_{i} \\ a_{i + 1} & x = a_{i} \\ a_{1} & x = a_{k} \end{cases}

הערה

למחזור באורך $2$ קוראים חילוף, האורך של מחזור $f = (a_{1} a_{2} a_{3} \dots a_{k}) \in S_{n}$ הוא $k$

מחזורים זרים הם מחזורים שאין להם מספר משותף.
טענה: מחזורים זרים הם מתחלפים זה עם זה כלומר $σ \circ θ = θ \circ σ$ כאשר אלו מחזורים.

הבחנה

אם מחזורים זרים מתחלפים זה עם זה מקיים $(a \circ b)^{m} = a^{m} b^{m}$

נשים לב: כל תמורה אפשר להציג כהרכבה של מחזורים זרים וכל מחזור אפשר להציג כהרכבה של חילופים .

למשל

(\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{matrix}) = (1 2) (3 4)

משפט

(\begin{matrix} a_{1} & a_{2} & \dots & a_{k} \end{matrix}) = (a_{1} a_{2}) (a_{2} a_{3}) \dots (a_{k - 1} a_{k})

כלומר, כל מחזור אפשר להציג כהרכבה של חילופים.

הוכחה-
נוכיח שיש שיוויון בין שתי פונקציות כלומר שהן שולחו כל איבר לאותו המקום. נחלק למקרים

$x \neq a_{i}$ :

(\begin{matrix} a_{1} & a_{2} & \dots & a_{k} \end{matrix}) (x) = (a_{1} a_{2}) (a_{2} a_{3}) \dots (a_{k - 1} a_{k}) (x) = x

$x = a_{i}$ :

(\begin{matrix} a_{1} & a_{2} & \dots & a_{k} \end{matrix}) (a_{i}) = a_{i + 1}

\begin{matrix} (a_{1} a_{2}) (a_{2} a_{3}) \dots (a_{k - 1} a_{k}) (a_{i}) = (a_{1} a_{2}) (a_{2} a_{3}) \dots (a_{i} a_{i + 1}) (a_{i}) \\ = (a_{1} a_{2}) (a_{2} a_{3}) \dots (a_{i - 1} a_{i}) (a_{i + 1}) = a_{i + 1} \end{matrix}

סימן החילוף

עבור $f$ חילוף נוכיח שהסימן הוא $- 1$ ולכן הסימן של מחזור הוא

s i g n (a_{1} \dots a_{k}) = s i g n ((a_{1} a_{2}) \dots (a_{k - 1} a_{k})) = (- 1)^{k - 1}

ההוכחה לנ״ל תהיה על סימן החילוף הספציפי $(1, 2)$ ועל כל אחד אחר ההוכחה תהיה זהה:

s i g n (f) = \frac{2 - 1}{1 - 2} \cdot \frac{2 - 3}{1 - 3} \dots \frac{2 - n}{1 - n} \cdot \frac{1 - 3}{2 - 3} \dots \frac{1 - 2}{2 - n} \dots = \frac{2 - 1}{1 - 2} = - 1

המעבר האחרון נובע מכך שאחרי שחישבנו את את המכפלות עבור הערכים $1, 2$ נקבל פשוט כפל של 1 כי האיברים יצטמצמו לנו.

הבחנה

אנחנו יודעים שכל החבורות הציקליות הן גם אבליות ולכן מcontra positive של הטענה יתקיים שאם חבורה אינה אבלית היא גם אינה ציקלית, קל לראות ש $S_{n}$ אינה ציקלית לכל $n \geq 3$ כי אלו לא אבליות.

משפט: סדר של מחזור זה האורך שלו.
מסקנה כל תמורה מסדר אי זוגי היא מסימן זוגי.

חבורת החילופין

חבורת החילופין (נקראת גם חלופת התמורות הזוגיות) $A_{n}$ היא תת החבורה הבאה של $S_{n}$

A_{n} = {σ \in S_{n} | s i g n (σ) = 1}

הסדר של החבורה הזו הוא $\frac{n!}{2}$ . נשים לב ש $A_{n} = k e r (s i g n)$ כי אנחנו יודעים שהסימן הוא הומומורפיזם.