דטרמיננטות

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

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

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

מקבילון זה אותו דבר, רק ב-\( n \) מימדים ועם \( n \)וקטורים.

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

הנוסחה שאנחנו מכירים מהתיכון לשטח של מקבילית מערבת איזה גובה, לא את שני הוקטורים שעליהם המקבילית בנויה. הרעיון הוא שאם מעבירים שני גבהים בתוך המקבילית אפשר לחלק אותה למלבן (שאת השטח שלו קל לחשב) ושני משולשים (שגם השטח שלהם לא נורא כל כך). מקבלים ששטח המקבילית הוא \( h\cdot a \) כאשר \( h \) הוא הגובה ו-\( a \) הוא אורך הצלע שאליה מורידים את הגובה (כלומר, האורך של אחד מהוקטורים \( u \) או \( v \)).

כרגע אני לא מנסה למצוא נוסחה אלטרנטיבית - במקום זה, בואו נחשוב שניה על התכונות של שטח מקבילית כתלות בוקטורים \( u,v \) שפורשים אותה. הנוסחה שראינו מבהירה לנו מייד שאם כופלים את אחד הוקטורים בסקלר אי שלילי, השטח של המקבילית מוכפל גם הוא באותו סקלר (כי \( a \) מוחלף ב-\( \lambda a \) אבל \( h \) לא משתנה - הגובה לא מושפע מאורך הצלע שאליה מורידים אותו). אם אנחנו רוצים להכניס גם סקלרים שליליים למשחק אנחנו עוברים לדבר על “שטח מכוון” - השטח של המקבילית שנקבעת על ידי \( u,v \) הוא חיובי אם כשהולכים מ-\( u \) אל \( v \) נגד כיוון השעון עוברים דרך המקבילית ושלילי אחרת (מי שלמד קצת פיזיקה אולי מזהה את זה בתור “כלל יד ימין”). מי שעניין הכיוון מבלבל אותו, לא נורא; כל מה שצריך להבין מהדיון הזה הוא שהכללנו טיפה את מושג השטח כך שכעת כפל בסקלר כלשהו של אחד הוקטורים אכן יכפיל בסקלר גם את השטח.

בואו נשתמש בסימונים כדי להקל על ההבנה של מה שהולך כאן: אשתמש ב-\( S\left(u,v\right) \) כדי לתאר את שטח המקבילית שנקבעת על ידי \( u,v \). בינתיים ראינו כי \( S\left(\lambda u,v\right)=S\left(u,\lambda v\right)=\lambda\cdot S\left(u,v\right) \). האבחנה הבאה, שהיא אולי מבלבלת קצת יותר, היא ש-\( S\left(u+v,w\right)=S\left(u,w\right)+S\left(v,w\right) \) (ובדומה גם \( S\left(u,v+w\right)=S\left(u,v\right)+S\left(u,w\right) \)). כלומר, אם יש לנו מקבילית שאחד מהוקטורים שלה הוא סכום של שני וקטורים \( u,v \), אז אפשר להסתכל על שתי המקביליות שהוקטורים הללו יוצרים בנפרד יחד עם \( w \) ולחבר את השטחים שלהם כדי לקבל את שטח המקבילית המקורית. כדי להוכיח את זה פורמלית צריך ממש לצייר את הסיטואציה ולהשתמש בחפיפת משולשים ואקשן. אם כן, קיבלנו ש-\( S \) היא פונקציה לינארית בכל משתנה בנפרד (כלומר, אם מקפיאים משתנה אחד, אז \( S \) היא לינארית כפונקציה של המשתנה השני). לפונקציה כזו קוראים “מולטי-לינארית”.

כעת, הנה תכונה קצת יותר ברורה: \( S\left(u,u\right)=0 \). כלומר, למקבילית “מנוונת” שבה כל הצלעות הן אותו קו, יש שטח אפס. עוד תכונה ברורה למדי היא ש-\( S\left(\left(1,0\right),\left(0,1\right)\right)=1 \), כלומר המקבילית שצלעותיה הם בדיוק וקטורי הבסיס הסטנדרטי ב-\( \mathbb{R}^{2} \) ולכן היא בעצם ריבוע עם אורך צלע 1 יש שטח 1. מסתבר שהתכונות שציינתי עד כה של \( S \) - מולטי-לינאריות, התאפסות על אותו הוקטור ו-1 על וקטורי הבסיס הסטנדרטי - מספיקות כדי לאפיין את \( S \) לחלוטין.

אפשר להכליל את הדיון כאן גם ל-\( \mathbb{R}^{n} \); לא אכנס כאן לאופן המדויק שבו מגדירים מקבילון \( n \)-ממדי, אבל גם במקרה הזה אפשר לדבר על פונקציה \( S\left(v_{1},\dots,v_{n}\right) \) שמקבלת וקטורים ב-\( \mathbb{R}^{n} \), וניתן להראות שהיא מקיימת מולטי-לינאריות, ושאם \( v_{i}=v_{j} \) עבור \( i\ne j \) כלשהם אז \( S\left(v_{1},\dots,v_{n}\right)=0 \) (כלומר, מספיק ששתי צלעות של המקבילון יהיו זהות כדי שהוא יהיה מנוון ובעל נפח 0), ו-\( S\left(e_{1},\dots,e_{n}\right)=1 \) - נפח המקבילון על אברי הבסיס הסטנדרטי ב-\( \mathbb{R}^{n} \) הוא 1. אם כן, יש לנו מוטיבציה לחקור פונקציות שמקיימות את התנאים הללו - וכאמור, אנו עומדים לראות כי קיימת פונקציה אחת ויחידה כזו (עבור \( n \) נתון) שמקיימת את כל התכונות גם יחד. הפונקציה הזו נקראת דטרמיננטה. רק שאת הפונקציה הזו אפשר להגדיר לכל מרחב \( \mathbb{F}^{n} \), גם לא מעל \( \mathbb{R} \) ספציפית (למרות שבשדות \( \mathbb{F} \) אחרים לא תמיד ברור מהו “מקבילון”, אבל כאמור - המשמעות של דטרמיננטה היא רחבה הרבה יותר מכך), וכך גם נעשה.

אם כן, יהא \( V=\mathbb{F}^{n} \) מרחב וקטורי מעל השדה \( \mathbb{F} \). אנו מתעניינים בפונקציות \( f:V^{n}\to\mathbb{F} \), כלומר פונקציות שמקבלות \( n \) משתנים שכל אחד מהם הוא איבר של \( V=\mathbb{F}^{n} \), ומחזירות ערך ב-\( \mathbb{F} \) (במילים אחרות, פונקציונלים).

פונקציה \( f \) שכזו נקראת לינארית במשתנה ה-\( i \) אם מתקיים \( f\left(v_{1},v_{2},\dots,\alpha v_{i}+\beta u_{i},v_{i+1},\dots,v_{n}\right)=\alpha f\left(v_{1},\dots,v_{i},\dots,v_{n}\right)+\beta f\left(v_{1},\dots,u_{i},\dots,v_{n}\right) \), כלומר אם כאשר מקפיאים את כל המשתנים פרט למשתנה ה-\( i \) של \( f \) מקבלים פונקציה לינארית. כעת, \( f \) היא מולטי-לינארית אם היא לינארית בכל \( n \) המשתנים שלה.

\( f \) היא מתחלפת אם \( v_{i}=v_{j} \) עבור \( i\ne j \) גורר ש-\( f\left(v_{1},\dots,v_{n}\right)=0 \), כלומר הצבת אותו ערך בשניים מהמשתנים של \( f \) מבטיחה שערכה של \( f \) יהיה 0. כדי להבין את הכוונה ב”מתחלפת”, בואו נראה תעלול בפונקציה בשני משתנים שמשתמש במולטי-לינאריות שלה:

\( 0=f\left(a+b,a+b\right)=f\left(a,a+b\right)+f\left(b,a+b\right)=f\left(a,a\right)+f\left(a,b\right)+f\left(b,a\right)+f\left(b,b\right)=f\left(a,b\right)+f\left(b,a\right) \)

כאן השתמשנו בכך ש-\( f\left(a+b,a+b\right)=f\left(a,a\right)=f\left(b,b\right)=0 \) כי \( f \) מתחלפת. כעת, העברת אגפים נותנת לנו \( f\left(a,b\right)=-f\left(b,a\right) \). כלומר, אם החלפנו את המקומות של \( a,b \) ב-\( f \) זה גרם בדיוק להחלפת הסימן של ערך \( f \). את אותו התעלול אפשר לעשות גם עבור \( f \) עם יותר משתנים: הכלל הוא שאם מחליפים שניים מתוך \( n \) הערכים שהוצבו ב-\( f \), התוצאה היא היפוך הסימן של \( f \).

אחרי כל הפמפום הזה כבר ברור מה אני רוצה להוכיח: שקיים פונקציונל מולטי-לינארי מתחלף יחיד \( f \) שמקיים \( f_{0}\left(e_{1},\dots,e_{n}\right)=1 \) כאשר \( e_{1},\dots,e_{n}\in V \) הם וקטורי הבסיס הסטנדרטי של \( V \) (זכרו ש-\( V=\mathbb{F}^{n} \) ולכן יש משמעות ל”בסיס סטנדרטי” כאן). בואו ננסה להבין איך \( f \) הזה חייב להיראות.

כמקודם, כדי שהעסק יהיה ביותר ברור אני אניח בהתחלה ש-\( f \) היא פונקציה על שני קלטים, אבל ההוכחה הכללית תהיה זהה. נניח אם כן ש-\( f \) היא פונקציה שמקיימת את שלוש הדרישות שלעיל ונסתכל על ערכה על שני קלטים שרירותיים לחלוטין, כלומר \( f\left(u,v\right) \). אפשר לייצג את הקלטים הללו באמצעות הבסיס הסטנדרטי באופן יחיד, ולכן \( f\left(u,v\right)=f\left(\alpha_{1}e_{1}+\alpha_{2}e_{2},\beta_{1}e_{1}+\beta_{2}e_{2}\right) \), ועל ידי שימוש במולטי-לינאריות נקבל:

\( f\left(u,v\right)=\alpha_{1}\beta_{1}f\left(e_{1},e_{1}\right)+\alpha_{1}\beta_{2}f\left(e_{1},e_{2}\right)+\alpha_{2}\beta_{1}f\left(e_{2},e_{1}\right)+\alpha_{2}\beta_{2}f\left(e_{2},e_{2}\right) \)

או בקיצור, הערכים של \( f \) על קלטים שרירותיים נקבעים על ידי הערכים שלה על זוגות של איברים מהבסיס הסטנדרטי. זה לא ממש מפתיע; זו הכללה של העובדה שהערכים של פונקציה לינארית נקבעים על ידי ערכיה על אברי הבסיס הסטנדרטי.

כעת, בגלל ש-\( f \) מתחלפת, \( f\left(e_{1},e_{1}\right)=f\left(e_{2},e_{2}\right)=0 \). לכן כל מה שקובע את ערכיה של \( f \) הוא \( f\left(e_{1},e_{2}\right) \) ו-\( f\left(e_{2},e_{1}\right) \). אבל כפי שראינו, \( f\left(e_{2},e_{1}\right)=-f\left(e_{1},e_{2}\right) \), ולכן הדבר היחיד שקובע את ערכיה של \( f \) הוא \( f\left(e_{1},e_{2}\right) \). אבל כאן אין לנו חופש בחירה - דרשנו במפורש ש-\( f\left(e_{1},e_{2}\right)=1 \).

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

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

בשביל מה כל זה טוב? בשביל הנוסחה הנפלאה והפשוטה \( f\left(e_{\sigma\left(1\right)},\dots,e_{\sigma\left(n\right)}\right)=\mbox{sgn}\left(\sigma\right)f\left(e_{1},\dots,e_{n}\right)=\mbox{sgn}\left(\sigma\right) \). הסבירו לעצמכם מדוע היא נכונה! זה נובע, כפי שכבר ראינו, מכך שהחלפה של שני ערכים שמוצבים ב-\( f \) הופכת את הסימן של \( f \).

נסכם - ראינו שאם יש פונקציה כלשהי שמקיימת את כל הדרישות (מולטי-לינארית, מתחלפת ו-1 על וקטורי הבסיס הסטנדרטי) אז היא חייבת להיות הפונקציה שמקיימת \( f\left(e_{\sigma\left(1\right)},\dots,e_{\sigma\left(n\right)}\right)=\mbox{sgn}\left(\sigma\right) \) ו-0 על סדרות של וקטורי הבסיס הסטנדרטי שבהן אותו וקטור חוזר על עצמו, מה שקובע את יתר ערכיה באופן מוחלט. זה מראה שאם קיימת פונקציה כלשהי שעונה על הדרישות, היא יחידה; זה עדיין לא מראה שהיא קיימת, למרות שמפתה לומר זאת. הסיבה לכך היא שגם אם נגדיר את \( f \) על וקטורי הבסיס באופן הזה זה לא מבטיח מייד שהיא תקיים את כל הדרישות, אבל קל לראות שזה אכן כך - מולטי-לינאריות נובעת מכך שאנחנו מרחיבים את \( f \) באופן כזה שמבטיח שהיא תהיה מולטי-לינארית; 1 על וקטורי הבסיס נובע מיידית מההגדרה; החלק המסובך היחיד הוא להראות ש-\( f \) היא מתחלפת. ראינו שזה כך על קלט שמורכב מאברי הבסיס הסטנדרטי, אבל למה זה כך באופן כללי?

כדי לטפל בבעיה הזו אנחנו רוצים ראשית למצוא נוסחה קצת יותר מפורשת עבור \( f \). כאן נוח לחשוב על \( f \) לא כפונקציה שפועלת על וקטורים, אלא כפונקציה על מטריצה \( A \), כך שהשורה ה-\( i \) במטריצה היא הוקטור ה-\( i \) שעליו \( f \) פועלת. כלומר, \( A_{ij} \) הוא הכניסה ה-\( j \) בתוך הוקטור \( v_{i} \). כדי לקשור את זה למה שכבר ראינו, בואו נזכור ש-\( v_{i}=\sum_{j=1}^{n}A_{ij}e_{j} \). כעת, אם נפתח את \( f\left(A\right)=f\left(v_{1},\dots,v_{n}\right) \) לסכום על ידי כתיבת כל \( v_{i} \) בתור צירוף לינארי שכזה ושימוש במולטי-לינאריות של \( f \), ונשתמש בנוסחה לערכי \( f \) על אברי בסיס שראינו קודם, נקבל לבסוף את התוצאה הזו:

\( f\left(A\right)=\sum_{\sigma}\mbox{sgn}\left(\sigma\right)A_{1\sigma\left(1\right)}A_{2\sigma\left(2\right)}\cdots A_{n\sigma\left(n\right)} \)

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

\( f\left(A\right)=\sum_{\sigma}\mbox{sgn}\left(\sigma\right)\prod_{i=1}^{n}A_{i\sigma\left(i\right)} \)

וכעת אפשר כבר להפסיק להשתמש בסימון \( f \): הסימון המקובל לפונקציה הזו הוא \( \det A \), או \( \left|A\right| \). הנוסחה שלמעלה היא לרוב ההגדרה הסטנדרטית שלה.

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

\( \sum_{\sigma}\mbox{sgn}\left(\sigma\right)\prod_{i=1}^{n}A_{i\sigma\left(i\right)}=\sum_{\sigma\tau}\mbox{sgn}\left(\sigma\tau\right)\prod_{i=1}^{n}A_{i\sigma\tau\left(i\right)}=\sum_{\sigma\tau}-\mbox{sgn}\left(\sigma\right)\prod_{i=1}^{n}A_{i\sigma\tau\left(i\right)} \)

אלא שבגלל שהחלפנו שתי שורות זהות, \( \prod_{i=1}^{n}A_{i\sigma\tau\left(i\right)}=\prod_{i=1}^{n}A_{i\sigma\left(i\right)} \) (כלומר, ל-\( \tau \) “אין השפעה”), ולכן מקבלים

\( \sum_{\sigma}\mbox{sgn}\left(\sigma\right)\prod_{i=1}^{n}A_{i\sigma\left(i\right)}=-\sum_{\sigma}\mbox{sgn}\left(\sigma\right)\prod_{i=1}^{n}A_{i\sigma\left(i\right)} \)

ומכאן שבהכרח \( \left|A\right|=0 \). זו הוכחה טיפה טכנית, ומי שלא הצליח לעקוב אחריה לגמרי - לא נורא.

לכאורה סיימנו - יש לנו עכשיו הגדרה עם נוסחה יפה (כן כן, הנוסחה הזו יפהפיה!) לדטרמיננטה שהיא מה שרצינו כל הזמן. אלא שהנוסחה הזו לא פרקטית לחישובים מעשיים - יש \( n! \) פרמוטציות על \( n \) איברים, ו-\( n! \) גדל מאוד מאוד מהר, כך שחישוב דטרמיננטה בעזרת הנוסחה הוא בעיה חישובית קשה. למעשה, יש פונקציה מאוד דומה לדטרמיננטה - הפרמננטה, שמוגדרת כך: \( \mbox{perm}\left(A\right)=\sum_{\sigma}\prod_{i=1}^{n}A_{i\sigma\left(i\right)} \). כלומר, אותו הדבר רק בלי הפלוס-מינוס של סימן התמורה. הפרמנטטה היא, באופן מוכח, בעיה \( \mbox{NP} \)-קשה; זה אומר שמאוד לא סביר שיימצא יום אחד אלגוריתם לחישוב יעיל שלה. אז מה שהופך את הדטרמיננטה לקלה (מאוד!) לחישוב הוא לא הנוסחה שהצגתי כבר אלא תכונות שלה שעוד צריך לדבר עליהן.

אם כן, ראינו שהדטרמיננטה היא פונקציה מולטי-לינארית ומתחלפת; מה זה אומר כשחושבים עליה כפונקציה של מטריצות? מתחלפת אומר שאם מחליפים שתי שורות במטריצה זה הופך את סימן הדטרמיננטה. מולטי-לינארית אומר, קודם כל, שאם כופלים שורה כלשהי בסקלר, זה מכפיל את הדטרמיננטה כולה באותו סקלר. את התכונה השניה שנובעת ממולטי-לינאריות אפשר לנסח כך: אם \( A \) היא מטריצה, ו-\( B,C \) הן מטריצות הזהות ל-\( A \) פרט לשורה ה-\( i \) כך שסכום השורות ה-\( i \) של \( B,C \) הוא השורה ה-\( i \) של \( A \), אז \( \left|A\right|=\left|B\right|+\left|C\right| \). שימו לב שזה לא נכון שמתקיים \( \left|B+C\right|=\left|B\right|+\left|C\right| \)! מולטי-לינאריות עובדת רק אם “מקפיאים” את כל השורות פרט לאחת ומפצלים את החיבור אך ורק בה. לצורך הפוסט הזה בלבד אמציא את הסימון הלא סטנדרטי והמוזר \( A=B\oplus_{i}C \) שאומר בדיוק את מה שתיארתי למעלה - ש-\( A \) היא המטריצה שמתקבלת מ-\( B,C \) (שהן מטריצות זהות פרט לשורה ה-\( i \)) כאשר השורה ה-\( i \) של \( A \) היא סכום השורות ה-\( i \) של \( B,C \) ושאר השורות של \( A \) זהות לשורות של \( B,C \).

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

במבט ראשון התכונה הכמו-חיבורית הזו נראית חלשה למדי. אבל היא אומרת משהו מאוד לא טריוויאלי ומאוד מפתיע: נניח ש-\( A \) מתקבלת מ-\( B \) על ידי כך שלוקחים שורה \( j \) של \( B \), כופלים אותה בסקלר ומחברים אותה לשורה אחרת \( i \); אז \( \left|A\right|=\left|B\right| \), כלומר הפעולה הזו בכלל לא משנה את הדטרמיננטה! הסיבה לכך היא שאפשר לחשוב על \( A \) בתור \( A=B\oplus_{i}C \) כאשר \( C \) זהה ל-\( B \) פרט לכך שבשורה ה-\( i \) מופיעה השורה ה-\( j \) של \( B \) (ולכן גם של \( C \)). כעת, \( \left|A\right|=\left|B\right|+\left|C\right| \) אבל \( \left|C\right|=0 \) כי השורה ה-\( i \) של \( C \) שווה לשורה ה-\( j \) של \( C \), והדטרמיננטה היא פונקציה מתחלפת.

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

את הטענה שלעיל אפשר לראות ישירות מהנוסחה. כזכור, מטריצה משולשית עליונה היא מטריצה שבה \( A_{ij}=0 \) אם \( i>j \) (כלומר, כל מה שמתחת לאלכסון הראשי הוא אפס). כעת, לכל פרמוטציה \( \sigma \) שאיננה הזהות, בהכרח יהיה \( i \) כלשהו עבורו \( i>\sigma\left(i\right) \) (זה תרגיל נחמד להוכיח זאת) ולכן \( A_{i\sigma\left(i\right)}=0 \) ולכן \( \prod_{i=1}^{n}A_{i\sigma\left(i\right)}=0 \) לכל \( \sigma \) שאיננה הזהות, ולכן נותרנו עם \( \left|A\right|=\prod_{i=1}^{n}A_{ii} \). אותו דבר תקף, כמובן, גם עבור מטריצה משולשית תחתונה (אבל בדירוג מטריצות רגיל מגיעים למטריצה משולשית עליונה). מכיוון שדירוג מטריצות ניתן לביצוע במהירות רבה, גם חישוב דטרמיננטה יכול להתבצע במהירות רבה, וזה מבלי שדיברנו על אופטימיזציות אחרות שאפשר אולי לנקוט בהן.

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

אם כן, תהא \( A \) מטריצה מסדר \( n\times n \). אני יכול לבחור שורה \( i \) ועמודה \( j \) של המטריצה ופשוט למחוק אותן לחלוטין, כאילו מעולם לא נתקיימו. לתוצאה קוראים מטריצת המינור ה-\( i,j \)-ית של \( A \) וזוהי מטריצה מסדר \( \left(n-1\right)\times\left(n-1\right) \). למטריצה הזו אפשר לחשב דטרמיננטה, והדטרמיננטה הזו נקראת המינור ה-\( i,j \)-י של \( A \) (לפעמים קוראים בשם “המינור” למטריצת המינור, אבל בואו לא ניתן לשמות וסימונים לבלבל אותנו יותר ממה שצריך). אשתמש בסימון שאני המצאתי, \( \left|A^{ij}\right| \) כדי לתאר את המינור ה-\( i,j \) של \( A \).

כעת, הבה ונקבע שורה \( i \) כלשהי באופן שרירותי. אני טוען שמתקיים \( \left|A\right|=\sum_{j=1}^{n}\left(-1\right)^{i+j}A_{ij}\left|A^{ij}\right| \). במילים אחרות, \( \left|A\right| \) היא סכום של המינורים שמתקבלים ממחיקת השורה ה-\( i \) וכל העמודות של \( A \) (כל עמודה בתורה), ובנוסף לכך הסכום הזה הוא מתחלף - לאיברים יש סימן פלוס או סימן מינוס, בהתאם לשאלה אם \( i+j \) זוגי או אי זוגי. הנוסחה הזו נקראת פיתוח לפי השורה ה-\( i \) של \( \left|A\right| \), ובאותה מידה אפשר גם לפתח לפי עמודות.

אציג דוגמה. ראשית, שימו לב לכך ש-\( \left|\begin{array}{cc}a & b\\c & d\end{array}\right|=ad-bc \) (קל לראות שזה נובע מההגדרה). כעת, בואו נראה פיתוח של דטרמיננטה של מטריצה מסדר \( 3\times3 \) על פי השורה הראשונה:

\( \left|\begin{array}{ccc}1 & 2 & 0\\5 & 1 & 7\\1 & 5 & 2\end{array}\right|=1\cdot\left|\begin{array}{cc}1 & 7\\5 & 2\end{array}\right|-2\left|\begin{array}{cc}5 & 7\\1 & 2\end{array}\right|+0\cdot\left|\begin{array}{cc}5 & 1\\1 & 5\end{array}\right|=\left(2-35\right)-2\left(10-7\right)+0\left(25-1\right)=-33-6=-39 \).

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

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

אעבור במעין אינדוקציה על \( n \): זה אומר שבנוסחה \( f\left(A\right)=\sum_{j=1}^{n}\left(-1\right)^{i+j}A_{ij}\left|A^{ij}\right| \) אני יכול להניח שהדטרמיננטה שמופיעה באגף ימין היא באמת פונקציית הדטרמיננטה המוכרת והאהובה עלינו, עבור מטריצות \( \left(n-1\right)\times\left(n-1\right) \), וכל שנותר לי לעשות הוא להוכיח ש-\( f \) מקיימת את התכונות הנדרשות מדטרמיננטה של מטריצות \( n\times n \). זה אומר, בפרט, שאני יכול להניח שהדטרמיננטות באגף ימין הן כבר מולטי-לינאריות, וזה גורר מייד שגם \( f \) כזו, כי היא בסך הכל צירוף לינארי של פונקציות מולטי-לינאריות - הרי לכם טיעון מחץ מתמטי שחוסך לנו לא מעט כתיבה מתישה (וכנראה לא משכנע חצי מכם).

כל מה שנשאר לעשות הוא להשתכנע ש-\( f \) היא מתחלפת. נניח אם כן ש-\( k,l \) הן שתי שורות זהות של \( A \) ונוכיח ש-\( f\left(A\right) \) היא אפס. ראשית, אם \( i\ne k,l \) אז נהדר, סיימנו: במקרה זה \( A^{ij} \) תהיה מטריצה שבה השורות שהגיעו משורות \( k,l \) הן זהות (כי כל השינוי שעשינו הוא למחוק משתי השורות הללו את הכניסה ה-\( j \)-ית) ולכן \( \left|A^{ij}\right|=0 \) ונגמר העניין. אם כן, נניח לנו ש-\( k=i \). אז במקרה זה:

\( f\left(A\right)=\sum_{j=1}^{n}\left(-1\right)^{k+j}A_{kj}\left|A^{kj}\right| \)

ועכשיו אני אשתמש בתעלול הופך קיבה: אני אשתמש בנוסחה הרקורסיבית (שכבר הוכחתי עבור מטריצות \( \left(n-1\right)\times\left(n-1\right) \)) כדי לחשב את \( \left|A^{kj}\right| \) על ידי כך שאני אפתח את הדטרמיננטה הזו לפי השורה… אם הצלחתם לעקוב אחרי עד לכאן, אולי כבר ניחשתם שעל פי השורה ה-\( l \) (כי איזו עוד שורה אפשר לבחור? השורה ה-\( k \) כבר נרצחה, וחוץ ממנה רק לשורה ה-\( l \) היה ייחוד; שימו לב איך אנחנו “נדחפים” כאן בכוח לכיוון ההוכחה הנכון).

ובכן, איך נראה הפיתוח של \( \left|A^{kj}\right| \) על פי השורה ה-\( l \)? מבחינה טכנית צריך טיפה להיזהר פה: מפתה לכתוב \( \left|A^{kj}\right|=\sum_{\begin{array}{c}i=1\end{array}}^{n}\left(-1\right)^{l+i}A_{li}\left|\left(A^{kj}\right)^{li}\right| \) כאשר \( \left(A^{kj}\right)^{li} \) היא מינור של מינור - המטריצה שמתקבלת מ-\( A \) על ידי מחיקת השורות \( l,k \) והעמודות \( j,i \). לרוע המזל, זו לא הנוסחה הנכונה: אבל שימו לב שכך אנו כוללים בפיתוח גם את העמודה \( j \) שכבר נרצחה (הרי אני מחשב את הדטרמיננטה של \( A^{kj} \)). גם \( \left|A^{kj}\right|=\sum_{\begin{array}{c}i\ne j\end{array}}^{n}\left(-1\right)^{l+i}A_{li}\left|\left(A^{kj}\right)^{li}\right| \) (כש-\( i \) מתחיל מ-1, כרגיל) היא לא נוסחה נכונה, בגלל שהחזקה של ה-\( -1 \) מתקלקלת מתישהו (בדיוק כאשר \( i \) קופץ “מעל” \( j \)). הנוסחה הנכונה היא:

\( \left|A^{kj}\right|=\sum_{\begin{array}{c}i=1\end{array}}^{j-1}\left(-1\right)^{l+i}A_{li}\left|\left(A^{kj}\right)^{li}\right|+\sum_{\begin{array}{c}i=j+1\end{array}}^{n}\left(-1\right)^{l+i-1}A_{li}\left|\left(A^{kj}\right)^{li}\right| \)

הבה ונציב את כל המפלץ הזה בנוסחה המקורית:

\( f\left(A\right)=\sum_{j=1}^{n}\left(-1\right)^{k+j}A_{kj}\left(\sum_{\begin{array}{c}i=1\end{array}}^{j-1}\left(-1\right)^{l+i}A_{li}\left|\left(A^{kj}\right)^{li}\right|+\sum_{\begin{array}{c}i=j+1\end{array}}^{n}\left(-1\right)^{l+i-1}A_{li}\left|\left(A^{kj}\right)^{li}\right|\right) \)

ומכל זה נקבל:

\( f\left(A\right)=\sum_{j=1}^{n}\sum_{i=1}^{j-1}\left(-1\right)^{l+k+i+j}A_{kj}A_{li}\left|\left(A^{kj}\right)^{li}\right|+\sum_{j=1}^{n}\sum_{i=1}^{j+1}\left(-1\right)^{l+k+i+j-1}A_{kj}A_{li}\left|\left(A^{kj}\right)^{li}\right| \)

עכשיו מגיע הפאנץ’. זכרו ש-\( k,l \) היו שורות זהות, ולכן \( A_{kj}=A_{lj} \) זה אומר שהאיבר \( A_{lt}A_{lr}\left|\left(A^{lt}\right)^{lr}\right| \) מופיע פעמיים - פעם בסכום השמאלי, ופעם בסכום הימני, וזאת לכל \( t,r \) רלוונטיים. רק שהמופעים של שני האיברים הללו הם עם סימנים הפוכים בגלל ההבדל הקטנטן בחזקה של ה-\( -1 \), ולכן הסכום הכולל הוא אפס.

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