מטריצת תמורה

בתורת המטריצות, מטריצת תמורה היא מטריצה ריבועית בינארית שמכילה בדיוק אחדה אחת בכל שורה ובכל עמודה ואפסים בכל המקומות האחרים. כל מטריצה $$ 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- בהתאם לזוגיות התמורה.