כפל מטריצות - מה, לעזאזל?

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

כשאני אומר “מזכיר”, אני מתכוון שמתקיים למשל \( 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 \) אכן מערב לו עוד אלגברה לינארית שטרם הגעתי אליה (בפרט, את המושגים של ערכים עצמיים ווקטורים עצמיים).

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