ארכיון חודשי: נובמבר 2011

ערכים עצמיים – מי, מה, כמה ולמה

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

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

נדבר על \(\mathbb{R}^{2}\). במרחב הזה שיקוף הוא תמיד ביחס לציר שהוא פשוט קו ישר. מכל נקודה במישור ניתן להוריד אנך אל הקו הישר הזה (אנך פירושו שהוא יוצר זווית של 90 מעלות עם הישר) – אורכו של האנך הוא מרחק הנקודה מהישר. כעת ניתן להעביר אנך באותו אורך בדיוק מצדו השני של הישר; שיקוף פירושו להחליף את הנקודות שבקצות שני האנכים הללו (כלומר, כל נקודה מוחלפת בשכנה שלה שנמצאת בהמשך של האנך לישר, מאותו אורך, בצד השני). באופן ציורי, תחשבו על כך שציר השיקוף הוא מראה, ואנחנו משנים את המישור כך שכל נקודה עוברת אל הנקודה המדומיינת שבה היא ראתה את עצמה במראה.

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

נניח אם כן שציר השיקוף הוא הישר שעובר דרך ראשית הצירים והנקודה \(\left(a,b\right)\). נסמן את הטרנספורמציה של השיקוף ב-\(T\), וכעת השאלה היא מהו \(T\left(x,y\right)\). באופן כללי לא ברור בכלל איך לתקוף את השאלה הזו בלי ללכלך את הידיים בהרבה גאומטריה; למרבה המזל, נחלצת לעזרנו העובדה ש-\(T\) פועלת בצורה פשוטה ביותר על וקטורים ספציפיים. ראשית, הוקטור \(\left(a,b\right)\) עצמו: הוא נמצא על ציר השיקוף, ולכן לא אמור להשתנות בכלל, כלומר \(T\left(\left(a,b\right)\right)=\left(a,b\right)\).

שנית, אם נעביר דרך ראשית הצירים ישר שמאונך לציר השיקוף, ואם \(\left(c,d\right)\) היא נקודה כלשהי על הישר הזה, אז ברור כמעט מייד ש-\(T\left(\left(c,d\right)\right)=-\left(c,d\right)\) (כי במקרה הזה האנך שמועבר מ-\(\left(c,d\right)\) אל ציר השיקוף הוא בדיוק הקו הישר שמחבר את \(\left(c,d\right)\) עם הראשית \(\left(0,0\right)\)). מצאנו אם כן שני וקטורים שעליהם \(T\) פועלת בצורה פשוטה – את אחד הוקטורים היא פשוט כופלת ב-1, ואת השני היא פשוט כופלת ב-\(-1\). כדי למצוא \(\left(c,d\right)\) אפשר, למשל, לסובב את המישור ב-90 מעלות; כבר הזכרתי את הטרנספורמציה הזו פעם ואמרתי שהיא ניתנת לתיאור על ידי כפל במטריצה \(\left[\begin{array}{cc}0 & 1\\-1 & 0\end{array}\right]\), ולכן \(\left(c,d\right)=\left(b,-a\right)\).

אם \(a\ne0\) או \(b\ne0\), אז שני הוקטורים \(\left(a,b\right)\) ו-\(\left(b,-a\right)\) הם בלתי תלויים לינארית מהנימוק הנפלא הבא: הדטרמיננטה של המטריצה \(\left[\begin{array}{cc}a & b\\b & -a\end{array}\right]\) היא בדיוק \(-\left(a^{2}+b^{2}\right)\), ומכיוון ש-\(a^{2}+b^{2}\) שווה לאפס אם ורק אם \(a=b=0\), נובע שהמטריצה הפיכה, ומטריצה היא הפיכה אם ורק אם השורות שלה הן בלתי תלויות לינארית (אחרת בעזרת פעולות אלמנטריות אפשר היה לאפס את אחת מהשורות). זו המחשה נאה (לטעמי) לאופן שבו טיעונים באלגברה לינארית הופכים לטריוויאליים אחרי שיש היכרות בסיסית כלשהי עם המושגים והכלים.

יפה, אם כן מצאנו בסיס \(B\) של \(\mathbb{R}^{2}\) שעליו \(T\) פועלת באופן פשוט ואנו יודעים איך להציג כל איבר ב-\(\mathbb{R}^{2}\) עם הבסיס הזה. השלב הבא הוא למצוא ייצוג של \(T\) על פי הבסיס הזה; זה אומר להפעיל את \(T\) על אברי הבסיס ולקחת את וקטורי הקואורדינטות של התוצאות וזו מהומה חישובית שלמה באופן כללי, אבל כאן אני יכול לכתוב את המטריצה בלי לחשוב בכלל: \(\left[T\right]_{B}=\left[\begin{array}{cc}1 & 0\\0 & -1\end{array}\right]\). למה? כי העמודה הראשונה של \(\left[T\right]_{B}\) היא וקטור הקוארדינטות של מה שמקבלים כשמפעילים את \(T\) על \(\left(a,b\right)\), ואמרנו שאז מקבלים שוב את \(\left(a,b\right)\); והעמודה השניה היא מה שמקבלים כשמפעילים אותה על \(\left(b,-a\right)\) ואמרנו שאז מקבלים את \(-\left(b,-a\right)\). מכיוון שבחרנו ל-\(T\) בסיס שבו הפעולה של \(T\) על אברי הבסיס היא פשוטה – רק כפל בסקלר – גם המטריצה של \(T\) פשוטה.

מכיוון שאולי יותר נוח לנו באופן כללי לייצג את \(T\) בבסיס הסטנדרטי, נותר רק למצוא את מטריצת המעבר מהבסיס \(B\) לבסיס הסטנדרטי: זוהי המטריצה \(P=\left[\begin{array}{cc}a & b\\b & -a\end{array}\right]\) (כאן אברי הבסיס \(B\) כתובים בעמודות; באופן קסום כלשהו הם כתובים גם בשורות, אבל זה לא כך באופן כללי). כל שנותר לעשות הוא למצוא את \(P^{-1}\) ואת זה אפשר לעשות כאן בקלות בעזרת נוסחת קרמר, שמראה לנו שבמקרה הזה המטריצה ההופכית של \(\left[\begin{array}{cc}a & b\\b & -a\end{array}\right]\) היא \(\frac{-1}{a^{2}+b^{2}}\left[\begin{array}{cc}-a & -b\\-b & a\end{array}\right]\) (באופן כללי ההופכית של מטריצה כללית מסדר \(2\times2\), שנסמן \(\left[\begin{array}{cc}a & b\\c & d\end{array}\right]\) היא \(\frac{1}{ad-bc}\left[\begin{array}{cc}d & -b\\-c & a\end{array}\right]\); זהו אולי השימוש הפשוט ביותר בנוסחת קרמר, וכזה שאפשר אפילו לזכור בעל פה לפעמים).

השלב האחרון הוא החישוב הלא-כל-כך-נעים של

\(\left[T\right]_{E}=P\left[T\right]_{B}P^{-1}=\frac{-1}{a^{2}+b^{2}}\left[\begin{array}{cc}a & b\\b & -a\end{array}\right]\left[\begin{array}{cc}1 & 0\\0 & -1\end{array}\right]\left[\begin{array}{cc}-a & -b\\-b & a\end{array}\right]=\frac{-1}{a^{2}+b^{2}}\left[\begin{array}{cc}a & b\\b & -a\end{array}\right]\left[\begin{array}{cc}-a & -b\\b & -a\end{array}\right]=\frac{1}{a^{2}+b^{2}}\left[\begin{array}{cc}a^{2}-b^{2} & 2ab\\2ab & b^{2}-a^{2}\end{array}\right]\)

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

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

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

בפוסט שעסק בכפל מטריצות אמרתי שאפשר לספור מסלולים בגרף באמצעות מטריצת השכנויות של הגרף. כזכור, זו הייתה מטריצה \(A\) שהכניסה ה-\(\left(i,j\right)\) שלה כללה את מספר הקשתות מ-\(i\) אל \(j\) בגרף, והתברר כי הכניסה \(A_{ij}^{k}\) היא בדיוק מספר המסלולים מאורך \(k\) מ-\(i\) אל \(j\). כעת, נניח שמבקשים מכם למצוא את כל המסלולים מאורך 1000 מ-\(i\) אל \(j\), כלומר לחשב את \(A_{ij}^{1000}\) – זה נראה איום ונורא על פניו, כי לכפול מטריצה בעצמה 1000 פעמים זה לא כיף. יש תעלול נחמד שחוסך זמן – להעלות את \(A\) בריבוע, ואת התוצאה שוב להעלות בריבוע, וכך חיש קל לקבל את כל החזקות של \(A\) שהן עצמן חזקות של 2 ואיתן "להרכיב" את 1000 איכשהו, אבל גם בשיטה הזו עדיין צריך לבצע הרבה כפלי מטריצות. ואם מבקשים מכם למצוא נוסחה כללית ל-\(A_{ij}^{n}\) כתלות ב-\(n\) זה כבר בכלל נראה קשה. אבל למרבה המזל לפעמים זה קל; אם אנחנו יודעים על מטריצה אלכסונית \(D\) כך ש-\(A=P^{-1}DP\) עבור \(P\) הפיכה כלשהי, אז שימו לב שלמשל

\(A^{3}=\left(P^{-1}DP\right)\left(P^{-1}DP\right)\left(P^{-1}DP\right)=P^{-1}D\left(PP^{-1}\right)D\left(PP^{-1}\right)DP=P^{-1}D^{3}P\)

וכפי שניתן לנחש – באופן כללי, \(A^{n}=P^{-1}D^{n}P\). כעת, אם \(D\) היא אלכסונית אז \(D^{n}\) קלה ביותר לחישוב – זו פשוט \(D\) כאשר כל איברי האלכסון מועלים בחזקת \(n\) (למשל, אם \(D=\left[\begin{array}{cc}2 & 0\\0 & 3\end{array}\right]\) אז \(D^{3}=\left[\begin{array}{cc}2^{3} & 0\\0 & 3^{3}\end{array}\right]=\left[\begin{array}{cc}8 & 0\\0 & 27\end{array}\right]\)). כלומר, חישוב חזקות של \(A\) הופך לטריוויאלי. איך זה קשור לערכים עצמיים? ובכן, אם אפשר לעבור מ-\(A\) באופן הזה למטריצה אלכסונית (זה נקרא לכסון של \(A\)) אז האיברים באלכסון של \(D\) הם בדיוק הערכים העצמיים של \(A\), והדרך הישירה למציאת \(D\) (ועוד יותר חשוב, \(P\)) היא בדיוק דרך מציאת הערכים העצמיים והוקטורים העצמיים של \(A\).

העניין רק מתחיל כאן. בעיות ספירה רבות בקומבינטוריקה ניתנות להצגה באמצעות ספירת מסלולים בגרף מסויים. לעתים קרובות הגרף הזה גדול מכדי שניתן יהיה ללכסן את המטריצה שמתאימה לו, אפילו אם היא ניתנת ללכסון, ולכן נוסחה מדוייקת לבעיית הספירה הופכת למשהו שקשה לחשב; אבל ניתן להראות שעבור מטריצות שבאות מגרפים שכאלו, מספר המסלולים שאותו סופרים יהיה מסדר גודל של \(O\left(\lambda^{n}\right)\) מסלולים מאורך \(n\), כאשר \(\lambda\) הוא הערך העצמי הממשי הגדול ביותר של המטריצה, ואותו אפשר לחשב באופן מקורב גם בלי ללכסן את המטריצה (איך? זהו תחום שלם באנליזה נומרית…). זוהי תוצאה מרתקת בקומבינטוריקה שקושרת אותה באופן חזק לאלגברה לינארית, ומוכחת באמצעות כלים מאנליזה – אחת מהדוגמאות הפשוטות ביותר להדגמה של האופן שבו ה"סוגים" השונים של המתמטיקה הם לא עולמות נפרדים אלא פנים משלימות של אותו הדבר.

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

אלו דוגמאות לשימושים שאני מכיר די טוב אישית; את רוב השימושים – ויש כאלו בתחומי מדע לא מעטים – אני פשוט לא מכיר. עם זאת, אני חייב לתת דוגמה אחת מפיזיקה אחרת באמת אחטא לעובדות. בשעתו כתבתי פוסט שעסק במשוואה הדיפרנציאלית שצצה כשמנסים להבין את התנהגותה של מסה שמחוברת לקפיץ. המשוואה שקיבלנו לבסוף הייתה \(f^{\prime\prime}\left(t\right)=-\omega^{2}\cdot f\left(t\right)\) (כאשר \(\omega=\sqrt{\frac{k}{m}}\) חושב מתוך הקבועים של הבעיה – קבוע הקפיץ והמסה של הגוף המעורב) והיא נפתרה על ידי \(f\left(t\right)=C\cdot e^{i\omega t}\) (במקום האקספוננט המרוכב אפשר היה להשתמש בסינוסים וקוסינוסים ממשיים, ופירטתי על כך בשעתו). ליתר דיוק, לכל \(C\) (שיכול להיות מספר מרוכב כלשהו) התקבלה פונקציה שפותרת את המשוואה, ובחרנו שתי פונקציות כאלו שהיו בלתי תלויות לינארית כדי לפרוש את כל מרחב הפתרונות.

עכשיו בואו נעבור לדבר על מערכת קצת יותר מחוכמת, זו:


כאן יש לנו שני גופים שמחוברים בקפיצים הן זה לזה והן כל אחד לקיר אחר. נניח שהמסות של הגופים זהות (ונסמן את המסה הזו ב-\(m\)) ושקבוע הקפיץ של כל הקפיצים זהה (ונסמן אותו ב-\(k\)). עכשיו יש לנו שתי פונקציות: \(f_{1}\left(t\right)\) ו-\(f_{2}\left(t\right)\) שמגדירות את מיקומי הגופים כפונקציה של הזמן. אפשר לחשוב על זה כעל וקטור של פונקציות: \(\overline{f}\left(t\right)=\left(f_{1}\left(t\right),f_{2}\left(t\right)\right)\).

כעת, כל מסה נמשכת הן על ידי הקפיץ שמחבר אותה לקיר, והן על ידי הקפיץ שמחבר בין שתי המסות. אורך הקפיץ שמחבר את שתי המסות הוא בדיוק \(\left|f_{1}-f_{2}\right|\), וזה מניב לנו את שתי המשוואות הבאות:

\(mf_{1}^{\prime\prime}=-kf_{1}+k\left(f_{2}-f_{1}\right)\)

\(mf_{2}^{\prime\prime}=-kf_{2}+k\left(f_{1}-f_{2}\right)\)

מה שמתבקש לאור נסיון העבר הוא "לנחש" שהפתרון הוא מהצורה \(\overline{f}=\left(C_{1}e^{i\omega t},C_{2}e^{i\omega t}\right)\). אם מציבים את הפתרון הזה במשוואות, מקבלים:

\(-m\omega^{2}C_{1}e^{i\omega t}=-kC_{1}e^{i\omega t}+k\left(C_{2}-C_{1}\right)e^{i\omega t}\)

\(-m\omega^{2}C_{2}e^{i\omega t}=-kC_{2}e^{i\omega t}+k\left(C_{1}-C_{2}\right)e^{i\omega t}\)

יש לנו כאן שלושה משתנים – \(C_{1},C_{2}\) ו-\(\omega\), ואנו מצפים לקבל אותם כפרמטרים של \(m,k\) איכשהו. ראשית כל אפשר לחלק את כל המשוואות ב-\(e^{i\omega t}\) וב-\(m\) ולקבל את התיאור הנקי יותר:

\(\omega^{2}C_{1}=2\frac{k}{m}C_{1}-\frac{k}{m}C_{2}\)

\(\omega^{2}C_{2}=2\frac{k}{m}C_{2}-\frac{k}{m}C_{1}\)

ואת זה אפשר לכתוב בצורת משוואה מטריציונית:

\(\left[\begin{array}{cc}2\frac{k}{m} & -\frac{k}{m}\\-\frac{k}{m} & 2\frac{k}{m}\end{array}\right]\left[\begin{array}{c}C_{1}\\C_{2}\end{array}\right]=\omega^{2}\left[\begin{array}{c}C_{1}\\C_{2}\end{array}\right]\)

במילים אחרות, \(\left[\begin{array}{c}C_{1}\\C_{2}\end{array}\right]\) הוא וקטור עצמי המתאים לערך העצמי \(\omega^{2}\) של הטרנספורמציה הלינארית המוגדרת באמצעות המטריצה \(\left[\begin{array}{cc}2\frac{k}{m} & -\frac{k}{m}\\-\frac{k}{m} & 2\frac{k}{m}\end{array}\right]\); זוהי טרנספורמציה שמאפיינת את המערכת שהצגתי, של זוג מסות וקפיצים מסויימים, אבל למערכות מורכבות אחרות של קפיצים ומסות גם כן אפשר (בעקרון) לחשוב על טרנספורמציה דומה. כעת, הפתרון של מערכת הקפיצים הזו יכלול את מציאת הערכים העצמיים האפשריים (הערכים הרלוונטיים של \(\omega\)) וערכים אלו יאפיינו את תדירויות התנודה של המערכת (בדומה לאופן שבו \(\omega\) עשה זאת במקרה של המערכת הפשוטה), ואת הוקטורים העצמיים שמתאימים לכל ערך עצמי, שמגדירים את אופני התנודה של המערכת.

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

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

סדרות ביטי ומלכות שחמט

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

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

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

בואו נניח שהמשבצת השמאלית-תחתונה היא \(\left(0,0\right)\) כי אז הניתוח יצא יפה יותר. בנוסף, בואו נסכים גם ש-\(\left(0,0\right)\) נחשבת למשבצת של הפסד (אפשר להגדיר ש"המפסיד הוא מי שכבר לא יכול לזוז" ואז זה ברור יותר). עכשיו בואו וננסה להבין אילו משבצות הן של ניצחון: ברור ש-\(\left(0,1\right),\left(1,0\right),\left(1,1\right)\) כולן משבצות מנצחות, כי מכולן אפשר להגיע בצעד אחד אל \(\left(0,0\right)\). מה עם \(\left(1,2\right)\)? ובכן, זו משבצת של הפסד, כי אם זזים בשורה אפשר להגיע רק אל \(\left(1,1\right)\) או \(\left(1,0\right)\) שמבטיחות ניצחון ליריב; ואם זזים בעמודה מגיעים אל \(\left(0,2\right)\) שגם היא משבצת ניצחון. בגלל הסימטריה של המשחק גם \(\left(2,1\right)\) היא משבצת הפסד. בגלל אותה סימטריה נרצה למצוא רק משבצות הפסד \(\left(i,j\right)\) שבהן \(i<j\). משבצות שבהן \(i>j\) הן לא מעניינות כי כדי להבין מה קורה בהן מספיק להבין מה קורה ב-\(\left(j,i\right)\); ואם \(i=j\) זה הכי לא מעניין כי ממשבצת כזו אפשר להגיע (באלכסון) ישר אל \(\left(0,0\right)\) ולכן זו תמיד משבצת נצחון.

עכשיו \(\left(2,3\right)\) היא משבצת ניצחון, כי ממנה אפשר לזוז אל \(\left(1,2\right)\) שתבטיח שהשחקן השני יפסיד. ומה עם \(\left(2,4\right)\)? אותו סיפור. בעצם, כל משבצת בשורה \(2\) עם עמודה שגדולה מ-1, מובטח לה שתהיה משבצת ניצחון. לכן בשורה 2 לא נמצא אף משבצת הפסד "מעניינת" (יש את \(\left(2,1\right)\) אבל היא לא מעניינת כי הקואורדינטה הראשונה גדולה מהשניה). לכן נעבור לשורה 3. המשבצת המעניינת הראשונה כאן היא \(\left(3,4\right)\); ממנה אפשר להגיע בתנועה באלכסון אל \(\left(1,2\right)\) שהיא משבצת הפסד, ולכן \(\left(3,4\right)\) היא משבצת נצחון. לעומת זאת מ-\(\left(3,5\right)\) כל צעד שנעשה יוביל אותנו למשבצת נצחון, ולכן \(\left(3,5\right)\) היא משבצת הפסד. כאן אפשר לעצור לרגע ולנסות ולראות את התמונה הגדולה.

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

העובדה ש-\(\left(1,2\right)\) היא משבצת הפסד אומרת שכל משבצת מהצורה \(\left(i,i+1\right)\), כאשר \(i>1\), לא יכולה להיות משבצת הפסד. בדומה, \(\left(3,5\right)\) גורמת לכך ש-\(\left(i,i+2\right)\) לא תהיה משבצת הפסד עבור \(i>3\). מכאן כבר אפשר לנחש את האופן הכללי שבו בונים את סדרת משבצות ההפסד: בכל צעד בוחרים את מספר השורה הקטן ביותר שטרם הופיעה לא כשורה ולא כעמודה בתוך משבצת הפסד קודם (למשל, מ-\(\left(1,2\right)\) עברנו לטפל בשורה \(3\) ולא בשורה 2 כי שורה 2 כבר טופלה בכך ש-\(\left(1,2\right)\) מראה לנו שגם \(\left(2,1\right)\) היא משבצת הפסד), ולמספר השורה הזה מצרפים את מספר העמודה שגדול ממנו ב-\(k\), כאשר \(k\) הוא מספר משבצות ההפסד שמצאנו עד כה.

אם תריצות את ה"אלגוריתם" הזה, תראו שאתם מקבלים את הסדרה הבאה:

\(\left(0,0\right),\left(1,2\right),\left(3,5\right),\left(4,7\right),\left(6,10\right),\left(8,13\right),\left(9,15\right),\left(11,18\right),\dots\).

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

\(1,3,4,6,8,9,11,\dots\)

\(2,5,7,10,13,15,18,\dots\)

האם יש חוקיות כאן? במבט ראשון קצת קשה לראות כזו, אבל שני דברים צצים לעין כמעט מייד – ראשית, ששתי הסדרות הן זרות – אין איבר ששייך לשתיהן. שנית, הן מכסות את כל הטבעיים, כלומר כל מספר טבעי ייכנס אליהן. זה לא באמת מפתיע אם חושבים על אופן הבניה שלהן: הכלל שלפיו בוחרים את המספר החדש להכניס לסדרה הראשונה הוא "בחר את המספר הקטן ביותר שטרם הופיע", מה שמבטיח שנתפוס את כולם מתישהו; קצת יותר טריקי להראות שאין איבר שמופיע בשני הסדרות גם יחד, אבל ההגיון פה גם די ברור – על פי הבניה, \(a_{n}<b_{n}\) תמיד, ולכן אם יש שוויון הוא של \(a_{n}=b_{m}\) עם \(m<n\), אבל \(a_{n}\) נבחר רק מקרב מספרים שלא הופיעו עד כה, ומכיוון ש-\(b_{m}\) כבר הופיע לפני השלב \(n\), אין סיכוי ש-\(a_{n}=b_{m}\).

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

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

ראשית, מי אותו \(b\) מסתורי יכול להיות? הנה שיקול יפה שנותן לנו רמז: סדרת הביטי שמתאימה ל-\(a\) תופסת בערך \(\frac{1}{a}\) מבין כל הטבעיים. בצורה קצת יותר פורמלית אפשר לדבר על \(\lim_{n\to\infty}\frac{\left|\left\{ a_{1},\dots,a_{n}\right\} \cap\left\{ 1,\dots,n\right\} \right|}{n}\) ולהראות שהוא שווה ממש ל-\(\frac{1}{a}\). אם כך, כדי ש-\(b_{n}\) תהיה סדרה משלימה, היא צריכה לתפוס את כל יתר הטבעיים, כלומר צריך שיתקיים \(\frac{1}{a}+\frac{1}{b}=1\). קצת חילוץ אלגברי ומקבלים \(b=\frac{a}{a-1}\).

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

הרעיון הוא כזה: דמיינו אצטדיון בצורת מעגל, שהיקפו הוא בדיוק 1. כעת, מהנקודה הצפונית ביותר באצטדיון, שנסמן בתור ה"ראשית" \(O\), יוצאים שני רצים – אליס ובוב – כל אחד לכיוון אחר (אחד עם כיוון השעון והשני נגד כיוון השעון). מהירות אליס היא \(\frac{1}{a}\) (כלומר, מרחק של \(\frac{1}{a}\) אצטדיון בכל יחידת זמן) ומהירות בוב היא \(\frac{1}{b}\) – כלומר, הם משלימים סיבוב סביב האצטדיון בזמנים \(a,b\) בהתאמה, ובגלל ש-\(\frac{1}{a}+\frac{1}{b}=1\) הם נפגשים בדיוק כל יחידת זמן. כעת התעלול פשוט: כאשר אליס עוברת ב-\(O\) היא צועקת את מספר הפעמים שהיא חלפה עד כה על פני בוב; וכאשר בוב חולף ב-\(O\) הוא צועק את מספר הפעמים שהוא חלף עד כה על פני אליס.

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

אבל עכשיו, למה אלו סדרות זרות ומשלימות? אנחנו מקבלים את זה כמעט בחינם מהמודל שלנו. האבחנה המרכזית פה היא שאליס ובוב לא יחזרו אף פעם להיות בו זמנית ב-\(O\), וזה נובע ישירות מכך ש-\(a,b\) אי רציונליים; אם \(a\) היה רציונלי אז גם \(b=\frac{a}{a-1}\) היה רציונלי, ועל ידי מכנה משותף היינו מגלים מייד מתי שניהם יחזרו להיות יחד ב-\(O\) (בדקו זאת!) והיינו מקבלים שהם צועקים את אותו המספר גם יחד והייתה התנגשות של הסדרות.

אוקיי, אז אם \(a,b\) רציונליים אליס ובוב לא נפגשים בראשית, אבל למה אם הם אי רציונליים מובטח שהם לא ייפגשו בראשית? פגישה כזו פירושה \(na=mb\) עבור \(n,m\) טבעיים, כלומר ש-\(a=\frac{m}{n}b\); ומכיוון ש-\(\frac{1}{a}+\frac{1}{b}=1\) נקבל ש-\(\left(\frac{n}{m}+1\right)\frac{1}{b}=1\), כלומר \(b=\frac{n+m}{m}\) שהוא מספר רציונלי לגמרי (ובדומה \(a=\frac{n+m}{n}\)). זו סיטואציה מאוד נפוצה עם מספרים אי רציונליים – תנו להם לרוץ סביב אצטדיון עם אורך רציונלי ותמדדו אותם בנקודות זמן רציונליות, והם אף פעם לא יחזרו לאותו מקום.

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

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

ובכן, כאן יש לנו נתון שאפשר להיעזר בו – העובדה ש-\(b_{n}=a_{n}+n\) (זוכרים? זה היה אחד מהקריטריונים שהכתיבו את אופן בניית הסדרה). כלומר, \(\left\lfloor nb\right\rfloor =\left\lfloor na\right\rfloor +n\) לכל \(n\). כדי שזה יקרה, צריך שיתקיים \(b=a+1\) (הוכיחו את זה לעצמכם!). נוסיף לכך את העובדה ש-\(b=\frac{a}{a-1}\) ונקבל \(a=\left(a+1\right)\left(a-1\right)\). פתיחת סוגריים והעברת אגפים תיתן לנו \(a^{2}-a-1=0\), והפתרונות למשוואה הזו הם \(\frac{1\pm\sqrt{5}}{2}\), כשאנחנו רוצים מראש את הפתרון החיובי מבין השניים. כלומר, \(a=\frac{1+\sqrt{5}}{2}\). את המספר הזה אתם מכירים כנראה יותר בסימון \(\phi\) ובשם "יחס הזהב"; הרי לכם מקום נחמד שבו הוא צץ מעצמו. מכיוון שיחס הזהב מקיים \(\phi^{2}=\phi+1\) הרי ש-\(b\) מיודענו הוא \(\phi^{2}\) במקרה זה. במילים אחרות, סדרות הביטי של \(\phi,\phi^{2}\) הן בדיוק מה שנותן את מצבי ההפסד במשחק המלכה. יש אמנם הכללות ודברים נוספים שאפשר לומר בעניין אבל זה נראה לי כמו מקום טוב לעצור בו.

מטריצות הפיכות, ומה שלדטרמיננטות יש לומר בעניין

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

בפוסט הקודם הצגתי את מושג הדטרמיננטה של מטריצה ריבועית \(A\), שסימנתי כ-\(\left|A\right|\). נתתי שלוש הגדרות שונות (אקסיומטית – הפונקציונל מולטי-לינארי על שורות \(A\) היחיד שהוא גם מתחלף ומחזיר 1 על מטריצת היחידה), ישירה (\(\left|A\right|=\sum_{\sigma}\mbox{sgn}\left(\sigma\right)\prod_{i=1}^{n}A_{i\sigma\left(i\right)}\)) ורקורסיבית, וכעת נותרה לי רק תכונה מרכזית אחת של הדטרמיננטה לתאר – היא כפלית, כלומר \(\left|AB\right|=\left|A\right|\left|B\right|\), כאשר \(A,B\) מטריצות ריבועיות מאותו סדר (יש גם נוסחה בשם "נוסחת קושי-בינה" שלא אציג שמכלילה את הנוסחה הזו למקרה שבו \(A,B\) אינן ריבועיות אך מכפלתן ריבועית). תכף אוכיח את התכונה אבל קודם כל בואו נשים לב למשהו מיידי שעולה ממנה.

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

על פניו נראה שההוכחה צריכה להיות טכנית להחריד, אבל התכונות היפות של הדטרמיננטה חוסכות לנו את רוב כאב הראש. אחת האבחנות שלנו בפוסט הקודם הייתה שכל פונקציה \(f\) שהיא מולטי-לינארית ומתחלפת (עם \(n\) משתנים שהם וקטורים ב-\(\mathbb{F}^{n}\)) נקבעת באופן יחיד על פי ערכה על וקטורי הבסיס הסטנדרטי, כלומר \(f\left(e_{1},\dots,e_{n}\right)\). קצר יותר קונקרטית, ראינו (אם כי לא הצגתי זאת כך) ש-\(f\left(v_{1},\dots,v_{n}\right)=\chi\left(v_{1},\dots,v_{n}\right)f\left(e_{1},\dots,e_{n}\right)\) כאשר \(\chi\left(v_{1},\dots,v_{n}\right)\) הוא איזה סקלר שמחושב מתוך \(v_{1},\dots,v_{n}\) באופן שאינו תלוי ב-\(f\) אלא רק באופן שבו \(v_{1},\dots,v_{n}\) מוצגים כצירופים לינאריים של אברי הבסיס הסטנדרטי. כעת, זכרו שהגדרנו דטרמיננטה בתור הפונקציה המולטי-לינארית המתחלפת שמחזירה 1 על וקטורי הבסיס הסטנדרטי, ולכן (אם מציבים \(f=\det\) בנוסחה שכתבתי לפני רגע) \(\det\left(v_{1},\dots,v_{n}\right)=\chi\). במילים אחרות, לכל פונקציה מולטי-לינארית מתחלפת \(f\), אנו רואים ש-\(f=f\left(e_{1},\dots,e_{n}\right)\cdot\det\). זה אומר ש-\(\det\) פורשת את מרחב הפונקציות המולטי-לינאריות המתחלפות, ומקל עלינו מאוד את הצעד הבא.

התעלול כעת הוא כדלהלן: אנו רוצים להוכיח כי \(\det AB=\det A\det B\). בואו נקבע את \(B\) ונגדיר פונקציונל מולטי-לינארי מתחלף \(f\left(v_{1},\dots,v_{n}\right)=\det\left(v_{1}B,\dots,v_{n}B\right)\) (\(v_{i}B\) מוגדר באמצעות כפל מטריצות רגיל – מכיוון שזה כפל של וקטור \(1\times n\) במטריצה \(n\times n\) התוצאה היא שוב וקטור \(1\times n\)). לא קשה לראות ש-\(f\) הזה הוא באמת מולטי-לינארי מתחלף – זה נובע מתכונות \(\det\) ומכך שכפל מטריצות הוא דיסטריביוטיבי. כעת, ראינו שכל פונקציונל מולטי-לינארי מתחלף הוא כפולה בסקלר של \(\det\), כלומר \(f\left(v_{1},\dots,v_{n}\right)=\det\left(v_{1},\dots,v_{n}\right)\cdot f\left(e_{1},\dots,e_{n}\right)=\det\left(v_{1},\dots,v_{n}\right)\det\left(e_{1}B,\dots,e_{n}B\right)\). כעת, מהו \(e_{i}B\)? לא קשה לראות מההגדרה שזוהי השורה ה-\(i\) של \(B\), ומכאן ש-\(\det\left(e_{1}B,\dots,e_{n}B\right)=\left|B\right|\). כל מה שנשאר לעשות הוא להציב ב-\(v_{1},\dots,v_{n}\) את שורות \(A\) ולשים לב לכך ש-\(v_{i}B\) הוא "השורה ה-\(i\) במטריצה \(AB\)", וקיבלנו ש-\(\det AB=\det A\det B\).

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

הנימוק הוא פשוט ואלגנטי להפתיע. אנחנו יודעים שצורה מדורגת מצומצמת של מטריצה ריבועית יכולה להיות בדיוק אחד משניים: או מטריצת היחידה (1 על האלכסון הראשי ו-0 בכל מקום אחר) או מטריצה שכוללת שורות אפסים; זה נובע ישירות מההגדרה של מטריצה מצומצמת. אם אפשר לקבל מ-\(A\) את מטריצת היחידה לאחר דירוג, זה אומר ש-\(EA=I\) עבור \(E\) כלשהי, ועל ידי כפל ב-\(E^{-1}\) רואים ש-\(A=E^{-1}\), מה שאומר ש-\(A\) הפיכה וההופכית שלה היא \(E\) (נקודה עדינה – אנו משתמשים כאן בכך שידוע ש-\(E\) הפיכה; המשוואה \(EA=I\) לבדה לא מוכיחה ש-\(A\) הפיכה כי למטריצות עשוי להיות "הופכי חד צדדי", כלומר בתיאוריה היה עשוי להתקיים ש-\(AE\ne I\) ואז \(A\) לא הייתה הפיכה).

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

מטריצה צמודה מכלילה במובן מסויים את המושג של מטריצה הופכית גם עבור מטריצות שאינן הפיכות. איזה מובן? אם \(A\) היא מטריצה, אסמן את הצמודה שלה כ-\(\mbox{adj}A\). המשפט שאוכיח עכשיו ("כלל קרמר") הוא ש-\(A\cdot\mbox{adj}A=\mbox{adj}A\cdot A=\left|A\right|I\). כלומר, אם \(A\) הפיכה אז \(A^{-1}=\frac{\mbox{adj}A}{\left|A\right|}\), ואם \(A\) לא הפיכה אז \(\mbox{adj}A\) מאפסת אותה.

משזה נאמר, ההגדרה של \(\mbox{adj}A\) היא לא הדבר הכי נעים בעולם ולא ברור כל כך איך הגיעו אליה (כנראה באמצעות הרבה חשיבה או הנדסה-לאחור של המשפט שאוכיח תכף). הכניסה ה-\(i,j\) של \(\mbox{adj}A\) שווה ל-\(\left(-1\right)^{i+j}\) כפול המינור ה-\(j,i\)-י של \(A\): \(\left[\mbox{adj}A\right]_{ij}=\left(-1\right)^{i+j}\left|A^{ji}\right|\). כזכור, המינור ה-\(j,i\)-י הוא מה שמקבלים מ-\(A\) כאשר מסירים את השורה ה-\(j\) ואת העמודה ה-\(i\) ולוקחים את הדטרמיננטה של היתר. שימו לב להיפוך שיש כאן – הכניסה בשורה ה-\(i\) והעמודה ה-\(j\) של הצמודה נקבעות על פי המינור של השורה ה-\(j\) והעמודה ה-\(i\).

טוב. אז איך נראה ש-\(A\cdot\mbox{adj}A=\left|A\right|I\)? בדם ואש, כמובן. אנחנו רוצים להראות ש-\(\left[A\cdot\mbox{adj}A\right]_{ij}=\left|A\right|\delta_{ij}\) (הדלתא של קרונקר – אפס או אחד, בהתאם לשאלה אם \(i\ne j\) או \(i=j\)). על פי ההגדרה, אנו יודעים ש:

\(\left[A\cdot\mbox{adj}A\right]_{ij}=\sum_{k=1}^{n}A_{ik}\left[\mbox{adj}A\right]_{kj}=\sum_{k=1}^{n}A_{ik}\left(-1\right)^{k+j}\left|A^{jk}\right|\)

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

\(0=\left|B\right|=\sum_{k=1}^{n}\left(-1\right)^{j+k}B_{jk}\left|B^{jk}\right|\)

רק מה, אם אנו מסירים מ-\(B\) את השורה ה-\(j\), אנו מקבלים מטריצה שזהה ל-\(A\), כלומר \(\left|B^{jk}\right|=\left|A^{jk}\right|\); ובגלל שהשורה ה-\(j\) של \(B\) היא בדיוק השורה ה-\(i\) של \(A\), הרי ש-\(B_{jk}=A_{ik}\). במילים אחרות -

\(0=\sum_{k=1}^{n}\left(-1\right)^{j+k}B_{jk}\left|B^{jk}\right|=\sum_{k=1}^{n}\left(-1\right)^{j+k}A_{ik}\left|A^{jk}\right|=\left[A\cdot\mbox{adj}A\right]_{ij}\)

וזה מסיים את ההוכחה הזו (עדיין צריך להוכיח ש-\(\mbox{adj}A\cdot A=\left|A\right|I\) – הרעיון זהה).

על פניו, עושה רושם שנוסחת קרמר נותנת לנו דרך מצויינת לחשב את ההופכי של מטריצה. אבל בפועל זו דרך גרועה למדי כי חישוב של כל כניסה של \(\mbox{adj}A\) הוא תובעני – צריך לחשב דטרמיננטה. הדרך ה"נכונה" למצוא הופכי של מטריצה \(A\) הוא פשוט לדרג אותה: אם \(EA=I\) אז \(E\) היא בדיוק ההופכית המבוקשת. כשרוצים לחשב דבר כזה בפועל באופן ידני, מה שבדרך כלל עושים הוא לדרג את \(A\) ובו זמנית את אותן פעולות שמבצעים בדירוג של \(A\), לבצע על מטריצת היחידה \(I\) (כלומר – מתחילים כש-\(A\) ו-\(I\) כתובות האחת מעל השניה, ומתחילים לדרג את \(A\) שלמעלה כשכל פעולה שמבצעים מבוצעת גם על המטריצה שלמטה). עם זאת, עדיין יש יתרונות לשימוש ב-\(\mbox{adj}\) אם רוצים למצוא רק כניסה אחת מתוך המטריצה ההופכית (לפעמים זה כל מה שצריך) ובהקשרים תיאורטיים שונים ומשונים.

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

דטרמיננטות

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ומכל זה נקבל:

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

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

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

קצר: הזמנה לתערוכה

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

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

החל מהשבוע הבא תוצג בבית התפוצות תערוכה בשם "Transcending Tradition: Jewish Mathematicians in German-Speaking Academic Culture" שנושאה הוא בדיוק התרבות היהודית-מתמטית המפוארת של גרמניה בטרם בוא הנאצים, וחורבנה. ניתן לראות כאן את אתר התערוכה. התערוכה גם מלווה בכנס מתמטי שיתקיים ב-14-15 לנובמבר ועוסק בעבודתם של מתמטיקאים יהודים-גרמנים מאותה התקופה; איני יודע מה תהיה רמתן הטכנית של ההרצאות ואני ממליץ למי ששוקל לבוא לקרוא את תיאורן ולראות אם זה נשמע לו מעניין. אני עצמי מתכנן לבקר הן בתערוכה והן בכנס. אם אבין משהו, אולי גם צפויים פוסטים בנושא; לעת עתה אמשיך עם סדרת הפוסטים על אלגברה לינארית.

פונקציונלים לינאריים והדואלי של הדואלי של הדואלי של הדואלי

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

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

ובכן, נסתכל על \(\mathbb{R}\left[x\right]\) – מרחב הפולינומים עם מקדמים ב-\(x\). דוגמה לפונקציונל לינארי על המרחב הזה הוא הצבה: \(T_{a}\left(p\left(x\right)\right)=p\left(a\right)\), כאשר \(a\in\mathbb{R}\) כלשהו. לא קשה להוכיח שזו פעולה לינארית (כלומר, \(T_{a}\left(\alpha p\left(x\right)+\beta q\left(x\right)\right)=\alpha p\left(a\right)+\beta q\left(a\right)\) כאשר \(\alpha,\beta\in\mathbb{R}\)), והיא אכן מעבירה כל איבר של \(\mathbb{R}\left[x\right]\) לאיבר של \(\mathbb{R}\). מה שמעניין כאן הוא האופן שבו הטרנספורמציה הזו משתמשת ב"מידע נוסף" שיש ב-\(\mathbb{R}\left[x\right]\) ולא בא לידי ביטוי במבנה שלו כמרחב וקטורי – העובדה שאפשר להציב ערכים ב-\(x\).

עוד דוגמה דומה מאוד היא אינטגרל מסויים. אינטגרלים מסויימים מוגדרים עבור המון פונקציות, אבל לשם פשטות נוח להתמקד במרחב פונקציות שמובטח שקיים להן אינטגרל מסויים ושהן יהוו מרחב וקטורי – פונקציות רציפות על קטע סגור. נסמן ב-\(C\left(\left[a,b\right]\right)\) את מרחב כל הפונקציות \(f:\left[a,b\right]\to\mathbb{R}\) שהן רציפות (זו משמעות ה-\(C\), מהמילה Continuous). כעת אפשר להגדיר פונקציונל לינארי עליהן: \(L\left(f\right)=\int_{a}^{b}f\left(x\right)dx\). הסיבה לכך שזהו פונקציונל לינארי דורשת הצדקה כלשהי; העובדה שמתקיים \(\int_{a}^{b}\left[\alpha f\left(x\right)+\beta g\left(x\right)\right]dx=\alpha\int_{a}^{b}f\left(x\right)dx+\beta\int_{a}^{b}g\left(x\right)dx\) נקראת לינאריות האינטגרל המסויים ויש להוכיח אותה.

עוד דוגמה מפורסמת למדי היא עקבה (Trace) של מטריצות. אם \(A\) היא מטריצה ריבועית \(n\times n\), אז \(\mbox{tr}A=\sum_{i=1}^{n}a_{ii}\), כלומר העקבה של \(A\) היא סכום האיברים שעל האלכסון שלה. לא קשה לראות כי \(\mbox{tr}\left(\alpha A+\beta B\right)=\alpha\mbox{tr}A+\beta\mbox{tr}B\) ולכן שוב יש לנו פונקציונל, הפעם מהמרחב \(M_{n}\left(\mathbb{F}\right)\) (מרחב המטריצות מסדר \(n\times n\) מעל השדה \(\mathbb{F}\)) אל \(\mathbb{F}\). בקיצור, פונקציונלים הם משהו שמקובע היטב במציאות המתמטית היומיומית.

בפוסטים קודמים כבר רמזתי, אם לא אמרתי במפורש, שאוסף כל הטרנספורמציות הלינאריות בין שני מרחבים נתונים הוא בעצמו מרחב וקטורי. זה מובלע בכך שהאוסף הזה איזומורפי למטריצות, שהן מרחב וקטורי, אבל כדאי לציין זאת במפורש: אם \(V,W\) הם שני מרחבים וקטוריים, אז קבוצת כל הטרנספורמציות הלינאריות \(T:V\to W\), שמסומנת לעתים כ-\(\mbox{Hom}\left(V,W\right)\), היא עצמה מרחב וקטורי, עם פעולות החיבור והכפל בסקלר ה"טבעיות" (כלומר, הטרנספורמציה \(T+S\) מוגדרת על ידי \(\left(T+S\right)\left(v\right)=T\left(v\right)+S\left(v\right)\) ו-\(\left(\lambda T\right)\left(v\right)=\lambda T\left(v\right)\)). יתר על כן, אם \(V,W\) הם ממימד סופי אז \(\mbox{\ensuremath{\dim}\ensuremath{\mbox{Hom}\ensuremath{\left(V,W\right)}=\ensuremath{\dim}V\ensuremath{\cdot\dim}W}}\) – לא מפתיע כל כך מכיוון שהמטריצות שמייצגות טרנספורמציה מ-\(V\) אל \(W\) הן מטריצות מסדר \(\dim W\times\dim V\), ומרחב המטריצות מסדר \(n\times m\) הוא ממימד \(nm\) (חשבו על בסיס עבורו).

כדי לחסוך בסימונים, במקום לכתוב \(\mbox{Hom}\left(V,\mathbb{F}\right)\) כדי לתאר את מרחב הפונקציונלים הלינאריים על \(V\), פשוט נסמן אותו כ-\(V^{*}\). כעת, מכיוון ש-\(\mathbb{F}\) הוא מרחב וקטורי ממימד 1 מעל עצמו, אז \(\dim V^{*}=\dim V\), ולכן \(V\) ו-\(V^{*}\) איזומורפיים כמרחבים וקטוריים (כזכור, כל שני מרחבים וקטוריים סוף ממדיים מאותו מימד הם איזומורפיים). מה שמעניין כאן הוא שאני רואה ששני המרחבים איזומורפיים, אבל לא הצגתי שום איזומורפיזם מפורש עבורם; האם ניתן לעשות זאת?

ובכן, נקבע בסיס \(B=\left\{ b_{1},\dots,b_{n}\right\} \) ל-\(V\). כעת, לכל \(b_{i}\), נגדיר פונקציונל \(f_{b_{i}}\) באופן הבא: \(f_{b_{i}}\left(b_{j}\right)=\delta_{ij}\) כאשר \(\delta_{ij}\) היא הדלתא של קרונקר: אם \(i\ne j\) אז \(\delta_{ij}=0\) ואם \(i=j\) אז \(\delta_{ij}=1\). זה בסך הכל סימון, אבל כזה שהוא נוח למדי לעתים קרובות.

הגדרתי את הפעולה של \(f_{b_{i}}\) רק על אברי \(B\), אבל כבר ראינו שדי בכך כדי להגדיר את פעולת \(f_{b_{i}}\) על כל אברי המרחב; הטענה שלי היא שקבוצת הפונקציונלים \(B^{*}=\left\{ f_{b_{1}},\dots,f_{b_{n}}\right\} \) היא בסיס של \(V^{*}\), ומכיוון שהיא מגודל \(n\) רק צריך להראות שהיא בלתי תלויה לינארית. כלומר, נניח ש-\(\sum\lambda_{i}f_{b_{i}}=0\) – איבר האפס כאן הוא "פונקציונל האפס", הפונקציונל שמחזיר 0 לכל קלט. כעת, נפעיל את \(\sum\lambda_{i}f_{b_{i}}\) על \(b_{j}\) ונקבל \(0=\sum\lambda_{i}f_{b_{i}}\left(b_{j}\right)=\sum\lambda_{i}\delta_{ij}=\lambda_{j}\) וכך קיבלנו ש-\(\lambda_{j}=0\) לכל \(j\), כלומר הפונקציונלים אכן בלתי תלויים לינארית, והקבוצה \(B^{*}\) היא אכן בסיס למרחב \(V^{*}\). הדמיון הרב בין \(V\) ל-\(V^{*}\) גורם לנו לקרוא ל-\(V^{*}\) המרחב הדואלי ל-\(V\); ו-\(B^{*}\) הוא באופן בלתי מפתיע הבסיס הדואלי ל-\(B\).

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

ובכן, יהא \(v\in V\) איבר כלשהו של \(V\). בואו נגדיר פונקציונל לינארי \(L_{v}:V^{*}\to\mathbb{F}\) באופן הבא: \(L_{v}\left(f\right)=f\left(v\right)\). כלומר, \(L_{v}\) הוא בסך הכל יצור מאוד דומה לפונקציונל ה"הצבה בפולינום" שראינו בתחילת הפוסט, רק שהפעם הוא מקבל כקלט פונקציונל \(f\) ולא פולינום \(p\), אבל הפעולה שלו זהה – הוא מציב בפונקציונל את הערך \(v\) שהוא "hard coded" בתוך הגדרת \(L_{v}\) ומחזיר את התוצאה. כעת צריך לבדוק שזה באמת פונקציונל לינארי, כלומר לשים לב לכך ש:

\(L_{v}\left(\alpha f+\beta g\right)=\left(\alpha f+\beta g\right)\left(v\right)=\alpha f\left(v\right)+\beta g\left(v\right)=\alpha L_{v}\left(f\right)+\beta L_{v}\left(g\right)\)

זה נובע ממש מההגדרות, אז אין לנו בעיה. אבל מדוע מה שתיארנו כאן הוא איזומורפיזם בין \(V\) ובין \(V^{**}\)? ובכן, בגלל ש-

\(L_{\alpha v+\beta u}\left(f\right)=f\left(\alpha v+\beta u\right)=\alpha f\left(v\right)+\beta f\left(u\right)=\alpha L_{v}\left(f\right)+\beta L_{u}\left(f\right)\)

מכיוון שזה נכון לכל \(f\in V^{*}\) אפשר פשוט לכתוב \(L_{\alpha v+\beta u}=\alpha L_{v}+\beta L_{u}\), מה שאומר שהטרנספורמציה \(T\left(v\right)=L_{v}\) היא טרנספורמציה לינארית \(T:V\to V^{**}\). במילים: זו טרנספורמציה שלוקחת וקטור של \(V\) ומחזירה פונקציונל שמקבל כקלט פונקציונל של \(V\). יש לנו כאן שלוש רמות שונות של טרנספורמציה לינארית, ועוד היד נטויה.

כעת, מכיוון ש-\(\dim V^{**}=\dim V^{*}=\dim V\), כדי להשתכנע ש-\(T\) היא איזומורפיזם מספיק להראות שהיא חח"ע, כלומר ש-\(\dim\ker T=0\) (כי אז ינבע ש-\(\dim\mbox{Im}T=\dim V-\dim\ker T=\dim V\) ולכן \(\mbox{Im}T=V^{**}\)). במילים אחרות, צריך להראות ש-\(L_{v}\) הוא פונקציונל האפס רק אם \(v=0\). כעת, אם \(L_{v}\) הוא פונקציונל האפס זה אומר ש-\(f\left(v\right)=0\) לכל פונקציונל \(f:V\to\mathbb{F}\). אבל אם \(L_{v}\) איננו פונקציונל האפס ברור שקיימים פונקציונלים שלא מתאפסים עליו; תשלימו את הקבוצה \(\left\{ v\right\} \) לבסיס של \(V\) ואז תסתכלו על אברי הבסיס הדואלי, יהיה שם פונקציונל שלא מתאפס על \(v\)…

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

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

ראשית, שימו לב שאפשר לחשוב על פונקציונל באופן כללי בתור פולינום לינארי במספר משתנים. למה הכוונה? קחו בסיס \(B=\left\{ b_{1},\dots,b_{n}\right\} \) ל-\(V\) ופונקציונל \(f\), ובואו נסמן \(a_{i}=f\left(b_{i}\right)\). כעת, איך \(f\) פועלת על וקטור \(v\) שוקטור הקואורדינטות שלו על פי \(B\) הוא \(\left[\lambda_{1},\dots,\lambda_{n}\right]\) (כלומר, \(v=\sum\lambda_{i}b_{i}\))? פשוט מאוד:

\(f\left(v\right)=f\left(\sum\lambda_{i}v_{i}\right)=\sum\lambda_{i}f\left(b_{i}\right)=\sum a_{i}\lambda_{i}\)

זה אומר שאפשר לחשוב על \(f\) בתור הפולינום \(p\left(x_{1},\dots,x_{n}\right)=a_{1}x_{1}+\dots+a_{n}x_{n}\), והצבה של \(v\) ב-\(f\) היא כמו הצבה של וקטור הקואורדינטות של \(v\) (על פי \(B\)) בתוך ה-\(x\)-ים של \(p\).

כעת, כל פונקציונל לינארי \(f\in V^{*}\) שאיננו פונקציונל האפס בהכרח חייב לקיים \(\mbox{Im}f=1\), כי המימד של המרחב שאליו \(f\) הולך הוא 1. לכן \(\dim\ker f=\dim V-\dim\mbox{Im}f=n-1\) – הגרעין של \(f\), אוסף כל הוקטורים ש-\(f\) מעביר לאפס, הוא ממימד קטן ב-1 מהמימד של \(V\) עצמו. לתת-מרחב לינארי כזה, שהמימד שלו קטן ב-1 מהמימד של המרחב כולו, קוראים על-מישור (hyperplane). השם "על-מישור" מגיע מהמקרה של \(V=\mathbb{R}^{3}\); במקרה זה העל-מישורים של המרחב הם מישורים במובן הרגיל ביותר של המילה; ולכן באופן מוכלל קוראים ליצורים כאלו "על-מישורים". אני חושב שהדוגמה הכי קלה היא דווקא עבור \(V=\mathbb{R}^{2}\) – במקרה זה העל-מישורים הם פשוט ישרים (ספציפית, ישרים שעוברים דרך הראשית).

הנה דרך נוספת לחשוב על כך: פולינום בשני משתנים \(p\left(x,y\right)=ax+by\) מגדיר לנו די בבירור קו ישר באמצעות המשוואה \(ax+by=0\) – דיברתי כבר על כך בפוסטים קודמים ועל איך שזו "הצורה הכללית" של כל הישרים שעוברים דרך הראשית. כל הדיון למעלה הוא פשוט הכללה של זה.

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

נניח ש-\(V\) הוא מרחב וקטורי סוף ממדי, ו-\(W\) תת-מרחב שלו. אז נסמן ב-\(W^{0}\) את אוסף כל הפונקציונלים הלינאריים ב-\(V^{*}\) שמתאפסים על כל איבר ב-\(W\). זה אוסף לא ריק, כי פונקציונל האפס תמיד שם; לא קשה לראות ש-\(W^{0}\) הוא תת מרחב של ממש (כי אם נחבר שני פונקציונלים שמתאפסים על כל אברי \(W\), גם התוצאה תתאפס על כל אברי \(W\) וכך גם עם כפל בסקלר). כעת נובעת התוצאה הלא ממש מפתיעה הבאה:

\(\dim W+\dim W^{0}=\dim V\)

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

התוצאה הזו לא מפתיעה כי היא נראית בדיוק כמו \(\dim\ker T+\dim\mbox{Im}T=\dim V\), וההוכחה היא דומה מאוד להוכחה של המשפט ההוא: ניקח בסיס עבור \(W\) ונשלים אותו לבסיס של \(V\) – \(B=\left\{ b_{1},\dots,b_{m},b_{m+1},\dots,b_{n}\right\} \), כאשר \(m=\dim W\) ו-\(m\) הוקטורים הראשונים הם הבסיס של \(W\). כעת בואו נסתכל על הבסיס הדואלי \(B^{*}=\left\{ f_{1},\dots,f_{n}\right\} \) ונטען ש-\(\left\{ f_{m+1},\dots,f_{n}\right\} \) הם בדיוק בסיס ל-\(W^{0}\), מה שיוכיח שהמימד של \(W^{0}\) הוא בדיוק \(n-m=\dim V-\dim W\).

ובכן, זה שכל \(f_{i}\) כזו עם \(m<i\le n\) מאפסת כל איבר של \(W\) זה ברור – \(f_{i}\left(b_{j}\right)=0\) לכל \(1\le j\le m\) ולכן \(f_{i}\) מאפסת כל איבר שניתן לכתוב כצירופים לינאריים רק של \(b_{1},\dots,b_{m}\). זה אומר ש-\(\mbox{span}\left\{ f_{m+1},\dots,f_{n}\right\} \subseteq W^{0}\), אבל מה עם הכיוון השני? ובכן, אם \(g\in W^{0}\) הוא פונקציונל שמאפס את כל אברי \(W\), נכתוב אותו כצירוף לינארי של אברי הבסיס – \(g=\sum\lambda_{j}f_{j}\), וכעת נציב בו לפי התור את \(b_{i}\) עבור \(1\le i\le m\) – אברי הבסיס של \(W\) שהם כמובן גם איברים של \(W\) ולכן \(g\left(b_{i}\right)=0\) לכל אחד מהם. נקבל \(0=g\left(b_{i}\right)=\sum\lambda_{j}f_{j}\left(b_{i}\right)=\sum\lambda_{j}\delta_{ij}=\lambda_{i}\) והנה – קיבלנו שבצירוף הלינארי שמרכיב את \(g\), כל המקדמים \(\lambda_{i}\) עבור \(1\le i\le m\) הם בהכרח אפס, ולכן הוקטורים שפורשים את כל ה-\(g\)-ים הללו הם \(\left\{ f_{m+1},\dots,f_{n}\right\} \). זה מסיים את ההוכחה.

בואו נסכם לרגע. ראינו שלכל תת מרחב \(W\) של \(V\) קיים תת-מרחב \(W^{0}\) של \(V^{*}\) של "הפונקציונלים שמתאפסים על \(W\)" וגם הבנו מה המימד שלו. זה כיוון אחד – מה עם הכיוון השני? האם כל תת-מרחב \(U\) של \(V^{*}\) מגדיר תת מרחב של \(V\), של "כל אברי \(V\) שמאפסים את כל הפונקציונלים ב-\(U\)"? התשובה חיובית, אבל אין צורך לעבוד שוב כדי לראות זאת; אולי כבר הבנתם שאנחנו פשוט יכולים להשתמש בתוצאה שכבר ראינו ובדואליות של \(V\) ו-\(V^{*}\). הבה ונניח שיש לנו תת-מרחב \(U\) של \(V^{*}\); אז ממה שכבר ראינו, קיים תת-מרחב \(U^{0}\) של \(V^{**}\) של כל האיברים של \(V^{**}\) שמאפסים את כל אברי \(U\). אבל מה זה \(V^{**}\)? ראינו שכל איבר בו הוא פונקציונל \(L_{v}\) עבור \(v\in V\), כך ש \(L_{v}\left(f\right)=f\left(v\right)\); אם כן, מה זה אומר שפונקציונל \(L_{v}\) מאפס את כל \(U\)? זה אומר שלכל \(f\in U\) מתקיים \(L_{v}\left(f\right)=0\), כלומר \(f\left(v\right)=0\), כלומר \(v\) הוא וקטור של \(V\) שמאופס על ידי כל אברי \(U\). מכאן שאפשר לחשוב על \(U^{0}\) בתור תת-מרחב של \(V\) (לפדנטיים – לא הוא, אלא העותק האיזומורפי שלו ב-\(V\) על ידי האיזומורפיזם הקנוני של \(V\) עם \(V^{**}\)) ויתקיים \(\dim U+\dim U^{0}=\dim V^{*}\).

שימו לב כמה זה נחמד: מצד אחד יש לנו תת-קבוצות של המרחב (למשל, מישורים וישרים ב-\(\mathbb{R}^{3}\)), מצד שני יש לנו קבוצות של פונקציונלים לינאריים (או בניסוח אחר, פולינומים לינאריים במספר משתנים) ואנחנו רואים שהקבוצות הללו הן אותו הדבר במובן מאוד חזק ואפשר לקבל מכל אחת את השניה.

הרעיונות הללו הם בדיוק מה שעומד בבסיס הגאומטריה האלגברית; השאלה הראשונה שנשאלת כאשר מתחילים ללמוד גאומטריה אלגברית היא איך נראית הדואליות הזו כאשר רוצים לתאר מרחבים קצת יותר מחוכמים, ולשם כך מדברים על פולינומים במספר משתנים ממעלה כלשהי, לא רק פולינומים לינאריים. כך למשל המשטח שהוא פני עיגול (ספרה) ברדיוס \(R\) ניתן לתיאור כאוסף האפסים של הפולינום \(p\left(x,y,z\right)=x^{2}+y^{2}+z^{2}-R^{2}\) שהוא פולינום ממעלה שניה; וכשמתירים מעלה כלשהי, יכולת התיאור גדלה פלאים. הקבוצות שניתנות לתיאור באופן הזה נקראות יריעות אלגבריות, והאבחנה הבסיסית היא שמתקיימת דואליות דומה מאוד לזו שהצגתי לעיל בין יריעות אלגבריות ובין אוספים של פולינומים. עם זאת, הסיטואציה מורכבת משמעותית יותר מזו שראינו למעלה וכדי לתת ניסוחים מדוייקים למה שהולך שם צריך להשתמש במושגים מתמטיים שהאלגברה הלינארית לא נכנסת אליהם (אידאלים, חוגי מנה, טופולוגיה…) ולכן הפוסטים בנושא ייאלצו להמתין.