מטריצת תמורה

בתורת המטריצות, מטריצת תמורה היא מטריצה ריבועית בינארית שמכילה בדיוק אחדה אחת בכל שורה ובכל עמודה ואפסים בכל המקומות האחרים. כל מטריצה $P$ כזאת מייצגת תמורה של $m$ איברים, וכאשר מכפילים אותה במטריצה אחרת $A$, גורמת לערבוב השורות (בכפל מלפני, כלומר $PA$) או העמודות (בכפל מאחרי, כלומר $AP$) של המטריצה $A$.

כיוון שבמטריצת תמורה יש בדיוק אחדה אחת בכל שורה או עמודה, ניתן להיעזר בדימוי מתחום השחמט כדי להבין איך היא נראית; אוסף מטריצות התמורות נמצא בהתאמה חד-חד ערכית עם אוסף ההעמדות של $m$ צריחים על לוח בגודל $m\times m$ כך שאף אחד לא יאיים על השני, כאשר מיקומי הצריחים מתאימים למיקומי האחדות במטריצות התמורה. מקומבינטוריקה עולה שיש $m!$ מטריצות תמורה, כגודל החבורה הסימטרית $S_{m}$.

הגדרה

בהינתן תמורה $\pi$ של $m$ איברים,

$\pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace$

המיוצגת בסימון שתי שורות כ-

${\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}}$

ישנן שתי דרכים טבעיות לקשר בין תמורה למטריצת תמורה; כאשר מתחילים ממטריצת הזהות מסדר $m\times m$, כלומר $I_{m}$, אז ניתן לבצע תמורה על עמודות או שורות המטריצה, בהתאם ל-$\pi$. מאמר זה ידון רק באחת מההצגות הללו, כאשר האחרת תוזכר רק אם יש הבדל ביניהן שיש להיות מודעים אליו.

למטריצת התמורה מסדר $m\times m$, כלומר $P_{\pi }=(p_{ij})$, המתקבלת מערבוב העמודות של מטריצת הזהות $I_{m}$, כלומר הפועלת כך שלכל $i$, מתקיים $p_{ij}=1$ אם $j=\pi (i)$ ו-0 אחרת, נתייחס כהצגת העמודות בערך זה. כיוון שהאיברים בשורה $i$ כולם 0 למעט ה-1 שמופיע בעמודה $\pi (i)$, ניתן לכתוב

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}}$

כאשר $\mathbf {e} _{j}$, וקטור בסיס סטנדרטי, מסמן וקטור שורה באורך $m$ עם 1 במיקום ה-$j$ ו-0 בכל מיקום אחר.

לדוגמה, מטריצת התמורה $P_{\pi }$ המתאימה לתמורה: $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}},$, היא:

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.$

ניתן להבחין בכך שהעמודה ה-$j$ של מטריצת הזהות $I_{5}$ מופיעה כעת כעמודה ה-$\pi (j)$ של $P_{\pi }$.

תכונות אלגבריות

הכפלת $P_{\pi }$ בווקטור עמודה g תערבב את השורות של הווקטור:

$P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\g_{\pi (2)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}.$

שימוש חוזר בתוצאה הזאת מראה שאם $M$ היא מטריצה במידות מתאימות, המכפלה $P_{\pi }M$ היא פשוט תמורה של השורות של $M$.

המטריצה ההופכית של מטריצה תמורה שווה למטריצה המשוחלפת שלה, כלומר: $P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{\mathsf {T}}$.

העקבה של מטריצת תמורה היא מספר נקודות השבת של התמורה. אם למטריצה יש נקודות שבת, אז היא ניתנת לכתיבה בצורה ציקלית כ-$\pi =(a_{1})(a_{2})\dots (a_{k})\sigma$, כאשר $\sigma$ היא תמורה ללא נקודות שבת, ו-$e_{a_{1}},e_{a_{2}},\dots ,e_{a_{k}}$ הם וקטורים עצמיים של מטריצת התמורה (אלו הם וקטורי השבת).

כדי לחשב את הערכים העצמיים של מטריצת תמורה נתונה $P_{\sigma }$, נכתוב את $\sigma$ כמכפלה של תמורות ציקליות, כלומר $\sigma =C_{1}C_{2}\cdots C_{t}$. יהיו האורכים של המחזורים הללו $l_{1},l_{2}...l_{t}$ בהתאמה, ויהי $R_{i}(1\leq i\leq t)$ אוסף הפתרונות המרוכבים של $x^{l_{i}}=1$ (כלומר שורשי היחידה מסדר $l_{i}$). אז האיחוד של כל ה-$R_{i}$-ים הוא אוסף הערכים העצמיים של מטריצת התמורות המתאימה. הריבוב הגאומטרי של כל ערך עצמי שווה למספר ה-$R_{i}$-ים שמכילים אותו.

מתורת החבורות ידוע שכל תמורה ניתנת להצגה כהרכבה של חילופים. לפיכך כל מטריצת תמורה $P$ ניתנת לפירוק כמכפלה של מטריצות אלמנטריות המחליפות שתי שורות, אשר לכל אחת יש דטרמיננטה 1-. לפיכך, מכפליות הדטרמיננטה מקבלים שהדטרמיננטה של כל מטריצת תמורה $P$ היא 1 או 1- בהתאם לזוגיות התמורה.

ראו גם

• תמורה (מתמטיקה)

קישורים חיצוניים

מדיה וקבצים בנושא מטריצת תמורה בוויקישיתוף

• מטריצת תמורה, באתר MathWorld (באנגלית)