תמורות

בקצרה: תמורה היא סידור מחדש של המספרים [math]\displaystyle{ 1,\dots,n }[/math], ופורמלית - פונקציה הפיכה (חד-חד-ערכית ועל) מהקבוצה [math]\displaystyle{ \{1,\dots,n\} }[/math] לעצמה. לכל תמורה מוצמד סימן [math]\displaystyle{ sign(f)=\pm1 }[/math] המבטא אם דרוש מספר זוגי או אי-זוגי של חילופים כדי לבנות אותה, וסימן זה הוא אבן היסוד להגדרת הדטרמיננטה.

תמורות נכנסות לתמונה בתחילת פרק הדטרמיננטות: לפני שמגדירים דטרמיננטה של מטריצה ריבועית, צריך קודם להבין מהי תמורה של המספרים [math]\displaystyle{ 1,\dots,n }[/math], מהו אוסף כל התמורות [math]\displaystyle{ S_n }[/math], וכיצד מצמידים לכל תמורה סימן [math]\displaystyle{ \pm1 }[/math]. הסימן משמש בהמשך ישירות בנוסחת הדטרמיננטה [math]\displaystyle{ det(A)=\sum_{f\in S_n}sign(f)\prod_{i=1}^n[A]_{i,f(i)} }[/math], ולכן חשוב לדעת לחשב אותו במהירות - בעזרת חילופים ומחזורים - ולא רק לפי ההגדרה הפורמלית שדורשת מעבר על כל הזוגות האפשריים.

הגדרה

• תמורה על הקבוצה [math]\displaystyle{ \{1,2,\dots,n\} }[/math] היא פונקציה הפיכה (חד-חד-ערכית ועל) מהקבוצה לעצמה, כלומר סידור מחדש של המספרים [math]\displaystyle{ 1,\dots,n }[/math].
• אוסף התמורות [math]\displaystyle{ S_n }[/math] הוא קבוצת כל הפונקציות ההפיכות מהקבוצה [math]\displaystyle{ \{1,2,...,n\} }[/math] לעצמה.
• [math]\displaystyle{ n! }[/math] ("[math]\displaystyle{ n }[/math] עצרת") הוא כמות התמורות ב-[math]\displaystyle{ S_n }[/math], כלומר [math]\displaystyle{ |S_n|=n! }[/math]. לפי ההגדרה [math]\displaystyle{ 0!=1 }[/math]: הפונקציה היחידה מהקבוצה הריקה לעצמה (זו שאינה שולחת אף איבר לשום מקום) היא אכן פונקציה הפיכה, ולכן יש בדיוק דרך אחת "לסדר" אפס איברים.
• לכל תמורה (פונקציה) [math]\displaystyle{ f\in S_n }[/math] נגדיר את סימן התמורה [math]\displaystyle{ sign(f)=\prod_{i<j}\frac{f(j)-f(i)}{j-i} }[/math] (המכפלה על כל הזוגות [math]\displaystyle{ 1\leq i<j\leq n }[/math]).
• תמורה נקראת חיובית או זוגית אם סימנה שווה [math]\displaystyle{ 1 }[/math], ושלילית או אי-זוגית אם סימנה שווה מינוס [math]\displaystyle{ 1 }[/math].
• חילוף הוא תמורה [math]\displaystyle{ (i\ j)\in S_n }[/math] המחליפה בין האיברים [math]\displaystyle{ i,j }[/math] ושולחת את שאר האיברים לעצמם.
• מחזור [math]\displaystyle{ (p_1\ p_2\ \cdots\ p_k) }[/math], כאשר [math]\displaystyle{ p_1,\dots,p_k }[/math] הם [math]\displaystyle{ k }[/math] איברים שונים מתוך [math]\displaystyle{ \{1,\dots,n\} }[/math] (לאו דווקא בסדר עולה), הוא התמורה [math]\displaystyle{ (p_1\ p_2\ \cdots\ p_k)=(p_1\ p_2)\circ(p_2\ p_3)\circ\cdots\circ(p_{k-1}\ p_k) }[/math]. בפועל המחזור שולח כל איבר [math]\displaystyle{ p_{i-1} }[/math] ל-[math]\displaystyle{ p_i }[/math], שולח את [math]\displaystyle{ p_k }[/math] ל-[math]\displaystyle{ p_1 }[/math], ואת כל איבר שאינו אחד מ-[math]\displaystyle{ p_1,\dots,p_k }[/math] משאיר במקומו.
• כתיב דו-שורתי: נהוג לרשום תמורה [math]\displaystyle{ \sigma\in S_n }[/math] בשתי שורות, כשמתחת לכל מספר רשומה התמונה שלו: [math]\displaystyle{ \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n)\end{pmatrix} }[/math]. למשל, התמורה ב-[math]\displaystyle{ S_3 }[/math] שמחליפה בין 1 ל-2 היא [math]\displaystyle{ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3\end{pmatrix}=(1\ 2) }[/math].

משפטים ותכונות

• כפליות הסימן: לכל שתי תמורות [math]\displaystyle{ f,g\in S_n }[/math] מתקיים [math]\displaystyle{ sign(f\circ g)=sign(f)\cdot sign(g) }[/math].

הוכחה: לפי ההגדרה [math]\displaystyle{ sign(f\circ g)=\prod_{i<j}\dfrac{f(g(j))-f(g(i))}{j-i} }[/math]. מכפילים ומחלקים באותו ביטוי חדש ומקבלים [math]\displaystyle{ \displaystyle\prod_{i<j}\frac{f(g(j))-f(g(i))}{g(j)-g(i)}\cdot\prod_{i<j}\frac{g(j)-g(i)}{j-i} }[/math] (אין חשש מחלוקה באפס, כי [math]\displaystyle{ g }[/math] חד-חד-ערכית). המכפלה השנייה היא בדיוק [math]\displaystyle{ sign(g) }[/math] לפי ההגדרה. במכפלה הראשונה, מכיוון ש-[math]\displaystyle{ g }[/math] חד-חד-ערכית ועל, הזוגות [math]\displaystyle{ \big(g(i),g(j)\big) }[/math] עוברים בדיוק על כל הזוגות האפשריים (בסדר אחר), ולכן המכפלה הראשונה שווה ל-[math]\displaystyle{ sign(f) }[/math]. סך הכל [math]\displaystyle{ sign(f\circ g)=sign(f)\cdot sign(g) }[/math].

• סימן הזהות: עבור תמורת הזהות [math]\displaystyle{ I\in S_n }[/math] (זו שאינה מזיזה אף איבר) מתקיים [math]\displaystyle{ sign(I)=1 }[/math].

הוכחה: לכל זוג [math]\displaystyle{ i<j }[/math] מתקיים [math]\displaystyle{ I(j)-I(i)=j-i }[/math], כך שכל גורם במכפלה שווה [math]\displaystyle{ 1 }[/math].

• סימן חילוף: חילוף הוא תמיד תמורה שלילית (אי-זוגית): [math]\displaystyle{ sign\big((p_1\ p_2)\big)=-1 }[/math] לכל שני איברים שונים [math]\displaystyle{ p_1,p_2 }[/math]. (הוכחה בהרצאה - באמצעות סידור מתאים של כל הזוגות לפי מעורבות [math]\displaystyle{ p_1,p_2 }[/math] וצמצום שיטתי של המונים והמכנים).

• סימן מחזור: סימנו של מחזור באורך [math]\displaystyle{ k }[/math] הוא [math]\displaystyle{ (-1)^{k-1} }[/math].

הוכחה: מחזור מוגדר כהרכבה של [math]\displaystyle{ k-1 }[/math] חילופים, ולפי כפליות הסימן וכך שסימן כל חילוף הוא [math]\displaystyle{ -1 }[/math], מתקבל [math]\displaystyle{ (-1)^{k-1} }[/math].

שימו לב לבלבול אפשרי: הזוגיות של מספר האיברים במחזור היא ההפך מזוגיות התמורה עצמה - מחזור באורך זוגי הוא תמורה שלילית (אי-זוגית), ומחזור באורך אי-זוגי הוא תמורה חיובית (זוגית).

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

שיטה / איך מחשבים

כדי לחשב את [math]\displaystyle{ sign(f) }[/math] של תמורה [math]\displaystyle{ f\in S_n }[/math] בלי לעבור על כל הזוגות לפי ההגדרה:

1. בוחרים את האיבר הקטן ביותר שעדיין לא טופל, ועוקבים אחרי הפעולה של [math]\displaystyle{ f }[/math] החל ממנו: [math]\displaystyle{ x,\ f(x),\ f(f(x)),\dots }[/math] עד שחוזרים בחזרה ל-[math]\displaystyle{ x }[/math]. זהו מחזור אחד בפירוק.
2. חוזרים על כך עם האיבר הקטן ביותר שנותר, וממשיכים עד שכל האיברים מטופלים - כולל איברים שנשארים במקומם, שנחשבים ל"מחזור" באורך [math]\displaystyle{ 1 }[/math] וסימנו [math]\displaystyle{ (-1)^0=1 }[/math].
3. לכל מחזור באורך [math]\displaystyle{ k }[/math] שהתקבל, סימנו הוא [math]\displaystyle{ (-1)^{k-1} }[/math].
4. מכפילים את סימני כל המחזורים (לפי כפליות הסימן) ומקבלים את [math]\displaystyle{ sign(f) }[/math].

בפועל, מספיק לספור כמה מחזורים באורך זוגי יש בפירוק: אם המספר הזה זוגי - [math]\displaystyle{ f }[/math] חיובית; אם אי-זוגי - [math]\displaystyle{ f }[/math] שלילית (מחזור באורך אי-זוגי תמיד תורם [math]\displaystyle{ 1 }[/math] לסימן ואינו משנה את התוצאה).

דוגמאות

דוגמה 1 (חישוב ישיר לפי ההגדרה): תהי [math]\displaystyle{ f\in S_4 }[/math] המוגדרת ע"י [math]\displaystyle{ f(1)=3,\ f(2)=1,\ f(3)=2,\ f(4)=4 }[/math]. נחשב את [math]\displaystyle{ sign(f) }[/math] על כל הזוגות [math]\displaystyle{ i<j }[/math]:

[math]\displaystyle{ sign(f)=\frac{f(2)-f(1)}{2-1}\cdot\frac{f(3)-f(1)}{3-1}\cdot\frac{f(4)-f(1)}{4-1}\cdot\frac{f(3)-f(2)}{3-2}\cdot\frac{f(4)-f(2)}{4-2}\cdot\frac{f(4)-f(3)}{4-3}=\frac{-2}{1}\cdot\frac{-1}{2}\cdot\frac{1}{3}\cdot\frac{1}{1}\cdot\frac{3}{2}\cdot\frac{2}{1}=1 }[/math]

כלומר [math]\displaystyle{ f }[/math] חיובית (זוגית). ואכן, אפשר להגיע מ-[math]\displaystyle{ f }[/math] לזהות בשני חילופים בדיוק: קודם מחליפים את האיבר שבמקום [math]\displaystyle{ 1 }[/math] עם זה שבמקום [math]\displaystyle{ 3 }[/math], ואז מחליפים בין המקומות שנותרו לא מסודרים - שני חילופים, בהתאמה לסימן החיובי.

דוגמה 2 (מהמחזור אל התמורה): מהי התמורה שמייצג המחזור [math]\displaystyle{ (4\ 2\ 6\ 3) }[/math] ב-[math]\displaystyle{ S_6 }[/math]? לפי ההגדרה, המחזור שולח [math]\displaystyle{ 4\to2,\ 2\to6,\ 6\to3,\ 3\to4 }[/math], ואת האיברים [math]\displaystyle{ 1,5 }[/math] שאינם מוזכרים בו - לעצמם. כלומר [math]\displaystyle{ f(1)=1,\ f(2)=6,\ f(3)=4,\ f(4)=2,\ f(5)=5,\ f(6)=3 }[/math]. זהו מחזור אחד באורך [math]\displaystyle{ 4 }[/math], ולכן [math]\displaystyle{ sign(f)=(-1)^{4-1}=-1 }[/math].

דוגמה 3 (בדיקת סימן חילוף): נבדוק את המשפט "חילוף הוא תמורה שלילית" על החילוף [math]\displaystyle{ (1\ 3)\in S_3 }[/math], כלומר [math]\displaystyle{ f(1)=3,\ f(2)=2,\ f(3)=1 }[/math]:

[math]\displaystyle{ sign(f)=\frac{f(2)-f(1)}{2-1}\cdot\frac{f(3)-f(1)}{3-1}\cdot\frac{f(3)-f(2)}{3-2}=\frac{-1}{1}\cdot\frac{-2}{2}\cdot\frac{-1}{1}=-1 }[/math]

בהתאם למשפט.

דוגמה 4 (פירוק תמורה גדולה למחזורים): תהי [math]\displaystyle{ f\in S_7 }[/math] כך ש-[math]\displaystyle{ 1\to3,\ 3\to4,\ 4\to1 }[/math] וכן [math]\displaystyle{ 2\to7,\ 7\to5,\ 5\to6,\ 6\to2 }[/math]. עוקבים אחרי [math]\displaystyle{ 1 }[/math] ומקבלים את המחזור [math]\displaystyle{ (1\ 3\ 4) }[/math] (אורך [math]\displaystyle{ 3 }[/math]), ועוקבים אחרי [math]\displaystyle{ 2 }[/math] ומקבלים את המחזור הזר [math]\displaystyle{ (2\ 7\ 5\ 6) }[/math] (אורך [math]\displaystyle{ 4 }[/math]). שני המחזורים זרים, ולכן [math]\displaystyle{ f=(1\ 3\ 4)\circ(2\ 7\ 5\ 6) }[/math] ומתקבל מיד

[math]\displaystyle{ sign(f)=(-1)^{3-1}\cdot(-1)^{4-1}=1\cdot(-1)=-1 }[/math]

בלי לחשב ולו זוג אחד לפי ההגדרה המקורית.

שאלות תרגול

שאלה 1. תהי [math]\displaystyle{ f\in S_5 }[/math] המוגדרת ע"י [math]\displaystyle{ f(1)=2,\ f(2)=4,\ f(3)=1,\ f(4)=5,\ f(5)=3 }[/math]. פרקו את [math]\displaystyle{ f }[/math] למחזורים זרים וחשבו את [math]\displaystyle{ sign(f) }[/math].

פתרון

עוקבים אחרי [math]\displaystyle{ 1 }[/math]: [math]\displaystyle{ 1\to2\to4\to5\to3\to1 }[/math]. זהו מחזור יחיד באורך [math]\displaystyle{ 5 }[/math] הכולל את כל האיברים: [math]\displaystyle{ f=(1\ 2\ 4\ 5\ 3) }[/math]. לכן [math]\displaystyle{ sign(f)=(-1)^{5-1}=1 }[/math] - תמורה חיובית.

שאלה 2. הוכיחו שלכל [math]\displaystyle{ f\in S_n }[/math] מתקיים [math]\displaystyle{ sign(f^{-1})=sign(f) }[/math].

פתרון

[math]\displaystyle{ f\circ f^{-1}=I }[/math], ולפי כפליות הסימן [math]\displaystyle{ sign(f)\cdot sign(f^{-1})=sign(I)=1 }[/math]. מכיוון ש-[math]\displaystyle{ sign(f)\in\{1,-1\} }[/math] מתקיים [math]\displaystyle{ \frac{1}{sign(f)}=sign(f) }[/math], ולכן [math]\displaystyle{ sign(f^{-1})=sign(f) }[/math].

שאלה 3. ידוע כי [math]\displaystyle{ f\in S_6 }[/math] ניתנת להצגה כהרכבה של [math]\displaystyle{ 4 }[/math] חילופים. האם ייתכן שהיא ניתנת להצגה גם כהרכבה של [math]\displaystyle{ 3 }[/math] חילופים? נמקו.

פתרון

לא. לפי כפליות הסימן, הרכבה של [math]\displaystyle{ 4 }[/math] חילופים נותנת [math]\displaystyle{ sign(f)=(-1)^4=1 }[/math]. אילו הייתה [math]\displaystyle{ f }[/math] גם הרכבה של [math]\displaystyle{ 3 }[/math] חילופים, היינו מקבלים [math]\displaystyle{ sign(f)=(-1)^3=-1 }[/math] - בסתירה לכך שלתמורה [math]\displaystyle{ f }[/math] יש סימן יחיד ומוגדר היטב. לכן זוגיות מספר החילופים בכל הצגה אפשרית של [math]\displaystyle{ f }[/math] כהרכבת חילופים היא קבועה, וקובעת בדיוק את [math]\displaystyle{ sign(f) }[/math].

שאלה 4. חשבו את סימנה של התמורה [math]\displaystyle{ f\in S_7 }[/math] הנתונה כהרכבת המחזורים הזרים [math]\displaystyle{ (1\ 3)\circ(2\ 5\ 4)\circ(6\ 7) }[/math].

פתרון

אורכי המחזורים הם [math]\displaystyle{ 2,3,2 }[/math], ולכן סימניהם הם [math]\displaystyle{ (-1)^1=-1,\ (-1)^2=1,\ (-1)^1=-1 }[/math] בהתאמה. לפי כפליות הסימן: [math]\displaystyle{ sign(f)=(-1)\cdot1\cdot(-1)=1 }[/math] - תמורה חיובית.

טעויות נפוצות

• לבלבל בין זוגיות "מספר האיברים" במחזור לבין זוגיות "התמורה" עצמה: מחזור באורך [math]\displaystyle{ k }[/math] תורם סימן [math]\displaystyle{ (-1)^{k-1} }[/math], כלומר מחזור באורך זוגי הוא תמורה שלילית ומחזור באורך אי-זוגי הוא תמורה חיובית - הפוך ממה שאינטואיטיבית עשויים לחשוב.
• לשכוח שתמורה יכולה להיות מיוצגת כהרכבת חילופים בדרכים רבות ושונות, אך זוגיות מספר החילופים בכל פירוק כזה תמיד זהה, ושווה לזוגיות שקובע הסימן - לא ניתן "להתחמק" ולקבל זוגיות אחרת.
• לנסות לחשב את סימן התמורה ישירות לפי ההגדרה (מכפלה על כל הזוגות [math]\displaystyle{ i<j }[/math]) גם כשהתמורה גדולה - זה מסורבל ומועד לטעויות; עדיף תמיד לפרק למחזורים זרים ולהשתמש בכפליות הסימן.
• לשכוח לכלול איברים שנשארים במקומם ("נקודות שבת") כשבונים את פירוק המחזורים, או לחשוב בטעות שכל תמורה היא מחזור בודד אחד.
• להתבלבל בסדר ההרכבה: מרכיבים פונקציות מימין לשמאל (קודם פועלת הפונקציה הימנית), וכך גם במחזור - יש לעקוב אחרי הסדר [math]\displaystyle{ (p_1\ p_2)\circ(p_2\ p_3)\circ\cdots }[/math] בזהירות.

שאלות ממבחנים

• מועד א' קיץ תשע"ו, שאלה 6א — מבחן · פתרון (חישוב A^2016 ו-A^2017 עבור מטריצת תמורה (permutation) מחזורית נתונה)
• מבחן מועד א' קיץ תשע"ב, שאלה חלק ב' - שאלה 9 — מבחן (דטרמיננטת מטריצת המעבר בין בסיס B לבסיס B' המתקבל מהחלפת סדר האיברים לפי תמורה)

הרשימה המלאה, לפי מבחן ולפי נושא: אלגברה לינארית 1/אינדקס שאלות.

סרטונים

בהרצאה זו מוגדרות התמורות ואוסף התמורות [math]\displaystyle{ S_n }[/math], מוסברת העצרת (כולל [math]\displaystyle{ 0!=1 }[/math]), מוגדר סימן התמורה, ומוכחות כפליות הסימן וכך שסימן הזהות הוא [math]\displaystyle{ 1 }[/math]:

בהרצאה זו מוגדרים חילוף ומחזור, מוכח שסימן חילוף הוא תמיד שלילי וכי סימן מחזור באורך [math]\displaystyle{ k }[/math] הוא [math]\displaystyle{ (-1)^{k-1} }[/math], ומוצגת שיטת פירוק תמורה למחזורים זרים לחישוב מהיר של הסימן: