חבורות של תמורות

מבוא

עד כה בסדרת הפוסטים שלי על תורת החבורות ראינו תוצאות אבסטרקטיות שנכונות לכל החבורות (או לכל החבורות הסופיות), ובתור דוגמא ראינו את חבורת השלמים. הבעיה היא שזו דוגמא פשוטה מדי: ראינו שהשלמים הם חבורה ציקלית, וגם החבורות שמוגדרות באמצעותה (תתי-החבורות וחבורות המנה שלה) הן ציקליות. חבורות ציקליות הן מאוד פשוטות וכבר הבנו את המבנה שלהן עד הסוף; אם כן, בשביל מה צריך את כל תורת החבורות? ברור שאנחנו חייבים לראות עוד דוגמאות קונקרטיות לחבורות, וכאלו שהן מסובכות יותר, כדי שיהיה טעם בכל העסק הזה. את הפוסט הזה אני הולך להקדיש כולו להצגה של מה שהוא ככל הנראה סוג החבורות החשוב ביותר: חבורות של תמורות (פרמוטציות). בהמשך הפוסט נראה שבמובן מסויים, זו גם הדוגמה הכללית ביותר, כי על כל חבורה אפשר לחשוב בתור חבורת תמורות, כפי שעל פי חבורה ציקלית היה אפשר לחשוב בתור חבורה של שלמים מודולו משהו.

מה זו תמורה? בהינתן קבוצה \( X \) כלשהי, תמורה של \( X \) היא פשוט פונקציה \( \sigma:X\to X \) שהיא חח”ע ועל. כלומר, היא מערבבת את האיברים של \( X \). כעת, אנחנו יודעים להרכיב פונקציות: \( \sigma\cdot\tau \) היא הפונקציה שמוגדרת על ידי “קודם נפעיל את \( \tau \) ואז נפעיל את \( \sigma \), כלומר \( \sigma\tau\left(x\right)=\sigma\left(\tau\left(x\right)\right) \). עם פעולת ההרכבה, אוסף כל התמורות של \( X \) מהווה חבורה. איבר היחידה הוא תמורת הזהות, \( \text{Id}:X\to X \) שהוא הפונקציה שמקיימת \( \text{Id}\left(x\right)=x \) לכל \( x\in X \), ולכל תמורה \( \sigma \) ההופכית שלה היא פשוט הפונקציה ההפוכה \( \sigma^{-1} \) (קיימת כזו כי \( \sigma \) חח”ע ועל). לכן אנחנו מקבלים חבורה. את חבורת כל התמורות של \( X \) מסמנים ב-\( S_{X} \) וקוראים לה החבורה הסימטרית של \( X \). במקרה הפרטי החשוב שבו \( X=\left\{ 1,2,\dots,n\right\} \) משתמשים גם בסימון \( S_{n} \) (במקום לכתוב \( S_{\left\{ 1,2,\dots,n\right\} } \)).

זהו, עכשיו אנחנו יודעים בדיוק מהן חבורות של תמורות, אבל מן הסתם אנחנו לא באמת “מרגישים” מה קורה איתן ולמה הן מעניינות ואיך חבורות כאלו נראות וכדומה. אז יתר הפוסט יוקדש לבחינה יותר טכנית של החבורות הללו. לטעמי, מה שנעשה בהמשך הפוסט הוא קריטי לחלוטין - בערך כמו לדעת לחבר ולחסר ולכפול ולחלק מספרים שלמים. אני אתמקד בחבורה \( S_{n} \), עבור \( n \) טבעי כללי ולפעמים עבור מקרים קונקרטיים שלו. אפשר הרי תמיד למספר את האיברים של כל קבוצה סופית \( X \) ולכן לדבר רק על \( S_{n} \) לא מגביל אותנו, כל עוד אנחנו מתעניינים רק בתמורות של קבוצה סופית (וזה מה שנעשה הפעם).

לפני שנתחיל לדבר על ההיבטים הטכניים של \( S_{n} \), בואו נשתכנע שכל חבורה איזומורפית לחבורת תמורות כלשהי. תהא \( G \) חבורה (סופית, לא סופית, אבלית, לא אבלית, מה שתרצו). זכרו שאחד מהדברים הראשונים שראינו על חבורות הוא שעבור \( a\in G \) כלשהו, הפעולה “כפל ב-\( a \)” היא חד-חד-ערכית ועל: אם \( ab=ac \) אז \( b=c \), וכמו כן לכל \( c\in G \) קיים \( b\in G \) כך ש-\( ab=c \) (\( b=a^{-1}c \)). מכאן שהפונקציה \( \sigma_{a}:G\to G \) המוגדרת על ידי \( \sigma_{a}\left(b\right)=ab \) היא תמורה של \( G \). מכאן שיש לנו פונקציה \( f:G\to S_{G} \) המוגדרת על ידי \( f\left(a\right)=\sigma_{a} \). קל לראות שזו פונקציה חח”ע, כי אם \( \sigma_{a}=\sigma_{b} \) אז בפרט \( a=\sigma_{a}\left(e\right)=\sigma_{b}\left(e\right)=b \). קל גם לראות שהיא הומומורפיזם, כי \( f\left(ab\right)=\sigma_{ab}=\sigma_{a}\sigma_{b}=f\left(a\right)f\left(b\right) \) שהרי על פי הגדרה, \( \sigma_{ab}\left(x\right)=abx=a\left(bx\right)=a\sigma_{b}\left(x\right)=\sigma_{a}\left(\sigma_{b}\left(x\right)\right) \). אז אם לסכם: הראנו הומומורפיזם חח”ע מ-\( G \) אל \( S_{G} \) ומכאן ש-\( G \) איזומורפית לתת-חבורה של \( S_{G} \).

האם התוצאה הזו אומרת שאפשר לשכוח מחבורות ומספיק להתעסק רק בתמורות? לא, כי כפי שכבר אמרתי בעבר, גם אם שתי חבורות הן איזומורפיות זה לא אומר שאין חשיבות לשיטות ייצוג שונות שלהן. מה שקל בשיטת ייצוג אחת עשוי להיות קשה באחרת. לכן טוב מאוד שאנחנו מודעים לכך שאפשר לחשוב על כל חבורה בתור חבורת תמורות; אבל זה לא אומר שמעכשיו נרצה לתת מונופול רק לדרך החשיבה הזו. בשביל מה?

פירוק למעגלים

הדבר הראשון שאני רוצה לעשות כשאני בא לדבר על \( S_{n} \) הוא למצוא דרך טובה לתאר פרמוטציות. שיטת סימון טובה היא המפתח לכל מה שעושים אחר כך. במקרה הנוכחי, שיטות הסימון שאראה הומצאו על ידי קושי. השיטה הראשונה היא פשוט לכתוב שתי רשימות של מספרים, האחת ממויינת והשניה מתאימה למה שהתמורה עושה. למשל:

\( \left(\begin{array}{cccc} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{array}\right) \)

מה שמתואר לעיל הוא התמורה שמעבירה את 1 ל-2, את 2 ל-4, את 3 ל-3 ואת 4 ל-1. כדי לראות לאן התמורה מעבירה מספר כלשהו פשוט מחפשים אותו בשורה העליונה ובודקים מי המספר שמתחתיו בשורה התחתונה. זו שיטת סימון לא רעה אבל היא מרגישה קצת מסורבלת - בשביל מה בעצם צריך את השורה העליונה? תמיד יהיה כתוב בה אותו דבר. השורה התחתונה היא לב העניין. למה לא לכתוב פשוט \( \left(2\ 4\ 3\ 1\right) \) וחסל? ובכן, כי אז יותר קשה במבט חטוף להבין לאן, למשל, 3 עובר: אם יש לנו תמורה ארוכה יחסית, אז צריך להתחיל לספור את האיברים בסוגריים כדי לוודא שהגענו לאיבר עם האינדקס הנכון, וזה קצת מעצבן. לכן אנחנו דבקים בשיטה למעלה של לכתוב שתי שורות. למרבה המזל, יש לנו דרך אחרת לגמרי לתאר תמורות שהיא הרבה יותר קומפקטית: מה שנקרא פירוק למעגלים של התמורה.

הרעיון ב”מעגל” הוא זה: אם נפעיל את התמורה על איבר כלשהו, ואז על הפלט שקיבלנו, ואז שוב ושוב, בסוף נחזור לאיבר שהתחלנו ממנו (בתנאי שהקבוצה \( X \) שלנו סופית - כזכור, רק על זה אנחנו מדברים). למשל, עבור התמורה שלנו \( \sigma\left(1\right)=2 \) ו-\( \sigma\left(2\right)=4 \) ו-\( \sigma\left(4\right)=1 \) - הופס, חזרנו לאיבר שהתחלנו ממנו. ראינו אם כן שאפשר לחשוב על חלק ממה שהתמורה עושה בתור “ללכת על המעגל” \( 1\to2\to4\to1 \).

למה זה תמיד עובד? ובכן, בואו ניקח \( a \) כלשהו ונסתכל על \( a,\sigma\left(a\right),\sigma^{2}\left(a\right),\dots \) וכן הלאה. יש לנו סדרה אינסופית של איברים אבל כמות הפלטים האפשרית של הפונקציה היא סופית (כי \( X \) סופית) ולכן יהיה איבר שמופיע פעמיים בסדרה. כלומר, קיימים \( n,k \) כך ש-\( n<k \) ו-\( \sigma^{n}\left(a\right)=\sigma^{k}\left(n\right) \), כלומר \( \sigma^{k-n}\left(a\right)=a \). קיבלנו ש-\( a \) מופיע פעמיים בסדרה, ושזה קורה לפני כל איבר אחר שמופיע פעמיים (למה?). זה קצת מזכיר את הניתוח של חבורות ציקליות שעשינו בפוסט קודם, ולא במקרה.

אם כן, ראינו שאת מה שכל תמורה עושה אפשר לתאר בעזרת מעגלים. בואו ניתן סימון קומפקטי למעגלים. את המעגל \( 1\to2\to4\to1 \) אפשר לתאר פשוט בתור \( \left(1\ 2\ 4\right) \). זהירות, לא להתבלבל עם צורת הסימון הקודמת שלנו! \( \left(1\ 2\ 4\right) \) לא אומר שהאיבר 1 עובר ל-1 והאיבר 2 עובר ל-2 וכדומה; הדרך הנכונה לקרוא מעגל היא להסתכל על אחד מהמספרים בו, ואז לומר שהתמורה מעבירה אותו אל המספר שמימין אליו (או במקרה של המספר הימני ביותר במעגל, מעבירה אותו לאיבר השמאלי ביותר במעגל). כמובן, אפשר לתאר אותו מעגל בכמה דרכים שונות, למשל \( \left(2\ 4\ 1\right) \) מתאר את אותו מעגל כמו \( \left(1\ 2\ 4\right) \); אבל לא להתבלבל - \( \left(1\ 4\ 2\right) \) אינו אותו מעגל כמו \( \left(2\ 4\ 1\right) \) כי למשל 1 עובר ל-4 במעגל הראשון אבל עובר ל-2 במעגל השני.

כעת, התמורה \( \left(\begin{array}{cccc} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{array}\right) \) מורכבת בעצם משני מעגלים: האחד הוא \( \left(1\ 2\ 4\right) \) מיודענו, והשני הוא \( \left(3\right) \) - מעגל בן איבר בודד. המוסכמה היא שאין צורך לכתוב מעגלים כאלו בכלל. לכן את התמורה \( \left(\begin{array}{cccc} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{array}\right) \) פשוט כותבים בתור \( \left(1\ 2\ 4\right) \) וחסל.

בואו נראה עכשיו דוגמה נוספת עם תמורה מסובכת יותר: \( \sigma=\left(\begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 2 & 1 & 8 & 3 & 4 & 7 & 6 \end{array}\right) \). אני רוצה למצוא את הייצוג של התמורה הזו בתור מעגלים. מה אני עושה? פשוט מאוד: אני בוחר מספר כלשהו באופן שרירותי, נאמר 1, ומתחיל לכתוב את המעגל שבו 1 נמצא. כלומר, אני מתחיל לכתוב “\( (1 \)” ואז מרים את הראש, מסתכל על \( \sigma \) ורואה לאן 1 עובר. הוא עובר ל-5 אז אני כותב 5 ליד 1 במעגל: “\( (1\ 5 \)”. עכשיו אני שוב מרים את הראש, רואה ש-5 עובר ל-3 וכותב “\( (1\ 5\ 3 \)”, ואחר כך מרים שוב את הראש ורואה ש-3 חזר אל 1. ברגע הזה אני סוגר את הסוגריים: קיבלנו את המעגל \( \left(1\ 5\ 3\right) \). עדיין לא סיימתי לכתוב את כל התמורה; טיפלתי רק באיברים 1,5,3. עכשיו אני עובר אל המספר הבא שטרם טיפלתי בו - במקרה שלנו, 2. אני רואה ש-2 עובר לעצמו כך שאני לא טורח לכתוב את זה בכלל. מי המספר הבא שטרם טיפלתי בו? 4, שעובר ל-8 שעובר ל-6 שעובר ל-4, אז אני מוסיף את המעגל \( \left(4\ 8\ 6\right) \), ולכן בינתיים כתובה לי התמורה \( \left(1\ 5\ 3\right)\left(4\ 8\ 6\right) \). המספר הבא שטרם טיפלתי בו הוא 7 שעובר לעצמו ולכן אני לא כותב אותו, וסיימנו; לא נותרו מספרים שטרם טיפלתי בהם. לכן הייצוג בעזרת מעגלים של התמורה \( \sigma \) הוא \( \left(1\ 5\ 3\right)\left(4\ 8\ 6\right) \). אין ספק שזה ייצוג קומפקטי יותר, ועדיין אפשר לדעת בקלות לאן עובר כל מספר (רוצים לדעת לאן 3 עובר? תחפשו אותו במעגל ותבדקו מי מימינו).

המעגלים שמצאתי נקראים מעגלים זרים כי אין להם מספרים משותפים. למעשה, כל המעגלים מהווים חלוקה של הקבוצה \( \left\{ 1,\dots,n\right\} \), בדומה לאופן שבו קוסטים של תת-חבורה הם חלוקה של כל אברי החבורה. כלומר, יש לנו כאן יחס שקילות מאחורי הקלעים. אתאר אותו באופן פורמלי רק בעתיד, כשנדבר על מושג בשם “פעולה של חבורה על קבוצה”; המעגלים הם מחלקות השקילות שלו. לשיטת ההצגה הזו קוראים “ייצוג באמצעות מעגלים זרים”.

מכפלת חילופים

את הרעיון הזה אפשר לקחת קדימה עוד קצת. מה זה \( \left(1\ 2\right)\left(1\ 3\right) \)? יש לנו כאן שני מעגלים, אבל הם לא מעגלים זרים כי 1 משותף לשניהם. אפשר לחשוב על הדבר הזה בתור מה שמקבלים כשלוקחים את התמורה \( \sigma \) שמעבירה את 1 ל-2 ואת 2 ל-1 ואת 3 לעצמו, וכופלים אותה בתמורה \( \tau \) שמעבירה את 1 ל-3 ואת 3 ל-1 ואת 2 לעצמו. אם כן, \( \left(1\ 2\right)\left(1\ 3\right) \) היא תמורה, אבל מה הייצוג שלה בעזרת מעגלים זרים? איך נמצא אותו?

ובכן, קודם כל ננסה להבין איך התמורה \( \left(1\ 2\right)\left(1\ 3\right) \) פועלת על 1. המוסכמה שלנו הייתה שכשכופלים שתי תמורות, מתקבלת התמורה שאופן הפעולה שלה הוא קודם כל להפעיל את התמורה הימנית במכפלה על הקלט, ואז להפעיל את התמורה השמאלית במכפלה על התוצאה. כלומר, כדי לדעת לאן \( \left(1\ 2\right)\left(1\ 3\right) \) מעבירה את 1, אנחנו קודם כל מפעילים את \( \left(1\ 3\right) \) על 1, מקבלים 3, ואז שואלים את עצמנו לאן \( \left(1\ 2\right) \) מעבירה את 3. היא מעבירה אותו לעצמו, ולכן קיבלנו שהתמורה כולה מעבירה את 1 ל-3. עכשיו אפשר לעשות את אותו הדבר גם עבור 3 וכן הלאה. כך נקבל את הייצוג של התמורה החדשה באמצעות מעגלים זרים: \( \left(1\ 2\right)\left(1\ 3\right)=\left(1\ 3\ 2\right) \) (תוודאו שזה אכן נכון).

מה שראינו כאן הוא את האופן שבו אפשר לחשב את התוצאה של כפל שתי תמורות - ואפשר לחשב גם כפל של שלוש או יותר באותו האופן. בתור אימון, בואו נחשב את \( \left(1\ 3\right)\left(1\ 2\right) \). אנחנו מתחילים שוב עם 1, ורואים שהוא עובר ל-2 ואז נשאר שם. ואנחנו רואים ש-2 עובר ל-1 ואחר כך עובר ל-3. ואנחנו רואים ש-3 עובר לעצמו בהתחלה ואחר כך ל-1. לכן קיבלנו \( \left(1\ 3\right)\left(1\ 2\right)=\left(1\ 2\ 3\right) \). שימו לב ש-\( \left(1\ 2\ 3\right)\ne\left(1\ 3\ 2\right) \), כך שאנחנו רואים פה שכפל תמורות אינו קומוטטיבי. חבורות של תמורות הן באופן כללי לא אבליות, ולכן הן מעניינות (למרות שכמובן, יש גם חבורות אבליות שאבריהן הן תמורות, למשל קחו את תת-החבורה שנוצרת על ידי \( \left(1\ 2\ 3\right) \) ב-\( S_{3} \)). מה שכן קומוטטיבי הוא מכפלה של שני מעגלים זרים (נסו להסביר לעצמכם למה).

המשוואה \( \left(1\ 3\right)\left(1\ 2\right)=\left(1\ 2\ 3\right) \) מעניינת גם כי היא מראה לנו שאפשר לכתוב מעגל של שלושה איברים בתור מכפלה של שני חילופים - חילוף זו בסך הכל תמורה של שני איברים שמחליפים מקום. האם אפשר לעשות את זה גם למעגלים גדולים יותר? באופן כללי, האם אפשר לכתוב כל תמורה בתור מכפלה של חילופים? מן הסתם ברור לנו שכן (רוב אלגוריתמי המיון מבצעים חילופים מקומיים שכאלו וזה מוביל למערך מסודר בסופו של דבר בלי קשר לכמה המערך המקורי היה מבולגן), אבל איך? אפשר לנחש שהכללה לא רעה של הדוגמה תהיה \( \left(1\ 4\right)\left(1\ 3\right)\left(1\ 2\right)=\left(1\ 2\ 3\ 4\right) \) - תבדקו ותראו שזה עובד. מכאן הדרך קצרה אל משהו כללי: \( \left(1\ n\right)\left(1\ n-1\right)\cdots\left(1\ 3\right)\left(1\ 2\right)=\left(1\ 2\ \dots\ n\right) \). למה זה עובד? פשוט מאוד: אם \( 1<k<n \) אז הוא מופיע בדיוק בחילוף אחד: \( \left(1\ k\right) \). מי שמופיע ממש לפניו הוא \( \left(1\ k+1\right) \). מכאן שהפעולה של התמורה על \( k \) היא זו: ראשית מעבירה אותו ל-1 ואחר כך מעבירה אותו משם אל \( k+1 \) ושם הוא נותר. זה בדיוק מתאים למעגל \( \left(1\ 2\ \dots\ n\right) \). עבור \( k=n \) יש רק חילוף אחד: \( \left(1\ n\right) \), ולכן אכן \( n \) יעבור אל 1. אבל מה לגבי 1 עצמו? הוא הרי מופיע בכל החילופים. איך זה מסתדר? זה דווקא החלק הקל ביותר כאן: רק החילוף הראשון משפיע עליו. הוא מעביר את 1 ל-2 וזהו; מכיוון ש-2 לא מופיע בחילופים שאחר כך, כאן נגמר הסיפור מבחינתו.

ל-1 עצמו אין מעמד קדוש כאן. היינו יכולים להשתמש בכל מספר אחר שמופיע במעגל באותה מידה. גם אין סיבה שהמספרים יהיו מסודרים מ-1 עד \( n \), זה סתם מפשט את הכתיבה. הניסוח הכללי ביותר הוא זה: אם \( \left(a_{1}\ a_{2}\ \dots\ a_{n}\right) \) הוא מעגל, אז \( \left(a_{1}\ a_{2}\ \dots\ a_{n}\right)=\left(a_{1}\ a_{n}\right)\left(a_{1}\ a_{n-1}\right)\dots\left(a_{1}\ a_{2}\right) \). כעת, מכיוון שכל תמורה אפשר לכתוב בתור מכפלת מעגלים זרים, המסקנה היא שכל תמורה אפשר לכתוב גם בתור מכפלת חילופים.

האם יש עוד דרכים להציג תמורה בתור מכפלת חילופים פרט לזו שהצגתי? בוודאי. למשל, \( \left(1\ 2\ 3\ 4\right)=\left(1\ 2\right)\left(2\ 3\right)\left(3\ 4\right) \) - באופן כללי \( \left(a_{1}\ a_{2}\ \dots\ a_{n}\right)=\left(a_{1}\ a_{2}\right)\left(a_{2}\ a_{3}\right)\dots\left(a_{n-1}\ a_{n}\right) \). הרעיון פה הוא שכל איבר פרט ל-\( a_{n} \) מתחלף קודם כל עם האיבר שגדול ממנו, ואז כבר לא יזוז עוד; רק \( a_{n} \) מתחלף על ההתחלה עם איבר שקטן ממנו, ואז מתחלף שוב ושוב ושוב עד שבסוף הוא מגיע אל \( a_{1} \). זו שיטת הצגה נוספת של מעגלים שיכולה להיות שימושים לעתים.

מה זהה בשתי שיטות ההצגה שלנו? מספר החילופים. בשתיהן כדי לייצג מעגל על \( n \) איברים נזקקנו לבדיוק \( n-1 \) חילופים. האם כל הצגה של מעגל על \( n \) איברים תהיה בהכרח בת \( n-1 \) חילופים? התשובה שלילית, כי אפשר להוסיף חילופים “מיותרים” שמבטלים זה את זה. למשל \( \left(1\ 2\ 3\right)=\left(1\ 3\right)\left(1\ 2\right)\left(2\ 3\right)\left(3\ 2\right) \). מה שכן, אנחנו רואים כאן שכדי להוסיף חילופים “מיותרים” אני צריך להוסיף זוגות של חילופים - אחד שמקלקל והשני שמתקן אותו. אם כן, יש תחושה שמשהו בכל זאת נשמר כאן: בכל פירוק של \( \sigma \) למכפלת חילופים, הזוגיות של מספר החילופים זהה. לתמורה שבפירוק כזה שלה יש מספר זוגי של חילופים קוראים תמורה זוגית ולתמורה שבה המספר הוא אי זוגי קוראים תמורה אי זוגית. ראינו כבר שמעגל מאורך \( n \) ניתן לייצוג על ידי \( n-1 \) חילופים, ולכן הכלל הוא מעגל מאורך זוגי הוא תמורה אי זוגית ומעגל מאורך אי זוגי הוא תמורה זוגית. עכשיו אפשר לדעת עבור תמורה כללית מה היא: מפרקים אותה למעגלים זרים ובודקים אם יש מספר אי זוגי של מעגלים מאורך זוגי. אם יש, התמורה אי זוגית; אחרת, היא זוגית. לפעמים נהוג לסמן \( \text{sign}\left(\sigma\right)=1 \) אם \( \sigma \) זוגית ו-\( \text{sign}\left(\sigma\right)=-1 \) אם היא אי זוגית.

המשפט שציטטתי לעיל, לפיו בכל פירוק של \( \sigma \) למכפלת חילופים הזוגיות של מספר החילופים זהה, הוא לא משפט טריוויאלי כלל; נחזור אליו בסוף הפוסט. בינתיים, הנה יישום פשוט ונחמד במיוחד שלו: משחק ה-15. הזכרתי את המשחק הזה בפוסט הראשון בבלוג והוכחתי שם שהוא לא פתיר; עם תורת החבורות אפשר לתת ניסוח קצת יותר אלגנטי של הפתרון.

ראשית, תזכורת קטנה על מה מדובר:

המשחק בנוי על לוח \( 4\times4 \) עם 15 לוחיות ממוספרות ועוד לוחית אחת חסרה. בכל צעד אנחנו מזיזים לוחית כלשהי אל המקום הפנוי של הלוחית החסרה - רעיונית, אנחנו מבצעים חילוף בין הלוחית שהזזנו ובין הלוחית החסרה. באופן הזה מתערבבים המספרים שעל הלוח, והיעד הוא להגיע ממצב של לוח מסודר למצב של לוח מסודר פרק להחלפה בין ה-14 וה-15 (זה מה שרואים באיור).

למה זה בלתי אפשרי? ובכן, בואו נחשוב על הלוח בתור תמורה חד ממדית של המספרים מ-1 עד 16, שהיא מה שמתקבל אם נקרא את השורות של הלוח אחת אחת. את הלוחית הריקה נסמן בתור לוחית מס’ 16. עכשיו כל צעד במשחק הוא כפל של התמורה הנוכחית בחילוף מהצורה \( \left(16\ n\right) \) כך ש-\( 1\le n\le15 \). התמורה ההתחלתית היא תמורת הזהות ולכן זוגית, ולכן המצב של הלוח שבו החלפנו רק את 14 ו-15 הוא תמורה אי זוגית. מכאן שבכל משחק שמוביל למצב הזה של הלוח יהיה מספר צעדים אי זוגי. מצד שני, קל לראות שאם אנחנו רוצים שלוחית מס’ 16 תהיה בקצה הימני-תחתון של הלוח גם בסיום, חייב להיות מספר מהלכים זוגי - למשל, אם נצבע את המשבצות של הלוח בשחור ולבן (עוד תעלול שהוזכר בפוסט ההוא, ביחס לחידה אחרת) נראה שכל צעד מעביר את לוחית 16 מלבן לשחור וההיפך. לכן חייבים מספר זוגי של צעדים כדי שהלוחית תגיע למשבצת באותו הצבע של המשבצת שממנה היא התחילה.

לסיום החלק הזה, הנה משחק נחמד נוסף שאפשר לבצע עם ייצוג תמורה באמצעות חילופים. נסתכל על המעגל \( \left(1\ 2\ \dots\ n\right) \). קודם ייצגנו את המעגל הזה על ידי מכפלה של חילופים שכולם היו בין איברים מתוך המעגל. אבל מה אם אנחנו רוצים סדרה של חילופים שבכל אחד מהם משתתף רק איבר אחד מהמעגל, והאיבר האחר בחילוף בכלל לא מופיע במעגל? האם זה אפשרי?

בואו נוסיף איבר חדש, \( x \), וננסה לכתוב את המעגל בעזרת חילופים שכל אחד מהם מערב את \( x \). אם סתם נכתוב \( \left(x\ n\right)\left(x\ n-1\right)\cdots\left(x\ 2\right)\left(x\ 1\right) \) נקבל את המעגל \( \left(x\ 1\ 2\ \dots\ n\right) \). אנחנו צריכים דרך כלשהי “לנטרל” את \( x \) מתוך המעגל. מה בעצם מקולקל במעגל? כל האיברים עוברים לאן שהם צריכים פרט ל-\( n \) שהולך אל \( x \) ול-\( x \) שהלך ל-1. אם אני רוצה לתקן, אני רוצה ש-\( n \) יילך אל \( 1 \), ולכן אם כרגע \( n \) הולך אל \( x \) כדאי לי לכפול משמאל ב-\( \left(x\ 1\right) \). ואכן, \( \left(x\ 1\right)\left(x\ 1\ 2\ \dots\ n\right)=\left(1\ \dots\ n\right) \).

הפתרון הזה הוא כמובן חוקי, אבל זה קל מדי - בואו נסבך עוד יותר את הדרישות שלנו. כרגע השתמשנו ב-\( \left(x\ 1\right) \) פעמיים, בהתחלה ובסוף. מה אם אסור לנו להשתמש בו יותר באופן מפורש? בואו נראה שיטה אחרת שבה אנחנו נעזרים באיבר חדש נוסף \( y \) שמאפשר לנו להמנע משימוש באותו חילוף פעמיים.

הרעיון הוא זה: נניח שכבר בנינו שני מעגלים:

\( \left(x\ 1\ \dots\ k\right) \)

\( \left(y\ k+1\ \dots\ n\right) \)

כאשר \( 1\le k\le n \) הוא איבר כלשהו. את המעגלים הללו אנחנו כבר יודעים לייצר על ידי חילופים של \( x,y \) עם האיברים המתאימים. מה שנרצה לעשות הוא “להדביק” את שני המעגלים הללו יחד תוך שאנחנו גוזרים את נקודות ההתחלה, \( x,y \). נוכל לעשות זאת על ידי כפל בשתי התמורות הבאות:

\( \left(y\ 1\right) \)

\( \left(x\ k+1\right) \)

דהיינו, אנחנו יוצרים את התמורה הכללית \( \left(x\ k+1\right)\left(y\ 1\right)\left(y\ k+1\ \dots\ n\right)\left(x\ 1\ \dots\ k\right) \). קל לראות שזה עובד ונותן לנו את \( \left(x\ y\right)\left(1\ \dots\ n\right) \). עכשיו אפשר לבטל את החילוף האחרון על ידי כפל ב-\( \left(x\ y\right) \).

המשחק הקטן הזה הוא פחות שרירותי משנראה במבט ראשון - הוא הופיע בפרק של הסדרה פיוצ’רמה בתור תסבוכת מציאותית מאוד (מציאותית בהתחשב בכך שזו סדרת מד”ב מופרעת) שהדמויות היו צריכות לפתור, והפתרון הזה אכן הופיע לשבריר שניה בפרק. כתבתי על הדבר המאוד מוצלח הזה פוסט כאן.

הצמדות

חבורות של תמורות נותנות לי הזדמנות להציג סוף סוף מושג כללי חדש שעד כה היה זנוח בצללים מכיוון שהוא חסר משמעות עבור חבורות אבליות: הצמדה של איברים. באופן כללי, אם \( G \) היא חבורה כלשהי ו-\( a,b \) איברים, אז ההצמדה של \( b \) על ידי \( a \) היא האיבר \( aba^{-1} \). אם החבורה היא אבלית אז \( aba^{-1}=aa^{-1}b=b \) ולכן הצמדה לא עושה שום דבר, אבל בחבורות כלליות היא עושה דברים מעניינים.

אם להיות הגונים, כבר דיברתי על הצמדה של תתי-חבורות: תת-חבורה הייתה נורמלית \( N \) אם ורק אם ההצמדה שלה על ידי כל איבר של \( G \) החזירה את \( N \). אבל הדיון הזה נותר אבסטרקטי כי לא היו לנו דוגמאות קונקרטיות לחבורות שבהן הצמדה עושה דברים מעניינים ברמת האיברים. ובכן, חבורות של תמורות נותנות לנו דוגמאות קונקרטיות שכאלו.

מה בכלל הרעיון בהצמדה? כדאי לחשוב על אברי החבורה שלנו בתור אובייקטים שמתארים פעולה כלשהי על מרחב כלשהו. עבור תמורות הפעולה היא לערבב את אברי הקבוצה; עבור טרנספורמציות לינאריות מעל \( \mathbb{R}^{2} \) הפעולה היא להזיז דברים במישור - למשל, לסובב/לשקף. כשאני מצמיד את \( b \) על ידי \( a \) אני אומר “הממ, מעניין איך הפעולה ש-\( b \) מתאר תשתנה אם אני אשנה את נקודת המבט שלי אפעיל את \( b \) בתוך נקודת המבט החדשה, ואז אחזור לנקודת המבט המקורית”. הנה דרך מאוד פשוטה לראות את זה: פתחו תמונה לא סימטרית כלשהי בעורך התמונות החביב עליכם. סובבו אותה ב-90 מעלות ימינה. רואים מה קיבלתם? יופי. עכשיו תחזרו לתמונה המקורית ותבצעו את הדבר הבא: קודם בצעו שיקוף אופקי; אחר כך סובבו ב-90 מעלות ימינה; אחר כך בצעו שוב שיקוף אופקי (ש”מתקן” את השיקוף המקורי). מה קיבלתם? התוצאה הסופית היא סיבוב של התמונה המקורית ב-90 מעלות שמאלה. ההצמדה של “סיבוב ב-90 מעלות ימינה” על ידי “שיקוף אופקי” גורמת לפעולה הזו להפוך לפעולה “סיבוב ב-90 מעלות שמאלה”.

נחזור לתמורות. ניקח תמורה \( \sigma \) כלשהי. מה הצמדה על ידי \( \sigma \) תעשה לתמורה אחרת? קל יותר להתחיל עם דוגמא מאשר עם הסבר מפורש. בואו ניקח את המעגל \( \left(1\ 2\ 3\right) \). הצמדה על ידי \( \sigma \) תשנה אותו באופן הבא: \( \sigma\left(1\ 2\ 3\right)\sigma^{-1}=\left(\sigma\left(1\right)\ \sigma\left(2\right)\ \sigma\left(3\right)\right) \). למשל, אם \( \sigma=\left(1\ 4\right)\left(2\ 3\right) \) אז \( \sigma\left(1\ 2\ 3\right)\sigma^{-1}=\left(4\ 3\ 2\right) \). דהיינו, אנחנו לוקחים את המעגל המקורי ומחליפים כל מספר \( k \) שמופיע בו במספר שאליו \( \sigma \) שולחת את \( k \).

המשפט הכללי הוא: אם \( \tau=\left(a_{1}\ \dots\ a_{n}\right) \) הוא מעגל כלשהו, אז \( \sigma\tau\sigma^{-1}=\left(\sigma\left(a_{1}\right)\ \dots\ \sigma\left(a_{n}\right)\right) \). איך מוכיחים את זה? על ידי חישוב מפורש. מכיוון ש-\( \sigma \) היא תמורה של \( X \), לכל איבר \( x\in X \) יש מקור, נסמן אותו \( b \): \( \sigma\left(b\right)=x \). עכשיו יש שתי אפשרויות: או ש-\( b \) מופיע במעגל \( \tau \) או שלא. אם הוא לא מופיע במעגל, אז זה אומר ש-\( \tau \) לא משנה אותו: \( \tau\left(b\right)=b \). לכן \( \sigma\tau\sigma^{-1}\left(x\right)=\sigma\left(\tau\left(\sigma^{-1}\left(\sigma\left(b\right)\right)\right)\right)=\sigma\tau\left(b\right)=\sigma\left(b\right)=x \) וקיבלנו ש-\( x \) עובר לעצמו גם ב-\( \sigma\tau\sigma^{-1} \).

לעומת זאת, אם \( b \) כן מופיע במעגל, נסמן \( b=a_{i} \) עבור האינדקס \( i \) המתאים. כעת: \( \sigma\tau\sigma^{-1}\left(x\right)=\sigma\tau\left(a_{i}\right)=\sigma\left(a_{i+1}\right) \) וקיבלנו ש-\( x=\sigma\left(a_{i}\right) \) עובר אל \( \sigma\left(a_{i+1}\right) \) (ובמקרה שבו \( i=n \), אז \( \sigma\left(a_{n}\right) \) עובר אל \( \sigma\left(a_{1}\right) \)). זה הכל. ההוכחה עצמה היא מאוד פשוטה, כשזוכרים את המשפט; ואחרי שמבינים את המשפט קל לזכור גם אותו (מה שקשה לי לזכור הוא האם הצמדה כאן היא \( \sigma\tau\sigma^{-1} \) או \( \sigma^{-1}\tau\sigma \), כפי שכותבים הצמדה לפעמים; בצורת הכתיב השניה המעגל שנקבל בסוף יהיה \( \left(\sigma^{-1}\left(a_{1}\right)\ \dots\ \sigma^{-1}\left(a_{n}\right)\right) \)).

תיארנו כאן הצמדה של מעגל בודד, אבל תמורה כללית היא מכפלה של כמה מעגלים זרים. אז מה עושים? הנה תכונה כללית של הצמדה: הצמדה של מכפלה היא מכפלת ההצמדות. פורמלית: \( ab_{1}b_{2}a^{-1}=ab_{1}a^{-1}ab_{2}a^{-1}=\left(ab_{1}a^{-1}\right)\left(ab_{2}a^{-1}\right) \). כלומר, אפשר לעשות תעלול ו”לשתול בתוך המכפלה” צמדים מהצורה \( aa^{-1} \) שמבטלים זה את זה. אם כן, כדי לדעת מהי ההצמדה של תמורה כללית מוצאים פירוק שלה למעגלים ומצמידים כל מעגל בנפרד, וסיימנו.

המסקנה שאנחנו מקבלים פה היא לא טריוויאלית. ראשית, אנחנו רואים שכל שתי תמורות שהן מעגלים הן צמודות זו לזו אם ורק אם המעגלים הם בדיוק מאותו האורך (כי הצמדה לא משנה את האורך של מעגל, אבל היא יכולה לשנות באופן שרירותי את האיברים שמופיעים בו). מכאן ששתי תמורות כלליות הן צמודות אם ורק אם בפירוק שלהן למעגלים זרים, לכל אורך אפשרי של מעגל, אותו מספר של מעגלים מהאורך הזה מופיע בשני הפירוקים. המשפט האחרון הוא מסורבל, אז הנה דרך יותר נוחה לנסח אותו: נגדיר את המבנה המעגלי של תמורה \( \sigma \) בתור סדרה ממויינת של מספרים טבעיים שמתאימים לאורכי המעגלים בפירוק (היחיד) של \( \sigma \) למכפלת מעגלים זרים. למשל, אם \( \sigma\in S_{8} \) היא התמורה \( \left(2\ 3\ 4\right)\left(5\ 6\right)\left(7\ 8\right) \) אז המבנה המעגלי שלה הוא הסדרה \( 1,2,2,3 \) שבא לומר שיש לנו מעגל אחד מאורך 1 (\( \left(1\right) \) שלא כתבתי במפורש), שניים מאורך 2 (\( \left(5\ 6\right) \) ו-\( \left(7\ 8\right) \)) ואחד מאורך 3 ((\( 2\ 3\ 4 \))). כעת, שתי תמורות הן צמודות אם ורק אם יש להן את אותו מבנה מעגלי (לפעמים מתארים מבנה מעגלי גם על ידי סדרה שבה האיבר באינדקס \( k \) אומר כמה מעגלים מאורך \( k \) יש לנו, אבל אני אוהב את שיטת הייצוג הזו הרבה פחות).

למשל ב-\( S_{4} \) התמורות הן על ארבעה איברים. מה המבנים המעגליים האפשריים? זה בעצם שקול לשאלה מה הדרכים השונות לכתוב את 4 כסכום של טבעיים חיוביים. כל דרך נותנת לנו מבנה מעגלים שונה. פתרונות אפשריים נותנים לנו את המבנה המעגלי \( 1,1,1,1 \) (מתאים לתמורת הזהות), את המבנה המעגלי \( 1,1,2 \) (מתאים לחילוף בודד), את המבנה המעגלי \( 2,2 \) (מתאים ל-\( \left(1\ 2\right)\left(3\ 4\right) \) למשל), את \( 1,3 \) (מתאים למשל ל-\( \left(1\ 2\ 3\right) \)) ואת \( 4 \) (מתאים למשל ל-\( \left(1\ 2\ 3\ 4\right) \)). אנחנו רואים, אם כך, למשל שכל האיברים בקבוצה \( \left\{ \left(1\ 2\right)\left(3\ 4\right),\left(1\ 3\right)\left(2\ 4\right)(,\left(1\ 4\right)\left(2\ 3\right)\right\} \) הם צמודים. שימו לב שהקבוצה הזו היא לא תת-חבורה; באופן כללי מחלקות צמידות שכאלו הן לא תת-חבורות ורוב תת-החבורות לא סגורות להצמדה. זה דבר חיובי - זה אומר שהנה, יש לנו עוד דרך חדשה ומעניינת לפרק חבורות (לא אבליות) לגורמים. אני אדבר על זה יותר בהמשך, כשאגיע לפעולה של חבורה על קבוצה.

ולסיום, המשפט על הפירוק לחילופים

אנחנו רוצים לראות עכשיו הוכחה לטענה שלי לפיה בכל פירוק של תמורה למכפלת חילופים, מספר החילופים הוא תמיד זוגי או שהוא תמיד אי זוגי. כל ההוכחות שאני מכיר הן בבסיסן אותו הדבר (או שהן מסתמכות על המושג של דטרמיננטה של מטריצה שבתורו מסתמך על מושג הזוגיות של תמורות שהוא לא מוגדר היטב בלי המשפט הזה) וההתלבטות הייתה האם להציג גרסה מפושטת של ההוכחה שמפספסת חלק מהרעיון או את ההוכחה שנותנת את התמונה הרחבה יותר. בסוף החלטתי ללכת על ההוכחה שנותנת את התמונה הרחבה יותר, ואני מקווה שכל מי ששרד עד כאן ישרוד גם את ההוכחה הזו, שהיא בסופו של דבר די נחמדה.

ההוכחה בנויה על שלושה שלבים:

1. מגדירים פונקציה \( \varepsilon:S_{n}\to\left\{ 1,-1\right\} \) בצורה שנראית קצת מוזרה במבט ראשון.
2. מוכיחים שהפונקציה הזו היא הומומורפיזם (כאן \( \left\{ 1,-1\right\} \) היא חבורה ביחס לפעולת הכפל הרגילה).
3. מוכיחים שעל כל חילוף, \( \varepsilon \) מחזירה \( -1 \).

בהינתן שלושת אלו, התוצאה שהזכרתי לעיל נובעת מעצמה: אם \( \sigma=\tau_{1}\cdots\tau_{k} \) כאשר \( \tau_{1},\dots,\tau_{k} \) הם חילופים, אז \( \varepsilon\left(\sigma\right)=\varepsilon\left(\tau_{1}\right)\cdots\varepsilon\left(\tau_{k}\right)=\left(-1\right)^{k} \), ומכאן שאם יש ל-\( \sigma \) הצגה בתור \( k_{1} \) חילופים וגם בתור \( k_{2} \) חילופים אז \( \left(-1\right)^{k_{1}}=\left(-1\right)^{k_{2}} \), דהיינו \( k_{1}\equiv k_{2}\left(\text{mod 2}\right) \).

השיטה של שימוש ב-\( \varepsilon \) היא בעלת יתרון נוסף - היא מאפשרת לנו להגדיר בקלות תת-חבורה \( A_{n}\triangleq\ker\varepsilon \) ומכיוון שהיא מוגדרת כגרעין, גם ברור שהיא נורמלית. החבורה הזו - “חבורת התמורות הזוגיות”, ובאנגלית Alternating Group, היא בעלת חשיבות גדולה בזכות עצמה וכנראה שעוד נדבר עליה בעתיד.

נותר רק להסביר איך \( \varepsilon \) מוגדרת. הנה הגדרה חצי פורמלית: \( \varepsilon\left(\sigma\right) \) שווה ל-\( -1 \) בחזקת מספר הפרות הסדר שב-\( \sigma \). מה זו הפרת סדר? זה כל זוג מספרים \( 1\le i<j\le n \) כך ש-\( \sigma\left(i\right)>\sigma\left(j\right) \). כלומר, מספרים שאם הרשימה הייתה ממויינת היו צריכים להופיע בסדר הפוך. לדוגמא, ברשימה \( 2,1,5,3,4 \) ברור לנו שהעובדה ש-2 בא לפני 1 היא “קלקול” של המיון של הרשימה, אבל 2 לא עושה צרות עם איברים אחרים ברשימה. לעומת זאת, 5 עושה צרות גם עם 3 וגם עם 4 והוא צריך להופיע אחרי שניהם. סך הכל יש לנו פה 3 הפרות סדר.

כל זה טוב ויפה, אבל זו לא הגדרה פורמלית כל כך. היא בוודאי יותר “קומבינטורית” באופיה מאשר אלגברית. הנה דרך פורמלית אלגברית להגדיר את זה שאני מקווה שלא תפחיד אתכם יותר מדי. בואו נגדיר איברים \( x_{1},\dots,x_{n} \). את האיברים הללו אפשר לחבר ולחסר ולכפול: אנחנו מקבלים פולינום במספר משתנים באופן הזה. פולינום בשני משתנים קל לנו להבין, למשל אני מקווה שלכולם נוח עם \( xy+y+3x \) וכדומה. אז כאן יש לנו את אותו דבר רק עם \( n \) משתנים שונים.

מה שעושים כעת הוא להסתכל על הפולינום הבא: \( \Delta=\prod_{1\le i<j\le n}\left(x_{i}-x_{j}\right) \). הנה דוגמא לפולינום הזה עבור \( n=4 \):

\( \Delta=\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right)\left(x_{1}-x_{4}\right)\left(x_{2}-x_{3}\right)\left(x_{2}-x_{4}\right)\left(x_{3}-x_{4}\right) \)

כעת, תהא \( \sigma \) תמורה כלשהי. נגדיר \( \sigma\left(x_{i}\right)=x_{\sigma\left(i\right)} \). אפשר לראות (כאן אני מנפנף בידיים קצת!) שעכשיו מתקיים:

\( \sigma\left(\Delta\right)=\prod_{1\le i<j\le n}\left(x_{\sigma\left(i\right)}-x_{\sigma\left(j\right)}\right) \)

מכיוון ש-\( \sigma \) היא חח”ע ועל, נובע שלכל זוג \( 1\le i<j\le n \) או ש-\( x_{i}-x_{j} \) או ש-\( x_{j}-x_{i} \) יופיע היכן שהוא ב-\( \sigma\left(\Delta\right) \), ומכאן ש-\( \frac{\sigma\left(\Delta\right)}{\Delta}=\pm1 \). מכאן שאפשר להגדיר \( \varepsilon\left(\sigma\right)=\frac{\sigma\left(\Delta\right)}{\Delta} \). יש בהגדרה המוזרה הזו אלגנטיות גדולה מאוד, אבל אני לא ארחיב על זה הפעם (למי שכן מכיר, שימו לב כמה זה דומה למה שקורה במשפט הילברט 90).

עיקר הקושי בהוכחה שלנו הוא להראות ש-\( \varepsilon \) היא הומומורפיזם. אנחנו לוקחים תמורות \( \sigma,\tau \) כלשהן וצריכים להסתכל על תמורת ההרכבה שלהן ומה שהיא עושה ל-\( \Delta \), דהיינו לחשב את \( \frac{\left(\tau\sigma\right)\left(\Delta\right)}{\Delta} \) ולהראות שזה יוצא \( \varepsilon\left(\tau\right)\varepsilon\left(\sigma\right) \).

כבר ראינו ש-\( \varepsilon\left(\sigma\right)=\frac{\sigma\left(\Delta\right)}{\Delta} \) ולכן על ידי כפל ב-\( \Delta \) נקבל ש-\( \sigma\left(\Delta\right)=\varepsilon\left(\sigma\right)\Delta \). כעת, על פי הגדרה, \( \left(\tau\sigma\right)\left(\Delta\right)=\tau\left(\sigma\left(\Delta\right)\right)=\tau\left(\varepsilon\left(\sigma\right)\Delta\right)=\varepsilon\left(\sigma\right)\tau\left(\Delta\right)=\varepsilon\left(\sigma\right)\varepsilon\left(\tau\right)\Delta \) וסיימנו (בשביל הצדקה פורמלית ממש אולי צריך לעבוד עוד טיפה).

לסיום, אנחנו רוצים לחשב את \( \varepsilon \) על חילוף \( \sigma \) כלשהו. אם ננסה לטפל ב-\( \sigma=\left(i\ j\right) \) עבור \( i,j \) כלליים זה יצריך מאיתנו קצת פנקסנות כי הרבה גורמים הולכים להשתנות בצורה רלוונטית. לכן בואו נטפל ב-\( \left(1\ 2\right) \) קודם כל. ברור ש-\( \varepsilon\left(\left(1\ 2\right)\right)=-1 \) כי הגורם \( x_{1}-x_{2} \) יתהפך ל-\( x_{2}-x_{1} \) בעוד שאר הגורמים (שהם תמיד מהצורה \( \left(x_{1}-x_{k}\right) \) ו-\( \left(x_{2}-x_{k}\right) \)) לא יתהפכו. עכשיו, בואו ננצל את זה שכבר הוכחנו ש-\( \varepsilon \) הוא הומומורפיזם כדי לטפל בתמורה \( \left(i\ j\right) \) כלשהי: נגדיר \( \tau=\left(1\ i\right)\left(2\ j\right) \), אז \( \left(1\ 2\right)=\tau\left(i\ j\right)\tau \) (בדקו זאת!) ולכן \( -1=\varepsilon\left(\left(1\ 2\right)\right)=\varepsilon\left(\tau\right)^{2}\varepsilon\left(i\ j\right)=\varepsilon\left(i\ j\right) \).

ההוכחה הזו טכנית, כפי שהיה רוב הפוסט הזה, אבל אני חושב שיש הרבה אלגנטיות בטכניקה הזו. ככה זה עם תמורות באופן כללי, גם בהמשך.