איך מחשבים דטרמיננטה?

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

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

דטרמיננטה מוגדרת על מטריצה ריבועית, כלומר על אוסף של מספרים שמסודר בטבלה עם אותו מספר שורות ועמודות. אם המספר הוא \( n \), אומרים שזו מטריצה מסדר \( n\times n \). בדרך כלל מסמנים את זה ב-

\( A=\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & & a_{2n}\\ \vdots & & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array}\right] \)

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

עכשיו עושים משהו דומה עם \( a_{12} \): מוחקים את השורה הראשונה והעמודה השניה, מקבלים מטריצה קטנה יותר, מחשבים את הדטרמיננטה שלה, כופלים ב-\( a_{12} \) ואז מחסרים את התוצאה ממה שקיבלנו קודם. ואז לוקחים את \( a_{13} \) ועושים את אותו הטריק איתו אבל מחברים - בקיצור, אנחנו רואים שזו מהומה, ושצריך להכניס קצת סימנים כדי לתאר את זה בצורה פשוטה.

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

\( \left|A\right|=\sum_{j=1}^{n}\left(-1\right)^{i+j}a_{ij}\left|A^{ij}\right| \)

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

\( \left|A\right|=\sum_{i=1}^{n}\left(-1\right)^{i+j}a_{ij}\left|A^{ij}\right| \)

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

\( A=\left[\begin{array}{cc} a_{11} & a_{12}\\ a_{21} & a_{22} \end{array}\right] \)

נפתח את הדטרמיננטה על פי השורה הראשונה: ראשית ניקח את \( a_{11} \), נמחק את השורה והעמודה הראשונות ונקבל את המטריצה \( \left[a_{22}\right] \) שהדטרמיננטה שלה היא \( a_{22} \), אז האיבר הראשון בסכום הוא \( a_{11}a_{22} \). עכשיו נעבור אל \( a_{12} \), נמחק שורה ראשונה ועמודה שניה, נקבל דטרמיננטה \( a_{21} \), נכפיל ונשים סימן חיסור על הכל, ונקבל בסך הכל ש-\( \left|A\right|=a_{11}a_{22}-a_{12}a_{21} \). עכשיו תנסו לעשות את אותו הדבר עם פיתוח של שורה אחרת או עמודה אחרת (למשל, עמודה 2) ותראו איך יוצא אותו דבר (אם סימני הפלוס/מינוס לא מסתדרים תזכרו את הגורם \( \left(-1\right)^{i+j} \); לא תמיד כשמפתחים לפי שורה או עמודה כלשהי, האיבר הראשון שבו מטפלים יהיה עם סימן חיובי).

def det(A):
    n = len(A)
    if n == 1:
        return A[0][0]
    result = 0
    for k in range(n):
        minor_matrix = [[A[i][j] for j in range(n) if j != k] for i in range(1, n)]
        result += (-1)**k * A[0][k] * det(minor_matrix)
    return result

האם זה עובד טוב? לא, זה עובד איום ונורא. זה ירוץ ויחזיר את התוצאה הנכונה, אבל באיזה מחיר? המחיר יהיה זמן ריצה גדול (וגם צריכת זכרון מיותרת, אבל בהיקף פחות משמעותי כאן). חשבו על זה כך: אם אני מפעיל את האלגוריתם על מטריצה מסדר \( n\times n \), אני צריך לחשב את הדטרמיננטה של \( n \) מטריצות מסדר \( \left(n-1\right)\times\left(n-1\right) \), וכל חישוב כזה דורש חישוב של \( n-1 \) דטרמיננטות של מטריצות מסדר \( \left(n-2\right)\times\left(n-2\right) \) וכן הלאה - יוצא שאני מחשב \( n\left(n-1\right)\left(n-2\right)\cdots1=n! \) דטרמיננטות. קצב הגידול של \( n! \) הוא אקספוננציאלי - תמיד חדשות רעות שמדובר על זמן חישוב. על מטריצת \( 4\times4 \) האלגוריתם הזה יעבוד מעולה ויסתיים חיש קל. על מטריצה מסדר \( 1000\times1000 \)? אני לא מעז להפעיל אותו.

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

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

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

\( A=\left[\begin{array}{ccc} 13 & 0 & 0\\ 0 & -2 & 0\\ 0 & 0 & 8 \end{array}\right] \)

אם נתחיל לפתח את הדטרמיננטה של \( A \) על פי השורה הראשונה, נקבל

\( \left|A\right|=13\cdot\left|\begin{array}{cc} -2 & 0\\ 0 & 8 \end{array}\right| \)

עכשיו את הדטרמיננטה של המטריצה החדשה אני יכול לחשב באותו אופן - פיתוח על פי השורה הראשונה, שהוא פשוט כפל במספר שכתוב בשורה הראשונה כפול הדטרמיננטה של מה שנשאר מהמטריצה כש”מגלחים” ממנה את השורה והעמודה הראשונה, וכן הלאה. אני אקבל \( \left|A\right|=13\cdot\left(-2\right)\cdot8 \): הדטרמיננטה של מטריצה אלכסונית היא מכפלת האיברים על האלכסון.

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

\( A=\left[\begin{array}{ccc} 13 & 0 & 0\\ 42 & -2 & 0\\ 555 & 0 & 8 \end{array}\right] \)

הדטרמיננטה שלה בכלל לא הייתה משתנה - הפיתוח לפי השורה הראשונה היה מניב \( \left|A\right|=13\cdot\left|\begin{array}{cc} -2 & 0\\ 0 & 8 \end{array}\right| \) באותה צורה כמו קודם. זה נכון שהפיתוח לפי העמודה הראשונה היה עכשיו מתנהל שונה לגמרי, אבל הוא היה מגיע לאותה תוצאה סופית (נסו!)

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

\( A=\left[\begin{array}{ccc} 13 & 0 & 0\\ 42 & -2 & 0\\ 555 & 9999 & 8 \end{array}\right] \)

התוצאה הזו מראה שמטריצות שבהן “החצי העליון” של המטריצה, מעל האלכסון הראשי, הוא אפסים הן מטריצות מעניינות. למטריצות כאלו קוראים “מטריצה משולשית תחתונה” (תחתונה, כי האיזור שבו כן יכולים להיות דברים שונים מאפס הוא זה שמתחת לאלכסון הראשי). פורמלית, זו מטריצה שבה אם \( j>i \) אז \( a_{ij}=0 \) (אם מספר העמודה גדול ממספר השורה, הכניסה היא אפס). מה שראינו עכשיו הוא שבמטריצות כאלו, הדטרמיננטה היא מכפלת אברי האלכסון הראשי. באופן דומה מגדירים גם “מטריצה משולשית עליונה” שבה אם \( i>j \) אז \( a_{ij}=0 \) ופיתוח הדטרמיננטה לפי עמודות ולא לפי שורות מראה שגם במקרה הזה הדטרמיננטה של מטריצה כזו היא מכפלת אברי האלכסון הראשי.

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

בשביל חישוב דטרמיננטה, מספיקים לנו שתי פעולות שאפשר לבצע על מטריצה:

• להחליף שתי שורות במטריצה
• לקחת שורה אחת, לכפול אותה במספר כלשהו, ולחבר לשורה אחרת

בואו נדגים את זה. הנה מטריצה:

\( A=\left[\begin{array}{ccc} 2 & 8 & 3\\ 4 & 9 & 1\\ 3 & 3 & 3 \end{array}\right] \)

אם אני אחליף את השורה השניה והשלישית, אני אקבל

\( A=\left[\begin{array}{ccc} 2 & 8 & 3\\ 3 & 3 & 3\\ 4 & 9 & 1 \end{array}\right] \)

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

\( B=\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array}\right] \)

בבירור \( \left|B\right|=1 \) כי זו מכפלת אברי האלכסון. עכשיו, בואו נחליף את השורה השניה בשלישית ונקבל

\( B=\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{array}\right] \)

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

\( \left|B\right|=1\cdot\left|\begin{array}{cc} 0 & 1\\ 1 & 0 \end{array}\right|=1\cdot\left(-1\right)=-1 \)

זה גם מה שיקרה במקרה הכללי אם ניקח מטריצה שכולה 1-ים על האלכסון הראשי ונחליף שתי שורות: אם נפתח את הדטרמיננטה וראשית כל נפתח אותה לפי השורות שלא השתנו, נקבל מכל שורה כזו 1, וכולם יוכפלו בסוף ב-\( \left|\begin{array}{cc} 0 & 1\\ 1 & 0 \end{array}\right| \), שזו הדטרמיננטה של מה שיישאר משתי השורות שכן הוחלפו, אחרי שכל יתר העמודות נקצצו מהמטריצה. כלומר (בנפנוף ידיים) לכל החלפת שורות, נקבל שהדטרמיננטה של המטריצה היא \( -1 \).

עכשיו מגיע הקסם, ואיך שאני אוהב את הקסם הזה! אם ניקח את \( B \) שלאחר ההחלפה ונכפול אותה ב-\( A \) המקורית, נקבל:

\( \left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{array}\right]\left[\begin{array}{ccc} 2 & 8 & 3\\ 4 & 9 & 1\\ 3 & 3 & 3 \end{array}\right]=\left[\begin{array}{ccc} 2 & 8 & 3\\ 3 & 3 & 3\\ 4 & 9 & 1 \end{array}\right] \)

מה קרה פה? הכפל במטריצה \( B \) אחרי החלפת השורה היה בעל אפקט של ביצוע החלפת שורה על \( A \)! כלומר, הצלחנו לתאר את הפעולה “החלפת שורה” בתור “כפל במטריצה כלשהי”. עכשיו, בגלל שאני יודע ש-\( \left|BA\right|=\left|B\right|\left|A\right| \) ובגלל ש-\( \left|B\right|=-1 \) כפי שזה עתה ראינו, אני מקבל שהדטרמיננטה של \( A \) אחרי החלפת שורות - וזה יעבוד לכל פעולה בודדת של החלפת שורות - הוא כפל ב-\( -1 \), כמו שהבטחתי.

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

\( B=\left[\begin{array}{ccc} 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1 \end{array}\right] \)

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

בואו ניקח את \( B \) שחישבתי קודם, זו שבה חיסרתי את פעמיים השורה הראשונה מהשניה, ונכפול אותה ב-\( A \) המקורית. נקבל:

\( \left[\begin{array}{ccc} 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1 \end{array}\right]\left[\begin{array}{ccc} 2 & 8 & 3\\ 4 & 9 & 1\\ 3 & 3 & 3 \end{array}\right]=\left[\begin{array}{ccc} 2 & 8 & 3\\ 0 & -7 & -5\\ 3 & 3 & 3 \end{array}\right] \)

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

אבל עכשיו בואו ותראו מה קרה. מהמטריצה \( A \) המסובכת קיבלתי גרסה חדשה של \( A \), עם אותה דטרמיננטה, אבל שנראית יותר פשוטה: יש בה 0 באחד המקומות. זה לא קרה בטעות: אני הסתכלתי על \( A \), ראיתי שבעמודה הראשונה, יש בשורה הראשונה 2 ובשורה השניה 4 ושאלתי את עצמי “במה אני צריך לכפול את 2 כדי שאחרי שאחבר אותו אל 4 אקבל 0?” וזה היה בדיוק \( -2 \) אז זה מה שעשיתי. עכשיו נעשה את זה במקרה המלוכלך יותר, של השורה השלישית: בשורה השניה יש 2, בשלישית יש \( 3 \), אז אני צריך לכפול ב-\( -\frac{3}{2} \). זה אולי יגרום לכל המספרים שמופיעים בשורה השלישית במטריצה להיות שברים מעיקים, אבל לא אכפת לי! אני אעשה את זה! הנה!

\( \left[\begin{array}{ccc} 2 & 8 & 3\\ 0 & -7 & -5\\ 0 & -9 & -\frac{3}{2} \end{array}\right] \)

עכשיו אנחנו מאוד קרובים למטריצה משולשית - רק ה-\( -9 \) בשורה השלישית מפריע לנו. אני יכול להעלים אותו על ידי כפל השורה השניה ב-\( -\frac{9}{7} \) וחיבור שלה לשלישית, ואני אקבל

\( \left[\begin{array}{ccc} 2 & 8 & 3\\ 0 & -7 & -5\\ 0 & 0 & \frac{69}{14} \end{array}\right] \)

קיבלתי על האלכסון את המספר \( \frac{69}{14} \). זה לא נראה טוב. זה נראה כמו שבר משובר. זה בעצם העונש שלי על שתי פעולות של איפוס איברים שעשיתי “בכוח”, על ידי זה שהיה לי \( a \) בכניסה אחת ו-\( b \) בכניסה אחרת וכפלתי ב-\( -\frac{b}{a} \) וחיברתי, בלי שיהיה איזה צמצום נחמד שמערב את \( a,b \). זו גם בדיוק הנקודה שלי: לא צריך שדברים יסתדרו “יפה”. אפשר פשוט לעשות את זה בכוח - או טוב יותר, לתת למחשב לעשות את זה. למחשב לא אכפת אם החישובים הם מכוערים, הוא פשוט יעשה את זה.

וכעת, כדי לקבל את הדטרמיננטה של המטריצה המקורית, כל מה שנשאר לעשות הוא לכפול את האיברים שעל האלכסון ולקבל ש…\( 2\cdot\left(-7\right)\cdot\frac{69}{14}=-69 \). הא. קיבלנו בסופו של דבר דטרמיננטה שהיא לא שבר אלא מספר שלם נחמד. זה לא באמת מפתיע, אם חושבים על זה - בהגדרה שנתתי לדטרמיננטה (וגם בהגדרות התיאורטיות יותר) לא מעורב חילוק - יש לנו סכומים של מכפלות של האיברים שבתוך המטריצה, כך שאם כולם היו מספרים שלמים, גם הדטרמיננטה תצא מספר שלם.

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

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

\( A=\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array}\right] \)

אותי מה שמעניין כאן הוא העמודה הראשונה. היעד שלי הוא ליצור מטריצה משולשית עליונה, אז בשביל זה אני רוצה לאפס את כל הכניסות בעמודה הראשונה. את זה אני אעשה בכוח, כפי שתיארתי כבר. כדי לאפס את \( a_{21} \) אני מחבר לשורה השניה את הראשונה כשהיא מוכפלת ב-\( -\frac{a_{21}}{a_{11}} \), בשביל השלישית אני מכפיל ב-\( -\frac{a_{31}}{a_{11}} \) וכן הלאה. אני אקבל:

\( A=\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}\\ 0 & \frac{a_{22}a_{11}-a_{21}a_{12}}{a_{11}} & \cdots & \frac{a_{2n}a_{11}-a_{21}a_{1n}}{a_{11}}\\ \vdots & \vdots & \ddots & \vdots\\ 0 & \frac{a_{n2}a_{11}-a_{n1}a_{12}}{a_{11}} & \cdots & \frac{a_{nn}a_{11}-a_{n1}a_{1n}}{a_{11}} \end{array}\right] \)

החל מהנקודה הזו, העמודה והשורה הראשונות לא מעניינות אותי יותר. הרי אם אני אתחיל לפתח את הדטרמיננטה על פי העמודה הראשונה, אני אקבל שהיא שווה ל-\( a_{11} \) כפול הדטרמיננטה של מה שמתקבל ממחיקת השורה והעמודה הראשונה. אז נמחק אותן ונטפל ביתר המטריצה על פי אותו עיקרון, עד שנסיים לטפל בכל העמודות. אם כן, האם סיימנו? לא, בגלל שהתעלמתי מבעיה אחת שיכולה לצוץ: מה אם \( a_{11}=0 \)?

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

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

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

def det(A):
    result = 1
    n = len(A)
    # go over all columns k=0,1,...,n-1
    for k in range(n):
        if A[k][k] == 0:
            for i in range(k+1, n):
                if A[i][k] != 0:
                    A[k], A[i] = A[i], A[k]
                    result *= -1
                    break
            if A[k][k] == 0:
                return 0
        # go over all rows i=k+1,k+2,...,n-1
        result *= A[k][k]
        for i in range(k+1, n):
            factor = A[i][k] / A[k][k]
            # go over all the nonzero elements in row i
            for j in range(k, n):
                A[i][j] -= factor * A[k][j]
    return result

אז זו הדרך הרגילה לחישוב דטרמיננטות; בפוסט הבא נראה משהו קצת שונה.