ארכיון הקטגוריה: אלגברה לינארית

עם קצת עבודה, מגיעים למכפלה סקלרית

פורסם בתאריך על ידי
1

אחד המושגים שתמיד בלבל אותי בפיזיקה הוא מושג העבודה. בואו נציג אותו בקצרה עבור מי שלא מכירים. נקודת המוצא שלנו היא החוק השני של ניוטון, \(F=ma\), שאומר שאם כוח כלשהו פועל על גוף (\(F\) הוא גודל הכוח, והוא חיובי אם הכוח מופעל "ימינה" ושלילי אם הוא מופעל "שמאלה") אז הוא גורם לגוף לתאוצה \(a\) שפרופורציונית הפוכה למסת הגוף \(m\) (תכפילו את המסה פי 2, והתאוצה לה גורם אותו כוח תקטן פי 2). אני מציג כאן בכוונה גרסה פשוטה של החוק כי לא נצטרך יותר מכך. בנוסף, שימו לב שהעולם שלי בינתיים הוא חד ממדי – עצמים יכולים לנוע רק ימינה או שמאלה. זה יסתבך בקרוב.

כעת, מהי תאוצה? היא מוגדרת בתור השינוי במהירות לאורך זמן. ומהי מהירות? השינוי במיקום לאורך זמן. אם גוף מתחיל ממיקום \(x_{0}\) כשמהירותו ההתחלתית \(v_{0}\) ומאותו רגע והלאה הוא מאיץ בתאוצה קבועה \(a\), אז אחרי זמן \(t\) מהירותו תהיה \(v\left(t\right)=at+v_{0}\) ומיקומו יהיה \(x\left(t\right)=\frac{at^{2}}{2}+v_{0}t+x_{0}\) (למשוואות הללו ניתן להגיע באמצעות אינטגרציה: \(\int adt=at+v_{0}\) ו-\(\int\left(at+v_{0}\right)dt=\frac{at^{2}}{2}+v_{0}t+x_{0}\), אבל למי שזה לא אומר לו כלום, לא נורא). יש לנו אם כן שלושה גורמים שונים שאיכשהו מתקשרים ביניהם יחדיו – מהירות הגוף, מיקום הגוף, והכוח שפעל על הגוף. האם יש לנו דרך לתאר את כל הסיפור הזה מבלי להכניס לתמונה בכלל גורמים כמו התאוצה והזמן?

באופן די מפתיע, מתברר שכן. בואו נניח שניה ש-\(x_{0}=v_{0}=0\) כדי לפשט את המשוואות, ונתבונן במהירות ובמיקום אחרי זמן \(t\) מסויים. המהירות היא \(v=at\) והמיקום הוא \(x=\frac{at^{2}}{2}\) . מכיוון ש-\(t\) מופיע בריבוע במשוואה של המיקום, בואו נעלה גם את משוואת המהירות בריבוע ונקבל \(v^{2}=a^{2}t^{2}\). עכשיו, בואו נבודד את \(t^{2}\) ממשוואת המיקום ונקבל \(t^{2}=\frac{2x}{a}\). נציב במשוואת המהירות ונקבל \(v^{2}=2xa\). כעת נחליף את \(a\) ב-\(\frac{F}{m}\), בעזרת החוק השני של ניוטון, ונקבל \(v^{2}=2x\frac{F}{m}\). נחלק ב-\(\frac{2}{m}\) וקיבלנו את המשוואה \(\frac{mv^{2}}{2}=Fx\).

מה שמעניין במשוואה הזו (וכעת אנפנף קצת בידיים) הוא שהיא מתארת באגף ימין שלה תהליך שהתרחש לאורך זמן, בלי לציין את הזמן בכלל – הכוח \(F\) פעל על הגוף לכל אורך תנועתו של הגוף מרחק של \(x\). באגף שמאל, לעומת זאת, יש לנו גודל "רגעי" – \(\frac{mv^{2}}{2}\) מתאר את המהירות והמסה כאן ועכשיו. כאמור, זה נפנוף ידיים שאין לו משמעות אמיתית, אבל אני חושב שהוא נותן אינטואיציה טובה לסיבה שבגללה מייחדים ל-\(\frac{mv^{2}}{2}\) שם – אנרגיה קינטית. להסביר עכשיו מה הכוונה במילה "אנרגיה" (בוריאציה על איניגו מונטויה – הרבה אנשים משתמשים שוב ושוב במילה הזו, אך איני חושב שהיא אומרת מה שהם חושבים שהיא אומרת) לא אנסה אפילו; אני מסתפק בהצהרה ש-\(\frac{mv^{2}}{2}\) היא כמות "מעניינת" ואסמן אותה ב-\(E\).

כעת בואו לא נתעצל ונחשוב מה קורה אם \(x_{0}\) ו-\(v_{0}\) הם ערכים כלליים. וכשאני אומר "לא נתעצל" אני מתכוון – קחו נייר ועט ועשו את החישוב בעצמכם כדי לראות שהבנתם. אני את החישוב עשיתי בצד, והנה מה שמקבלים: \(\frac{m\left(v^{2}-v_{0}^{2}\right)}{2}=F\left(x-x_{0}\right)\). ברשותכם, אסמן \(E=\frac{mv^{2}}{2}\) ו-\(E_{0}=\frac{mv_{0}^{2}}{2}\) – אלו האנרגיות בהתחלה ובסוף, ואסמן \(\Delta E=E-E_{0}\) – זהו השינוי באנרגיה הקינטית של הגוף, ואסמן \(\Delta x=x-x_{0}\) – זה השינוי במיקום הגוף, וקיבלנו את המשוואה

\(\Delta E=F\cdot\Delta x\)

ובמילים – השינוי באנרגיה הקינטית של הגוף כתוצאה מפעולת הכוח \(F\) שווה לגודל הכוח הזה כשהוא מוכפל בשינוי המיקום של הגוף (שימו לב ש"שינוי המיקום של הגוף" – מה שנקרא לפעמים "ההעתק" – אינו בדיוק המרחק שלו; אם הגוף היה בהתחלה בנקודה 0 ובסיום התנועה בנקודה \(-10\), אז \(\Delta x=-10\) למרות שהגוף עבר מרחק של 10).

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

מה שדיברנו עליו עד כה היה עולם חד-ממדי. בעולם הזה לכוחות ולמהירויות ולהעתקים אין ממש כיוון, אם כי הם יכולים להיות חיוביים או שליליים ולפי זה נקבע הסימן שלהם. מה שעשיתי עד כה היה עקבי עם הגישה הזו – למשל, אם \(\Delta x\) הוא חיובי אבל \(F\) הוא שלילי, מה שהמשוואות מתארות הוא גוף שנע בכיוון החיובי כשבאותו הזמן פועל עליו כוח בכיוון הנגדי, כלומר כוח שדווקא מאיט אותו. התוצאה? שינוי שלילי באנרגיה הקינטית (מכפלה של \(\Delta x\) החיובי ב-\(F\) השלילי), מה שמתאים לנו להאטה. שימו לב שאנחנו רואים כאן ש-\(F\) בכלל לא חייב להיות הגורם לשינוי במיקום; הנקודה היא ש-\(F\) משפיע על אופי השינוי במיקום, ואיכשהו אפשר לחלץ מההשפעה הזו בדיוק את השינוי באנרגיה הקינטית ש-\(F\) גרם לגוף. זה רעיון לא טריוויאלי כלל לטעמי.

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

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

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

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

נניח שהגוף שלנו נמצא כרגע בגובה \(h\) מעל פני הקרקע. אפשר לשים אותו על הרבה משטחים משופעים – למשל, משטח שנמצא בזווית של \(90^{\circ}\) ביחס לקרקע, כך שהגוף פשוט ייפול באופן חופשי לקרקע; או משטח בזווית של \(45^{\circ}\) שהוא נקודת האמצע בין משטח ניצב ומשטח שטוח; או משטח שהוא "כמעט שטוח", נאמר עם זווית של מעלה בודדת, ובו הכדור בקושי יזוז בהתחלה. באופן כללי אם אורך המשטח הוא \(L\) והוא מגיע לגובה \(h\), אז הזווית שהוא יוצר עם ניצב לפני הקרקע, שאסמן ב-\(\alpha\), מקיימת \(\cos\alpha=\frac{h}{L}\). תכף תהיה לזווית הזו חשיבות רבה.

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

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

במערכת הצירים הזו, הכיוון החיובי של ציר \(x\) הוא פני המשטח המשופע, ולכן הזווית שיוצר וקטור כוח הכובד עם ציר \(x\) היא \(\alpha\) (אל תתעצלו! שבו וציירו את זה בעצמכם! זו הדרך הכי טובה להבין מה הולך כאן). את כוח הכובד עצמו אנחנו מפרקים לסכום של שני וקטורים – \(\vec{F}=\vec{F}_{x}+\vec{F}_{y}\), כך ש-\(\vec{F}_{x}\) הוא וקטור שכיוונו ככיוון ציר \(x\) ואילו \(\vec{F}_{y}\) הוא וקטור שכיוונו ככיוון ציר \(y\) (חיבור וקטורים פועל כך: לוקחים את אחד הוקטורים ושמים בראשית הצירים, מדביקים את השני בקצהו, ואז הוקטור החדש הוא הוקטור מראשית הצירים אל נקודת הקצה של הוקטור השני). בעזרת טריגונומטריה אנחנו יודעים לחשב את גדלי הוקטורים הללו: \(F_{y}=F\sin\alpha\) ו-\(F_{x}=F\cos\alpha\). במילים אחרות, הכוח שגורם לתנועה של העצם על המשטח המשופע הוא \(F\cos\alpha\), וכוח זה פועל באותו כיוון כמו ההעתק של הגוף. כשהגוף מגיע לתחתית המשטח המשופע הוא עבר מרחק של \(L\), ולכן העבודה של \(F\) הייתה בדיוק \(F\cdot L\cdot\cos\alpha\). זו המשוואה החשובה ביותר בפוסט; הסיבה שבגללה כתבתי אותו מלכתחילה.

לפני שאני מרחיב על המשוואה הזו, בואו רק נשים לב לכך שמכיוון ש-\(\cos\alpha=\frac{h}{L}\) הרי שהעבודה של כוח הכובד על הגוף היא בעצם \(F\cdot L\cdot\cos\alpha=F\cdot h\). כעת, אם כוח הכובד גורם לתאוצה \(g\) בגוף, כלומר \(F=mg\), אפשר לכתוב את המשוואה הזו גם כ-\(F\cdot h=mgh\), וקיבלנו שהשינוי באנרגיה הקינטית של הגוף הוא בדיוק \(mgh\). כעת שימו לב ש-\(mgh\) הוא גודל שתלוי בשני ערכים שהם קבועים במערכת שלנו – \(m,g\) ובערך שלישי, שהוא הגובה שהגוף "איבד". אפשר לחשוב על זה גם כך – כאשר הגוף היה בגובה \(h\), היה לו פוטנציאל לזכות באנרגיה קינטית של \(mgh\) אם רק ייפול/יתגלגל במשטח המשופע; לכן קוראים ל-\(mgh\) אנרגיה פוטנציאלית של הגוף, והמשטח המשופע הוא כלי שממיר את האנרגיה הפוטנציאלית שלו לאנרגיה קינטית. באופן כללי אנרגיה פוטנציאלית היא מושג מורכב יותר – צריך להסביר פוטנציאלית ביחס למה (כאן זה ביחס לכדור הארץ), ולא תמיד \(g\) קבוע, ולא תמיד \(m\) קבוע, ואני לא הולך להיכנס לדברים הללו בכלל.

חזרה למשוואה \(F\cdot L\cdot\cos\alpha\). בעצם לקחנו את הוקטור \(\vec{F}\) שמתאר את כל פעולת כוח הכובד על הגוף, לא רק בכיוון ה"נכון", ואת הוקטור \(\vec{L}\) שמתאר את ההעתק של הגוף, וכפלנו את הגדלים שלהם זה בזה, ואת כל זה הכפלנו ב-\(\cos\alpha\) כאשר \(\alpha\) היא הזווית שלהם. את הדבר הזה אפשר לעשות באופן כללי, לכל שני וקטורים: \(\vec{v}\cdot\vec{u}=\left|v\right|\cdot\left|u\right|\cdot\cos\alpha\) כאשר \(\alpha\) היא הזווית בין \(u\) ו-\(v\). למכפלה כזו קוראים מכפלה סקלרית.

שאלה שחלקכם ודאי שואלים עכשיו היא מה זה אומר "הזווית בין שני וקטורים", הרי תמיד אפשר לחשוב על שתי זוויות (האחת היא הזווית שבה יש לסובב את \(\vec{u}\) נגד כיוון השעון כדי שינוח על \(\vec{v}\), והשניה היא הזווית שבה יש לסובב את \(\vec{v}\) נגד כיוון השעון כדי שינוח על \(\vec{u}\)). ובכן, זה נכון – יש שתי זוויות שונות בין הוקטורים – \(\alpha\)ו-\(360^{\circ}-\alpha\). למרבה המזל, \(\cos\left(\alpha\right)=\cos\left(360^{\circ}-\alpha\right)\) ולכן זה לא משנה.

הרעיון במכפלה סקלרית הוא לכפול את גדלי שני הוקטורים, אבל תוך "תיקון" שמתחשב בכך שיש ביניהם זווית. אם זה לא אינטואיטיבי לכם, הנה דרך אחרת לחשוב על העניין. נניח ש-\(\vec{v},\vec{u}\) הם וקטורים כלשהם, ואנחנו קובעים מערכת צירים כלשהי שבה הצירים \(x,y\) מאונכים זה לזה. עכשיו נפרק את שני הוקטורים לרכיבים: \(\vec{v}=\vec{v}_{x}+\vec{v_{y}}\) ו-\(\vec{u}=\vec{u}_{x}+\vec{u_{y}}\). נניח ש-\(\vec{u}\) יוצר זווית \(\theta\) כלשהי עם ציר \(x\), אז \(\vec{v}\) יוצר זווית \(\theta+\alpha\) עם ציר \(x\) כש-\(\alpha\) הוא הזווית שמעבירה את \(\vec{u}\) אל \(\vec{v}\). כעת, שימו לב לקסם הבא:

\(\left|u_{x}\right|\left|v_{x}\right|+\left|u_{y}\right|\left|v_{y}\right|=\left(\left|u\right|\cos\theta\right)\left(\left|v\right|\cos\left(\theta+\alpha\right)\right)+\left(\left|u\right|\sin\theta\right)\left(\left|v\right|\sin\left(\theta+\alpha\right)\right)\)

\(=\left|u\right|\left|v\right|\left(\cos\theta\cos\left(\theta+\alpha\right)+\sin\theta\sin\left(\theta+\alpha\right)\right)\)

\(=\left|u\right|\left|v\right|\cos\left(\theta+\alpha-\theta\right)=\left|u\right|\left|v\right|\cos\alpha\)

השתמשתי כאן בזהות הטריגונומטרית לקוסינוס של הפרש – \(\cos\left(\alpha-\beta\right)=\cos\alpha\cos\beta+\sin\alpha\sin\beta\).

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

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

פורסם בתאריך על ידי
17

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

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

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

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

כאן אני שולף מהשרוול שפן בדמות טענה לא טריוויאלית לגמרי בתורת הגרפים – לכל גרף אפשר לפרק את קבוצת הצמתים שלו לשתי קבוצות זרות \(V_{1},V_{2}\) כך שבתת-הגרפים המושרים על \(V_{1},V_{2}\) כל הצמתים הם מדרגה זוגית. תכף אוכיח את הטענה הזו אבל בואו נבין איך נעזרים בה כדי להראות שקיימת בגרף קבוצה \(S\) כמו שאנחנו רוצים. הרעיון הוא לבצע בניית עזר – לקחת את הגרף של המשחק, ולהוסיף צומת חדשה \(u\) שמחוברת לכל צומת בגרף שדרגתו זוגית. כעת אפשר לחלק את הגרף לשתי קבוצות \(V_{1},V_{2}\) כאמור לעיל. בואו נניח ש-\(u\in V_{2}\), בלי הגבלת הכלליות; אז נגדיר \(S=V_{1}\).

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

טוב ויפה, אבל איך מוצאים פירוק ל-\(V_{1},V_{2}\) שכזה? אם בגרף שלנו כל הצמתים מדרגה זוגית אז \(V_{1}=V,V_{2}=\emptyset\) הוא פירוק טריוויאלי שכזה (ועל הדרך יש בגרף מעגל אוילרי) אבל אפשר לצפות שבאופן כללי יהיה בגרף איזה צומת \(v\) שהוא מדרגה לא זוגית. אם כן, הופס! נוציא את \(v\) מהגרף.

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

אם כן, על ידי הוצאת \(v\) קיבלנו גרף קטן יותר (עם פחות צמתים) ולכן אפשר לשלוף מהכיס את קסם ההוכחה באינדוקציה ולטעון שבגרף הקטן יותר יש חלוקה לשתי קבוצות \(W_{1},W_{2}\) כך שדרגת כל צומת בתת-הגרף שמושרה על ידי כל אחת מהקבוצות היא זוגית. מה שנרצה לעשות הוא להחזיר את \(v\) לאחת מהקבוצות הללו, אבל לאיזו מהן? מכיוון ש-\(S\) אי-זוגית, בהכרח \(S\cap W_{1}\) אי זוגית או \(S\cap W_{2}\) אי זוגית (אחרת היה אפשר לכתוב מספר אי זוגי כסכום שני מספרים זוגיים). בואו נניח ש-\(S\cap W_{1}\) זוגית – אני טוען שלהוסיף את \(v\) לקבוצה הזו יסיים את העסק. כלומר, נגדיר \(V_{1}=W_{1}\cup\left\{ v\right\} \) ו-\(V_{2}=W_{2}\). נותר רק להבין למה זה עובד.

ברור כי כל צמתי \(V\) שלא היו שייכים ל-\(S\) ואינם \(v\) עדיין מקיימים את תכונת הזוגיות הנדרשת – מבחינתם לא שיניתי כלום. לעומת זאת, צמתי \(S\cap W_{1}\) חוו טראומה כפולה – גם חיברו להם את \(v\) (ובכך שינו להם את הזוגיות) וגם הפכו את הקשתות בינם לבין עצמם. כל איבר של \(S\) היה מחובר למספר אי זוגי של שכנים מתוך \(S\) ב-\(W_{1}\), מה שאומר שמספר השכנים מתוך \(S\) ב-\(W_{1}\) שהוא לא היה מחובר אליהם היה בעל סימן הפוך, ולכן אחרי היפוך הקשתות הזוגיות משתנה ומבטלת את שינוי הזוגיות ש-\(v\) גרם לו.

מבלבל? בהחלט. בואו נראה דוגמת צעצוע. נניח ש-\(S\cap W_{1}\) הייתה מגודל 6. נסתכל על צומת \(x\in S\cap W_{1}\) כלשהו. יש לו בדיוק 5 שכנים פוטנציאליים שגם הם ב-\(S\cap W_{1}\). נניח שכרגע יש לו קשת ל-2 מהם, זה אומר שאין קשת ל-3, ואחרי שנהפוך את זה (נמחק את הקשתות הקיימות וניצור את כל הקשתות שלא היו קודם) הזוגיות של הדרגה של \(x\) תשתנה בשל כך (קודם היא הייתה זוגית, עכשיו היא כבר לא). אם לעומת זאת הייתה קשת מ-\(x\) רק לצומת אחד אחר ב-\(S\cap W_{1}\) אחרי השינוי תהיה קשת ל-4: שוב שינוי בזוגיות. תוסיפו לכך את השינוי בזוגיות ש-\(v\) גורם לו, וקיבלנו שגם ב-\(V_{1}\) האיבר \(x\) מחובר רק למספר זוגי של צמתים.

עכשיו כבר די ברור מה קורה ב-\(S\cap W_{2}\), אני מקווה. אנחנו לא מוסיפים את \(v\) לשם כך שהוא לא גורם לשום שינוי. מצד שני, גם היפוך הקשתות לא יגרום לשום שינוי, כי לכל צומת \(x\in S\cap W_{2}\) יש מספר שכנים פוטנציאלי זוגי מתוך \(S\cap W_{2}\). לכן: או שקודם \(x\) היה מחובר למספר זוגי, ואחרי השינוי הוא עדיין יהיה מחובר למספר זוגי, או שקודם הוא היה מחובר למספר אי זוגי, ואחרי השינוי הוא עדיין יהיה מחובר למספר אי זוגי. סיימנו.

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

כבר הזכרתי בפוסט על כפל מטריצות את הרעיון לפיו אפשר לייצג גרף באמצעות מטריצה, ובכך להכניס את האלגברה הלינארית לתורת הגרפים בדלת הקדמית. אם הגרף מכיל את הצמתים \(\left\{ v_{1},\dots,v_{n}\right\} \) אז המטריצה, שאסמן \(A\), תהיה מסדר \(n\times n\), כך שהכניסה \(A_{ij}\) שווה 1 אם יש קשת בין \(v_{i}\) ו-\(v_{j}\) ו-0 אחרת. במקרה שלנו הגרף איננו מכוון כך ש-\(A_{ij}=A_{ji}\) – המטריצה סימטרית. מכיוון שהמטריצה מכילה רק 0 ו-1 ואין משמעות לערכים אחרים, הגיוני לחשוב עליה בתור מטריצה מעל השדה הפצפון \(\mathbb{F}_{2}=\left\{ 0,1\right\} \) (אלגברה לינארית תמיד עושים מעל שדה, אחרת תוצאות בסיסיות – כמו זה שאפשר לדרג כל מטריצה – פשוט לא עובדות יותר).

כעת, מה המשמעות של כפל המטריצה \(A\) בוקטור \(x\) כלשהו מעל \(\mathbb{F}_{2}\)? התוצאה תהיה וקטור \(u\) כך ש-\(y_{i}=\sum_{j=1}^{n}A_{ij}x_{j}\), כלומר \(y_{i}\) הוא מספר האינדקסים \(j\in\left\{ 1,\dots,n\right\} \) כך שבו זמנית \(A_{ij}=1\) וגם \(x_{j}=1\). חשבו על \(x_{j}=1\) כאומר "בחרנו ללחוץ על \(x_{j}\) בפתרון שלנו", ואז \(y_{i}\) מתאר בדיוק מה יהיה המצב של הצומת \(v_{i}\) אחרי הלחיצות – אנחנו עוברים על כל צומת שמחובר ל-\(v_{i}\) בקשת ואם רואים שבחרנו ללחוץ עליו, אנחנו מוסיפים 1 ל-\(y_{i}\) ובסופו של דבר (בגלל שאנחנו מעל \(\mathbb{Z}_{2}\)) נקבל ש-\(y_{i}\) מכיל את זוגיות מספר הלחיצות. שימו לב שבשביל שזה יעבוד אנחנו חייבים לקבוע ש-\(A_{ii}=1\) לכל \(i\), כי הרי לחיצה על צומת משנה גם את מצבו שלו (אפשר – וכדאי – לחשוב על כך כאילו יש קשת מהצומת לעצמו וחסל).

אם לסכם, מה שאנחנו רוצים לעשות הוא פשוט לפתור את המשוואה \(Ax=\overline{1}\), כאשר \(\overline{1}\) הוא הוקטור שכולו אחדות (ואם הלוח התחיל ממצב אחר שבו לא כל המשבצות כבויות, פשוט יש משוואה שונה שאפשר לנסות לפתור – אבל במקרה הזה לא מובטח שהיא תהיה פתירה בהכרח; נסו למצוא לוח לא פתיר!). הנה הצלחנו לתרגם עוד בעיה קומבינטורית לגמרי לבעיה בסיסית של אלגברה לינארית. האופן שבו פותרים את הבעיה ידוע – דירוג מטריצות, שניתן לביצוע באופן כללי ביעילות סבירה – ועיקר העניין כרגע הוא בהוכחה שתמיד קיים פתרון. ההוכחה עצמה היא עניין של שורה או שתיים שמבוססות על תוצאות סטנדרטיות באלגברה לינארית – אבל תוצאות שטרם הראיתי, וזו הזדמנות טובה לראות להן דוגמה קונקרטית לפני שמציגים את התורה הכללית.

בתור התחלה, שימו לב ש-\(Ax\) הוא בעצם צירוף לינארי של עמודות \(A\) שמקדמיו נקבעים לפי הכניסות של \(x\). באופן דומה, \(xA\) הוא צירוף לינארי של שורות \(A\) (כרגיל, אני ממשיך במנהג הנלוז שלי לכתוב \(x\) גם לוקטור שורה וגם לוקטור עמודה מתוך הנחה שתבינו מההקשר: \(Ax\) הוא מכפלה של \(A\) בוקטור עמודה, ואילו \(xA\) הוא מכפלה של \(A\) בוקטור שורה). במקרה שלנו \(A\) סימטרית, ולכן אם משהו נמצא בתמונה של \(A\) (כלומר, מתקבל על ידי כפל \(Ax\)) הוא נמצא במרחב שנפרש על ידי שורות \(A\) ולהיפך. נשארנו עם להוכיח ש-\(\overline{1}\) נמצא במרחב שנפרש על ידי שורות \(A\). את המרחב הזה קל במיוחד להבין על ידי התבוננות בגרעין של \(A\), \(\ker A\) – כל הוקטורים \(c\) שמקיימים \(Ac=\overline{0}\).

שימו לב לכך שאם יש לנו \(c\in\ker A\) אז מתקיים \(\left(xA\right)c=x\left(Ac\right)=x\overline{0}=0\). במילים: אם ניקח וקטור כלשהו שנפרש על ידי שורות \(A\) ונכפול אותו עם איבר של \(\ker A\), נקבל 0. אם הרעיון של כפל שני וקטורים מבלבל אתכם, זכרו שהאחד הוא וקטור שורה והשני וקטור עמודה ואפשר לחשוב על הכפל כמכפלה של מטריצה \(1\times n\) במטריצה \(n\times1\). אפשר גם לחשוב על זה כך: אם \(x=\left(x_{1},\dots,x_{n}\right)\) ו-\(y=\left(y_{1},\dots,y_{n}\right)\), אפשר להגדיר מכפלה שלהם על ידי \(x\cdot y=\sum_{i=1}^{n}x_{i}y_{i}\). זה זהה לחלוטין למה שמתקבל מכפל המטריצות, אבל אנחנו כבר לא צריכים להטריד את עצמנו בעניינים כמו מי וקטור שורה ומי וקטור עמודה. המכפלה שהגדרתי כרגע נקראת מכפלה סקלרית של וקטורים, ועוד נפגוש בה בהמשך הפוסטים על אלגברה לינארית.

אם \(x\cdot y=0\) אומרים ש-\(x,y\) אורתוגונליים (מאונכים), מסיבות גאומטריות שיובהרו בפעם אחרת. לעת עתה, מה שראינו הוא שכל איבר במרחב השורות של \(A\) אורתוגונלי לכל איבר בגרעין של \(A\). אני רוצה לטעון שגם ההפך הוא נכון – אם \(x\) אורתוגונלי לכל איבר בגרעין של \(A\), אז \(x\) נמצא במרחב השורות של \(A\).

לב הענין הוא בטענה הבאה: אם \(V\) הוא מרחב וקטורי כלשהו, ואם \(W\) הוא תת מרחב כלשהו, ואם \(W^{\perp}=\left\{ x|\forall y\in W:xy=0\right\} \) הוא אוסף כל האיברים ב-\(V\) שאורתוגונליים לכל איברי \(W\), אז \(\dim V=\dim W+\dim W^{\perp}\). לא אוכיח כרגע את התכונה הזו אבל אני מקווה שאסגור את החשבון באחד מהפוסטים העתידיים. כדי להבין איך הטענה הזו עוזרת לנו, זכרו שמתקיים \(\dim V=\dim\ker A+\dim\mbox{Im}A\) – זו תכונה חשובה של טרנספורמציות לינאריות שכבר הוכחתי בעבר. אם \(W=\ker A\) אז חיבור שני השוויונות מראה לנו שמימד מרחב השורות של \(A\) הוא כמימד \(W^{\perp}\) ומכיוון שידוע לנו שמרחב השורות מוכל ב-\(W^{\perp}\) עולה שהם שווים, מה שמסיים את הוכחת הטענה שאם וקטור אורתוגנלי לכל הגרעין אז הוא במרחב השורות.

כל שנותר לעשות הוא להוכיח שהוקטור \(\overline{1}\) אורתוגונלי לכל איבר בגרעין של \(A\). לצורך כך אנחנו שולפים מהשרוול את התעלול האחרון שלנו, שעובד רק מעל \(\mathbb{F}_{2}\). ניקח וקטור כלשהו \(v\). מהו \(vAv\)? אם נחשב לפי ההגדרה הישירה, נקבל ש-

\(vAv=v\cdot\left(\sum_{i=1}^{n}A_{1i}v_{i},\dots,\sum_{i=1}^{n}A_{ni}v_{i}\right)=\sum_{j=1}^{n}v_{j}\left(\sum_{i=1}^{n}A_{ji}v_{i}\right)=\sum_{i,j=1}^{n}A_{ji}v_{i}v_{j}\)

בהערת אגב אציין שהרעיון הזה, של לכפול מטריצה מימין ומשמאל בוקטור כדי לקבל סקלר, הוא מה שעומד בלב המושג של תבניות בילינאריות שאני מקווה להגיע אליהן בהמשך. מה שקורה כרגע הוא מקרה פרטי שבו העסק פשוט הרבה יותר בגלל שאנחנו מעל \(\mathbb{F}_{2}\) ובגלל ש-\(A\) סימטרית. שימו לב שבגלל הסימטריה הזו, \(A_{ji}=A_{ij}\) ואם \(i\ne j\) אז בסכום מופיעים גם \(A_{ji}v_{j}v_{i}\) וגם \(A_{ij}v_{i}v_{j}\) והסכום של שניהם הוא פשוט \(2A_{ij}v_{j}v_{i}=0\) – אפס, כי אנחנו ב-\(\mathbb{F}_{2}\). לכן מכל הסכום נותר לנו רק \(\sum_{i=1}^{n}A_{ii}v_{i}^{2}\). בגלל שאנחנו מעל \(\mathbb{F}_{2}\), אז \(v_{i}^{2}=v_{i}\) (כי \(v_{i}\in\left\{ 0,1\right\} \)), ולכן קיבלנו שנותר לנו רק \(\sum_{i=1}^{n}A_{ii}v_{i}\) – וזו, במילים אחרות, המכפלה הסקלרית של האלכסון של \(A\) עם הוקטור \(v\).

כעת, אם \(v\) בגרעין של \(A\), אז \(Av=0\) ולכן בוודאי \(vAv=0\), ולכן האלכסון של \(A\) אכן אורתוגונלי לגרעין של \(A\) וההוכחה נסתיימה. אולי היא נראית קצת מסורבלת ומוזרה כעת, אבל למי שבקיא במושגים היא לא דורשת יותר משורה-שתיים.

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

איך אלגברה לינארית מתקשרת לשרשראות מרקוב (ואיך כל זה קשור לגוגל)

פורסם בתאריך על ידי
5

שרשראות מרקוב

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

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

הנה דוגמה פשוטה: נניח שאתם מטילים קוביה שוב ושוב ושוב ולאחר כל הטלה רושמים את הסכום של כל ההטלות עד כה. התהליך הזה הוא שרשרת מרקוב; המצבים מתוארים על ידי הסכום הנוכחי שלכם, כלומר יש מצב לכל מספר טבעי. אם כרגע הסכום שלכם הוא 42, הרי שההסתברות שמכאן תגיעו אל 45 היא \(\frac{1}{6}\) (ההסתברות שיצא לכם בדיוק "3" בהטלת הקוביה), וזה בכלל לא משנה אם הגעתם ל-42 על ידי 7 הטלות רצופות של "6" או על ידי 42 הטלות רצופות של "1" או כל סדרה אחרת של מספרים. מרגע שהגעתם ל-42, ולא משנה איך, המשך התהליך יתנהג (הסתברותית) באותו אופן בדיוק.

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

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

אני הולך לדבר רק על שרשראות שמרחב המצבים שלהן סופי, כי שרשראות כאלו ניתנות לתיאור באמצעות מטריצות. זאת מכיוון שאפשר לחשוב על כל שרשרת מרקוב בזמן בדיד בתור הילוך בגרף מכוון, כאשר הצמתים של הגרף הם המצבים של השרשרת, ועל הקשתות יש משקלים שמתאימים להסתברות המעבר בין צומת אחד לשני. לצורך פשטות, מסמנים את המצבים במספרים מ-1 ועד \(n\), ואז אפשר לתאר את השרשרת בעזרת מטריצה \(P\) מסדר \(n\times n\) כך ש-\(P_{ij}\) היא ההסתברות לעבור מהמצב \(i\) למצב \(j\). הנה דוגמה לאיך שזה נראה:


המטריצה המתאימה כאן היא \(P=\left(\begin{array}{ccc}\frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\\frac{1}{2} & 0 & \frac{1}{2}\\1 & 0 & 0\end{array}\right)\). שימו לב לכך שבמטריצה הזו סכום כל שורה הוא 1. זה לא במקרה; השורה ה-\(i\) מייצגת את ההסתברויות לעבור מ-\(i\) לכל אחד מהמצבים האחרים (או להישאר במקום, מה שממודל בתור מעבר ל-\(i\)). מכיוון שאחד מאלו חייב לקרות, סכום כל ההסתברויות הוא בדיוק 1. למטריצה כזו, ששורותיה מסתכמות כולן ל-1, קוראים מטריצה סטוכסטית, ועוד נראה חשיבות לתכונה הזו בהמשך.

בפוסט שדיבר על כפל מטריצות הזכרתי את העובדה שאם \(A\) היא מטריצה מייצגת של גרף – כלומר, אם \(A_{ij}\) שווה ל-1 כשיש קשת מ-\(i\) אל \(j\) ו-0 אם אין כזו, אז \(A_{ij}^{k}\) הוא מספר המסלולים מאורך \(k\) מ-\(i\) אל \(j\) בגרף. מאותו נימוק ואותה הוכחה (שלא אכנס לפרטיה כאן אבל היא תרגיל מצויין לספקנים) אפשר לראות ש-\(P_{ij}^{k}\) היא בדיוק ההסתברות לעבור מהמצב \(i\) למצב \(j\) אחרי \(k\) צעדים; כלומר, אם התחלנו את השרשרת שלנו כאשר אנחנו במצב \(i\), וביצענו \(k\) צעדים, אז ההסתברות שבסוף ההרפתקאה הזו נהיה ב-\(j\) היא בדיוק, אבל בדיוק \(P_{ij}^{k}\). אני מאוד מקווה שהתוצאה הזו נראית לכם טריוויאלית לחלוטין; עכשיו עצרו לרגע וחשבו שאנחנו חיים בעולם ללא מטריצות וללא כפל מטריצות, וחשבו כיצד בעולם כזה היה נראה התיאור של החישוב של הסתברות המעבר מ-\(i\) אל \(j\) ב-\(k\) צעדים. זו דוגמה נאה לכך שבמתמטיקה ההגדרה הנכונה חשובה לעתים לא פחות מאשר המשפט הנכון – ברגע שרואים משהו מזווית הראייה הנכונה, הכל פתאום פשוט וכל החתיכות נופלות למקום. בדרך כלל אותה זווית ראייה היא משהו שכדי לשלוט בו נדרש קצת מאמץ (לאף אחד מאיתנו כפל מטריצות לא בא בקלות…) ולכן ההפשטה שיש כאן כל כך מועילה – מרגע שהבנו כפל מטריצות, אנחנו מסוגלים באמצעותו להבין המוני בעיות שונות ומשונות שאת כולן ניתן לתרגם לכפל מטריצות, ובכך לחסוך את המאמץ שהיה נדרש מאיתנו להבין כל אחת לחוד.

בואו נניח שאנחנו רוצים לשאול שאלה קצת יותר כללית: "אחרי \(k\) צעדים בשרשרת המרקוב, מה התפלגות המצבים שבהם נהיה?". למה הכוונה בכך? התשובה הצפויה היא משהו בסגנון "בהסתברות חצי נהיה במצב מס' 1, בהסתברות שליש במצב 2, ובהסתברות שישית במצב 3". את זה אפשר לתאר על ידי וקטור עם \(n\) כניסות, \(v\), כך ש-\(v_{i}\) הוא ההסתברות להיות במצב \(i\). וקטור כזה יכול לתאר גם את המצב ההתחלתי של השרשרת – אף אחד לא אמר שחייבים להתחיל ממצב אחד ספציפי; אפשר לבחור את המצב שבו מתחילים גם כן באופן מקרי. לכן \(v=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)\) הוא וקטור שמתאר בחירה של כל מצב בהסתברות אחידה, ו-\(v=\left(0,1,0\right)\) הוא וקטור שמתאר התחלה ודאית במצב 2.

מה שצפוי כעת הוא שיתקיים שאם \(v\) הוא ההתפלגות הנוכחית שלנו בנקודת זמן כלשהי, אז \(Pv\) תהיה ההתפלגות אחרי צעד אחד. רק שזה לא עובד. כדי לראות זאת, בואו נניח ש-\(v=\left(1,0,0\right)\) – התחלה ודאית ממצב 1. נכפול ב-\(P\) שלמעלה, ונקבל \(Pv=\left(1,\frac{1}{2},1\right)\), שהוא בוודאי לא וקטור שמייצג הסתברות ולא כלום (יש כאן גם עניין לפיו \(v\) הוצג כוקטור שורה ולא עמודה, אבל אני מניח שהפורמליזם הזה לא מפריע לכם). למעשה, אם תחשבו על זה לרגע, לא הייתה שום סיבה להניח שזה יעבוד; האפקט הרצוי מושג דווקא על ידי פעולת כפל מהצד השני, שהיא משהו שפחות ראינו עד היום אבל היא לגיטימית לגמרי לכשעצמה: \(vP=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)\) – לא במפתיע, השורה הראשונה ב-\(P\) – ולא קשה להוכיח שבאופן כללי כפל משמאל אכן מעביר את ההתפלגות \(v\) להתפלגות הצפויה אחרי צעד אחד. וכמובן, \(vP^{k}\) היא ההתפלגות שאליה מגיעים אחרי \(k\) צעדים אם התחלנו ב-\(v\).

ואיך אלגברה לינארית מתקשרת אליהן

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


לצורך פשטות לא ציירתי את הקשתות מצומת לעצמו (אפשר להסיק מה הערכים שלהן). המטריצה של השרשרת הזו היא \(P=\left(\begin{array}{ccc}0 & 1 & 0\\0 & \frac{1}{2} & \frac{1}{2}\\\frac{1}{2} & 0 & \frac{1}{2}\end{array}\right)\). כעת נותנים לנו תרגיל – למצוא נוסחה כללית עבור ההסתברות לפיה אם נתחיל מהמצב \(1\), אז כעבור \(n\) צעדים גם כן נהיה במצב 1. בניסוח מטריציוני, שואלים אותנו מהי \(\left[P^{n}\right]_{11}\). זוהי שאלת אלגברה לינארית למהדרין, והדרך לפתרון שלה עוברת דרך ערכים עצמיים, אז בואו נתחיל מלמצוא את הערכים העצמיים לפי הספר. כאן יש לנו מזל – המטריצה קטנה, אז קל למצוא את הערכים העצמיים שלה, אבל לפעמים זה יכול להיות קשה למדי. הפולינום האופייני הוא

\(\left|\begin{array}{ccc}x & -1 & 0\\0 & x-\frac{1}{2} & -\frac{1}{2}\\-\frac{1}{2} & 0 & x-\frac{1}{2}\end{array}\right|=x\left|\begin{array}{cc}x-\frac{1}{2} & -\frac{1}{2}\\0 & x-\frac{1}{2}\end{array}\right|+\left|\begin{array}{cc}0 & -\frac{1}{2}\\-\frac{1}{2} & x-\frac{1}{2}\end{array}\right|\)

\(=x\left(x-\frac{1}{2}\right)^{2}-\frac{1}{4}=x^{3}-x^{2}+\frac{1}{4}x-\frac{1}{4}=x^{2}\left(x-1\right)+\frac{1}{4}\left(x-1\right)=\left(x-1\right)\left(x^{2}+\frac{1}{4}\right)\)

אם כן, מייד רואים ש-\(1\) הוא ערך עצמי, אבל פרט אליו אין ערכים עצמיים ממשיים: שני האחרים הם השורשים של \(x^{2}+\frac{1}{4}\), כלומר \(\pm\frac{i}{2}\). הנה צצים לנו מספרים מרוכבים בבעיה ממשית למהדרין, אבל אין כאן שום בעיה.

כעת, שימו לב שכל הערכים העצמיים הם שונים זה מזה, מה שמפשט לנו מאוד את החיים – מכיוון שהפולינום האופייני מתפרק לגורמים לינאריים שונים \(\left(x-1\right)\left(x-\frac{i}{2}\right)\left(x+\frac{i}{2}\right)\) נובע מייד ש-\(P\) לכסינה, כלומר \(P=U^{-1}\left(\begin{array}{ccc}1 & 0 & 0\\0 & \frac{i}{2} & 0\\0 & 0 & -\frac{i}{2}\end{array}\right)U\) עבור איזו \(U\) הפיכה שלא מעניינת אותנו. מכאן נובע מייד ש-\(P^{n}=U^{-1}\left(\begin{array}{ccc}1 & 0 & 0\\0 & \left(\frac{i}{2}\right)^{n} & 0\\0 & 0 & \left(-\frac{i}{2}\right)^{n}\end{array}\right)U\).

כעת אפשר לחשב ישירות את \(\left[P^{n}\right]_{11}\) על ידי חישוב \(U\) וביצוע הכפל, אבל \(U\) עשויה להיות מכוערת למדי ולא ברור עד כמה זה יוביל אותנו לנוסחה כללית טובה. במקום זאת ננקוט בתעלול אחר: מכיוון ש-\(P^{n}\) מתקבלת על ידי כפל המטריצה האלכסונית מימין ב-\(U\) ומשמאל ב-\(U^{-1}\), הרי ש-\(\left[P^{n}\right]_{11}\) תהיה צירוף לינארי של הכניסות השונות מאפס של המטריצה האלכסונית (כי זה מה שכפל מטריצות עושה – צירופים לינאריים). לכן \(\left[P^{n}\right]_{11}=\alpha\cdot1+\beta\cdot\left(\frac{i}{2}\right)^{n}+\gamma\left(-\frac{i}{2}\right)^{n}\). כל שנותר לעשות הוא למצוא את המקדמים \(\alpha,\beta,\gamma\) המתאימים. את זה עושים על ידי חישוב קונקרטי של \(\left[P^{0}\right]_{11},\left[P^{1}\right]_{11},\left[P^{2}\right]_{11}\) והצבה בנוסחה (שאמורה לעבוד לכל \(n\)). קל לראות שהערכים המתאימים הם 1,0,0, כך שקיבלנו את המשוואות:

\(\alpha+\beta+\gamma=1\)

\(\alpha+\left(\frac{i}{2}\right)\left(\beta-\gamma\right)=0\)

\(\alpha-\frac{1}{4}\left(\beta+\gamma\right)=0\)

הפתרון למערכת הזו הוא \(\alpha=\frac{1}{5},\beta=\frac{2}{5}+\frac{1}{5}i,\gamma=\frac{2}{5}-\frac{1}{5}i\). שימו לב בפרט ש-\(\gamma=\overline{\beta}\) (צמוד מרוכב) וזכרו ש-\(-i=\overline{i}\), כך שקיבלנו את הפתרון הכללי:

\(\left[P^{n}\right]_{11}=\frac{1}{5}+\left(\frac{1}{2}\right)^{n}\left[\beta i^{n}+\overline{\beta i^{n}}\right]=\frac{1}{5}+\left(\frac{1}{2}\right)^{n}\left(2\mbox{Re}\left(\beta i^{n}\right)\right)\)

ב-\(i^{n}\) הכי קל לטפל בהצגה קוטבית שלא מצריכה חלוקה למקרים: \(i^{n}=e^{i\frac{\pi}{2}n}\), ולכן \(\beta i^{n}=\frac{2}{5}e^{i\frac{\pi}{2}n}+\frac{1}{5}ie^{i\frac{\pi}{2}n}\), ואם זוכרים ש-\(e^{i\theta}=\cos\theta+i\sin\theta\) מקבלים חיש קל ש-\(2\mbox{Re}\left(\beta i^{n}\right)=\frac{4}{5}\cos\frac{n\pi}{2}-\frac{2}{5}\sin\frac{n\pi}{2}\), ולכן הפתרון לשאלה הוא:

\(\left[P^{n}\right]_{11}=\frac{1}{5}+\left(\frac{1}{2}\right)^{n}\left(\frac{4}{5}\cos\frac{n\pi}{2}-\frac{2}{5}\sin\frac{n\pi}{2}\right)\)

השתמשתי כאן בתעלול או שניים כדי לפשט את הפתרון, אבל לא יותר מדי – זו גם שיטת העבודה הכללית. בהערת אגב, אפשר היה לפשט עוד את הפתרון על ידי ביצוע משהו שאולי היה נראה לחלקכם כמו רמאות: כשקיבלתי את נוסחת הנסיגה \(\alpha\cdot1+\beta\cdot\left(\frac{i}{2}\right)^{n}+\gamma\left(-\frac{i}{2}\right)^{n}\) להגיד "בגלל שאנחנו יודעים שהפתרון הוא ממשי, אז אפשר להחליף את הנוסחה הזו בנוסחת הנסיגה \(\alpha+\left(\frac{1}{2}\right)^{n}\left(\beta\cos\frac{n\pi}{2}+\gamma\sin\frac{n\pi}{2}\right)\)", אבל כמו שאנחנו רואים זה לא משפיע על התוצאה.

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

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

בואו ננסה עכשיו להבין קצת יותר טוב מה הנוסחה ל-\(\left[P^{n}\right]_{11}\) אומרת: שאחרי \(n\) צעדים, אם התחלנו מהמצב 1, ההסתברות שלנו להיות ב-1 היא חמישית ועוד איזה "גורם כאוטי" שמתואר באמצעות \(\frac{4}{5}\cos\frac{n\pi}{2}-\frac{2}{5}\sin\frac{n\pi}{2}\) (הסינוסים והקוסינוסים מעידים על כך שהגורם הזה הוא מחזורי, דבר לא מפתיע בפני עצמו) אבל כזה שההשפעה שלו דועכת אקספוננציאלית עם הזמן, מה שבא לידי ביטוי בכפל ב-\(\left(\frac{1}{2}\right)^{n}\). פורמלית, בבירור \(\lim_{n\to\infty}\left[P^{n}\right]_{11}=\frac{1}{5}\), מה שאומר שאנחנו מצפים, אם ניתן למערכת לרוץ זמן ארוך אחרי שהתחילה ממצב 1, להגיע לכך שבכל פרק זמן ההסתברות שהמערכת תהיה במצב 1 היא \(\frac{1}{5}\), ולכן שבריצה לטווח ארוך המערכת תהיה במצב 1 חמישית מהזמן. עכשיו אני רוצה לדבר על האופן שבו מבצעים ניתוח של "התנהגות לטווח ארוך" שכזו.

לב העניין הוא במה שמכונה "התפלגות אינוריאנטית" (או "שיווי משקל", או אולי "התפלגות סטציונרית"). בואו נתחיל מלשים לב לכך שהעובדה ש-1 היה ערך עצמי של \(P\) בדוגמה למעלה לא הייתה מקרית. באופן כללי, אם כל השורות של מטריצה מסתכמות לאותו מספר \(a\) (או כל העמודות מסתכמות לאותו מספר \(a\)) אז \(a\) הוא ערך עצמי של המטריצה. דרך אחת לראות זאת היא כך: אם כל השורות של המטריצה \(A\) מסתכמות ל-\(a\) אז \(v=\left(1,1,\dots,1\right)\) הוא וקטור עצמי של המטריצה כי \(Av=\left(a,a,\dots,a\right)=av\) (כי כפל ב-\(v\) פשוט סוכם את כל השורות של \(A\) אחת אחת). אם כל העמודות של \(A\) מסתכמות ל-\(a\) אז מתקיים \(vA=\left(a,a,\dots,a\right)\) אבל לא הגדרנו ערכים עצמיים באמצעות פעולת הכפל משמאל. מצד שני, זה לא משנה כי מתקיים ש-\(vA=\left(Av\right)^{t}=A^{t}v\), כאשר \(t\) מציין את אופרטור השחלוף: \(\left[A_{ij}^{t}\right]=A_{ji}\) (שיקוף הכניסות של \(A\) ביחס לאלכסון הראשי). לא קשה להוכיח של-\(A\) ול-\(A^{t}\) אותו פולינום אופייני (הפיתוח של הדטרמיננטה יהיה זהה פרט לכך שכאשר מפתחים אחת מהן על פי שורה, את השניה מפתחים על פי עמודה) ולכן אותם ערכים עצמיים.

במקרה שלנו שורות \(P\) מסתכמות ל-1, ולכן תמיד יתקיים ש-\(P\cdot\left(1,\dots,1\right)=\left(1,\dots,1\right)\) ולכן 1 הוא ערך עצמי של \(P\). מה שזה אומר הוא שקיים וקטור \(v\) שמקיים \(vP=v\) גם בכפל משמאל; הוקטור הזה כלל לא צריך להיות דומה ל-\(\left(1,\dots,1\right)\). בואו נגלה אותו עבור \(P\) של הדוגמה שלנו; אנחנו רוצים לפתור את מערכת המשוואות \(\left(\begin{array}{ccc}-1 & 0 & \frac{1}{2}\\1 & -\frac{1}{2} & 0\\0 & \frac{1}{2} & -\frac{1}{2}\end{array}\right)v=0\) (שחלפתי את \(P\) והפחתתי 1 מהאלכסון הראשי). קצת דירוג מטריצות ונקבל \(\left(\begin{array}{ccc}1 & 0 & -\frac{1}{2}\\0 & 1 & -1\\0 & 0 & 0\end{array}\right)v=0\), כלומר הצורה הכללית של הפתרון \(v\) היא \(v=\left(\frac{1}{2}\alpha,\alpha,\alpha\right)\) עבור פרמטר \(\alpha\) כלשהו.

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

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

התוצאה המעניינת הראשונה על התפלגויות אינוריאנטיות מסבירה את ה-\(\frac{1}{5}\) שקיבלנו ב-\(u\). אם יש לנו שרשרת מרקוב סופית (הסופיות קריטית פה) כך שעבור מצב \(i\) כלשהו מתקיים ש-\(\lim_{n\to\infty}\left[P_{ij}^{n}\right]=\pi_{j}\) לכל מצב \(j\) (אנו דורשים רק שהגבול יהיה קיים; \(\pi_{j}\) הוא איך אנחנו מסמנים אותו אם הוא קיים) אז הוקטור \(\left(\pi_{1},\pi_{2},\dots,\pi_{k}\right)\) הוא וקטור התפלגות אינוריאנטית. במקרה של \(P\) שלנו אכן מתקיים \(\lim_{n\to\infty}\left[P_{12}^{n}\right]=\lim_{n\to\infty}\left[P_{13}^{n}\right]=\frac{2}{5}\) אבל לא טרחתי לחשב את הנוסחה שלהם כדי לראות זאת.

אם כן, ההתפלגות האינוריאנטית מתארת את ההתנהגות לטווח ארוך של \(P\) אם קיימת כזו – \(P\) "שואפת" להתפלגות האינוריאנטית. השאלה המהותית יותר היא מתי התכנסות כזו אכן מובטחת. בואו נראה דוגמה פשוטה ביותר שבה אין התכנסות – שרשרת שבה יש שני מצבים, כך שמכל אחד עוברים לשני בהסתברות אחת. לשרשרת הזו יש את המטריצה \(P=\left(\begin{array}{cc}0 & 1\\1 & 0\end{array}\right)\). בבירור 1 הוא ערך עצמי של \(P\). מרחב הוקטורים העצמיים השייכים לערך העצמי 1 נפרש על ידי \(\left(\alpha,\alpha\right)\) ולכן \(\left(\frac{1}{2},\frac{1}{2}\right)\) היא התפלגות אינוריאנטית (חשבו על זה קצת – זה פשוט למדי אחרי שמבינים מה הולך כאן). אלא ש-\(P\) לא מתכנסת לשום מקום; שימו לב ש-\(P^{2}=\left(\begin{array}{cc}1 & 0\\0 & 1\end{array}\right)\) ולכן \(P^{3}=P\), ובאופן כללי כל כניסה של \(P\) "מזגזגת" בין 0 ו-1 ולכן לא מתכנסת. הבעיה כאן היא בכך שהשרשרת שלנו היא מחזורית. אין צורך להסתבך עם הגדרות בעייתיות פה כדי לתאר מחזוריות של תהליך אקראי: די לנו להגדיר ששרשרת היא לא מחזורית אם \(\left[P^{n}\right]_{ii}>0\) עבור \(n\) גדול דיו לכל \(i\) (אפשר לראות שהגדרה זו שקולה לדרישה שהמחלק המשותף הגדול ביותר של קבוצת ה-\(n\)-ים שעבורם \(\left[P^{n}\right]_{ii}>0\) עבור \(i\) מסויים הוא 1).

אפשר היה אולי לחשוב שמספיק לדרוש שמצב אחד בלבד יהיה לא מחזורי, ואז אי-המחזוריות שלו "תפעפע" לשאר המחרוזת. זה גם נכון, בתנאי שלא ניתן לפרק את המחרוזת ל"רכיבי קשירות" שלא מתקשרים זה עם זה. מבלי להיכנס יותר מדי להגדרות הפורמליות, שרשרת מרקוב היא בלתי פריקה אם לכל מצב \(i\) ולכל מצב \(j\), אם התחלנו מ-\(i\) יש לנו סיכוי להגיע מתישהו ל-\(j\) (קצת יותר פורמלית, \(\left[P^{n}\right]_{ij}>0\) עבור \(n\) גדול דיו). אפשר להראות ששרשרת מרקוב שיש בה מצב אחד בלבד שהוא אי מחזורי והיא אי פריקה תהיה אי מחזורית בכל המצבים שלה.

כעת אפשר לנסח את מה שהוא כנראה המשפט החשוב ביותר בכל הפוסט: אם נתונה לנו שרשרת מרקוב אי מחזוריות ובלתי פריקה (לא בהכרח סופית!) וקיימת לה התפלגות אינוריאנטית \(\pi=\left(\pi_{1},\dots,\pi_{k}\right)\), אז בלתי תלות בשאלה מה ההתפלגות שבה מתחילים את ריצת השרשרת, לכל מצב \(j\) ההסתברות שהשרשרת תהיה ב-\(j\) בצעד ה-\(n\) שואפת ל-\(\pi_{j}\) כאשר \(n\) שואף לאינסוף (\(\lim_{n\to\infty}\mbox{P}\left(X_{n}=j\right)=\pi_{j}\) כאשר \(X_{n}\) הוא המשתנה המקרי שמתאים ל"המצב של השרשרת בזמן \(n\)"). בפרט זה אומר ש-\(\lim_{n\to\infty}\left[P^{n}\right]_{ij}=\pi_{j}\) לכל \(i,j\). פירוש הדבר הוא שבשרשראות אי מחזוריות ובלתי פריקות, ההתפלגות האינוריאנטית של השרשרת מתארת בדיוק את ההתנהגות לטווח ארוך שלה. ההוכחה של המשפט היא מקסימה גם היא אבל אינה פשוטה ולא אציג אותה כעת.

ואיך כל זה קשור לגוגל

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

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

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

\(\mbox{PR}\left(A\right)=\frac{1-d}{N}+d\sum_{T_{i}}\frac{\mbox{PR}\left(T_{i}\right)}{C\left(T_{i}\right)}\)

כאשר \(N\) הוא מספר הדפים הכולל באינטרנט (ליתר דיוק – באוסף הדפים שעבורם מחשבים את PageRank) הסכום רץ על כל הדפים \(T_{i}\) שמקשרים ל-\(A\), ו-\(C\left(T_{i}\right)\) הוא מספר הלינקים הכולל שיוצא מ-\(T_{i}\). הגדרה מעגלית, אבל בכלל לא בעייתית. הנקודה היא שזה בדיוק מה שמקבלים אם ממדלים גלישה באינטרנט בתור שרשרת מרקוב.

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

אין ספק שיש לנו כאן תיאור נאיבי ביותר של האופן שבו אנשים גולשים באינטרנט, אבל אפשר לשפר אותו אם יש בכך צורך (למשל, שלא כל הלינקים בתוך עמוד יקבלו משקל זהה), וגם בגרסתו הבסיסית התיאור הזה נותן תוצאות מועילות למדי. כעת, שימו לב ששרשרת המרקוב הזו היא אי מחזורית (כי תמיד יש סיכוי שתחזור לדף שהתחלת ממנו – אפילו אחרי צעד אחד אם אתה "משתעמם") ואי פריקה (שוב, ה"שיעמום" מבטיח שתוכל להגיע לכל דף מכל דף אחר בהסתברות נמוכה כלשהי). לכן היא מתכנסת להתפלגות אינוריאנטית – ומה זו ההתפלגות האינוריאנטית הזו? ניחשתם נכון, קל לראות ש-\(\mbox{PR}\left(A\right)\) היא בדיוק התפלגות אינוריאנטית של השרשרת הזו. המעגליות של ההגדרה נפתרה: זו בדיוק אותה מעגליות שיש בהגדרה בסגנון "\(Av=v\)" – אם \(A\) נתונה, כמובן שזו לא הגדרה מעגלית של \(v\) כלל.

בקיצור, \(\mbox{PR}\left(A\right)\) מתאים בדיוק להתנהגות לטווח ארוך של גולש אקראי במודל הגלישה שהצענו. מבחינה אינטואיטיבית המודל הזה קורץ למדי. עם זאת, עוד לא הבהרנו שתי נקודות חשובות: ראשית, למה בכלל קיים וקטור עצמי של 1 שהוא אי-שלילי? כל עוד לא הוכחנו קיום של כזה, לא הוכחנו שיש בכלל פתרון למערכת המשוואות שמגדירה את \(\mbox{PR}\). שנית, איך מוצאים את הוקטור הזה בפועל? אנחנו מדברים כאן על מטריצות ענקיות (ברין ופייג' דיברו במאמר על מטריצות מסדר 26 מיליון על 26 מיליון; בפועל כמובן שגוגל מתעסקים עם דברים גדולים יותר).

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

בהינתן מטריצה \(A\) מעל \(\mathbb{R}\) או \(\mathbb{C}\), הרדיוס הספקטרלי שלה \(\rho\left(A\right)\) הוא הערך המוחלט המקסימלי של הערכים העצמיים של \(A\) – אם תרצו, חשבו על זה בתור רדיוס העיגול הקטן ביותר ב-\(\mathbb{C}\) שמרכזו בראשית הצירים ומכיל בתוכו את כל הערכים העצמיים של \(A\) (שהם בסופו של דבר איברים של \(\mathbb{C}\)). שימו לב כי \(\rho\left(A\right)\) הוא תמיד מספר ממשי. כעת, החלק הרלוונטי עבורנו ממשפט פרון-פרובניוס אומר כי אם \(A\) היא מטריצה חיובית (שכל כניסותיה הן מספרים ממשיים גדולים מאפס, כמו במקרה של \(P\) של ברין ופייג') כך ש-\(r=\rho\left(A\right)\), אז \(r\) הוא ערך עצמי של \(A\) (זה בפני עצמו לא טריוויאלי; אם \(r=\rho\left(A\right)\) כל מה שאפשר לעשות באופן כללי הוא לומר שקיים ערך עצמי \(\lambda\) – שיכול להיות שלילי או מרוכב – כך ש-\(r=\left|\lambda\right|\)), וכל ערך עצמי אחר של \(A\) הוא קטן ממש בערכו המוחלט מ-\(r\), וקיים וקטור עצמי של \(r\) (הן מימין והן משמאל) שכל הכניסות שלו חיוביות.

כעת, מה הרדיוס הספקטרלי של מטריצה סטוכסטית כמו אלו שבהן התעסקנו בפוסט הזה? ברור שהוא לפחות 1 כי 1 הוא וקטור עצמי. ממשפט פרון-פרובניוס עולה כי אם 1 הוא לא הרדיוס הספקטרלי אז קיים \(\lambda>1\) ממשי שגם הוא ערך עצמי, עם וקטור עצמי \(v\) שכל כניסותיו הן ממשיות חיוביות, כלומר \(Av=\lambda v\). קל מאוד לראות שזה בלתי אפשרי: נניח ש-\(v_{max}\) הוא ערכה של הכניסה הגדולה ביותר ב-\(v\), אז מכיוון שכל שורה של \(A\) מסתכמת ל-1, רואים מייד שכל כניסה ב-\(Av\) היא לכל היותר \(v_{max}\), אבל ב-\(\lambda v\) יש כניסה שהיא גדולה ממש מ-\(v_{max}\). לכן במקרה שלנו הרדיוס הספקטרלי הוא בדיוק 1, ולכן קיים למטריצה וקטור עצמי אי-שלילי עבור הערך העצמי 1, ולכן קיימת התפלגות אינוריאנטית, בדיוק כפי שרצינו (יש עוד דרכים להוכיח את עניין הרדיוס הספקטרלי בלי תותח כבד כמו פרון-פרובניוס, אבל לצרכים שלנו כאן זה הכי התאים).

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

משפט הפירוק הפרימרי

פורסם בתאריך על ידי
18

בפעם האחרונה שבה דיברתי על אלגברה לינארית המושג הדומיננטי היה זה של תת-מרחב שמור. כזכור, \(W\subseteq V\) הוא תת-מרחב שמור של טרנספורמציה לינארית \(T:V\to V\) אם \(T\left(W\right)\subseteq W\), והחשיבות של תתי-מרחבים כאלו נובעת מהעובדה שאפשר לצמצם את \(T\) אליהם – להגדיר טרנספורמציה \(T_{W}:W\to W\) כך ש-\(T_{W}\left(w\right)=T\left(w\right)\) על \(w\in W\). אם הצלחנו לפרק את \(V\) לסכום ישר של תתי-מרחבים שכולם תתי-מרחבים שמורים של \(T\), נובע מכך פירוק של \(T\) לסכום של טרנספורמציות פשוטות יותר, ומכאן נובעת הבנה יותר טובה של מה \(T\) עושה. המקרה הפשוט ביותר היה כאשר \(T\) הייתה לכסינה – במקרה זה אפשר היה לפרק את \(V\) לתתי-מרחבים שמורים שבכל אחד מהם \(T\) פועלת פשוט על ידי כפל בסקלר (ולכן מיוצגת על ידי מטריצה סקלרית – מטריצה אלכסונית שבאלכסון שלה יש תמיד אותו מספר). כפי שראינו, התכונה הזו הייתה שקולה לכך שהפולינום המינימלי שמאפס את \(T\) מתפרק לגורמים לינאריים שונים. בפוסט הזה נראה את ההכללה של התוצאה הזו עבור המקרה הכללי ביותר; ההכללה הזו נקראת משפט הפירוק הפרימרי. שמו של המשפט נובע כנראה מכך שהוא אינו סוף הסיפור אלא רק ההתחלה – גם אחרי הפירוק עדיין צריך להבין איך נראית \(T\) כשהיא מצומצמת לתתי-המרחבים שמשפט הפירוק נותן – אבל הוא הצעד הראשון (וההכרחי?) שיש לנקוט בו.

נתחיל מלצטט את המשפט, ואז נוכיח. כרגיל, נתחיל עם טרנספורמציה לינארית \(T:V\to V\), כאשר \(V\) הוא מרחב סוף-ממדי (בכל הדיון הנוכחי אנחנו לא מדברים על מרחבים אינסוף ממדיים; יש להם תורה דומה לזו שאני מציג כאן אבל היא מורכבת יותר ודורשת הכנסה לתמונה של עוד הרבה מושגים יפים שיוצגו בפעם אחרת). אם \(p\) הוא הפולינום המינימלי של \(T\) אז אפשר לכתוב אותו בתור מכפלה של חזקות של פולינומים אי פריקים (מתוקנים, כלומר עם מקדם מוביל 1) \(p=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}\). נגדיר את המרחבים \(W_{i}\) בתור \(W_{i}=\ker\left(p_{i}^{r_{i}}\left(T\right)\right)\) (כלומר, \(W_{i}\) הוא אוסף כל הוקטורים שמתאפסים על ידי הטרנספורמציה שמתקבלת כשמציבים את \(T\) ב-\(p_{i}^{r_{i}}\)), אז ה-\(W_{i}\)-ים הללו הם פירוק של \(V\) לתת-מרחבים שמורים של \(T\); והפולינום המינימלי של \(T_{W_{i}}\) הוא בדיוק \(p_{i}^{r_{i}}\).

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

נעבור להוכחה. הכלי שבו נשתמש כדי לפרק את \(V\) לתת-מרחבים הוא הטלות. כזכור, הטלה \(E\) היא טרנספורמציה לינארית שמקיימת \(E^{2}=E\). אם יש לנו קבוצה של טרנספורמציות \(E_{i}\) כך ש-\(\sum E_{i}=I\) ו-\(E_{i}E_{j}=0\) לכל \(i\ne j\), אז הטרנספורמציות הן הטלות (נסו להוכיח שזה אכן נובע, זה קל) והתמונות של ההטלות הללו הן פירוק של \(V\) לסכום ישר של תתי-מרחבים. מכאן שהאתגר במשפט הפירוק הפרימרי הוא למצוא את ההטלות הנכונות. כאן תצטרכו לסמוך עלי לרגע – אני אציג את ההטלות, במה שייראה כמו קסם שבא משום מקום, ואז נראה שהן עובדות.

לב העניין הוא הפולינום המינימלי \(p=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}\). לכל גורם \(i\) שלו, נגדיר פולינום \(q_{i}=\frac{p}{p_{i}^{r_{i}}}\), או במילים אחרות \(q_{i}=\prod_{j\ne i}p_{j}^{r_{j}}\) – "סיננו" את הגורם \(p_{i}\) על כל חזקותיו מתוך \(p\). כעת די ברור שהמחלק המשותף המקסימלי של כל הפולינומים \(q_{1},\dots,q_{k}\) הוא 1, ושפן אלגברי שאני שולף מהכובע ולא מוכיח כרגע הוא שבשל כך, קיימים פולינומים \(h_{1},\dots,h_{k}\) כך ש-\(\sum h_{i}q_{i}=1\). זה מוביל אותנו להגדרה \(E_{i}=\left(h_{i}q_{i}\right)\left(T\right)\) ומהנוסחה \(\sum h_{i}q_{i}=1\) אנחנו מקבלים מיידית ש-\(\sum E_{i}=I\).

אוקיי, אבל… מה? למה, למשל, \(E_{i}E_{j}=0\)? ובכן, כי \(E_{i}E_{j}=\left(h_{i}q_{i}h_{j}q_{j}\right)\left(T\right)\), אבל \(h_{i}\) ו-\(h_{j}\) יחדיו כוללים את כל הרכיבים של \(p\), ולכן \(p|h_{i}h_{j}\), ולכן \(h_{i}q_{i}h_{j}q_{j}\) הוא פולינום שמתחלק על ידי הפולינום המינימלי של \(T\) ולכן כשמציבים בו את \(T\) מקבלים 0. פשוט למדי.

אם כן, ה-\(E_{i}\)-ים הללו הן אכן הטלות ולכן מפרקות את \(V\), אבל האם זה כמו שרצינו? לשם כך צריך להראות ש-\(E_{i}\left(V\right)=W_{i}\). נתחיל מהכיוון הקל. נניח ש-\(w\in E_{i}\left(V\right)\), אז זה אומר ש-\(E_{i}\left(w\right)=w\) (בשל התכונה \(E_{i}=E_{i}^{2}\)). מכאן שמתקיים:

\(p_{i}^{r_{i}}\left(T\right)\left(w\right)=p_{i}^{r_{i}}\left(T\right)E_{i}\left(w\right)=\left(p_{i}^{r_{i}}h_{i}q_{i}\right)\left(T\right)\left(w\right)=0\)

כשהשוויון האחרון נובע שוב מכך ש-\(p_{i}^{r_{i}}h_{i}q_{i}\) מתחלק על ידי הפולינום המינימלי של \(T\).

בכיוון השני, נניח ש-\(w\in\ker\left(p_{i}^{r_{i}}\left(T\right)\right)\). היינו רוצים להראות ש-\(w\in E_{i}\left(V\right)\), אבל יהיה לנו יותר קל להראות תכונה משלימה: ש-\(E_{j}\left(w\right)=0\) לכל \(j\ne i\), מה שיסיים מייד את ההוכחה כי אז \(w=I\left(w\right)=\sum E_{j}\left(w\right)=E_{i}\left(w\right)\in E_{i}\left(V\right)\). כעת, \(p_{i}^{r_{i}}\) מחלק את \(h_{j}\) לכל \(j\ne i\) ולכן \(E_{j}\left(w\right)=\left(h_{j}q_{j}\left(T\right)\right)\left(w\right)=0\) כי אפשר להציג את \(h_{j}q_{j}\left(T\right)\) כמכפלה של \(p_{i}^{r_{i}}\left(T\right)\) (שמאפס את \(w\) ולכן המכפלה תצא 0) בעוד איזה פולינום לא מעניין.

יפה. קיבלנו ש-\(W_{i}=E_{i}\left(V\right)\) ולכן \(V=W_{1}\oplus\dots\oplus W_{k}\). קיבלנו פירוק של \(V\) למרחבים שהצהרנו עליהם מראש, אבל למה הם תת-מרחבים שמורים של \(T\)? ובכן, אם \(p_{i}^{r_{i}}\left(T\right)\left(w\right)=0\) אז \(p_{i}^{r_{i}}\left(T\right)\left(T\left(w\right)\right)=T\left(p_{i}^{r_{i}}\left(T\right)\left(w\right)\right)=T\left(0\right)=0\) – כאן השתמשנו בכך שטרנספורמציה מתחלפת בכפל עם כל פולינום בה. נותר רק להראות ש-\(p_{i}^{r_{i}}\) הוא הפולינום המינימלי של \(T_{W_{i}}\). את זה שהוא מאפס את \(T_{W_{i}}\) קל לראות ישירות מההגדרה של \(W_{i}\) (הרי \(W_{i}\) הוגדר בתור אוסף האיברים שמאופסים על ידי \(p_{i}^{r_{i}}\left(T\right)\), כלומר באופן שמבטיח ש-\(p_{i}^{r_{i}}\left(T\right)\) יהיה אפס בכל \(W_{i}\), ולכן \(p_{i}^{r_{i}}\left(T_{W_{i}}\right)\) הוא אפס בכל מקום שבו הוא מוגדר). למה הוא מינימלי? נניח ש-\(q\) הוא פולינום כלשהו שמאפס את \(T_{W_{i}}\). אז \(q\cdot q_{i}\) יאפס את כל \(T\) (כי \(q\left(T\right)\) מתאפס על כל \(W_{i}\), ואילו \(q_{i}\left(T\right)\) יתאפס על כל \(W_{j}\) עבור \(j\ne i\)), ומכאן ש-\(p\) מחלק את \(q\cdot q_{i}\). אבל ב-\(q_{i}\) בכלל לא מופיע הגורם \(p_{i}^{r_{i}}\) של \(p\) ולכן הוא חייב להופיע בשלמותו ב-\(q\), כלומר \(q\) מתחלק על ידי \(p_{i}^{r_{i}}\), ומכאן שזהו אכן הפולינום המינימלי. סוף ההוכחה.

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

להטיל לכסון סימולטני בתת-מרחב שמור, בערך

פורסם בתאריך על ידי
9

תת-מרחבים שמורים

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

מה שעשינו היה להראות שוקטורים עצמיים השייכים לערכים עצמיים שונים הם בלתי תלויים לינארית, במובן זה שאם \(v_{1}+\dots+v_{k}=0\) כשכל \(v_{i}\) הוא וקטור המקיים \(T\left(v_{i}\right)=\lambda_{i}v_{i}\) עבור \(\lambda_{i}\)-ים שונים כולם, אז \(v_{1}=\dots=v_{k}=0\). ואז בא איזה שלב מזוויע שבו כתבתי צירוף לינארי של אוספי וקטורים שכל אחד מהם הוא בסיס לתת-מרחב עצמי אחר… אבל בעצם, עם קצת יותר סימונים והגדרות, אפשר היה לעשות את זה טיפה פחות מזוויע.

את מה שעשינו אפשר היה לנסח גם כך: לכל ערך עצמי \(\lambda_{i}\) הגדרנו תת-מרחב \(U_{i}\subseteq V\) – "המרחב העצמי של \(\lambda_{i}\)" – של כל הוקטורים המקיימים \(T\left(v\right)=\lambda_{i}v\) (כל הוקטורים העצמיים של \(\lambda_{i}\) בתוספת וקטור האפס), ואז ראינו שמתקיים \(V=U_{1}\oplus\dots\oplus U_{k}\), כאשר \(U_{1},\dots,U_{k}\) הם כל המרחבים העצמיים של הערכים העצמיים של \(T\). תזכורת: להגיד ש-\(V=U_{1}\oplus\dots\oplus U_{k}\) ("\(V\) הוא סכום ישר של \(U_{1},\dots,U{}_{k}\)") אומר שכל איבר ב-\(V\) ניתן לכתיבה כסכום \(v_{1}+\dots+v_{k}\) של איברים מ-\(U_{1},\dots,U_{k}\), ושכל המרחבים הללו זרים זה לזה, במובן זה שאם ניקח ולו אחד מהם ונוריד אותו מהסכום, אז לו וליתר הסכום לא יהיה איבר משותף השונה מ-0 (פורמלית \(U_{i}\cap\left(U_{1}+\dots+U_{i-1}+U_{i+1}+\dots+U_{k}\right)=\left\{ 0\right\} \); אולי טבעי יותר לדרוש ש-\(U_{i}\cap U_{j}=\left\{ 0\right\} \) וחסל אבל זו לא דרישה חזקה מספיק). זה תרגיל טוב להוכיח שהדרישה השניה שקולה לכך שדרך ההצגה של איבר ב-\(V\) כסכום איברים מתתי-המרחבים תהיה יחידה.

עכשיו, לכתוב את \(V\) כסכום ישר של תתי-מרחבים כלשהם זה דבר קל למדי – קחו כל בסיס שתרצו, חלקו את אברי הבסיס לכמה קבוצות שתרצו, ותת-המרחבים שנפרסים על ידי אברי הקבוצות (כל תת-מרחב נפרס על ידי אברי קבוצה אחת) יהוו סכום ישר שנותן את \(V\). יש אינספור דרכים לפרק את \(V\) כך, ורובן לא אומרות לנו משהו מועיל על הטרנספורמציה הלינארית \(T\). העסק מתחיל להיות מעניין כאשר יש לנו תת-מרחב \(W\) שמקיים את התכונה "כל מה שקורה ב-\(W\) (על ידי \(T\)) נשאר ב-\(W\)", ופורמלית \(T\left(W\right)\subseteq W\) (התמונה של כל איבר ב-\(W\) על ידי \(T\) נמצאת גם היא ב-\(W\)). תת-מרחב כזה נקרא תת-מרחב שמור (ביחס ל-\(T\)).

מכיוון שבמבט ראשון אולי לא ברור למה זו הגדרה מעניינת, בואו ונבין ראשית כל מה ינבע מכך שאני יודע לכתוב את \(V\) בתור סכום ישר \(U\oplus W\) כאשר \(U,W\) שניהם תתי-מרחבים שמורים של \(T\). ניקח בסיס ל-\(U\) ובסיס ל-\(W\) ואז איחודם הוא בסיס ל-\(V\) ואפשר להסתכל על המטריצה המיצגת של \(T\) בבסיס הזה. אז אני טוען שהמטריצה המייצגת תורכב משני בלוקים – תת-מטריצות ריבועיות מסויימות, כך שכל שאר המטריצה שווה לאפס. משהו כזה: \(\left[T\right]_{V}=\left[\begin{array}{cc}\left[T\right]_{U} & 0\\0 & \left[T\right]_{W}\end{array}\right]\) (כאן אני מתעלל בסימונים בצורה נוראית – \(\left[T\right]_{V}\) כאן פירושו "המטריצה המייצגת של \(T\) בבסיס שזה עתה דיברתי עליו של \(V\); באופן כללי אין לסימון \(\left[T\right]_{V}\) משמעות כי לכל בסיס של \(V\) שניקח נקבל מטריצה מייצגת אחרת). שימו לב ששני הבלוקים של המטריצה אינם כוללים תוכן מקרי, אלא את המטריצה המייצגת של \(T\) לפי הבסיסים של תתי-המרחבים. הסיבה שבגללה זה עובד היא שאם נפעיל את \(T\) על איבר בסיס של \(U\) נקבל איבר ב-\(U\) ולכן הוא יוצג כצירוף לינארי של אברי \(U\) בלבד; אברי \(W\) לא משתתפים בכלל במשחק. לכן על עמודה שמתאימה לאיבר בסיס של \(U\) מכילה אפסים בשורות שמתאימות לבסיס של \(W\), ואותו הדבר גם עבור העמודות שמתאימות לאברי בסיס של \(W\). אותיר לכם לכתוב את ההוכחה הפורמלית לעצמכם אם אתם עוד לא משוכנעים.

מכאן ממשיכים באינדוקציה ומקבלים את התוצאה הכללית: אם \(V=V_{1}\oplus\dots\oplus V_{k}\) כך ש-\(V_{i}\) הם תתי-מרחבים שמורים של \(T\), אז כאשר מייצגים את \(T\) בבסיס שהוא איחוד הבסיסים של אותם תת-מרחבים, \(T\) היא מטריצה בת \(k\) בלוקים. מה שמעניין אותנו עכשיו הוא אם אפשר להגיד עוד משהו על האופן שבו \(T\) מתפרקת בין כל תתי-המרחבים השמורים, וכמובן לשאול את עצמנו האם פירוק כזה קיים בכלל.

תתי-מרחבים שמורים הם הכללה ברורה של מרחבים עצמיים. אם \(U\) הוא מרחב עצמי של טרנספורמציה \(T\) הוא בוודאי יהיה תת-מרחב שמור שלה, כי כל מה שהפעלת \(T\) על איבר ב-\(U\) עושה היא לכפול אותו בסקלר, וזו פעולה שמשאירה את התוצאה בתוך התת-מרחב מעצם הההגדרה של תת-מרחב. למעשה, אם \(v\) הוא וקטור עצמי אז תת-המרחב שנפרש על ידו בלבד הוא תת-מרחב שמור. זה מבהיר לנו מייד מדוע אם יש למרחב בסיס של וקטורים עצמיים אז \(T\) לכסינה בבסיס זה – במקרה זה אפשר לפרק את \(V\) לסכום ישר של \(n\) תתי-מרחבים שכל אחד מהם ממימד 1, ולכן המטריצה שמייצגת את \(T\) היא מטריצת "בלוקים" שבה כל בלוק הוא מטריצה מסדר \(1\times1\). אין כאן שום רעיון חדש – הנימוק שכבר הבאתי לכך שטרנספורמציה היא לכסינה אם יש בסיס של וקטורים עצמיים השתמש באותם נימוקים שבהם השתמשתי כאן כדי להסביר איך מתקבלת מטריצת בלוקים – אבל זו עדיין דרך מחשבה נחמדה.

אם \(W\subset V\) הוא תת-מרחב שמור של \(T\), אז אפשר להסתכל על \(T\) כאשר היא מצומצמת רק לתת-מרחב \(W\). בואו נגדיר את זה פורמלית כדי למנוע בלבול: יש לנו טרנספורמציה \(T:V\to V\), ואפשר להגדיר טרנספורמציה חדשה \(T_{W}:W\to W\) שפשוט מוגדרת בתור \(T_{W}\left(w\right)=T\left(w\right)\) לכל \(w\in W\). הנקודה היא שבגלל ש-\(T_{W}\) מוגדרת על מרחב קטן יותר, קל יותר לחקור אותה – למשל, המטריצה המייצגת שלה תהיה קטנה יותר. עוד תכונה מעניינת שתהיה רלוונטית בהמשך היא שהפולינום האופייני של \(T_{W}\) מחלק את הפולינום האופייני של \(T\), אבל הם ממש לא חייבים להיות זהים. למה הוא מחלק? ובכן, אם \(p\left(T\right)\) היא טרנספורמציית האפס על \(V\) זה אומר שהיא מחזירה 0 לכל איבר של \(V\) ולכן בפרט לכל איבר של \(W\), ולכן \(p\) הוא פולינום שמאפס את \(T_{W}\); אבל כזכור, הפולינום המינימלי של \(T_{W}\) מחלק כל פולינום אחר שמאפס את \(T_{W}\).

לכסון סימולטני

בואו נעבור להמחשה של השימוש במושג של תת-מרחבים שמורים – לכסון סימולטני של טרנספורמציות (או מטריצות; זכרו שעבורנו זה אותו הדבר). בואו נניח ש-\(S,T\) הם שני אופרטורים לכסינים; זה אומר שקיים בסיס שבו \(T\) מיוצגת על ידי מטריצה אלכסונית, וקיים בסיס שבו \(S\) מיוצגת על ידי מטריצה אלכסונית, אבל האם קיים בסיס שבו שתיהן גם יחד מיוצגות על ידי מטריצה אלכסונית? התשובה היא שלא תמיד; קל לראות שהכרחי שהן יתחלפו, כלומר שיתקיים \(ST=TS\) (זכרו שטרנספורמציות ומטריצות לא מתחלפות תמיד בכפל – נסו למצוא דוגמאות!). הסיבה לכך היא שמטריצות אלכסוניות כן מתחלפות בכפל, ולכן אם \(S,T\) ניתנות בו זמנית להצגה בידי מטריצות אלכסוניות הן אכן יתחלפו בכפל. זו דוגמה לתנאי הכרחי, אבל מה שמפתיע כאן הוא שהוא גם מספיק: שתי טרנספורמציות לכסינות הן בעלות לכסון משותף אם ורק אם הן מתחלפות בכפל. למעשה, ההוכחה שאציג כעת עובדת גם אם יש יותר משתי טרנספורמציות – אפילו עבור מספר אינסופי שלהן, כל עוד כולן לכסינות וכל זוג טרנספורמציות מתחלפות בכפל.

תכונת ההתחלפות-בכפל תועיל לי באופן הבא: נניח של-\(T\) יש ערך עצמי \(\lambda\), אז המרחב העצמי השייך לערך העצמי הזה הוא בעצם הגרעין של הטרנספורמציה \(T-\lambda I\), ואם \(T\) מתחלף עם \(S\) כך גם הטרנספורמציה \(T-\lambda I\). כעת אני יכול לטעון טענה כללית קצת יותר: אם \(U,S\) טרנספורמציות לינאריות שמתחלפות בכפל, אז הגרעין של \(U\) הוא תת-מרחב שמור של \(S\), שהרי אם \(u\) נמצא בגרעין הזה נקבל ש-\(US\left(u\right)=SU\left(u\right)=S\left(0\right)=0\), כלומר גם \(S\left(u\right)\) בגרעין של \(U\).

מכאן נובע המשפט על לכסינות סימולטנית כמעט מאליו: אם לכל הטרנספורמציות יש רק ערך עצמי אחד אז כל בסיס שנבחר ילכסן את כולן בו זמנית (זכרו שהן לכסינות, כלומר הריבוי הגיאומטרי של הערך העצמי היחיד של כל אחת מהן הוא מימד \(V\)). בואו נניח אם כן שיש \(T\) עם יותר מערך עצמי אחד, \(\lambda_{1},\dots,\lambda_{t}\). זה מגדיר פירוק של \(V\) לתת-מרחבים עצמיים: \(V=W_{1}\oplus\dots\oplus W_{t}\) כש-\(W_{i}\) הוא המרחב העצמי של \(T\) שמתאים לערך העצמי \(i\). כעת בואו ניקח טרנספורמציה אחרת \(S\). אני בהחלט לא יכול לומר ש-\(W_{i}\) הוא מרחב עצמי שלה, אבל בגלל שהיא מתחלפת עם \(T\) אני בהחלט כן יכול לומר שהוא תת-מרחב שמור שלה, מהנימוק שהבאתי קודם (במקרה הזה, \(U=T-\lambda I\)). מה שנותר עכשיו לשים לב אליו הוא שכל \(S\) היא לכסינה גם כשהיא מצומצמת ל-\(W_{i}\) כי הפולינום המינימלי שלה ב-\(W_{i}\) מחלק את הפולינום המינימלי שלה ב-\(V\) (כאן אני מתבסס על טענה שטרם הוכחתי – שמטריצה היא לכסינה אם ורק אם לפולינום המינימלי שלה אין שורשים מרובים), ולכן אפשר באינדוקציה להניח שכל הצמצומים של הטרנספורמציות על \(W_{i}\) הן לכסינות סימולטנית ולסיים על ידי איחוד כל הבסיסים המלכסנים-סימולטנית של כל ה-\(W_{i}\).

למי שנראה לו שרימתי עם האינדוקציה בסוף, שימו לב לכך שבמרחב ממימד 1 כל בחירת בסיס "תלכסן סימולטנית" את כל הטרנספורמציות כי מטריצה \(1\times1\) היא תמיד אלכסונית; ושבגלל שבחרתי לעבוד עם \(T\) שיש לה יותר מערך עצמי אחד, יש לה יותר מ-\(W_{i}\) אחד ולכן המימד של כולם קטן יותר מהמימד של \(V\) ואפשר להשתמש באינדוקציה. ההוכחה הזו מבליטה היטב את הכוח שבדיבור על תתי-מרחבים שמורים – הם מאפשרים להוכיח דברים בשיטת הפרד ומשול.

הטלות

בואו נשכח לרגע מתתי-מרחבים שמורים ונדבר על פירוק כלשהו לסכום ישר, \(V=W_{1}\oplus\dots\oplus W_{k}\). בכל פירוק שכזה יש טרנספורמציות לינאריות שמאפיינות את הפירוק בדיוק כשם ש-\(W_{1},\dots,W_{k}\) מאפיינות אותו – ההטלות למרחבים \(W_{1},\dots,W_{k}\). פורמלית נהוג להגדיר באלגברה לינארית הטלה בתור כל טרנספורמציה לינארית \(T:V\to V\) המקיימת \(T^{2}=T\). בואו נבין למה: נסמן \(U=\mbox{Im}T\), ניקח בסיס ל-\(U\) ונשלים אותו לבסיס של \(V\) וניקח את אברי הבסיס שאינם של \(U\) ונביט במרחב \(U^{\prime}\) שהם פורשים – נקבל ש-\(V=U\oplus U^{\prime}\), ושאת \(T\) אפשר לתאר כך: אם \(v=u+u^{\prime}\) כאשר \(u\in U\) ו-\(u^{\prime}\in U^{\prime}\) (קיימת בדיוק דרך אחת להציג כך את \(v\)) אז \(T\left(v\right)=u\), כלומר \(T\) לוקחת את הרכיב של \(v\) שנמצא בתוך \(U\) ומוחקת את היתר. זה מתאים לאינטואיציה שיש לנו לגבי הטלות "קלאסיות" (הטלות כאלו הן בדרך כלל ביחס למערכת צירים שבה הצירים מאונכים זה לזה; גם לכך נגיע בסדרת הפוסטים הזו, אבל עוד חזון למועד).

את הרעיון הזה אפשר להכליל למקרה של \(V=W_{1}\oplus\dots\oplus W_{k}\). במקרה הזה, כל וקטור \(v\) ניתן להציג בצורה יחידה כ-\(v=w_{1}+\dots+w_{k}\) כאשר \(w_{i}\in W_{i}\); נגדיר טרנספורמציה לינארית \(E_{i}:V\to V\) על ידי \(E_{i}\left(v\right)=w_{i}\). קל לראות שזוהי הטלה, כלומר \(E_{i}^{2}=E_{i}\)וקל לראות ש=\(\mbox{Im}E_{i}=W_{i}\). מההגדרה נובע גם כמעט מייד ש-\(E_{i}E_{j}=0\) אם \(i\ne j\), ועם עוד טיפה עבודה אפשר לראות ש-\(I=\sum E_{i}\), כלומר הסכום של כל ההטלות הללו נותן לנו את טרנספורמציית הזהות.

מה שבאמת מעניין הוא שכל קבוצה של \(k\) הטלות \(E_{1},\dots,E_{k}\) שמקיימות את התכונה שהרכבה של שתיים מהן היא אפס וסכום כולן הוא הזהות מגדירות פירוק של \(V\) לסכום ישר של מרחבים שהם התמונות של ההטלות. גם זו טענה קלה יחסית אבל אוכיח אותה כאן כי היא לא מיידית כמו הכיוון השני. לפני כן רק אסביר לאן אני חותר עם זה – לב האתגר במשפט הפירוק הפרימרי (שהוא המטרה העיקרית של הפוסט הזה ואחד מה"גביעים הקדושים" בסדרת הפוסטים כולה באופן כללי) הוא למצוא הטלות שמקיימות תכונות מסויימות, ואז הפירוק נובע מהן בדיוק על פי המשפט שזה עתה אוכיח.

טוב, אז מה עושים? ראשית מגדירים \(W_{i}=\mbox{Im}E_{i}\). עכשיו צריך להראות גם שכל איבר ב-\(V\) ניתן לכתיבה כסכום של איברים ב-\(W_{i}\)-ים הללו, וגם שדרך ההצגה הזו היא יחידה. התכונה הראשונה נובעת מכך ש-\(I=\sum E_{i}\): פשוט נשים לב לכך ש-\(v=I\left(v\right)=\sum E_{i}\left(v\right)\) והנה קיבלנו הצגה של \(v\) כסכום של איברים ב-\(W_{i}\). כדי לראות שדרך ההצגה הזו היא יחידה, בואו קודם כל נשים לב לכך שאם \(v\in W_{i}\) אז \(E_{i}\left(v\right)=v\) ואילו \(E_{j}\left(v\right)=0\). למה? כי אם \(v\in W_{i}\) זה אומר ש-\(v\) הוא בתמונה של \(E_{i}\), כלומר \(v=E_{i}\left(u\right)\), ולכן \(E_{i}\left(v\right)=E_{i}^{2}\left(u\right)=E_{i}\left(u\right)=v\) ובדומה, \(E_{j}\left(v\right)=E_{j}E_{i}\left(u\right)=0\).

כעת, אם \(v=w_{1}+\dots+w_{k}\) אז מהתכונות לעיל נובע ש-\(E_{i}\left(v\right)=w_{i}\) – אבל הערך של \(E_{i}\left(v\right)\) ודאי אינו תלוי באופן שבו אנו בוחרים לפרק את \(v\) לסכום! במילים אחרות, גם אם היינו כותבים \(v=\alpha_{1}+\dots+\alpha_{k}\) כך ש-\(\alpha_{i}\in W_{i}\) היינו מקבלים \(E_{i}\left(v\right)=\alpha_{i}\) ולכן \(w_{i}=\alpha_{i}\) ודרך ההצגה הזו היא יחידה.

עכשיו אפשר לחזור למרחבים שמורים. מה שמעניין אותנו הוא השאלה הבאה: נתון פירוק \(V=W_{1}\oplus\dots\oplus W_{k}\) ונתונה טרנספורמציה \(T\) – מתי כל המרחבים \(W_{i}\) הם תתי-מרחבים שמורים של \(T\)? התשובה מקסימה, לטעמי, באלגנטיות שלה: אם ורק אם \(T\) מתחלפת עם ההטלות \(E_{i}\) המתאימות למרחבים.

כיוון אחד הוא קלי קלות: אם \(T\) מתחלפת עם \(E_{i}\) ו-\(w\in W_{i}\) אז \(T\left(w\right)=TE_{i}\left(w\right)=E_{i}T\left(w\right)\in W\) כשסימן השייכות בסוף נובע מכך ש-\(W_{i}\) הוא תמונת \(E_{i}\). מה שמעניין הוא הכיוון השני, להראות ש-\(T\) מתחלפת עם \(E_{i}\).

אם כן, הבה וניקח \(v\in V\) כלשהו ונפרק אותו לרכיביו, \(v=\sum w_{i}\). אז \(T\left(v\right)=\sum T\left(w_{i}\right)=\sum u_{i}\) כאשר \(u_{i}\in W_{i}\) – זה נובע מכך שמדובר על תתי-מרחבים שמורים של \(T\). כעת הבה ונפעיל על כל זה הטלה: \(E_{i}T\left(v\right)=u_{i}\) (מאותן סיבות שכבר ראינו עד כה). מצד שני, \(TE_{i}\left(v\right)=T\left(w_{i}\right)=u_{i}=E_{i}T\left(v\right)\), והנה קיבלנו ש-\(TE_{i}=ET_{i}\) (כי ההוכחה הייתה על \(v\) כלשהו).

הדבר הבא שאני רוצה להראות הוא אפיון אלטרנטיבי ללכסינות, שבכלל לא מדבר על ערכים עצמיים, בסיסים, ריבוי אלגברי וגאומטרי ושום דבר דומה לזה, אלא רק על הטלות. בואו נתחיל מכך שאם \(T\) לכסינה עם ערכים עצמיים \(\lambda_{1},\dots,\lambda_{k}\) אז כפי שכבר אמרתי מאות פעמים, אפשר לפרק את \(V\) לסכום של מרחבים עצמיים. בואו ניקח את \(E_{1},\dots,E_{k}\) להיות ההטלות על אותם מרחבים עצמיים, אז כמו תמיד הן יקיימו \(I=\sum E_{i}\) ו-\(E_{i}E_{j}=0\) לכל \(i\ne j\). יופי. רק שהן יקיימו הפעם תכונה נוספת: \(T=\sum\lambda_{i}E_{i}\). למה? ובכן, קחו \(v\in V\) כלשהו, אז כמקודם \(v=I\left(v\right)=\sum E_{i}\left(v\right)\), ומכיוון ש-\(E_{i}\left(v\right)\) נמצא במרחב העצמי \(W_{i}\) אז \(T\left(E_{i}\left(v\right)\right)=\lambda_{i}E_{i}\left(v\right)\), כלומר \(T\left(v\right)=\sum\lambda_{i}E_{i}\left(v\right)\) לכל \(v\), ולכן \(T=\sum\lambda_{i}E_{i}\).

מסתבר שהתכונה הזו היא גם מספיקה כדי ש-\(T\) תהיה לכסינה. במילים אחרות, \(T\) לכסינה אם קיימים סקלרים שונים \(\lambda_{1},\dots,\lambda_{k}\) וטרנספורמציות לינאריות \(E_{1},\dots,E_{k}\) שונות מאפס כך ש-\(T=\sum\lambda_{i}E_{i}\) ו-\(I=\sum E_{i}\) ו-\(E_{i}E_{j}=0\) (ובאופן צפוי, \(\lambda_{i}\) הם הערכים העצמיים שלה, ו-\(E_{i}^{2}=E_{i}\) כך ש-\(E_{i}\) הן הטלות). ההוכחה היא תרגיל טוב ולא שונה כל כך ממה שכבר ראינו אז אוותר עליה. במקום זה בואו נראה שימוש מיידי של התוצאה הזו: אם \(T=\sum\lambda_{i}E_{i}\), מהו \(T^{2}\)? לכאורה על פי חוקי הכפל נקבל \(T^{2}=\sum_{i,j}\lambda_{i}\lambda_{j}E_{i}E_{j}\), אבל אם נשתמש בכך ש-\(E_{i}E_{j}=0\) ובכך ש-\(E_{i}^{2}=E_{i}\) נקבל ש-\(T^{2}=\sum\lambda_{i}^{2}E_{i}\), ובאופן כללי לא קשה לראות שאם \(p\) הוא פולינום כלשהו אז \(p\left(T\right)=\sum p\left(\lambda_{i}\right)E_{i}\). לא רק שהאבחנה הזו תעזור לנו בהמשך, היא כבר כעת מוכיחה מייד שאם יש לנו טרנספורמציה \(T\), אז הערכים העצמיים של \(p\left(T\right)\) הם בדיוק הפעלת \(p\) על הערכים העצמיים של \(T\) – לא תוצאה טריוויאלית כלל ממבט ראשון.

כעת אוכיח סוף סוף את הקריטריון ללכסינות שמבוסס על הפולינום המינימלי: טרנספורמציה היא לכסינה אם ורק אם לפולינום המינימלי שלה אין שורש מרובה (כלומר, הוא מהצורה \(\left(x-\lambda_{1}\right)\cdots\left(x-\lambda_{k}\right)\) כאשר כל ה-\(\lambda_{i}\) שונים זה מזה).

נתחיל מהכיוון הקל. נניח של-\(T\) יש את הערכים העצמיים \(\lambda_{1},\dots,\lambda_{k}\), אז \(T=\sum\lambda_{i}E_{i}\). אם \(p\) פולינום שמאפס את \(T\), אז בהכרח \(\sum p\left(\lambda_{i}\right)E_{i}=0\). על ידי הפעלות של \(E_{j}\) על המשוואה הזו רואים שבהכרח נובע ממנה ש-\(p\left(\lambda_{i}\right)=0\) לכל \(\lambda_{i}\). כלומר: כל פולינום שמאפס את \(T\) חייב להתאפס על ידי כל הערכים העצמיים. כמו כן, הפולינום \(\left(x-\lambda_{1}\right)\cdots\left(x-\lambda_{k}\right)\) מאפס את כל הערכים העצמיים בו זמנית ולכן מאפס את \(T\), ולכל פולינום שמחלק אותו קיים ערך עצמי שהוא לא מחלק. מסקנה: \(\left(x-\lambda_{1}\right)\cdots\left(x-\lambda_{k}\right)\) הוא הפולינום המינימלי של \(T\).

הכיוון השני הוא העיקר – נניח ש-\(\left(x-\lambda_{1}\right)\cdots\left(x-\lambda_{k}\right)\) הוא הפולינום המינימלי של טרנספורמציה \(T\) ונוכיח שהיא לכסינה ועם הערכים העצמיים \(\lambda_{1},\dots,\lambda_{k}\). הרעיון יהיה לבנות הטלות שמקיימות את התכונות של המשפט שלעיל – סכומן הוא \(I\), סכומן המשוקלל עם \(\lambda_{1},\dots,\lambda_{k}\) הוא \(T\), וההרכבה של כל זוג מהן היא אפס. האופן שבו מוצאים את ההטלות הללו הוא מקסים למדי ונותן לי תירוץ להציג יותר בפירוט משהו שכבר דיברתי עליו – אינטרפולציית לגראנז'.

הרעיון באינטרפולציית לגראנז' הוא לבנות פולינום בעל ערכים נתונים. נותנים לי סדרת זוגות של נקודות \(\left(x_{0},y_{0}\right),\left(x_{1},y_{1}\right),\dots,\left(x_{d},y_{d}\right)\) ודורשים ממני למצוא פולינום \(g\) ממעלה \(d\) לכל היותר שמקיים \(g\left(x_{i}\right)=y_{i}\) לכל זוג מזוגות הנקודות (לא קשה להוכיח שאם קיים פולינום כזה, הוא יחיד – כל שני פולינומים ממעלה לכל היותר \(d\) שמסכימים על \(d+1\) נקודות הם זהים). הפתרון הוא להשתמש במעין בסיס (לא במובן הסטנדרטי) שמותאם לסדרת ה-\(x_{i}\)-ים הנתונה ומאפשרת, לכל סדרת \(y_{i}\)-ים, לבנות בקלות את \(g\) המתאים. לב העניין הוא בבניה של פולינומים \(p_{0},p_{1},\dots,p_{d}\) שכל אחד מהם מקיים \(p_{i}\left(x_{j}\right)=\delta_{ij}\), כלומר הוא מתאפס על כל ה-\(x\)-ים פרט לאחד, ועליו הוא מקבל 1. פולינום כזה קל לבנות במפורש: \(p_{i}\left(x\right)=\prod_{j\ne i}\frac{x-x_{j}}{x_{i}-x_{j}}\) (כאשר \(\prod\) כאן מייצג מכפלה). הציבו בפולינום הזה \(x_{i}\) ותראו מה מקבלים, ואחר כך חשבו מה קורה כשמציבים בו \(x_{j}\) אחר.

עכשיו, אם ה-\(p\)-ים הללו נתונים לנו, אז את \(g\) בונים בצורה הבאה: \(g\left(x\right)=\sum y_{i}p_{i}\left(x\right)\). כשמציבים ב-\(g\) את \(x_{i}\), מה שנשאר כשהעשן מתפזר הוא \(y_{i}\). הדבר הזה מאוד דומה להטלות, שבתורן מאוד דומות לבסיסים למרחבים וקטוריים (ובפרט לבסיס אורתונורמליים, אבל עוד חזון למועד…) ולא סתם – הנה לנו דוגמה יפה למקום שבו כל הקשרים הללו באים לידי ביטוי.

איך כל זה קשור לענייננו, תשאלו? פשוט מאוד: ניקח את סדרת ה-\(x\)-ים שלנו להיות \(\lambda_{1},\dots,\lambda_{k}\) ונבנה פולינומים \(p_{1},\dots,p_{k}\) מתאימים. כעת נבצע בעזרתם אינטרפולציה לשני פולינומים: אחד שמחזיר 1 על הכל, ושני שאם הוא מקבל \(x\) הוא מחזיר \(x\). מנוסחת האינטרפולציה שלנו נקבל:

\(1=\sum p_{i}\)

\(x=\sum\lambda_{i}p_{i}\)

(אני מניח כאן באופן סמוי ש-\(k>1\) אבל זה בסדר כי \(k=1\) אומר ש-\(T-\lambda I=0\) (פשוט הצבתי את \(T\) בפולינום המינימלי) ולכן \(T\) בבירור לכסינה).

עכשיו הטוויסט הסופי מגיע: נגדיר את \(E_{i}=p_{i}\left(T\right)\). הצבנו את \(T\) בפולינומי האינטרפולציה, וקיבלנו מייד שמתקיים:

\(I=\sum E_{i}\)

\(T=\sum\lambda_{i}E_{i}\)

טוב ויפה, אבל למה \(E_{i}E_{j}=0\)? או, טוב ששאלתם: כי \(p\) בהכרח מחלק את \(p_{i}p_{j}\), וזאת מכיוון ש-\(p_{i}p_{j}\) הוא פולינום שמתאפס על כל \(\lambda_{1},\dots,\lambda_{j}\) ולכן בהכרח מכיל בתוכו רכיב מהצורה \(\prod\left(x-\lambda_{i}\right)\) – הפולינום המינימלי בכבודו ובעצמו (כאן השתמשתי בהנחה שאין לפולינום המינימלי שורש מרובה).

הדבר האחרון שעוד צריך להשתכנע בו הוא שכל ה-\(E_{i}\)-ים שונים מאפס (זה תנאי הכרחי של המשפט שאותו לא הוכחתי). גם זה פשוט – אם \(E_{i}=0\) זה אומר ש-\(p_{i}\left(T\right)=0\) והנה מצאנו פולינום שמאפס את \(T\) אבל דרגתו היא רק \(k-1\), כלומר קטנה מדרגת הפולינום המינימלי. זה מסיים את הכל.

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