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

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

נניח שיש לנו מרחב וקטורי \(V\) ויש לו שני בסיסים סדורים \(B=\left\{ b_{1},\dots,b_{n}\right\} \) ו-\(C=\left\{ c_{1},\dots,c_{n}\right\} \). נניח גם שיש לנו וקטור \(v\), שנתון לנו על ידי וקטור הקואורדינטות שלו לפי \(B\): \(\left[v\right]_{B}\). האם יש לנו דרך נוחה לקבל את וקטור הקואורדינטות שלו על פי \(C\)? כמובן, אפשר לתת תשובות לשאלה הזו שהן ספציפיות למרחב הוקטורי שבו אנו עובדים – אפשר לקחת את וקטור הקואורדינטות \(\left[v\right]_{B}\), לחשב ממנו ייצוג מפורש נוח כלשהו עבור \(v\) ואז לחשב מהייצוג המפורש הזה את \(\left[v\right]_{C}\). אלא שלא באמת צריך את זה. בואו נזכור שלכל טרנספורמציה \(T:V\to V\) אפשר לדבר על המטריצה \(\left[T\right]_{B}^{C}\) שמייצגת את \(T\) על פי הבסיסים \(B,C\). כאן קורה משהו טיפה מוזר – \(T\) היא ממרחב כלשהו אל עצמו, ועם זאת אנו מתעקשים להשתמש בשני בסיסים שונים – אבל הפורמליזם תקין, ומתקיים \(\left[T\right]_{B}^{C}\left[v\right]_{B}=\left[T\left(v\right)\right]_{C}\). כעת, בואו נבחר בתור \(T\) טרנספורמציה פשוטה במיוחד: טרנספורמציית הזהות, \(I\), שמקיימת \(I\left(v\right)=v\) לכל \(v\in V\). כעת מה יקרה? \(\left[I\right]_{B}^{C}\left[v\right]_{B}=\left[v\right]_{C}\) ממש על פי הגדרה, כלומר \(\left[I\right]_{B}^{C}\) היא מטריצה שההכפלה בה עושה בדיוק את מה שרצינו. למטריצה כזו אני קורא מטריצת המעבר מהבסיס \(B\) לבסיס \(C\), ואולי כדאי להזהיר מראש שיש ספרים שדווקא קוראים לה מטריצה המעבר מ-\(C\) אל \(B\), אלוהים יודע למה.

את מטריצת המעבר הזו קל לחשב: פשוט לוקחים את אברי \(B\), מוצאים את וקטורי הקואורדינטות שלהם לפי הבסיס \(C\) ואלו עמודות מטריצת המעבר, שאסמן \(M_{B}^{C}\) לצורך פשטות.

כעת, כמו שהגדרתי את \(M_{B}^{C}\) אני יכול באותה מידה בדיוק להגדיר את \(M_{C}^{B}\) שמעבירה מהבסיס \(C\) לבסיס \(B\). כעת עולה מאליה השאלה מהי המטריצה \(M_{C}^{B}M_{B}^{C}\), והתשובה האולי לא מפתיעה היא שמדובר על מטריצת היחידה \(I\) (כן, אותו סימון לטרנספורמציה ומטריצה! אהההה!) שבה יש 1-ים על האלכסון הראשי ו-0-ים בכל מקום אחר. למטריצת היחידה התכונה הנחמדה שאם כופלים אותה בוקטור כלשהו הוא אינו משתנה, כך שהיא מייצגת את הטרנספורמציה "לא משנים כלום, אפילו לא את הקואורדינטות" שהיא בדיוק גם הטרנספורמציה ש-\(M_{C}^{B}M_{B}^{C}\) מבצעת (אם העברנו קואורדינטות מ-\(B\) אל \(C\) אבל אז חזרנו מ-\(C\) אל \(B\) אז לא עשינו כלום). בדומה גם \(M_{B}^{C}M_{C}^{B}=I\).

באופן כללי אם יש לנו שתי מטריצות \(P,Q\) מסדר \(n\times n\) – כלומר, ריבועיות, כך ש-\(PQ=QP=I\) אומרים על שתיהן שהן הפיכות ומסמנים \(Q=P^{-1}\). מה שראינו כרגע הוא שמטריצות המעבר בין בסיסים הן הפיכות וראינו גם מה ההופכי שלהן. איך כל זה קשור לשאלה המקורית שלי על מטריצות שונות שמייצגות את אותה טרנספורמציה? טוב ששאלתם.

תהא לה \(T:V\to V\) טרנספורמציה ממרחב אל עצמו (לפעמים קוראים בשם "אופרטור" לכזו טרנספורמציה, אבל זה לא קשר מחייב) ויהיו \(B,C\) בסיסים של \(V\). לצורך פשטות אסמן את \(\left[T\right]_{B}^{B}\) פשוט כ-\(\left[T\right]_{B}\)(כלומר, אם אותו בסיס משמש גם בתור הבסיס של המקור וגם בתור הבסיס של היעד – מה שאפשרי רק עבור אופרטורים – כותבים אותו רק פעם אחת) וכעת השאלה שלי היא מה טיב הקשר בין \(\left[T\right]_{B}\) ובין \(\left[T\right]_{C}\). הפתרון טמון באבחנה הבאה: להפעיל את \(\left[T\right]_{C}\) על וקטור קואורדינטות על פי \(C\) זה אותו דבר בדיוק כמו לקחת וקטור קואורדינטות על פי \(C\), להמיר אותו לוקטור קואורדינטות על פי \(B\), להפעיל את \(\left[T\right]_{B}\) על התוצאה, ואת התוצאה הזו להמיר חזרה לבסיס \(C\). בנוסחה:

\(\left[T\right]_{C}=M_{B}^{C}\left[T\right]_{B}M_{C}^{B}\)

ובניסוח טיפה שונה: אם \(P\) היא מטריצת המעבר מהבסיס \(C\) לבסיס \(B\), אז \(\left[T\right]_{C}=P^{-1}\left[T\right]_{B}P\). זה מראה שאם אנחנו רוצים לעשות שינוי במערכת הקואורדינטות שבה אנו מייצגים את המרחב, כל שעלינו לעשות הוא לחשב את מטריצת המעבר בין שתי מערכות הקואורדינטות, ואז נוכל לתקן בהתאם את הכל – גם וקטורים, וגם מטריצות שמתארות טרנספורמציות מורכבות.

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

באופן כללי במתמטיקה, לא רק באלגברה לינארית, צצה לפעמים סיטואציה שבה שני איברים \(a,b\) קשורים ביניהם על ידי משוואה מהצורה \(a=x^{-1}bx\). דוגמה קלאסית היא תמורות בתורת החבורות; לא אכנס לכך כעת, אבל כדאי לדעת שזה קיים. אם \(a=x^{-1}bx\) אז אומרים ש-\(a\) התקבל מ-\(b\) על ידי הצמדה על ידי \(x\); במקרה של מטריצות, אם מטריצה \(A\) מתקבלת ממטריצה \(B\) על ידי הצמדה, אומרים ש-\(A\) דומה ל-\(B\).

שימו לב לכך ש-\(A=I^{-1}AI\) ולכן כל מטריצה דומה לעצמה; לכך שאם \(A=P^{-1}BP\) אז \(B=PAP^{-1}\) ולכן \(B\) דומה ל-\(A\) (על ידי הצמדה ב-\(P^{-1}\)); ואם \(A=P^{-1}BP\) ו-\(B=Q^{-1}CQ\) אז \(A=\left(QP\right)^{-1}C\left(QP\right)\) (התוצאה האחרונה נובעת מהטענה הטכנית שלא הוכחתי לפיה \(\left(AB\right)^{-1}=B^{-1}A^{-1}\) לכל זוג מטריצות הפיכות \(A,B\)). שלוש הטענות הללו יחד מראות כי דמיון מטריצות הוא יחס שקילות: אפשר לחלק את מרחב כל המטריצות לקבוצות כך שבכל קבוצה כל המטריצות דומות זו לזו. מסקנה אחת מכך היא שאם יש לי שתי טרנספורמציות שמיוצגות (כל אחת בבסיס אחר) על ידי אותה מטריצה, הן מיוצגות בדיוק על ידי אותן מטריצות. זה בפרט מראה שתכונות מסויימות של הטרנספורמציה שבאות לידי ביטוי במטריצות שמייצגות אותה חייבות להישמר על ידי הצמדה. אולי הדוגמה הכי בולטת היא הפיכות – אם טרנספורמציה היא הפיכה (כלומר, חח"ע ועל) אז גם כל המטריצות שמייצגות אותה חייבות להיות הפיכות, ולכן הצמדה של מטריצה הפיכה גם היא הפיכה. למעשה, יש עוד מספר תכונות חשובות שנשמרות אבל כדי להציג אותן יש צורך להתעסק קצת יותר לעומק במטריצות וזאת טרם עשיתי.

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

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

כשאני אומר "מזכיר", אני מתכוון שמתקיים למשל \(A+B=B+A\) (כלל החילוף), ושמתקיים \(A\left(B+C\right)=AB+AC\) (כלל הפילוג) ומתקיים \(\left(AB\right)C=A\left(BC\right)\) (כלל הקיבוץ, שמתקיים גם לחיבור). בנוסף, עוד לפני שהפוסט הזה יסתיים נראה איך פעולת הכפל של מטריצות מתקשרת הן לפתרון משוואות והן לבעיה שונה לחלוטין – ספירת מסלולים בגרפים.

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

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

בואו ניזכר טיפה מהן מטריצות. מטריצה \(A\) שהיא מסדר \(n\times m\) כוללת \(nm\) "כניסות", כך שכל כניסה היא בעלת שני אינדקסים – הראשון בין 1 ו-\(n\) ("שורה") והשני בין 1 ו-\(m\) ("עמודה"). כל כניסה כוללת מספר כלשהו (לצורך הדיון בינתיים אני מניח שזה מספר ממשי). את הכניסה בשורה \(i\) ועמודה \(j\) מסמנים ב-\(A_{ij}\).

כעת, אם יש לנו שתי מטריצות \(A,B\), כיצד נגדיר מטריצה \(C=A+B\)? בתור התחלה, אף אחד לא אומר שאנחנו בכלל יודעים איך להגדיר כזה דבר; אם \(A,B\) לא שתיהן בדיוק מאותם מימדים – כלומר, עם \(n\) שורות ועם \(m\) עמודות, החיבור כלל לא מוגדר פשוט כי לא ברור איך נכון להגדיר אותו. אבל, אם \(A,B\) שתיהן מאותן מימדים יש הגדרה מאוד טבעית שצצה לראש – נחבר אותן "כניסה כניסה". בדוגמה:

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

ובהגדרה פורמלית: אם \(C=A+B\) אז \(C_{ij}=A_{ij}+B_{ij}\).

זה מוביל אותנו גם להגדרה מאוד טבעית ופשוטה של כפל: אם \(C=AB\) אז \(C_{ij}=A_{ij}B_{ij}\). כלומר, כופלים את המטריצות "כניסה כניסה". זו לא ההגדרה שאני רוצה להציג. לא שזו לא הגדרה קיימת; למכפלה "כניסה כניסה" קוראים "מכפלת הדמר", מסמנים אותה ב-\(A\circ B\) ומתעסקים איתה קצת. אלא שהשם "כפל מטריצות" שמור לפעולה שונה, שהיא פי עשרות מונים יותר נפוצה ושימושית.

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

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

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

פורמלית, \(\left(a_{1},a_{2},\dots,a_{n}\right)\cdot\left(b_{1},b_{2},\dots,b_{n}\right)=a_{1}b_{1}+a_{2}b_{2}+\dots+a_{n}b_{n}\), וזו ההזדמנות שלי להציג סימן מקוצר לחיבור שהוא קריטי כשמדברים על כפל מטריצות: \(\Sigma\). בסימון המקוצר הזה המכפלה הסקלרית של הוקטורים שלמעלה מתוארת כך: \(\sum_{i=1}^{n}a_{i}b_{i}\). מה שקורה כאן הוא שבתחתית של ה-\(\Sigma\) מגדירים "משתנה אינדקס" בשם \(i\) ו"מאתחלים" אותו ל-1; ה-\(n\) למעלה פירושו "לכל ערך טבעי של \(i\) החל מערך האתחול שלו ועד ל-\(n\)", וה-\(a_{i}b_{i}\) אומר שלכל \(i\) שרצים עליו, מוסיפים לסכום של \(a_{i}b_{i}\). אין כאן שום דבר יותר מאשר כתיב מקוצר של \(a_{1}b_{1}+a_{2}b_{2}+\dots+a_{n}b_{n}\) שדורש הרבה, הרבה פחות מקום; ולשם שינוי אני לא אתחיל להגדיר פעולות כפל מוזרות גם על ה-\(\Sigma\) הזה עצמו.

עכשיו אפשר לתת הגדרה בנפנוף ידיים מהיר של כפל מטריצות: \(C=AB\) היא מטריצה שהכניסה ה-\(ij\) שלה היא התוצאה של המכפלה הסקלרית של השורה ה-\(i\) של \(A\) עם העמודה ה-\(j\) של \(B\). הרי על שורה של מטריצה אפשר לחשוב גם כוקטור שורה העומד בפני עצמו; ועל עמודה של \(j\) אפשר לחשוב גם כוקטור עמודה העומד בפני עצמו; ואפשר להכפיל אותם; והתוצאה תהיה מספר, אז ההגדרה שנתתי היא בעלת משמעות.

יש בכל זאת בעיה אחת שמייד קופצת: כדי לכפול סקלרית שני וקטורים הם צריכים להיות מאותו האורך. אם אני כופל שורות של \(A\) בעמודות של \(B\), זה אומר שאני צריך שהאורך של כל שורה של \(A\) יהיה זהה לאורך של כל עמודה של \(B\). זה אומר, למשל, שאי אפשר לכפול יחד שתי מטריצות מסדר \(2\times3\)! במטריצה \(\left[\begin{array}{ccc}1 & 2 & 3\\1 & 2 & 3\end{array}\right]\) האורך של כל שורה הוא 3 (כמספר העמודות במטריצה) והאורך של כל עמודה הוא 2 (כמספר השורות במטריצה) וזה אומר שעל פי ההגדרה שנתתי אי אפשר לכפול אותה אפילו עם עצמה! זה מוזר למדי אבל זו אכן תוצאה הכרחית של ההגדרה שלי.

לכן הנה הכלל: אם \(A\) היא מטריצה מסדר \(n\times m\) (\(n\) שורות, \(m\) עמודות) ו-\(B\) היא מטריצה מסדר \(k\times l\) (\(k\) שורות, \(l\) עמודות) אז כדי שתהיה משמעות למכפלה \(AB\) חייב להתקיים \(m=k\) (מספר העמודות של \(A\) שווה למספר השורות של \(B\)). אם אכן \(m=k\), אז המכפלה \(AB\) תהיה מטריצה מסדר \(n\times l\) (\(n\) שורות, \(l\) עמודות), כי יש כניסה ב-\(AB\) לכל זוג של שורה ב-\(A\) ועמודה ב-\(B\) שמוכפלות סקלרית.

בואו נראה דוגמה: \(\left[\begin{array}{ccc}1 & 2 & \pi\\0 & 3 & 6\end{array}\right]\left[\begin{array}{cc}5 & 0\\1 & 0\\0 & 1\end{array}\right]=\left[\begin{array}{cc}7 & \pi\\3 & 6\end{array}\right]\). למה הכניסה \(1,1\) של המכפלה היא 7? כי זו התוצאה של המכפלה הסקלרית \(\left(1,2,\pi\right)\cdot\left(5,1,0\right)=5+2+\pi\cdot0=7\). נסו להבהיר לעצמכם למה שאר הכניסות קיבלו את הערכים שהן קיבלו, ולמה הממדים של התוצאה הם \(2\times2\). אם הצלחתם, כבר הבנתם את ההגדרה גם אם טרם הבנתם "למה".

בואו נגדיר כפל באופן פורמלי כדי שלא יהיו ספקות. אם \(A\) היא מטריצה מסדר \(n\times m\) ו-\(B\) היא מטריצה מסדר \(m\times k\) אז \(C=AB\) היא מטריצה מסדר \(n\times k\) כך ש-

\(C_{ij}=\sum_{r=1}^{m}A_{ir}B_{rj}\)

זה הכל.

לכפל מטריצות יש תכונה מוזרה אחת (מוזרה עבור מי שרגיל לכפל "רגיל") שצריך לשים על השולחן כמה שיותר מהר: לא בהכרח מתקיים \(AB=BA\). ראשית, בכלל לא ברור שתהיה משמעות גם ל-\(AB\) וגם ל-\(BA\); בשביל זה שתי המטריצות חייבות להיות עם אותו מספר שורות ועמודות – מטריצות כאלו מכונות מטריצות ריבועיות. אבל גם אם \(A,B\) שתיהן ריבועיות מסדר \(n\times n\) זה ממש לא נכון שבהכרח יתקיים \(AB=BA\) (אם כי לפעמים זה כן קורה). למשל, \(\left[\begin{array}{cc}1 & 1\\0 & 0\end{array}\right]\left[\begin{array}{cc}1 & 0\\1 & 0\end{array}\right]=\left[\begin{array}{cc}1 & 0\\0 & 0\end{array}\right]\) אבל \(\left[\begin{array}{cc}1 & 0\\1 & 0\end{array}\right]\left[\begin{array}{cc}1 & 1\\0 & 0\end{array}\right]=\left[\begin{array}{cc}1 & 1\\1 & 1\end{array}\right]\). אתם צריכים לחשוב על זה שהתכונה הזו לא מתקיימת בתור דבר טוב: זה אומר שאפשר לתאר עם כפל מטריצות עולם יותר עשיר משנדמה לנו, כי במציאות יש גם פעולות שהן לא חילופיות באופן הזה (למשל, הטרנספורמציות של צורות תלת ממדיות שהזכרתי בתחילת הפוסט אינן כאלו – לסובב ואז לשקף לא תמיד נותן אותו דבר כמו לשקף ואז לסובב).

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

\(2x+3y=17\)

\(8x-4y=6\)

ממש לא מעניין אותי הפתרון של המערכת. מה שכן מעניין אותי היא לתרגם את הבעיה "פתור את המערכת" לבעיה "פתור את המשוואה הבאה שמערבת מטריצות". לשם כך ראשית כל אסתכל על המטריצה של מקדמי המשוואה: \(\left[\begin{array}{cc}2 & 3\\8 & -4\end{array}\right]\). שימו לב שבניגוד לקודם, כעת אני לא לא מכניס פנימה גם את המספרים שמעבר לסימן השווה; אותם אני מכניס לוקטור נפרד – וקטור העמודה \(\left[\begin{array}{c}17\\6\end{array}\right]\). בנוסף, אני אכניס לתמונה וקטור חדש לגמרי – וקטור של משתנים: \(\left[\begin{array}{c}x\\y\end{array}\right]\). כעת מערכת המשוואות שלמעלה זהה לחלוטין למשוואה הבודדת הבאה על מטריצות:

\(\left[\begin{array}{cc}2 & 3\\8 & -4\end{array}\right]\left[\begin{array}{c}x\\y\end{array}\right]=\left[\begin{array}{c}17\\6\end{array}\right]\)

לא מאמינים? ובכן, קל לחשב על פי ההגדרה שנתתי שמתקיים \(\left[\begin{array}{cc}2 & 3\\8 & -4\end{array}\right]\left[\begin{array}{c}x\\y\end{array}\right]=\left[\begin{array}{c}2x+3y\\8x-4y\end{array}\right]\) (זכרו שוקטור עמודה הוא מטריצה, פשוט עם עמודה בודדת) ולכן השוויון שלמעלה הוא השוויון \(\left[\begin{array}{c}2x+3y\\8x-4y\end{array}\right]=\left[\begin{array}{c}17\\6\end{array}\right]\) ומכיוון שמשווים וקטורים "כניסה כניסה" זו בדיוק מערכת המשוואות המקורית.

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

ראשית, בואו נסתכל על מטריצה מיוחדת – מטריצת היחידה, \(I=\left[\begin{array}{ccc}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{array}\right]\). זו מטריצה מסדר \(3\times3\) אבל על פי אותו עיקרון ניתן להגדיר מטריצת יחידה לכל סדר (אבל היא חייבת להיות ריבועית) במילים, לכל כניסה \(ii\) יש במטריצת היחידה 1, ולכל כניסה \(ij\) כך ש-\(i\ne j\) יש בה 0. המקומות שבהם נמצאים ה-1-ים של המטריצה נקראים האלכסון הראשי של המטריצה.

המטריצה הזו מעניינת כי אם \(A\) היא מטריצה מסדר \(n\times m\) ו-\(I\) היא מטריצת יחידה מסדר \(n\times n\) אז \(IA=A\). כדי להבין למה, בואו ננסה להבין מהי הכניסה ה-\(ij\) של \(IA\): זו המכפלה הסקלרית של השורה ה-\(i\) של \(I\) בעמודה ה-\(j\) של \(A\). השורה ה-\(i\) של \(I\) כוללת רק אפסים חוץ ממקום אחד שכולל 1 – בדיוק המקום ה-\(i\). אז כשכופלים את השורה הזו בעמודה ה-\(j\) של \(A\) אנחנו מתעלמים מכל הכניסות בעמודה הזו חוץ מאחת – הכניסה ה-\(i\)-ית, שהיא בדיוק מה שנמצא בשורה ה-\(i\)-ית של \(A\). לכן בכניסה ה-\(ij\) של \(IA\) יהיה בדיוק את האיבר בכניסה ה-\(ij\) של \(A\).

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

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

אם כן, נניח ש-\(\overline{x}\) מסמן לנו וקטור של משתנים, ו-\(\overline{c}\) וקטור של מספרים, מערכת כללית של משוואות לינאריות מתוארת על ידי \(A\overline{x}=\overline{c}\) (שימו לב ש-\(\overline{x}\) ו-\(\overline{c}\) בכלל לא חייבים להיות מאותו האורך; אורכו של הראשון הוא מספר המשתנים ואורכו של השני הוא מספר המשוואות). כעת, אם \(E\) היא מטריצה אלמנטרית כלשהי, אפשר לכפול בה את שני אגפי המשוואה ולקבל \(\left(EA\right)\overline{x}=E\overline{c}\) (כמובן, צריך להוכיח שדברים כאלו באמת עובדים; אלו הוכחות לא מעניינות ולא אציג אותן כאן). אם אנחנו רוצים להפעיל שתי פעולות אלמנטריות, \(E_{1}\) ו-\(E_{2}\), אפשר לכפול את המשוואה בהן בזו אחר זו ולקבל \(\left(E_{2}\left(E_{1}A\right)\right)\overline{x}=E_{2}\left(E_{1}\overline{c}\right)\). כעת העובדה שכפל מטריצות מקיים את חוץ הקיבוץ הופכת לקריטית: זה אומר ש-\(E_{2}\left(E_{1}A\right)=\left(E_{2}E_{1}\right)A\), ולכן במקום לכפול את \(A\) קודם ב-\(E_{1}\) ואז ב-\(E_{2}\) אפשר לכפול את \(A\) רק פעם אחת במטריצה \(E_{2}E_{1}\) ש"מקודדת בתוכה" הפעלה של שתי פעולות אלמנטריות ולא רק אחת. באותו אופן, אם אנחנו רוצים להפעיל על \(A\) כמות סופית כלשהי של פעולות אלמנטריות, אפשר קודם כל לכפול את המטריצות האלמנטריות אלו באלו ובסוף לקבל מטריצה \(E\) שכבר מאחסנת בתוכה את כל הפעולות שרוצים לבצע על \(A\) כשהן מסודרות לפי הסדר הנכון. אחרי הכפל נקבל \(\left(EA\right)\overline{x}=E\overline{c}\); מכיוון ש-\(E\overline{c}\) הוא בעצמו וקטור אחר של מספרים, מה שקיבלנו בסופו של דבר הוא משוואה אחרת מהצורה \(B\overline{x}=\overline{d}\), שבה אנחנו יכולים להניח ש-\(B\) היא מטריצה מצומצמת. בקיצור, כשבפוסט הבא אחזור לעסוק בפתרון משוואות אוכל לצמצם את כל הבעיה שלנו למשוואות מהצורה \(B\overline{x}=\overline{d}\) עם מטריצות מצומצמות.

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

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

אנחנו רוצים לספור מסלולים בגרף. מסלול הוא פשוט סדרה של צמתים כל שכל שני צמתים בסדרה מחוברים בקשת, ואורכו הוא כמספר הקשתות שבו. לכל מסלול גם יש צומת התחלתי וצומת סופי – הצמתים הראשונים והאחרונים בסדרה. כך למשל \(v\to u\) הוא מסלול באורך 1 מ-\(v\) אל \(u\), ו-\(v\to u\to w\) הוא מסלול באורך 2 מ-\(v\) אל \(w\) (שעובר ב-\(u\)). גם \(v\) לבדו הוא מסלול: מסלול באורך 0 עם צומת התחלה \(v\) וצומת סיום \(v\). זה נשמע מטופש אבל תכף נראה שזו הגדרה מועילה.

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

כעת, נניח שיש לנו גרף עם \(n\) צמתים, \(v_{1},\dots,v_{n}\). מגדירים עבורו מטריצה \(A\) מסדר \(n\times n\) – "מטריצת השכנויות/סמיכויות" שלו – באופן הבא: \(A_{ij}\) שווה למספר הקשתות מ-\(i\) אל \(j\). כלומר זה מספר שלם אי שלילי (בגלל שאנחנו מרשים קשתות מקבילות, \(A_{ij}\) יכול להיות גדול מ-1; ובגלל שהגרף מכוון \(A_{ij}\) לא בהכרח שווה ל-\(A_{ji}\)).

מכיוון ש-\(A\) היא מטריצה ריבועית, אפשר לכפול אותה בעצמה. \(A^{k}\) היא מה שמקבלים כשכופלים את \(A\) בעצמה \(k\) פעמים. כמו ש-\(a^{0}=1\) עבור מספרים, כך מגדירים גם ש-\(A^{0}=I\) כאשר \(I\) היא מטריצת היחידה מסדר \(n\times n\).

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

למה זה עובד? ובכן, עבור \(A^{0}\) זה ברור מההגדרה שנתתי: מסלול באורך 0 חייב להתחיל ולהסתיים באותו צומת, ויש בדיוק 1 כזה. זה מתאים בדיוק לכך שעל האלכסון הראשי של \(A^{0}\) יש 1 ובשאר הכניסות יש 0.

עבור \(A^{1}\) זה גם ברור: כל קשת \(v\to u\) מגדירה מסלול באורך 1 מ-\(v\) אל \(u\), ולכן מספר המסלולים הכולל מ-\(v\) אל \(u\) באורך 1 הוא כמספר הקשתות מ-\(v\) אל \(u\).

הכיף מתחיל עבור \(A^{2}\), וכאן ההגדרה של כפל מטריצות מתגלה במלוא כוחה. מהו מסלול באורך 2? מסלול מהצורה \(v\to u\to w\) (הצמתים לא חייבים להיות שונים אלו מאלו בהכרח). אם אנחנו מתעניינים במספר המסלולים מ-\(v\) אל \(w\), אז כל מסלול כזה נבנה באופן הבא: בחר צומת \(u\) שישמש בתור צומת האמצע; בחר קשת מ-\(v\) אל \(u\) (אם קיימת כזו), ואז בחר קשת מ-\(u\) אל \(w\) (אם קיימת כזו).

כמה מסלולים כאלו יש? אם קבענו את \(u\), אז נותר לבחור קשת מ-\(v\) אל \(u\), ולבחור קשת מ-\(u\) אל \(w\), ושתי הבחירות הללו בלתי תלויות זו בזו, ולכן מספר האפשרויות הוא מכפלה של מספר האפשרויות לבחור קשת מ-\(v\) אל \(u\) במספר האפשרויות לבחור קשת מ-\(u\) אל \(w\) (זהו "עקרון הכפל" הקומבינטורי). כעת, לכל \(u\) שיכול לשמש כצומת ביניים אנחנו מקבלים מספר אפשרויות כלשהו, ולכן מספר האפשרויות הכולל הוא סכום כל האפשרויות על כל ה-\(u\)-ים האפשריים (זהו "עקרון החיבור" הקומבינטורי).

בואו נסמן את הצמתים במספרים כדי שיהיה לנו קצת יותר קל. נניח שאנחנו רוצים לדעת כמה מסלולים יש מ-\(v_{i}\) אל \(v_{j}\), וש-\(v_{r}\) הוא צומת הביניים שלנו. אז יש \(A_{ir}\) קשתות מ-\(v_{i}\) אל \(v_{r}\); \(A_{rj}\) קשתות מ-\(v_{r}\) אל \(v_{j}\); ולכן \(A_{ir}A_{rj}\) מסלולים מ-\(v_{i}\) אל \(v_{j}\) שעוברים דרך \(v_{r}\); ולכן \(\sum_{r=1}^{n}A_{ir}A_{rj}\) מסלולים בסך הכל מ-\(v_{i}\) אל \(v_{j}\). אבל \(\sum_{r=1}^{n}A_{ir}A_{rj}\) ידידינו הוא בדיוק ההגדרה שלנו לכניסה ה-\(ij\) בכפל המטריצה \(A\) בעצמה, ולכן \(A^{2}\) אכן מקודד בדיוק את המסלולים מאורך 2 בין צמתים בגרף.

ההוכחה הכללית עבור \(A^{t}\) פשוטה באותה מידה, אם שמים לב לכך ש-\(A^{t}=A^{t-1}A\) ומשתמשים באינדוקציה כדי להניח ש-\(A^{t-1}\) כבר מקודד את מספר המסלולים מאורך \(t-1\) בין צמתים בגרף. במקרה זה, אפשר לחשוב על מסלול מאורך \(t\) בגרף מ-\(v_{i}\) אל \(v_{j}\) כאילו הוא מהצורה \(v_{i}\rightarrow v_{r}\to v_{j}\), כאשר \(v_{i}\rightarrow v_{r}\) מייצג לא קשת אחת אלא מסלול שלם מאורך \(t-1\) מ-\(v_{i}\) אל \(v_{r}\). שאר הניתוח זהה: מספר המסלולים מ-\(v_{i}\) אל \(v_{j}\) מאורך \(t\) שהצומת הלפני-אחרון בהם הוא \(v_{r}\) הוא כמספר המסלולים מאורך \(t-1\) מ-\(v_{i}\) אל \(v_{r}\) כפול מספר הקשתות מ-\(v_{r}\) אל \(v_{j}\). סוף הסיפור.

אני לא יכול להתאפק כאן ולהזכיר מאוד בחטף נושא מתקדם טיפה יותר. נניח שהמטריצה \(A\) שלנו, במקום לקודד את מספר הקשתות, הייתה מקודדת הסתברות למעבר מ-\(v_{i}\) אל \(v_{j}\)? כלומר, הגרף שלנו היה כזה שבו אם אתם נמצאים בצומת מסוייים, אז בסיבוב הבא עליכם לזוז לצומת אחר (או להישאר במקום – זה נחשב כאילו זזתם מהצומת אל עצמו) והייתם בוחרים לאן לעבור בהסתברות קבועה מסויימת על בסיס המיקום הנוכחי שלכם. אם \(A\) הייתה המטריצה שמקודדת את ההסתברויות הללו, מה הייתה המשמעות של \(A^{t}\)? כמעט אותו דבר – \(A_{ij}^{t}\) הייתה ההסתברות שבה אם התחלתם מ-\(v_{i}\) וביצעתם \(t\) סיבובים, תגיעו אל \(v_{j}\). לכן אם אנחנו יודעים איך מתנהגת \(A^{t}\) עבור ערכים גדולים מאוד של \(t\), אנחנו יודעים מה ההתנהגות לאורך זמן של ההילוך האקראי הזה – לאיזה מקומות בגרף יותר סביר להגיע ולבלות בהם יותר זמן, וכדומה. הרעיון הזה עמד בבסיס אלגוריתם הדירוג של גוגל (מה שידוע על אלגוריתם הדירוג של גוגל, לפחות) כאשר הגרף הוא "האינטרנט" (ואתרים חשובים בו הם כאלו שאליהם ההילוך המקרי מגיע לעתים קרובות יותר) והניתוח של התנהגות \(A^{t}\) עבור ערכים גדולים של \(t\) אכן מערב לו עוד אלגברה לינארית שטרם הגעתי אליה (בפרט, את המושגים של ערכים עצמיים ווקטורים עצמיים).

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

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

בואו ניקח לדוגמה מערכת של שתי משוואות לינאריות בשני נעלמים:

\(2x+7y=21\)

\(2x-4y=10\)

לאלו שממש ממש במתח, הפתרון של המערכת הוא \(x=7,y=1\), אבל זה לא מה שמעניין אותנו כרגע, ואפילו לא איך פותרים אותה כי ראינו את השיטה לכך בפוסט הקודם, אלא פשוט איך אפשר לכתוב את המערכת הזו בצורה קצת פחות טרחנית מזו שבה כתבתי אותה. בצורת הכתיבה שלי יש הרבה טקסט מיותר – ה-\(x,y\) מיותרים כי אני יודע שבכל משוואה לינארית יהיו משתנים; וסימן השווה מיותר; וגם הפלוס שלפני ה-7 מיותר למרות שהמינוס שלפני הארבע לא. זה לא נראה כמו משהו גרוע עד כדי כך, אבל צריך לזכור שאנחנו חושבים על פתרון משוואות עוד יותר כלליות, כאלו שיש בהן גם שבעה נעלמים ושבע משוואות. בסיטואציות כאלו כבר מפסיקים לתת אות מיוחדת לכל משתנה ופשוט קוראים להם \(x_{1},x_{2},\dots,x_{7}\) וכדומה. די ברור שהשמות הללו הם חסרי משמעות עבורנו והיינו שמחים להימנע מהצורך להשתמש בהם.

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

\(\begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array}\)

טוב. חייבים להודות שזה לא נראה משהו. אז כדי שיהיה ברור שכל המספרים הללו קשורים אחד לשני, מקיפים אותם בסוגריים:

\(\left[\begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array}\right]\)

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

פורמלית, עבור מספרים טבעיים \(n,m\), מטריצה מסדר \(n\times m\) (בעלת \(n\) שורות ו-\(m\) עמודות) היא אוסף של איברים ("איברים", בכל הקשר שנזדקק לו, פירושו כאן "מספרים") כך שלכל איבר יש שני אינדקסים שמציינים באיזו שורה ובאיזו עמודה הוא נמצא במטריצה. למשל, במטריצה שהצגתי למעלה, האיבר בשורה 1 ועמודה 1 הוא 2, וגם האיבר בשורה 2 ועמודה 1 הוא 2; ואילו האיבר בשורה 2 ועמודה 3 הוא 10. לרוב משתמשים באותיות לטיניות גדולות כמו \(A,B,C\) כדי לתאר מטריצות, ואז \(A_{11}\) מסמן את האיבר בשורה 1 ובעמודה 1 במטריצה \(A\) (ה"כניסה" ה-\(1,1\) במטריצה), וכדומה. כלומר, אם

\(A=\left[\begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array}\right]\)

אז \(A_{12}=-4\) ו-\(A_{23}=10\) וכדומה.

מה קורה אם יש במטריצה מספר דו ספרתי של שורות או עמודות? ובכן, אפשר לכתוב משהו כמו \(A_{10,3}\) עם פסיק ואז לא יהיו בלבולים. בכל מקרה הסימון שאני מציג כאן הוא לא קדוש ויש עוד הרבה וריאציות עליו שבהן משתמשים.

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

1. אפשר להחליף שתי שורות.
2. אפשר לכפול שורה במספר שונה מאפס.
3. אפשר להוסיף לשורה אחת שורה אחרת שמוכפלת במספר כלשהו.

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

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

\(\left[\begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array}\right]\overset{r_{2}-r_{1}}{\to}\left[\begin{array}{ccc}2 & 7 & 21\\0 & -11 & -11\end{array}\right]\overset{-\frac{1}{11}r_{2}}{\to}\left[\begin{array}{ccc}2 & 7 & 21\\0 & 1 & 1\end{array}\right]\overset{r_{1}-7r_{2}}{\to}\left[\begin{array}{ccc}2 & 0 & 14\\0 & 1 & 1\end{array}\right]\overset{\frac{1}{2}r_{1}}{\to}\left[\begin{array}{ccc}1 & 0 & 7\\0 & 1 & 1\end{array}\right]\)

כשאני כותב \(r_{2}-r_{1}\) אני מתכוון "משנים את \(r_{2}\) – שורה 2 – על ידי כך שמחסירים ממנה את \(r_{1}\)". כשאני כותב "\(-\frac{1}{11}r_{2}\)" אני מתכוון "כופלים את \(r_{2}\) ב-\(-\frac{1}{11}\)", וכדומה. גם זה לא ממש סימון סטנדרטי אבל אני מקווה שהוא מספיק ברור כאן.

המטריצה שקיבלנו לבסוף, \(\left[\begin{array}{ccc}1 & 0 & 7\\0 & 1 & 1\end{array}\right]\), מייצגת את מערכת המשוואות הבאה:

\(x=7\)

\(y=1\)

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

מדוע המטריצה \(\left[\begin{array}{ccc}1 & 0 & 7\\0 & 1 & 1\end{array}\right]\) היא נקודת סיום טובה כל כך עבורנו? מכיוון שבכל שורה מופיע רק אחד המשתנים, והוא מופיע עם המקדם 1. זה אומר שאותה השורה בעצם אומרת "המשתנה כך וכך שווה ל…" ותו לא. אבל איך הצלחנו להגיע אליה? הפתרון טמון דווקא בעמודות. שימו לב שכבר הפעולה הראשונה שביצעתי בשרשרת המטריצות למעלה יועדה לגרום לכך שבעמודה הראשונה במטריצה, בשורה השניה, יהיה 0. מה שזה אומר בפועל הוא שמחקתי את המשתנה \(x\) מהמשוואה השניה והשארתי אותו רק בראשונה. אחר כך, כשחיברתי את השורה השניה לראשונה, זה כבר לא יכל להשפיע על המשתנה \(x\), כלומר על העמודה הראשונה, כי בשורה השניה היה שם 0.

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

אלא מה, לא תמיד אפשר לעשות את זה בכלל. למשל, מה עם המטריצה \(\left[\begin{array}{ccc}1 & 0 & 7\\0 & 0 & 0\end{array}\right]\)? לא משנה מה נעשה, העמודה השניה תמיד תכיל 0. ומה עם המטריצה \(\left[\begin{array}{ccc}1 & 1 & 1\\1 & 1 & 1\end{array}\right]\)? אנחנו לא יכולים לאפס את הכניסה בשורה 2 ועמודה 1 מבלי לאפס גם את הכניסה בשורה 2 ועמודה 2. לכן צריך להיות קצת יותר זהירים ביחס ליעד שלנו. זה המקום שבו צצה ההגדרה של מטריצה מצומצמת. זו הגדרה מדויקת של "מה שאנחנו יכולים לצפות לו תמיד מהתהליך שתיארנו", אבל לא קריטי להבין אותה במלואה בינתיים. בכל זאת אביא אותה פה, כמובן. מטריצה היא מצומצמת אם היא מקיימת ש:

1. בכל שורה שלה, הכניסה הראשונה שאיננה 0 היא 1.
2. בכל עמודה שלה, אם יש כניסה שהיא הכניסה הראשונה שאינה 0 בשורה כלשהי, אז שאר הכניסות בעמודה הן 0.
3. כל השורות שמכילות רק אפסים נמצאות מתחת לכל השורות האחרות.
4. בהינתן שתי שורות שאינן שורות אפסים, הכניסה הראשונה שאיננה אפס בשורה העליונה יותר מופיעה בעמודה מוקדמת יותר מאשר הכניסה הראשונה שאיננה אפס בעמודה השניה.

אולי הכי ברור להבין את ההגדרה הזו על ידי דוגמאות שלא מתאימות לה:

המטריצה \(\left[\begin{array}{cc}1 & 0\\0 & 2\end{array}\right]\) לא עונה לדרישה 1, כי הכניסה הראשונה שאיננה 0 בשורה 2 היא 2.

המטריצה \(\left[\begin{array}{cc}1 & 0\\1 & 1\end{array}\right]\) לא עונה לדרישה 2 כי העמודה הראשונה מפירה את התנאי: יש שתי כניסות שהן הכניסות הראשונות שאינן 0. גם \(\left[\begin{array}{cc}1 & 1\\0 & 1\end{array}\right]\) מפירה את התנאי בצורה דומה – כאן הכניסה \(A_{12}\) אמנם איננה הכניסה הראשונה שאיננה 0 בשורה הראשונה, אבל \(A_{22}\) היא כן הכניסה הראשונה שאיננה 0 בשורה 2, ולכן שאר העמודה צריכה להכיל אפסים.

דוגמה נגדית ל-3 זה קל מאוד: \(\left[\begin{array}{cc}0 & 0\\1 & 0\end{array}\right]\).

ההגדרה של 4 מסובכת אבל דוגמה נגדית היא פשוטה גם כאן: \(\left[\begin{array}{cc}0 & 1\\1 & 0\end{array}\right]\) היא דוגמה נגדית, כי השורה של ה-01 באה לפני השורה של ה-10 אבל הכניסה הראשונה שאיננה 0 בשורה 01 היא בעמודה 2, ואילו הכניסה הראשונה שאיננה 0 בשורה 10 היא בעמודה 1.

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

כעת אפשר להבין למה כל ארבע התכונות שתיארתי למעלה הן הכרחיות בשביל שהמטריצה המצומצמת תהיה יחידה: כל הדוגמאות הנגדיות שנתתי עונות על כל שלוש הדרישות פרט לדרישה שהן באות לנגוד, כך שאם נשמיט ולו אחת מהדרישות, כבר יהיו שתי מטריצות מצומצמת אפשריות. במקרה הראשון \(\left[\begin{array}{cc}1 & 0\\0 & 2\end{array}\right]\) ניתנת לצמצום אל \(\left[\begin{array}{cc}1 & 0\\0 & 1\end{array}\right]\); במקרה השני \(\left[\begin{array}{cc}1 & 0\\1 & 1\end{array}\right]\) ניתנת לצמצום אל \(\left[\begin{array}{cc}1 & 0\\0 & 1\end{array}\right]\); במקרה השלישי \(\left[\begin{array}{cc}0 & 0\\1 & 0\end{array}\right]\) ניתנת לצמצום אל \(\left[\begin{array}{cc}1 & 0\\0 & 0\end{array}\right]\) ובמקרה הרביעי \(\left[\begin{array}{cc}0 & 1\\1 & 0\end{array}\right]\) ניתנת לצמצום אל \(\left[\begin{array}{cc}1 & 0\\0 & 1\end{array}\right]\).

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

\(\left[\begin{array}{ccc}0 & 2 & 1\\2 & 1 & 1\\1 & 3 & 1\end{array}\right]\overset{r_{1}\leftrightarrow r_{2}}{\to}\left[\begin{array}{ccc}2 & 1 & 1\\0 & 2 & 1\\1 & 3 & 1\end{array}\right]\overset{\frac{1}{2}r_{1}}{\to}\left[\begin{array}{ccc}1 & \frac{1}{2} & \frac{1}{2}\\0 & 2 & 1\\1 & 3 & 1\end{array}\right]\overset{r_{3}-r_{1}}{\to}\left[\begin{array}{ccc}1 & \frac{1}{2} & \frac{1}{2}\\0 & 2 & 1\\0 & \frac{5}{2} & \frac{1}{2}\end{array}\right]\)

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

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

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