לא מדויק

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

25 בינואר, 2012

"כיבוי אורות", או 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$ , זה אומר שהוא מחובר למספר זוגי של צמתים שאינם ב- $S$ כולל הצומת החדש $u$ . זה שאומר ש- $v$ מחובר למספר אי זוגי של צמתים שאינם ב- $S$ ואינם $u$ . כעת מגיע טיעון המחץ: את $u$ חיברנו רק לצמתים שהיו מדרגה זוגית מלכתחילה, ולכן אם $v$ מחובר למספר אי זוגי של צמתים שאינם מ- $S$ ודרגתו לפני הוספת $u$ לגרף הייתה זוגית, הוא חייב להיות מחובר למספר אי זוגי של צמתים מ- $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$ וההוכחה נסתיימה. אולי היא נראית קצת מסורבלת ומוזרה כעת, אבל למי שבקיא במושגים היא לא דורשת יותר משורה-שתיים.

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

תגים: Lights out, מטריצה מייצגת של גרף, אלגברה לינארית, פתרון מתמטי של משחק, תורת הגרפים
שייך לקטגוריות משחקים וחידות מתמטיות, אלגברה לינארית, תורת הגרפים | 5 תגובות »

משפט קנטור-שרדר-ברנשטיין

21 בינואר, 2012

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

ראשית, רקע קצר (אם כי הפוסט הזה כן מיועד רק למי שכבר מכירים את הרקע): הכלי המתמטי שבו אנו משתמשים כדי להשוות בין הגדלים של שתי קבוצות – סופיות או אינסופיות, הוא פונקציות חד-חד-ערכיות ועל. $f:A\to B$ היא חד-חד-ערכית (חח"ע) אם $f\left(x\right)=f\left(y\right)$ גורר ש- $x=y$ ("שני איברים שונים של $A$ לא מועברים לאותו איבר ב- $B$ ") ו- $f:A\to B$ היא על אם לכל $b\in B$ קיים $a\in A$ כך ש- $f\left(a\right)=b$ ("כל איבר של $B$ הוא תמונה של איבר כלשהו ב- $A$ ").

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

וחוץ מזה, עבור קבוצות סופיות זה עובד.

עוד דבר שאנו מכירים בקבוצות סופיות הוא שאם $\left|A\right|\le\left|B\right|$ וגם $\left|B\right|\le\left|A\right|$ (הגודל של $A$ קטן-שווה מהגודל של $B$ , ואילו הגודל של $B$ קטן-שווה מהגודל של $A$ ) אז $\left|A\right|=\left|B\right|$ . עבור קבוצות אינסופיות, הטענה מנוסחת כך: אם יש פונקציה חח"ע $f:A\to B$ ופונקציה חח"ע $g:B\to A$ אז יש פונקציה חח"ע ועל $h:A\to B$ . זהו משפט קנטור-שרדר-ברנשטיין (קנטור העלה את ההשערה שהדבר נכון אך לא הוכיח את המשפט; ברנשטיין הוכיח אותו, ואין לי מושג מה שרדר עשה – אולי הכניסו אותו כדי שאפשר יהיה לצחוק בתורת הקבוצות על צבי הנינג'ה).

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

אנחנו רוצים לבנות את $h$ וכלי הנשק שלנו הם $f$ ו- $g$ . אולי הכי מתבקש להגדיר $h\left(a\right)=f\left(a\right)$ לכל $a\in A$ אבל זה חסר טעם לגמרי – $h$ לא תהיה בהכרח על $B$ , ולא עשינו כלום. נסיון א' כשל.

מצד שני, אפשר לעשות את ההתחכמות הבאה: $g\left(B\right)=\left\{ g\left(b\right)|b\in B\right\}$ היא תת-קבוצה של $A$ (כל האיברים ש"נתפסים" על ידי $B$ ). אם $a\in g\left(B\right)$ זה אומר שיש $b\in B$ יחיד (כי $g$ חח"ע) כך ש- $g\left(b\right)=a$ ; אפשר להגדיר אם כן פונקציה הפוכה, $g^{-1}:g\left(B\right)\to B$ כך ש- $g^{-1}\left(a\right)=b$ . הפונקציה הזו, למרבה השמחה, היא על – כל איבר של $B$ נתפס על ידה (למה?). בנוסף, היא גם חח"ע, כי אם $g^{-1}\left(a_{1}\right)=g^{-1}\left(a_{2}\right)=b$ זה אומר ש- $g\left(b\right)=a_{1}$ וגם $g\left(b\right)=a_{2}$ , כלומר $a_{1}=a_{2}$ . הרי לנו פונקציה חח"ע ועל. האם סיימנו? ודאי שלא, כי $g^{-1}$ לא הוגדרה לכל איבר של $A$ . אנחנו חייבים להגדיר את $h$ המיועדת שלנו לכל אברי $A$ .

אם כן, בואו נסמן $C_{0}=A\backslash g\left(B\right)=\left\{ a\in A|a\notin g\left(B\right)\right\}$ (ה-0 בא לרמז שעוד מעט נגדיר עוד קבוצות כאלו) . זו קבוצת כל ה"דחויים" – כל אלו שלא נבחרו על ידי איבר מ- $B$ באמצעות $g$ . מה אפשר לעשות איתם? ובכן, פשוט להפעיל עליהם את $f$ . במילים אחרות, הבה וננסה את ההגדרה הבאה:

$h\left(a\right)=\begin{cases}f\left(a\right) & a\in C_{0}\\g^{-1}\left(a\right) & a\notin C_{0}\end{cases}$

הפונקציה $h$ היא חוקית לגמרי, והיא בוודאי על $B$ בגלל שתמונת כל האיברים $a\notin C_{0}$ לבדם מכסה את $B$ , אבל כאן גם נעוצה הבעיה: היא לא חח"ע. ייתכן שיש התנגשות ו- $h$ מעבירה לאותו איבר ב- $B$ גם איבר של $C_{0}$ וגם איבר שאינו ב- $C_{0}$ . אז מה עושים? פשוט מאוד: איברים שאינם ב- $C_{0}$ ומתנגשים עם תמונה של איברים מ- $C_{0}$ – נפעיל עליהם את $f$ . החח"ע של $f$ תבטיח שהתמונה של אותם איברים לא תתנגש יותר עם כלום.

מכיוון שלהגיד "איברים שאינם ב- $C_{0}$ ומתנגשים עם תמונה של איברים מ- $C_{0}$ " זה מסורבל, הבה וניתן שם קומפקטי לקבוצה הזו: $C_{1}=g\left(f\left(C_{0}\right)\right)$ . מה עשינו פה? ראשית, הלכנו ומצאנו את כל האיברים ב- $B$ שמתקבלים באמצעות הפעלת $f$ על $C_{0}$ (זוהי $f\left(C_{0}\right)$ ); כעת חזרנו ל- $A$ ומצאנו את כל אותם איברים שהם תמונה של הפעלת $g$ על $f\left(C_{0}\right)$ (זוהי $g\left(f\left(C_{0}\right)\right)$ ).

עכשיו אפשר לנסות ולהגדיר את $h$ בצורה טובה יותר:

$h\left(a\right)=\begin{cases}f\left(a\right) & a\in C_{0}\cup C_{1}\\g^{-1}\left(a\right) & a\notin C_{0}\cup C_{1}\end{cases}$

אבל גם ההגדרה הזו נכשלת! כי שוב, מי יערוב לנו שאין איזה $a$ שאיננו ב- $C_{0}\cup C_{1}$ אבל $g^{-1}\left(a\right)$ מתנגש עם התמונה של $f$ על איזה איבר של $C_{0}\cup C_{1}$ ? למעשה, הדבר היחיד שיכול לקרות הוא התנגשות עם הפעלת $f$ על איבר של $C_{1}$ כי באלו של $C_{0}$ כבר טיפלנו (אם $a\notin C_{1}$ אז מובטח לנו ש- $g^{-1}\left(a\right)$ לא מתנגש עם תמונה של איבר מ- $C_{0}$ ) אז שוב, אפשר לנקוט באותו תעלול ולהגדיר קבוצה $C_{2}=g\left(f\left(C_{1}\right)\right)$ ולהגדיר את $h$ הפעם בהסתמך על $C_{0}\cup C_{1}\cup C_{2}$ , אבל שוב זה יכול להיכשל! ולכן…

כבר הבנתם לאן זה הולך. הגדרנו סדרה אינסופית של קבוצות, $C_{0},C_{1},C_{2},\dots$ באופן אינדוקטיבי, כך ש- $C_{n+1}=g\left(f\left(C_{n}\right)\right)$ . אם נעצור אחרי מספר סופי של קבוצות, ניכשל, אבל אחרי מספר אינסופי? ובכן, שווה לנסות את זה, לכל הפחות. נגדיר $C=\bigcup_{n=0}^{\infty}C_{n}$ , וכעת נגדיר:

$h\left(a\right)=\begin{cases}f\left(a\right) & a\in C\\g^{-1}\left(a\right) & a\in A\backslash C\end{cases}$

ברור כי $h$ מוגדרת על כל אברי $A$ , כי זה מה שקורה בהגדרה: $a\notin C$ פירושו בעצם $a\in A\backslash C$ . נותר להראות שהיא חח"ע, ושהיא על. החח"ע הוא המעניין יותר, כי כל הבניה שלנו הוקדשה כדי להבטיח ש- $h$ תהיה חח"ע. אז למה זה עובד? עצרו שניה ונסו להוכיח זאת לעצמכם. זה קל עד להפתיע.

ובכן, נניח כי קיימים $a_{1},a_{2}$ כך ש- $h\left(a_{1}\right)=h\left(a_{2}\right)$ . אם $a_{1},a_{2}\in C$ אז זה אומר ש- $f\left(a_{1}\right)=f\left(a_{2}\right)$ ולכן $a_{1}=a_{2}$ מהחח"ע של $f$ . אם $a_{1},a_{2}\notin C$ זה אומר ש- $g^{-1}\left(a_{1}\right)=g^{-1}\left(a_{2}\right)$ ומזה נובע מייד ש- $a_{1}=a_{2}$ מהנימוק שנתתי כבר קודם בפוסט. נותר לטפל במקרה בו $a_{1}\in C$ ו- $a_{2}\notin C$ (בלי הגבלת הכלליות אני מניח ש- $a_{1}$ הוא זה שנמצא ב- $C$ ).

מכיוון ש- $a_{1}\in C=\bigcup_{n=0}^{\infty}C_{n}$ , נובע שקיים $n$ כלשהו כך ש- $a_{1}\in C_{n}$ . לכן, מההגדרה, $g\left(f\left(a_{1}\right)\right)\in C_{n+1}\subseteq C$ . כעת, אנו מניחים ש- $f\left(a_{1}\right)=g^{-1}\left(a_{2}\right)$ , כלומר שהן $a_{1}$ והן $a_{2}$ הועברו על ידי $h$ לאותו איבר ב- $B$ . הבה ונפעיל את $g$ על האיבר הזה; נקבל $g\left(f\left(a_{1}\right)\right)=g\left(g^{-1}\left(a_{2}\right)\right)=a_{2}$ , והנה לנו סתירה, כי $a_{2}=g\left(f\left(a_{1}\right)\right)\in C$ , ומצד שני הנחנו ש- $a_{2}\notin C$ . אם כל מה שהבנתם מהשורה האחרונה הוא פורמליזם, לא טוב; עצרו, נסו להוכיח את החח"ע בעצמכם, ואל תוותרו – ברגע שמבינים מה הלך כאן מבינים עד הסוף את ההוכחה.

נסיים את ההוכחה על ידי כך שנראה ש- $h$ על. יהיה $b\in B$ כלשהו. האם אתם מנחשים לאן זה הולך? ובכן, נתבונן על $a=g\left(b\right)$ . אם $a\notin C$ , סיימנו; $h\left(a\right)=b$ כנדרש. אם לעומת זאת $a\in C$ זה אומר שקיים $n$ כך ש- $a\in C_{n}$ . אם $n=0$ , זה אומר ש- $a\in A\backslash g\left(B\right)$ , אבל זה בוודאי לא נכון כי ראינו ש- $a=g\left(b\right)$ ולכן $a\in g\left(B\right)$ . לכן $n>0$ . מכאן ש- $a\in g\left(f\left(C_{n-1}\right)\right)$ , כלומר קיים $b_{2}\in f\left(C_{n-1}\right)$ כך ש- $a=g\left(b_{2}\right)$ . קיבלנו ש- $g\left(b\right)=g\left(b_{2}\right)$ ומהחח"ע של $g$ נקבל ש- $b=b_{2}\in f\left(C_{n-1}\right)$ , כלומר קיים איבר כלשהו ב- $A$ שעובר ל- $b$ , ובזאת תמה ההוכחה.

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

תגים: קנטור-שרדר-ברנשטיין, תורת הקבוצות, הוכחות
שייך לקטגוריות תורת הקבוצות | 13 תגובות »

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

19 בינואר, 2012

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

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

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

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

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

תגים: PageRank, משפט פרון-פרובניוס, אלגברה לינארית, ערכים עצמיים, שרשראות מרקוב, המתמטיקה למען האנושות, הסתברות
שייך לקטגוריות אלגברה לינארית, הסתברות | 5 תגובות »

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

9 בינואר, 2012

בפעם האחרונה שבה דיברתי על אלגברה לינארית המושג הדומיננטי היה זה של תת-מרחב שמור. כזכור, $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}$ -ים הללו), אם כי אחזור אליה בהמשך; לעת עתה נעבור לדבר החל מהפוסט הבא על מושג שעליו באמת אפשר לדבר מכאן ועד אינסוף – מכפלה פנימית.

תגים: משפט הפירוק הפרימרי, אלגברה לינארית
שייך לקטגוריות אלגברה לינארית | 18 תגובות »

נוסחת ההיפוך של מביוס

7 בינואר, 2012

נוסחת ההיפוך הקלאסית

נתחיל מדוגמה. ככה יהיה הרבה יותר קל להבין מה אני רוצה. בפוסט הקודם הזכרתי את פונקציית אוילר $\varphi\left(n\right)$ שלכל מספר טבעי מחזירה את סכום המספרים הקטנים ממנו שזרים לו. בנוסף לכל מעלותיה, היא מקיימת את התכונה היפה הבאה: $\sum_{d|n}\varphi\left(d\right)=n$ . כלומר, כל מספר טבעי שווה לסכום הערכים של פונקציית אוילר כל כל מחלקיו.

לנוסחה הזו יש הוכחה קומבינטורית פשוטה שלחלוטין לא רלוונטית לפוסט אז העצלנים יכולים לדלג עליה – נספור את כל המספרים מ-1 עד $n$ (בדיוק $n$ ) בדרך קצת שונה – לכל מספר $1\le k\le n$ , נסמן ב- $N_{k}$ את מספרם של המספרים בין 1 ו- $n$ שהמחלק המשותף המקסימלי שלהם ושל $n$ הוא בדיוק $k$ , כלומר $N_{k}=\left|\left\{ 1\le a\le n|\gcd\left(a,n\right)=k\right\} \right|$ . בבירור אם $k$ לא מחלק את $n$ אז $N_{k}=0$ ; מהו $N_{k}$ אם $k|n$ ? ובכן, זהו מספרם של המספרים מהצורה $k,2k,3k,\dots,n$ שאין להם מחלק משותף גדול מ- $k$ עם $n$ , כלומר מספרים מהצורה $tk$ כך ש- $t$ זר ל- $\frac{n}{k}$ (תעצרו, תנשמו עמוק ותסבירו את זה לעצמכם – אם אתם לא מצליחים, לא נורא כי זה לא קשור ממש לפוסט). נסמן $d=\frac{n}{k}$ ונקבל ש- $N_{k}=\varphi\left(d\right)$ , ומכאן נובעת הנוסחה.

יופי, בשביל מה זה היה טוב? ובכן, זו דוגמה לסיטואציה שבה יש לנו פונקציה מסובכת $f$ שסכום שלה על פני המחלקים של $n$ יוצא משהו פשוט יותר. פורמלית, זה אומר שקיימת פונקציה $g\left(n\right)$ כך ש- $g\left(n\right)=\sum_{d|n}f\left(d\right)$ . היינו רוצים איכשהו "לחלץ" את $f$ מתוך הנוסחה הזו ולכתוב אותה כפונקציה כלשהי של $g$ הפשוטה יותר. נוסחת ההיפוך של מביוס נותנת לנו בדיוק את זה.

אפשר עכשיו פשוט להציג את הנוסחה, אבל חבל – אני רוצה לנצל את ההזדמנות כדי להכיר לכם מושג חדש, שממנו אפשר יהיה להגיע לנוסחה באופן טבעי יותר – קונבולוציית דיריכלה. קונבולוציה "רגילה" של שתי פונקציות $f,g$ שמוגדרות על הטבעיים היא פונקציה חדשה $h$ שמוגדרת כך: $h\left(n\right)=\sum_{k=0}^{n}f\left(k\right)g\left(n-k\right)$ . דוגמה קלאסית לסיטואציה מתמטית שבה קונבולוצייה רגילה צצה מאליה היא כפל של פולינומים: אם $p\left(x\right)=\sum a_{i}x^{i}$ ו- $q\left(x\right)=\sum b_{j}x^{j}$ אז כל מקדם של המכפלה שלהם הוא קונבולוציה: המקדם של $x^{n}$ ב- $p\left(x\right)q\left(x\right)$ הוא $\sum_{k=0}^{n}a_{k}b_{n-k}$ . שימו לב, שניתן לכתוב קונבולוציה גם עם חיבור ולא חיסור: $h\left(n\right)=\sum_{k+r=n}f\left(k\right)g\left(r\right)$ .

קונבולוציית דיריכלה היא דומה באופיה, רק שבמקום חיבור/חיסור משתמשים בכפל/חילוק, דהיינו אם $h\left(n\right)$ היא קונבולוציית דיריכלה של $f\left(n\right),g\left(n\right)$ אז

$h\left(n\right)=\sum_{d\cdot e=n}f\left(d\right)g\left(e\right)=\sum_{d|n}f\left(d\right)g\left(\frac{n}{d}\right)$

זה כבר טיפה מזכיר את מה שהלך למעלה.

בואו נסמן $h=f*g$ כדי לומר ש- $h$ היא קונבולוציית דיריכלה של $f,g$ . אז האלגבראיסט הפנימי שבנו מתלהב מכך שמצאנו פעולה חשבונית חדשה ודוחק בנו לחקור את התכונות שלה. למשל, $\left(f*g\right)*h=f*\left(g*h\right)$ עבור שלוש פונקציות $f,g,h$ כלשהן (שמוגדרות על טבעיים; זה תמיד ההקשר של הדיון), כך שקונבלוציית דיריכלה היא אסוציאטיבית. זה מגביר את ההתלהבות של האלגבראיסט הפנימי לשמיים כי הוא מקווה שיש לנו כאן חבורה, כלומר מבנה אלגברי שהפעולה שלו היא אסוציאטיבית, עם איבר יחידה, ועם הופכי לכל איבר. ובכן, איבר יחידה בהחלט יש: נסמן ב- $\epsilon$ את הפונקציה שמקיימת $\epsilon\left(1\right)=1$ ו- $\epsilon\left(n\right)=0$ לכל $n>1$ , אז קל מאוד לראות מההגדרה ש- $\epsilon*f=f*\epsilon=f$ .

וכעת, מה עם הופכי? ובכן, נניח שעבור $f$ קיימת $g$ כך ש- $f*g=\epsilon$ , זה אומר ש- $\sum_{d|1}f\left(d\right)g\left(\frac{n}{d}\right)=1$ , כלומר $f\left(1\right)g\left(1\right)=1$ ; אבל אם $f\left(1\right)=0$ אז אבוד לנו – המשוואה הזו לעולם לא תתקיים. לכן תנאי הכרחי לכך ש- $f$ יהיה הפיך הוא ש- $f\left(1\right)\ne0$ . מסתבר שזה גם תנאי מספיק, אבל נעזוב את החיפוש אחר הופכי במקרה הכללי כרגע ובמקום זאת נתמקד בהופכי של פונקציה פשוטה במיוחד: הפונקציה שמחזירה 1 לכל קלט, שאסמן פשוט כ- $\mathbb{I}$ . את ההופכי שלה, שתכף נוכיח את קיומו, נסמן ב- $\mu$ מסיבות היסטורית. אם כן, $\mathbb{I}*\mu=\epsilon$ . בואו נראה מה נובע מכך.

זכרו שהתחלנו את כל הסיפור מהמשוואה $g\left(n\right)=\sum_{d|n}f\left(d\right)$ . עם הטרמינולוגיה החדשה שלנו ניתן לנסח זאת בתור $g=f*\mathbb{I}$ . כעת נכפול את שני האגפים ב- $\mu$ , נשתמש באסוציאטיביות, ונקבל:

$g*\mu=f*\left(\mathbb{I}*\mu\right)=f*\epsilon=f$

במילים אחרות, $g=f*\mathbb{I}$ אם ורק אם $f=g*\mu$ , ובניסוח המקורי שלנו $g\left(n\right)=\sum_{d|n}f\left(d\right)$ אם ורק אם $f\left(n\right)=\sum_{d|n}g\left(d\right)\mu\left(\frac{n}{d}\right)$ . זוהי נוסחת ההיפוך של מביוס, והפונקציה $\mu$ נקראת, בהתאם, פונקצית מביוס. בואו נבין איך היא נראית.

ראשית, $\mu\left(1\right)=1$ בבירור על פי ההגדרה, כי צריך שיתקיים $\mu\left(1\right)\mathbb{I}\left(1\right)=1$ . שנית, לכל $n>1$ צריך שיתקיים $0=\epsilon\left(n\right)=\sum_{d|n}\mu\left(d\right)\mathbb{I}\left(\frac{n}{d}\right)=\sum_{d|n}\mu\left(d\right)$ . כלומר, אם לסכם באופן קומפקטי, פונקציית מביוס חייבת לקיים $\sum_{d|n}\mu\left(d\right)=\delta_{1n}$ . מכאן אפשר להסיק בשלבים איך $\mu$ נראית על כל מספר טבעי. נתחיל מהמספרים הקלים ביותר לטיפול בהקשר הזה (כמו שקורה לעתים קרובות ביותר בתורת המספרים) – ראשוניים, אם $d|p$ עבור $p$ ראשוני, אז $d=1$ או $d=p$ , ולכן הנוסחה שלעיל מתורגמת עבורנו ל- $0=\mu\left(1\right)+\mu\left(p\right)$ , כלומר $\mu\left(p\right)=-1$ לכל ראשוני. אפשר להמשיך ולטפל בצורה דומה במכפלות של ראשוניים, אבל אני לא מכיר דרך אלגנטית במיוחד להציג את הניתוח הזה ולכן אקפוץ למסקנה הסופית: $\mu$ היא כפלית על מספרים זרים. מה זה אומר? שאם $a,b$ הם שני מספרים ללא מחלק משותף גדול מ-1, אז $\mu\left(ab\right)=\mu\left(a\right)\mu\left(b\right)$ (באופן הולם למדי, גם $\varphi$ של אוילר היא כזו). ומה אם $a,b$ לא זרים? גם אז המצב פשוט: $\mu\left(ab\right)=0$ .

כעת אפשר להסיק נוסחה עבור $\mu$ . נניח ש- $n=p_{1}p_{2}\cdots p_{k}$ כאשר כל הראשוניים הללו שונים זה מזה, אז $\mu\left(n\right)=\prod_{i=1}^{k}\mu\left(p_{k}\right)=\left(-1\right)^{k}$ ; ואילו אם $n$ מכיל את אותו ראשוני פעמיים בפירוק שלו, $\mu\left(n\right)=0$ .

לא קשה לראות שאכן $\sum_{d|n}\mu\left(d\right)=0$ בהגדרה זו לכל $n>0$ ; אם $n=p_{1}^{t_{1}}\cdots p_{k}^{t_{k}}$ הרי שהסכום יהיה רק על מחלקים $d$ מהצורה $p_{1}^{e_{1}}\cdots p_{k}^{e_{k}}$ עם $e_{i}\in\left\{ 0,1\right\}$ (כי היתר יתאפסו), ועבור כל מכפלה כזו, $\mu\left(p_{1}^{e_{1}}\cdots p_{k}^{e_{k}}\right)$ שווה למינוס 1 בחזקת מספר ה- $e_{i}$ -ים שהם 1, ולכן $\sum_{d|n}\mu\left(d\right)=\sum_{i=0}^{k}{k \choose i}\left(-1\right)^{i}=\left(1-1\right)^{k}=0$ (המעבר האחרון הוא הבינום של ניוטון). כלומר, $\mu$ שנתתי אכן מקיימת את מה שנדרש ממנה, וזה מבטיח שהיא אכן תהיה ההופכית של $\mathbb{I}$ ושנוסחת ההיפוך של מביוס תתקיים.

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

$g\left(A\right)=\sum_{B\supseteq A}f\left(B\right)$

ואת הנוסחה הזו "הפכנו" לקבלת

$f\left(A\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}g\left(B\right)$

הדמיון כאן לנוסחת ההיפוך של מביוס אדיר. במקום $d|n$ יש לנו $B\supseteq A$ כש- $B$ על תקן $d$ ו- $A$ על תקן $n$ , ובמקום $\mu\left(d\right)$ יש לנו $\left(-1\right)^{\left|B-A\right|}$ , אבל זה כל ההבדל. המבנה הרעיוני זהה. יתר על כן, הדמיון בין חלוקה והכלה של קבוצות הוא משהו שכבר ראינו בבלוג פעם, בהקשר של תורת המספרים האלגברית; אם נגדיר את $A$ כקבוצת "כל המספרים המתחלקים על ידי $n$ " ואת $B$ כקבוצת "כל המספרים המתחלקים על ידי $d$ " אז $B\supseteq A$ שקול לאמירה $d|n$ (אבל אז לא ברור מהו $\left|B-A\right|$ שיהיה אינסופי). הדמיון הרב מאוד בין שני המקרים לא נגמר בהם; הוא נובע מכך ששניהם מקרים פרטיים של נוסחת היפוך כללית ביותר, שתקפה לכל מבנה מתמטי שמכליל את התכונות של "הכלה" או של "חלוקה" שרלוונטיות לעניינו – ולמבנה כזה קוראים קבוצה סדורה חלקית (קס"ח).

קס"חים

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

(רפלקסיביות) $a\le a$ לכל $a\in X$
(אנטי-סימטריה) $a\le b$ וגם $b\le a$ גורר $a=b$
(טרנזיטיביות) $a\le b$ וגם $b\le c$ גורר $a\le c$

צריך מייד להבהיר ש- $\le$ הוא סימון של היחס. זה לא "גדול או שווה" במשמעות הרגילה שלו. מה שכן, היחס "גדול או שווה" הוא יחס סדר חלקי, אולי אחד מהפשוטים ביותר, ומכאן הסימון. אם כן, $\mathbb{N}$ עם יחס הסדר "גדול או שווה מ-" היא דוגמה לקבוצה סדורה חלקית; אבל $\mathbb{N}$ עם יחד הסדר "מחלק את", כלומר אם $a|b$ מסמנים זאת $a\le b$ היא דוגמה מעניינת הרבה יותר. ברור שזה אכן יחס סדר חלקי כי $a|a$ לכל $a\in\mathbb{N}$ , וגם שתי התכונות האחרות נובעות די בקלות מההגדרות; אבל בניגוד ליחס הקטן-או-שווה הרגיל, עבור יחס החלוקה יש לנו איברים שאינם ניתנים להשוואה. למשל, 2 ו-3 לא מחלקים זה את זה ולכן לא מתקיים לא $2\le3$ וגם לא $3\le2$ עבור יחס סדר זה. קבוצה סדורה חלקית שבה כל שני איברים כן ניתנים להשוואה נקראת קבוצה סדורה מלאה, או סדורה לינארית.

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

אם יש לנו קבוצה $X$ כלשהי, אז אפשר להגדיר על אוסף תת-הקבוצות שלה $P\left(X\right)$ יחס סדר על ידי הכלה (כלומר, לכל $A,B\subseteq X$ מגדירים $A\le B$ אם $A\subseteq B$ ), וגם, באופן מעניין, על ידי הכלה הפוכה, כלומר $A\le B$ אם $B\supseteq A$ (אומרים שהקס"ח שסדורה על ידי הכלה הפוכה דואלית לזו שסדורה על ידי הכלה רגילה; אפשר להגדיר דואלי שבו יחס הסדר מתהפך לכל קס"ח). אם כן, המושג של יחס סדר חלקי תופס את ה"עולם" שבו מתקיימות שתי הנוסחאות שהצגתי למעלה, ועכשיו נותר רק לברר איך נראית הנוסחה הכללית ביותר. כדי לספק את הסקרנות שלכם אני אציג אותה כבר עכשיו, ואז נוכל לחשוב איך להציג אותה בצורה מעניינת, על ידי הבנה טובה יותר של קבוצות סדורות חלקית (המטרה שלנו תהיה להכליל במובן מסויים את גישת הקונבולוציה של נוסחת ההיפוך הקלאסית).

ובכן, נוסחת ההיפוך הכללית אומרת שאם $\left(X,\le\right)$ היא קבוצה סדורה חלקית עם יחס הסדר $\le$ אשר מקיימת תכונת סופיות מסויימת (כל אידאל סדר ראשי הוא סופי – זה יתבהר בהמשך) אז אם יש לנו שתי פונקציות $f,g:X\to\mathbb{C}$ אשר מקיימות $g\left(x\right)=\sum_{y\le x}f\left(y\right)$ , אז מתקיים $f\left(x\right)=\sum_{y\le x}g\left(y\right)\mu\left(y,x\right)$ , כאשר $\mu$ היא פונקצית מביוס של הקס"ח $X$ . איך בדיוק היא מוגדרת – גם את זה נבין בהמשך. לכל קס"ח יש את פונקצית המביוס שלו, וכבר ראינו שתיים: את זו של הקס"ח עם יחס החלוקה, שהייתה $\mu$ הקלאסית; ואז זו של הקס"ח עם יחס ההכלה ההפוך של קבוצות, שקיימה $\mu\left(B,A\right)=\left(-1\right)^{\left|B-A\right|}$ .

מכיוון שאני רוצה להציג את נוסחת ההיפוך ופונקצית מביוס כנובעים מרעיון עמוק יותר, מעין הכללה של קונבולוציית דיריכלה, אני צריך לתת עוד כמה הגדרות שקשורות לקס"חים. ראשית, לכל שני איברים $x,y\in X$ אפשר להגדיר את הקטע $\left[x,y\right]=\left\{ z\in X|x\le z\le y\right\}$ , כלומר כל האיברים שניתנים להשוואה עם $x,y$ ונמצאים ביניהם, כולל הם עצמם. אם אין אף איבר בין $x$ ל- $y$ , כלומר $\left[x,y\right]=\left\{ x,y\right\}$ , אומרים ש- $y$ מכסה את $x$ . על $X$ אומרים שהיא סופית מקומית אם כל קטע ב- $X$ הוא סופי (כך למשל $\mathbb{Z}$ עם יחס הסדר הרגיל היא סופית מקומית, אבל $\mathbb{Q}$ עם אותו יחס סדר בדיוק איננה).

שרשרת היא פשוט קבוצה של איברים ב- $X$ שכולם ניתנים להשוואה זה עם זה (תת-קבוצה סדורה מלאה של $X$ ), ושמה מגיע מכך שאפשר לכתוב את איבריה כ- $x_{1}\le x_{2}\le\dots\le x_{n}$ (במקרה שבו השרשרת סופית, אבל ממילא רק זה יעניין אותנו כאן). אנטי-שרשרת היא בדיוק ההפך מכך – קבוצה של איברים ב- $X$ שלא ניתן להשוות אף זוג מהם – למשל, אם ניקח את הטבעיים עם יחס החלוקה, אז כל קבוצה של ראשוניים היא אנטי-שרשרת.

אידאל סדר $I$ הוא תת-קבוצה של $X$ בעלת התכונה שאם $x\in I$ ו- $y\le x$ אז $y\in X$ (מי שמכיר קצת אלגברה מופשטת ודאי רואה את הדמיון להגדרה ה"קלאסית" של אידאל). יש קשר בין אידאלי סדר ואנטי-שרשראות: אם ניקח את כל האיברים המקסימליים באידאל סדר $I$ כלשהו (איברים $x\in I$ כך שלא קיים $y\in I$ כך ש- $x\le y$ ) אז נקבל אנטי-שרשרת, ומצד שני אם ניקח אנטי-שרשרת $A$ ונגדיר $I=\left\{ y\in X|\exists x\in A,y\le x\right\}$ נקבל אידאל סדר, ואם $X$ סופית זה נותן לנו התאמה חח"ע ועל בין אנטי-שרשרות ואידאלי סדר. באופן כללי אם בהינתן $A$ מגדירים ממנה $I$ כפי שתיארתי כאן, אז אומרים ש- $A$ יוצרת את האידאל $I$ ; ואידאל $I$ הוא אידאל סדר ראשי אם הוא נוצר בדיוק על ידי איבר אחד, כלומר קיים $x\in A$ כך ש- $I=\left\{ y\le x|y\in X\right\}$ . במקרה הזה מסמנים לעתים $I=\left\langle x\right\rangle$ . שוב, למי שבקיא באלגברה מופשטת הדמיון לאידאלים "קלאסיים" מאוד ברור כאן.

קונבולוצייה והיפוך, הגרסה המוכללת

אוקיי, הגענו לאקשן. בואו ניקח קבוצה סדורה חלקית $X$ שהיא סופית מקומית, ונגדיר פונקציות על קבוצת כל הקטעים ב- $X$ (פונקציות ממשיות, אבל אפשר גם עבור שדות אחרים). במילים אחרות, פונקציות שנראות ככה: $f\left(\left[x,y\right]\right)$ . לצורך פשטות אפשר לחשוב עליהן כפונקציות בשני משתנים: $f\left(x,y\right)$ , אבל הכרחי שיתקיים $x\le y$ אחרת אין משמעות ל- $\left[x,y\right]$ .

בין כל זוג פונקציות כזה אפשר להגדיר פעולת כפל שתכליל את קונבולוציית דיריכלה, אבל נמאס לי מהכוכב המעצבן הזה אז אני פשוט אשתמש בסימון הסטנדרטי לכפל: שום סימון. אם $f,g$ הן פונקציות מקבוצת הקטעים של $X$ אל $\mathbb{R}$ , אז נגדיר:

$fg\left(x,y\right)=\sum_{x\le z\le y}f\left(x,z\right)g\left(z,y\right)$

כאן העובדה ש- $X$ סופית מקומית היא קריטית; אחרת הסכום הזה לא בהכרח היה סופי.

בואו נראה איך המושג הזה מכליל את זה של תחילת הפוסט. שם התעסקנו עם פונקציות שמוגדרות על הטבעיים; כאן $X=\mathbb{N}$ ויחס הסדר הוא חלוקה, כלומר $a\le b$ פירושו $a|b$ . כעת, אם $f$ היא פונקציה שמוגדרת על הטבעיים, אפשר להגדיר אותה גם על קטעים באופן הבא: $f\left(a,b\right)=f\left(\frac{b}{a}\right)$ (זכרו: בגלל ש- $\left[a,b\right]$ הוא קטע, $a\le b$ ולכן $a|b$ ). לכן בפרט $f\left(a\right)=f\left(1,a\right)$ , ומההגדרה למעלה נקבל:

$fg\left(n\right)=fg\left(1,n\right)=\sum_{1|d|n}f\left(1,d\right)g\left(d,n\right)=\sum_{d|n}f\left(d\right)g\left(\frac{n}{d}\right)$

הופה! בדיוק ההגדרה של קונבולוציית דיריכלה.

אפשר להגדיר $\epsilon$ כמו קודם: $\epsilon\left(x,x\right)=1$ לכל $x\in X$ , ולכל $x\ne y$ $\epsilon\left(x,y\right)=0$ (למעשה, $\delta$ מתאים פה יותר, למי שזוכר את הדלתא של קרונקר, אבל לא חשוב). לא קשה לראות ש- $\epsilon$ היא איבר יחידה ביחס לכפל הפונקציות שהגדרתי לעיל. גם לא קשה לראות שהכפל אסוציאטיבי.

את מקומה של הפונקציה שסימנתי אז $\mathbb{I}$ תופסת עכשיו פונקציית זטא: $\zeta\left(x,y\right)=1$ לכל $x\le y$ . רגע, למה זטא? אודה ואתוודה – לא יודע, אני לא בטוח מה הקשר של הפונקציה הזו לשאר פונקציות הזטא הקיימות, אבל אלו הסימונים. באופן בלתי מפתיע, מגדירים כעת את פונקצית מביוס של הקס"ח $X$ בתור ההופכית של $\zeta$ , כלומר $\zeta\mu=\mu\zeta=\epsilon$ . כעת, נוסחת ההיפוך של מביוס, בתיאורה האבסטרקטי ביותר, היא פשוט האבחנה הסופר-טריוויאלית ש- $f\zeta=g$ אם ורק אם $f=g\mu$ (רק שיש כאן טוויסט כאן שתכף אסביר).

קרוב לודאי שאתם מרגישים שיצאתי יותר מדי בזול מכל העניין. איפה אני מוכיח משהו, בכלל? אתם כמובן צודקים – מה שחסר לי הוא הוכחה ש- $\zeta$ הפיכה בכלל. כדי לטפל בכך אוכיח משהו כללי יותר – שפונקציה $f$ היא הפיכה אם ורק אם $f\left(x,x\right)\ne0$ לכל $x\in X$ . חזרנו אל "החיפוש אחרי הופכי במקרה הכללי" של תחילת הפוסט, רק שהפעם אני לא הולך להתחמק.

למרבה המזל, האתגר לא גדול במיוחד. נתונה לי $f$ ואני רוצה למצוא $g$ כך ש- $fg=\epsilon$ . כלומר, כך ש- $fg\left(x,x\right)=\epsilon\left(x,x\right)=1$ לכל $x$ , ומכיוון שעל פי הגדרה $fg\left(x,x\right)=f\left(x,x\right)g\left(x,x\right)$ , הרי ש- $g\left(x,x\right)=\left(f\left(x,x\right)\right)^{-1}$ (כאן אני נעזר בכך שהערכים שהפונקציות מקבלות שייכים לשדה), ואנו רואים גם למה הכרחי שיתקיים $f\left(x,x\right)\ne0$ .

כעת, לכל $x\ne y$ שניתנים להשוואה צריך להתקיים $fg\left(x,y\right)=\epsilon\left(x,y\right)=0$ , ולכן על פי הנוסחה $\sum_{x\le z\le y}f\left(x,z\right)g\left(z,y\right)=0$ . בואו נבודד מהסכום הזה את האיבר שמתקבל כש- $z=x$ ונעביר אגף, נקבל ש:

$g\left(x,y\right)=-\left(f\left(x,x\right)\right)^{-1}\sum_{x<z\le y}f\left(x,z\right)g\left(z,y\right)$ .

הנוסחה הזו מספיקה כדי להגדיר את $g$ לכל קטע באופן רקורסיבי. זה לא מבטיח לנו נוסחה פשוטה יותר עבור $g$ , ומכאן בפרט שאין לנו תמיד נוסחה פשוטה עבור $\mu$ . מה כן יש לנו? ובכן, אם נציב את $\zeta$ בתור $f$ בנוסחאות הללו, נקבל ש- $\mu$ מתוארת על ידי הנוסחאות הבאות:

$\mu\left(x,x\right)=1$ לכל $x\in X$ .

$\mu\left(x,y\right)=-\sum_{x<z\le y}\mu\left(z,y\right)=-\sum_{x\le z<y}\mu\left(x,z\right)$ לכל $x<y$ .

את נוסחת ההיפוך עצמה ניתן לתאר עם סכומים באופן הבא: אם $f\zeta=g$ זה אומר ש- $g\left(x,y\right)=\sum_{x\le z\le y}f\left(x,z\right)$ , ולכן $f\left(x,y\right)=\sum_{x\le z\le y}g\left(x,z\right)\mu\left(z,y\right)$ .

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

$g\left(x\right)=\sum_{y\le x}f\left(y\right)$

אם ורק אם

$f\left(x\right)=\sum_{y\le x}g\left(y\right)\mu\left(y,x\right)$

בניסוח הזה אנחנו חייבים שב- $X$ כל אידאל סדר ראשי יהיה סופי פשוט כי אחרת הסכום $\sum_{y\le x}$ (כאשר $x$ קבוע – כלומר, הסכום הוא בדיוק על איברי אידאל הסדר שנוצר על ידי $x$ ) איננו סופי. למעשה, יש כאן נקודה עדינה למדי – אותן $f,g$ שאני מדבר עליהן כאן מוגדרות על איברים של $X$ , לא על קטעים. אין בעיה של ממש לטפל בעניין הזה אבל אני חושב שהתעללתי בקוראים מספיק ואסיים כאן.

תגים: נוסחת ההיפוך של מביוס, קבוצות סדורות חלקית
שייך לקטגוריות קומבינטוריקה, תורת המספרים | 2 תגובות »

עקרון ההכלה וההפרדה, ואז הכללה והפחדה

31 בדצמבר, 2011

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

מהו עקרון ההכלה וההפרדה

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

בואו נתחיל מגרסה עוד יותר פשוטה של הבעיה הראשונה: כמה מספרים בין 1 ל-100 כן מתחלקים ב-2 או ב-3? ובכן, בדיוק 50 מספרים מתחלקים ב-2 – כל הזוגיים. כמו כן, 33 מתחלקים ב-3; כל המספרים שהם כפולות של 3 עד 99, ו-100 לא עוזר לנו כי אינו מתחלק ב-3. קצת מחשבה מראה לנו את הנוסחה הכללית: מספרים מ- $1$ ועד $n$ שמתחלקים ב- $k$ יש בדיוק, אבל בדיוק, $\left\lfloor \frac{n}{k}\right\rfloor$ , כשהקווים מייצגים ערך שלם תחתון: אם התקבלה תוצאה שברית, מעגלים למטה למספר השלם הקרוב.

אם כן, הפיתוי גדול לומר שיש $50+33=83$ מספרים בין 1 ו-100 שמתחלקים ב-2 או ב-3. אבל ספירה מהירה תראה שזה לא נכון. בעצם, עזבו אתכם ממספרים בין 1 ל-100 שקשה לספור; אם ננסה באותה שיטה לספור מספרים בין 1 ל-10 נקבל $8$ מספרים, אבל בבירור יש רק 7: $\left\{ 2,3,4,6,8,9,10\right\}$ . איפה הטעות שלנו? במספר המעצבן 6, שמתחלק בו זמנית גם ב-2 וגם ב-3. ספרנו אותו פעמיים: פעם אחת כחבר בקבוצה $\left\{ 2,4,6,8,10\right\}$ של מספרים שמתחלקים ב-2, ופעם אחת בקבוצה $\left\{ 3,6,9\right\}$ של מספרים שמתחלקים ב-3. את הספירה הכפולה הזו צריך לתקן – פשוט נחסיר 1 מהתוצאה.

עבור מספרים בין 1 ל-100 הרעיון דומה; יש 83 מספרים פחות כמות המספרים בין 1 ל-100 שמתחלקים גם ב-2 וגם ב-3. למזלנו קל לדעת מיהם – אלו בדיוק המספרים שמתחלקים 6, כלומר $\left\lfloor \frac{100}{6}\right\rfloor =16$ . קיבלנו שיש $50+33-16=67$ מספרים בין 1 ל-100 שמתחלקים או ב-2, או ב-3, או בשניהם.

מכאן כבר אפשר לנחש את המקרה הכללי: אם יש לנו קבוצות $A_{1},\dots,A_{k}$ ואנו רוצים לדעת מה הגודל של $\bigcup_{i=1}^{k}A_{i}$ , קודם כל נסכום את הגדלים של כל הקבוצות, אחר כך נחסיר את הגודל של כל החיתוכים של שתי קבוצות, נחבר את הגודל של חיתוכים של שלוש, נחסיר את הגודל של חיתוכים של ארבע… אני אומר את זה מילולית כי לכתוב את זה בנוסחה – ובכן, איך נאמר זאת בעדינות – זה כואב. הנה הנוסחה:

$\left|\bigcup_{i=1}^{n}A_{i}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1\le i<j\le n}\left|A_{i}\cap A_{j}\right|+\dots+\left(-1\right)^{n+1}\left|\bigcap_{i=1}^{n}A_{i}\right|$

לקצרנים שבינינו, אפשר גם עם סכום כפול:

$\left|\bigcup_{i=1}^{n}A_{i}\right|=\sum_{t=1}^{n}\sum_{1\le i_{1}<i_{2}<\dots<i_{t}\le n}\left(-1\right)^{t+1}\left|\bigcap_{j=1}^{t}A_{i_{j}}\right|$

לא נעים כל כך, אבל העיקרון עצמו ברור למדי. עם זאת, צריך גם להוכיח שהוא עובד. הרעיון הוא להסתכל על איבר כלשהו $x\in\bigcup_{i=1}^{n}A_{i}$ ולשאול את עצמנו – מה הוא תורם לאגף ימין, ומה הוא תורם לאגף שמאל? לאגף שמאל הוא תורם בדיוק 1; אגף ימין קצת יותר מסובך. נניח ש- $x$ נמצא בדיוק ב- $k$ קבוצות, אז לכל $t>k$ , פשוט לא ייתכן ש- $x\in\bigcap_{j=1}^{t}A_{i_{j}}$ כי אנחנו חותכים פה יותר קבוצות מאשר יש קבוצות שמכילות את $x$ ולכן הוא לא בחיתוך. לכן מה שרלוונטי מראש הוא רק $t\le k$ , וגם אז – רק חיתוכים $\bigcap_{j=1}^{t}A_{i_{j}}$ שבהם כל הקבוצות כוללות את $x$ , כלומר כל הקבוצות נלקחות מתוך $k$ הקבוצות שכוללות את $x$ מלכתחילה. המספר שלהן הוא מה שמסמנים כ- ${k \choose t}$ : מספר האפשרויות לבחור $t$ מתוך $k$ . זה אומר ש- $x$ תורם לסכום באגף ימין בדיוק את תת-הסכום הבא:

$\sum_{t=1}^{k}{k \choose t}\left(-1\right)^{t+1}$

כדי לחשב את הסכום הזה משתמשים בנוסחת הבינום של ניוטון, שקל לראות ממנה שמתקיים $0=\left(1-1\right)^{k}=\sum_{t=0}^{k}{k \choose t}\left(-1\right)^{t}$ . לכן אנו מקבלים:

$\sum_{t=1}^{k}{k \choose t}\left(-1\right)^{t}=\sum_{t=0}^{k}{k \choose t}\left(-1\right)^{t+1}+1=1-\sum_{t=0}^{k}{k \choose t}\left(-1\right)^{t}=1$

כפי שרצינו.

ואיך עושים איתו דברים מעניינים

סיימנו את ההוכחה ואפשר לעבור לאקשן – פתרון של דברים אמיתיים. נתחיל עם המספרים בין 1 ל- $n$ שאינם מתחלקים ב- $2$ או $3$ או $5$ : כאן הקבוצות הן של המספרים שכן מתחלקים ב-2, וכן מתחלקים ב-3, וכן מתחלקים ב-5, ואנחנו רוצים לחסר את זה מהקבוצה של כלל המספרים, שהיא מגודל $n$ . לכן נקבל:

$n-\left(\left\lfloor \frac{n}{2}\right\rfloor +\left\lfloor \frac{n}{3}\right\rfloor +\left\lfloor \frac{n}{5}\right\rfloor \right)+\left(\left\lfloor \frac{n}{6}\right\rfloor +\left\lfloor \frac{n}{10}\right\rfloor +\left\lfloor \frac{n}{15}\right\rfloor \right)-\left\lfloor \frac{n}{30}\right\rfloor$

חייבים להודות שהנוסחה הזו לא נראית הכי מלהיבה בעולם; אבל חשבו לרגע על הדרך הנאיבית לחשב את המספר הזה – לעבור על כל המספרים מ- $1$ עד $n$ ולכל אחד לבדוק אם הוא מתחלק ב-2 או 3 או 5. אם $n$ קטן זה לא נורא, אבל מה אם $n=10^{100}$ ? במקרה הזה האלגוריתם שלנו לעולם לא יסתיים, ואילו בעזרת הנוסחה שלנו צריך יהיה לבצע 7 פעולות חילוק ולחבר/לחסר את התוצאות וזהו, כלומר החישוב יסתיים בחלקיקי שניה גם אם $n$ מפלצתי בגודלו. זו המחשה ראשונה לכוח שבהכלה והפרדה.

בואו נעבור לדוגמה השניה: עבור טבעי $n$ , $\varphi\left(n\right)$ ("פונקצית אוילר") מסמן את מספרם של המספרים הטבעיים בין 1 ל- $n$ שזרים ל- $n$ , כלומר שהמספר היחיד שמחלק את שניהם הוא $1$ עצמו. למשל, עבור $6$ , המספרים היחידים שקטנים ממנו וזרים לו הם 1 ו-5 ולכן $\varphi\left(6\right)=2$ ; עבור $8$ אלו הם $1,3,5,7$ ולכן $\varphi\left(8\right)=4$ , וכן הלאה. אם תסתכלו בגרף של הפונקציה הזו תראו שהיא מתנהגת בצורה די מטורללת – כל הזמן קופצת בין ערכים קטנים לגדולים. נקודות השיא הן בראשוניים (מספרים שמתחלקים רק ב-1 ובעצמם): לכל מספר ראשוני $p$ מתקיים $\varphi\left(p\right)=p-1$ ולכן הערכים הגדולים ביותר של $\varphi$ יתקבלו על הראשוניים, שהם עצמם מפוזרים בצורה שנראית כמעט אקראית.

ועם זאת, יש נוסחה ל- $\varphi\left(n\right)$ , שמתבססת על כך שאנו יודעים בדיוק מהם הראשוניים שמחלקים את $n$ . יש לנוסחה הזו מספר הוכחות והאהובה עלי עושה שימוש במשפט חשוב למדי מאלגברה – "משפט השאריות הסיני". לא נדבר על זה בכלל הפעם, ובמקום זאת נראה איך גישת ההכלה וההפרדה מחסלת גם היא את הבעיה בקלות.

האבחנה האלגברית שבבסיס העניין היא שאם $n$ ו- $m$ לא זרים, אז קיים ראשוני $p$ כלשהו שמחלק את שניהם. נניח שהמחלקים הראשוניים השונים של $n$ הם בדיוק $p_{1},\dots,p_{k}$ , אז הקבוצה $A_{i}$ שלנו הפעם תהיה "קבוצת כל המספרים הטבעיים הקטנים או שווים ל- $n$ שמתחלקים ב- $p_{i}$ ". את הגודל המדויק של הקבוצה הזו אנחנו יודעים – הוא בדיוק $\frac{n}{p_{i}}$ , מהנימוקים שנתתי קודם. וכמות המספרים שמתחלקים בשני ראשוניים $p_{i},p_{j}$ היא $\frac{n}{p_{i}p_{j}}$ וכן הלאה. אז הכלה והפרדה נותנת את הדבר הבא:

$\varphi\left(n\right)=n-\sum_{i}\frac{n}{p_{i}}+\sum_{i,j}\frac{n}{p_{i}p_{j}}-\dots+\left(-1\right)^{k}\frac{n}{p_{1}\cdots p_{k}}$

על פניו, לא ברור מה הנוסחה הזו עזרה לנו, אבל שימו לב לכך ש- $n$ הוא גורם בכל אחד מהמחוברים, כך שניתן להוציא אותו החוצה ולהיוותר עם סכום מהצורה $\left(1-\sum\frac{1}{p_{i}}+\sum\frac{1}{p_{i}p_{j}}-\dots+\left(-1\right)^{k}\frac{1}{p_{1}\cdots p_{k}}\right)$ . מה שטוב בסכום הזה, שעדיין נראה מפלצתי, הוא שאפשר לכתוב אותו בצורה הרבה יותר פשוטה ומסודרת כמכפלה: $\prod_{i=1}^{k}\left(1-\frac{1}{p_{i}}\right)$ . כדי לראות את זה, שימו לב שאם פותחים את המכפלה הזו, מקבלים סכום של איברים כך שכל איבר הוא בעצמו מכפלה, שכל איבר בה הוא או $1$ או $-\frac{1}{p_{i}}$ (הדרך הפשוטה ביותר לראות זאת – נסו לעשות זאת עם שני ראשוניים בלבד).

אם כן, קיבלנו את הנוסחה $\varphi\left(n\right)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$ ( $p|n$ פירושו "מכפלה שנלקחת על כל הראשוניים $p$ שמחלקים את $n$ ") שהיא קלה ביותר לחישוב, אם יודעים מיהם ה- $p$ -ים המתאימים (ולדעת מי הם – זו כבר בעיה לא פשוטה כלל).

בואו נעבור עכשיו להפרות סדר, שגם בהן הכלה והפרדה נותנת נוסחה סגורה, אבל מרשימה אפילו יותר מאשר במקרה הקודם שכן היא לא תכלול שום מכפלה ושום סכום, בזכות תעלול מחדו"א שנשתמש בו. הפרת סדר היא בבסיסה תמורה – סידור בשורה של המספרים מ- $1$ עד $n$ . יש באופן כללי $n!=1\cdot2\cdots n$ תמורות; מהן אנחנו רוצים לחסר את מספר התמורות שבהן יש לפחות אינדקס אחד $i$ כך שהמספר במקום ה- $i$ הוא $i$ עצמו (למשל, $4132$ היא תמורה כזו עם האינדקס $i=3$ ).

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

עקרון ההכלה וההפרדה מניב לנו עכשיו את הנוסחה הבאה ל- $D\left(n\right)$ , מספר הפרות הסדר של $n$ איברים:

$D\left(n\right)=n!-{n \choose 1}\left(n-1\right)!+{n \choose 2}\left(n-2\right)!-\dots+\left(-1\right)^{n}{n \choose n}\left(n-n\right)!$ . כדי להבין מה פשר המקדם ${n \choose k}$ שמופיע שם בואו נחשוב שניה איך אמורה להיראות הנוסחה: היא אמורה להתחיל עם $n!$ , ואז אמורים לחסר ממנה, לכל מקום בין 1 ל- $n$ , את מספר התמורות שבהן מקום זה מקובע. לכל מקום נקבל אותו מספר – $\left(n-1\right)!$ , ויש ${n \choose 1}$ מקומות כאלו, ומכאן הכפל. בדומה, ${n \choose 2}$ מתאים למספר האפשרויות לבחור זוג מקומות לקבע, וכן הלאה.

בואו נכתוב שוב את הנוסחה שקיבלתי, בצורה יותר קומפקטית: $D\left(n\right)=\sum_{k=0}^{n}\left(-1\right)^{k}{n \choose k}\left(n-k\right)!$ . האם יש דרך לפשט אותה עוד יותר? ובכן, ${n \choose k}=\frac{n!}{k!\left(n-k\right)!}$ כך שאפשר לעשות כאן צמצום קטן ולקבל $D\left(n\right)=\sum_{k=0}^{n}\left(-1\right)^{k}\frac{n!}{k!}=n!\left(\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}\right)$ . הקומבינטוריקה מביאה אותנו עד כאן ותו לא, אבל עכשיו החדו"א יכול להיכנס לפעולה.

כל מי שמכיר חדו"א ובוהה בנוסחה $\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}$ כנראה ירגיש משהו מצלצל לו – זה נראה כמו פונקציית האקספוננט $e^{x}=\sum_{k=0}^{\infty}\frac{x^{k}}{k!}$ , רק שכאן הטור סופי ולא אינסופי. במילים אחרות, $\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}=e^{-1}-\sum_{k=n+1}^{\infty}\frac{\left(-1\right)^{k}}{k!}$ . אז קיבלנו שהסכום הוא "כמעט" $\frac{1}{e}$ , רק שיש גם שארית מעצבנת $\sum_{k=n+1}^{\infty}\frac{\left(-1\right)^{k}}{k!}$ שצריך להבין מה בדיוק, או לפחות בערך, הגודל שלה. במקרה הספציפי שלנו זה קל במיוחד כי הטור הוא מה שנקרא "טור לייבניץ" – טור מהצורה $\sum\left(-1\right)^{n}a_{n}$ כש- $a_{n}$ שואפת מונוטונית לאפס, וידוע שסכום של טור שכזה, בערכו המוחלט, הוא קטן או שווה לגודל האיבר הראשון בו. כלומר, $\left|\sum_{k=n+1}^{\infty}\frac{\left(-1\right)^{k}}{k!}\right|\le\left|\frac{\left(-1\right)^{n+1}}{\left(n+1\right)!}\right|=\frac{1}{\left(n+1\right)!}$ .

אם כן, קיבלנו את הנוסחה $D\left(n\right)=n!\cdot\left(e^{-1}+\xi\left(n\right)\right)=\frac{n!}{e}+n!\xi\left(n\right)$ , כשכתבתי את השגיאה ב- $\xi$ בדיוק כדי שתיראה מכוערת ונרצה להיפטר ממנה. מה אנחנו יודעים עליה? ש- $\left|n!\xi\left(n\right)\right|\le\frac{n!}{\left(n+1\right)!}=\frac{1}{n}$ . במילים אחרות, עבור $n\ge3$ , השגיאה קטנה מחצי. זה מאפשר לנו לטעון את הטענה הנועזת הבאה: $D\left(n\right)=\left[\frac{n!}{e}\right]$ , כאשר הסוגריים המרובעים פירושם "ערך שלם" – המספר השלם הקרוב ביותר ל- $\frac{n!}{e}$ . זה עובד מכיוון שלכל מספר ממשי, הערך השלם שלו הוא במרחק לכל היותר $\frac{1}{2}$ ממנו, בעוד שכל מספר שלם אחר הוא מרחק של לפחות $\frac{1}{2}$ ממנו, ולכן אם כל ה"תיקון" שנדרש כדי לעבור מ- $\frac{n!}{e}$ ל- $D\left(n\right)$ הוא פחות מחצי, הערך השלם יביא אותנו ל- $D\left(n\right)$ בודאות. את זה ש- $D\left(n\right)=\left[\frac{n!}{e}\right]$ גם עבור $n=1,2$ אפשר לבדוק בצורה ישירה, והנה קיבלנו נוסחה סגורה ופשוטה ל- $D\left(n\right)$ . אפשר גם להסיק מסקנה הסתברותית – ככל ש- $n$ שואף לאינסוף, כך ההסתברות לקבלת הפרת סדר כשמגרילים תמורה באקראי שואפת ל- $\frac{1}{e}$ ; הנה לנו דוגמה נאה למקום שבו $e$ צץ באופן טבעי לגמרי בבעיה קומבינטורית שבכלל לא מזכירה אותו.

הכללה והפחדה

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

אם כן, תהא $X$ קבוצה כלשהי בת $n$ איברים (אפשר לחשוב עליה כעל קבוצה של "תכונות" אם זה עוזר לנו). ניקח מרחב וקטורי $V$ של כל הפונקציות $f:\mbox{P}\left(X\right)\to\mathbb{R}$ , כאשר $\mbox{P}\left(X\right)$ פירושו קבוצת החזקה של $X$ – אוסף כל תת-הקבוצות של $X$ . במילים אחרות, כל פונקציה $f$ כזו מגדירה ערך כלשהו שמתאים לתת-קבוצה של $X$ . קל לראות ש- $V$ הוא באמת מרחב וקטורי מעל $\mathbb{R}$ (למעשה, $\mathbb{R}$ לא ממש חשוב כאן וכל שדה אחר היה עובד באותה מידה). כעת נגדיר טרנספורמציה לינארית $T:V\to V$ באופן הבא:

$\left(Tf\right)\left(A\right)=\sum_{B\supseteq A}f\left(B\right)$

כלומר, בהינתן $f$ , הפונקציה החדשה ש- $Tf$ מגדירה היא כזו שערכה על כל תת-קבוצה $A\subseteq X$ הוא סכום ערכי $f$ על כל ה- $B$ שמכילות את $A$ . חשבו על זה כך: $f\left(A\right)$ אומרת כמה איברים ביקום שלנו מקיימים בדיוק את התכונות שבקבוצה $A$ ושום דבר אחר; $Tf\left(A\right)$ אומר כמה איברים ביקום שלנו מקיימים לפחות את התכונות שב- $A$ , ואולי עוד דברים. בדרך כלל את $f$ קשה לחשב ואילו את $Tf$ קל, ולכן מה שאנחנו רוצים לעשות הוא "להפוך" את $T$ ; לקבל איכשהו מ- $Tf$ את $f$ עצמה. לצורך כך צריך שהטרנספורמציה הלינארית שלנו תהיה הפיכה, ועקרון ההכלה וההפרדה אומר שזה בדיוק מה שקורה, וגם נותן לנו את הנוסחה המדוייקת של $T^{-1}$ :

$\left(T^{-1}f\right)\left(A\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f\left(B\right)$

תכף נראה איך זה מתקשר לדברים שראינו עד כה, אבל לפני כן בואו נוכיח. מה שאנחנו בעצם רוצים להראות הוא שאם נגדיר טרנספורמציה לינארית $S:V\to V$ על ידי $\left(Sf\right)\left(A\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f\left(B\right)$ אז יתקיים ש- $ST=TS=I$ . עכשיו, כמו שבדרך כלל קורה באלגברה לינארית, כל מה שצריך לעשות הוא להציב והכל כבר מסתדר מעצמו. הבה ונראה מהו $\left(TSf\right)$ :

$\left(TSf\right)\left(A\right)=T\left(\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f\left(B\right)\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}Tf\left(B\right)$

$=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}\left(\sum_{C\supseteq B}f\left(C\right)\right)$

כעת ננקוט בתעלול הטכני הסטנדרטי של שינוי סדר הסכימה. הסכום שלמעלה שווה ממש לסכום הבא:

$\sum_{C\supseteq A}\left(\sum_{A\subseteq B\subseteq C}\left(-1\right)^{\left|B-A\right|}\right)f\left(C\right)$

האינדקס בסכום האמצעי הוא $B$ . אז למה $\left|B-A\right|$ יכול להיות שווה? ברור שערכיו נעים בין 0 ובין $m=\left|C-A\right|$ . כמה קבוצות $B$ מקיימות ש- $\left|B-A\right|=i$ עבור $0\le i\le m$ ? ובכן, בדיוק כמספר האיברים לבחור $i$ מתוך $m$ האיברים של $C$ שאינם ב- $A$ , כלומר ${m \choose i}$ . לכן את הסכום האמצעי אפשר לכתוב גם כ- $\sum_{i=0}^{m}\left(-1\right)^{i}{m \choose i}=\left(1-1\right)^{m}$ (כאן השתמשתי בבינום של ניוטון), ולכן אם $m>0$ אז הסכום האמצעי שווה לאפס, ואם $m=0$ אז הסכום האמצעי שווה ל-1 (אני משתמש כאן בקונוונציה לפיה $0^{0}=1$ , אבל מי שלא מאמין לי יכול לבדוק ולהיווכח בכך ש- $\sum_{A\subseteq B\subseteq C}\left(-1\right)^{\left|B-A\right|}$ אכן שווה 1 כאשר $A=C$ , מה שמצדיק את השימוש בקונוונציה $0^{0}=1$ כאן).

לסיכום, קיבלנו ש- $\left(TSf\right)\left(A\right)=f\left(A\right)$ , וזאת לכל $A$ , ולכן $TS=I$ כנדרש. זה מסיים את הוכחת עקרון ההכלה וההפרדה הכללי ביותר שאני מכיר, אבל – מה בעצם עשינו כאן, לעזאזל?

התחלתי את הפוסט עם הנוסחה $\left|\bigcup_{i=1}^{n}A_{i}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1\le i<j\le n}\left|A_{i}\cap A_{j}\right|+\dots+\left(-1\right)^{n+1}\left|\bigcap_{i=1}^{n}A_{i}\right|$ . כאן חשבנו על $A_{i}$ בתור "קבוצת כל האיברים שמקיימים את התכונה ה- $i$ לפחות" (לא בדיוק!), ולכן על $A_{i}\cap A_{j}$ בתור כל האיברים שמקיימים לפחות את התכונות $i,j$ וכן הלאה. בלשון הקבוצות של המשפט שלמעלה, $S=\left\{ 1,2,\dots,n\right\}$ ו- $f\left(A\right)=\left|\bigcap_{i\in A}A_{i}\right|$ (כן, יש לי כאן שימוש כפול מוזר ב- $A$ וב- $A_{i}$ במשמעויות שונות לגמרי. אל תגידו לי שזה מה שיחסל אתכם עכשיו).

הנוסחה שלעיל מתארת את $\bigcup_{i=1}^{n}A_{i}$ , שהוא מספר האיברים שמקיימים לפחות אחת מהתכונות, אבל בדרך כלל התעניינו דווקא במספר האיברים שלא מקיימים אף אחת מהתכונות, מה שגרם לנו לחסר את הגודל של $\bigcup_{i=1}^{n}A_{i}$ ממספר האיברים הכולל ב"עולם" שלנו, שזו דרך אחרת להגיד "מספר האיברים שמקיימים לפחות אפס תכונות" (מעין "חיתוך ריק" שלא ממש ברור איך לכתוב אותו).

בואו נחדד את העניין, אם כן. נגדיר פונקציה $f_{=}\left(A\right)$ ששווה למספר האיברים שמקיימים בדיוק את התכונות שב- $A$ . אנחנו מעוניינים לרוב למצוא את $f_{=}\left(\emptyset\right)$ , אבל לפעמים גם עבור קבוצות מחוכמות יותר. כעת, נגדיר גם $f_{\ge}\left(A\right)$ בתור מספר האיברים שמקיימים לפחות את התכונות ב- $A$ , כלומר בדיוק $f_{\ge}\left(A\right)=\left|\bigcap_{i\in A}A_{i}\right|$ . כעת קל לראות שמתקיים הקשר

$f_{\ge}\left(A\right)=\sum_{B\supseteq A}f_{=}\left(B\right)$ (הסבירו לעצמכם למה!) כלומר $f_{\ge}=Tf_{=}$ , ולכן $f_{=}=T^{-1}f_{\ge}$ , כלומר

$f_{=}\left(A\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f_{\ge}\left(B\right)$

ובפרט עבור $A=\emptyset$ נקבל

$f_{=}\left(\emptyset\right)=\sum_{A}\left(-1\right)^{\left|A\right|}f_{\ge}\left(A\right)$

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

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

תגים: אקספוננט, עקרון ההכלה וההפרדה, קומבינטוריקה
שייך לקטגוריות קומבינטוריקה | 9 תגובות »

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

24 בדצמבר, 2011

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

כזכור, בסדרת הפוסטים על אלגברה לינארית הגענו להתעסק בשאלה הבאה: נתונה טרנספורמציה לינארית $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$ , כלומר קטנה מדרגת הפולינום המינימלי. זה מסיים את הכל.

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

תגים: אלגברה לינארית, פולינום מינימלי, תת מרחב שמור, לכסון סימולטני, הטלות
שייך לקטגוריות אלגברה לינארית | 7 תגובות »

הזמנה לתערוכה, והרצאות לקהל הרחב!

17 בדצמבר, 2011

תיקון: שימו לב, ההרצאה השניה (של אהרוני) תתקיים ב-15:00, לא ב-12:10!

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

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

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

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

ההרצאה תתקיים ביום שני ה-19/12 בשעה 18:00 בחדר 232 בבניין אמדאו (ולאחר מכן טקס הפתיחה של התערוכה).

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

ההרצאה תועבר ביום שלישי ה-27/12 בשעה 15:00 באולם 5 באגף החינוך במדעטק.

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

ההרצאה תועבר ביום שלישי ה-3/1 בשעה 12:10 באולם 6013 בבניין רבין באוניברסיטת חיפה.

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

ההרצאה תינתן ביום חמישי ה-5/1 בשעה 9:00 באולם באטלר במוסד נאמן בטכניון.

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

ההרצאה תינתן ביום שלישי ה-10/1 בשעה 18:00 בחדר 232 בבניין אמדאו בטכניון.

סה"כ ההרצאות נשמעות מרתקות, והתערוכה (שבה כבר הייתי) מעניינת. אני ממליץ לכולם לבוא – דברים כאלו לא קורים כל יום בישראל, לצערי.

שייך לקטגוריות כללי | 10 תגובות »

בעיית המעגל של גאוס (וגם קצת על טרחנות)

11 בדצמבר, 2011

הפנו אותי לאתר הבא, שבו מציג כותב ישראלי משהו בשם "Q-space theory" שהיא "An attempt to intuitively unify physics". ובכן, אתם ודאי יכולים לנחש מה אני חושב כשאני רואה משהו כזה. רוב תוכנו של האתר הוא קישורים לסרטוני יוטיוב שכבר הוסרו, אבל הסיבה שבגללה קישרו אותי אליו היא קובץ שבו מדובר על "התכנסות לערכו של פאי דרך הפתרונות הפיתגוראיים הטבעיים". ובכן, אתם ודאי יכולים לנחש מה אני חושב כשאני רואה משהו כזה. אבל, כמו תמיד בעניינים הללו, לא הייתי טורח לכתוב על זה אם לא הייתה מתמטיקה מעניינת בפנים.

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

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

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

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

אז מה הולך כאן ואיך מעגל נכנס לתמונה? ובכן, תשכחו מ"פתרון פיתגוראי טבעי" ותחשבו באופן גיאומטרי. אם $a^{2}+b^{2}\le n$ ("הפתרונות הפיתגוראיים הטבעיים שבהם סכום ריבועי הניצבים קטן או שווה ל- $n$ ") זה אומר שהנקודה $\left(a,b\right)$ במישור $\mathbb{R}^{2}$ היא במרחק לכל היותר $\sqrt{n}$ מראשית הצירים, כלומר היא נמצאת בתוך העיגול שרדיוסו $latex \sqrt{n}$. מכיוון שלא נוח לערב שורשים, בואו נדבר על עיגול ברדיוס $n$ ולכן המשוואה היא $a^{2}+b^{2}\le n^2$ . בנוסף, מכיוון שהוא מדבר רק על מספרים טבעיים הוא מדבר רק על הרבע הימני-עליון של העיגול – בואו נדבר על העיגול כולו, כלומר נרשה ל- $a,b$ להיות גם שליליים (אבל עדיין מספרים שלמים). אז השאלה היא כזו: בתוך עיגול שרדיוסו $n$ , כמה נקודות יש שהקואורדינטות שלהן הן מספרים שלמים?

אפשר להגדיר את זה הכי פורמלית בעולם כך: $N\left(n\right)=\left|\mathbb{Z}^{2}\cap\left\{ \left(a,b\right)\in\mathbb{R}^{2}|a^{2}+b^{2}\le n^{2}\right\} \right|$ . בסימונים הללו, ההשערה שהועלתה היא שמתקיים $\lim_{n\to\infty}\frac{N\left(n\right)}{n^{2}}=\pi$ . את זה אפשר גם לסמן בצורה קצת שונה, שמתאימה קצת יותר לאופי של בעיות מסוג זה בתורת המספרים: $N\left(n\right)=\pi n^{2}+o\left(n^{2}\right)$ , או במילים: $N\left(n\right)$ שווה ל- $\pi n^{2}$ ועוד שגיאה שגדלה בקצב אסימפטוטי נמוך ממש יותר מ- $n^{2}$ , ובמילים אחרות אם מחלקים אותה ב- $n^{2}$ ומשאיפים את $n$ לאינסוף מקבלים אפס.

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

מה גאוס הוכיח? ובכן, נסמן $N\left(n\right)=\pi^{2}n+E\left(n\right)$ כש- $E\left(n\right)$ היא פונקציית ה"שגיאה"; גאוס הוכיחש- $\left|E\left(n\right)\right|\le2\sqrt{2}\pi n$ (לפחות על פי ויקיפדיה; ברפרנס שהם מביאים בכלל לא מדובר על הקבוע), ומכאן קל לראות ש- $E\left(n\right)=o\left(n^{2}\right)$ וזה נותן את התוצאה שדובר עליה מייד. זה לא מסיים את הסיפור כי החסם של גאוס הוא עדיין גס למדי ויש חסמים טובים יותר; ההשערה היא ש- $E\left(n\right)=O\left(n^{\frac{1}{2}+\varepsilon}\right)$ , כלומר חזקה של $n$ שהיא הרבה פחות מ-1 כמו בחסם של גאוס, אבל כיום החזקה הטובה ביותר שהגיעו אליה (על פי ויקיפדיה) היא $0.6298\dots$ . בקיצור, חסם טוב על גודל השגיאה הוא עדיין אתגר פתוח במתמטיקה.

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

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

def N(n): return len([(a,b) for a in range(-n,n+1) for b in range(-n,n+1) if a^2+b^2<=n^2]) print [N(n) for n in range(10)]

שימו לב כמה העסק פשוט כאשר עובדים בשפה המתאימה – נדרשת בערך שורה אחת (שהיא אפילו קריאה, עבור מי שמכיר את השפה) כדי לעשות את החישוב שב"כפפה" דרש הרבה יותר קוד. כעת, אם מריצים את הקוד הזה יתקבל הפלט $[1,5,13,29,49,81,113,149,197,253]$ , ומה שעושים עם דבר כזה הוא ללכת לאנציקלופדיה האלקטרונית של סדרות מספרים. הסדרה מופיעה שם, כמו גם קישור לבעיית המעגל של גאוס. זו כמובן לא הדרך היחידה שאפשר לנקוט בה, אבל אני חושב שראוי להציג אותה כי לפעמים אנשים מפספסים את העובדה שסדרה של מספרים קונקרטיים שהיא לכאורה לא מעניינת לכשעצמה (כי מה אכפת לנו אם זה 197 שם ולא 196?) יכולה להיות מאוד מועילה כשמגששים באפלה של בעיה מסויימת (כמו גם שפת תכנות נוחה עבור מי שרוצה לחשב דברים "ביד", אם כי צריך להיזהר ולא להגזים עם זה כי אינטואיציות באות לפעמים דווקא כשעושים את החישובים באמת ביד).

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

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

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

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

באופן דומה, הבה וניקח ריבוע שחלקו בתוך העיגול אבל לא כולו, אז אפילו הנקודה בו שמרחקה ממרכז העיגול הוא הקטן ביותר לא יכולה להיות במרחק גדול מ- $\sqrt{2}$ משפת העיגול, אחרת כל הריבוע היה בפנים. לכן אפשר לצייר עיגול פנימי שרדיוסו קטן ב- $\sqrt{2}$ מרדיוס העיגול – זה העיגול המקווקו השני. אם מסתכלים על השטח של העיגול המקווקו החיצוני, שממנו מחסירים את השטח של העיגול המקווקו הפנימי, מקבלים טבעת. כל הריבועים הבעייתיים נמצאים בשלמותם בתוך הטבעת הזו, ולכן שטח כל הריבועים הבעייתיים קטן או שווה לשטח הטבעת. רק ששטח טבעת קל לחשב – פשוט מחסרים משטח העיגול המקווקו החיצוני את שטח העיגול המקווקו הפנימי, ומקבלים:

$\pi\left(n+\sqrt{2}\right)^{2}-\pi\left(n-\sqrt{2}\right)^{2}=4\pi\sqrt{2}n$

וזהו ההפרש המקסימלי בין שטח העיגול ( $\pi n^{2}$ ) ובין מספר הנקודות השלמות שבו ( $N\left(n\right)$ ), מה שמסיים את ההוכחה וסוגר את עניין ה"כפפה".

תגים: טרחנים מתמטיים, בעיית המעגל של גאוס
שייך לקטגוריות תורת המספרים | 11 תגובות »

השילוש הקדוש, הפולינום המינימלי ומשפט קיילי-המילטון

7 בדצמבר, 2011

השילוש הקדוש

בפוסט הקודם דיברנו על ערכים עצמיים ווקטורים עצמיים וראינו שהם קשורים קשר בל ינתק למושג של לכסון מטריצות. אם $A$ היא מטריצה ריבועית כלשהי, אומרים ש- $A$ ניתנת ללכסון או לכסינה אם היא דומה למטריצה אלכסונית $D$ (מטריצה אלכסונית היא מטריצה ריבועית שבה רק הכניסות שעל האלכסון הראשי שונות מאפס), כלומר רק אם יש מטריצה הפיכה $P$ כך ש- $P^{-1}AP=D$ . ראינו קריטריון שאומר ש- $A$ היא לכסינה אם ורק אם יש לה "מספיק ערכים עצמיים ומספיק וקטורים עצמיים" – אם ורק אם סכום הריבויים האלגבריים והגיאומטריים של הערכים העצמיים שלה היה $n$ , כש- $n$ הוא סדר המטריצה.

מכאן ואילך אני רוצה לדבר רק על המקרה שבו סכום הריבויים האלגבריים של הערכים העצמיים הוא $n$ ; כזכור, זה קורה אם ורק אם כל הערכים העצמיים של $A$ נמצאים בתוך השדה $\mathbb{F}$ שמעליו עובדים. הנקודה החשובה כאן היא שאם יש ל- $A$ ערכים עצמיים שאינם ב- $\mathbb{F}$ , אפשר להרחיב את השדה $\mathbb{F}$ על ידי הוספת הערכים העצמיים אליו, ואז הסתכלות על $A$ מעל השדה הגדול יותר הזה. אחרי שמבינים מה קורה ל- $A$ מעל השדה הגדול יותר אפשר, אם יש צורך בכך, לחשוב איך אפשר להפיק מהתוצאה הזו מידע על $A$ מעל $\mathbb{F}$ בלבד, אבל לא ניכנס לכך כעת. לרוב מניחים כדי למנוע את הדיון הזה על הרחבת שדות ש- $\mathbb{F}$ הוא מה שנקרא שדה סגור אלגברית – כזה שבו לכל פולינום ממעלה ראשונה ומעלה יש שורש.

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

הדבר הראשון שאני רוצה להתחיל ממנו הוא לשכנע אתכם בטענה קצת יותר פשוטה מהמשפט של ז'ורדן – כל $A$ מעל שדה סגור אלגברית דומה למטריצה משולשית עליונה. מטריצה משולשית עליונה היא כזו שבה כל האיברים מתחת לאלכסון הראשי הם 0 (פורמלית, $A_{ij}=0$ אם $i>j$ ). המשפט הזה הוא שימושי למדי כי מטריצות משולשיות הן שימושיות – כך למשל חישוב דטרמיננטה שלהן הוא פשוט לכפול את אברי האלכסון הראשי (כי חשבו מה קורה אם מפתחים את הדטרמיננטה לפי העמודה הראשונה, ואז השניה, ואז השלישית וכדומה).

ההוכחה יחסית פשוטה. הרעיון הוא להשתמש בכך שמעל שדה סגור אלגברית, לכל מטריצה $A$ יש לפחות ערך עצמי אחד (כי לפולינום האופייני של $A$ יש לפחות שורש אחד). אם יש ל- $A$ וקטור עצמי $v$ עם ערך עצמי $\lambda$ , אז אם נשלים את הקבוצה $\left\{ v\right\}$ לבסיס של $\mathbb{F}^{n}$ , נקבל שהטרנספורמציה ש- $A$ מייצגת בבסיס הסטנדרטי של $\mathbb{F}^{n}$ מיוצגת בבסיס שבו $v$ הוא הוקטור הראשון על ידי מטריצה מהצורה $B=\left[\begin{array}{cc}\lambda & u\\0 & A^{\prime}\end{array}\right]$ , כלומר $B$ הזו דומה ל- $A$ ( $P^{-1}AP=B$ עבור $P$ הפיכה). אני משתמש כאן בצורת סימון קצרנית למדי, אז אל תתבלבלו: $B$ היא מטריצה מסדר $n\times n$ . ה-0 שכתוב שם הוא בעצם וקטור עמודה מאורך $n-1$ , ה- $u$ הוא בעצם וקטור שורה מאורך $n-1$ , ואילו $A^{\prime}$ היא מטריצה מסדר $\left(n-1\right)\times\left(n-1\right)$ . כעת אפשר להשתמש באינדוקציה על הסדר של $A$ (הבסיס ברור) ולקבל ש- $A^{\prime}$ דומה למטריצה משולשית עליונה $B^{\prime}$ , כלומר $S^{-1}A^{\prime}S=B^{\prime}$ עבור $S$ הפיכה מסדר $\left(n-1\right)\times\left(n-1\right)$ .

האינטואיציה אומרת שעכשיו כדי לעבור מ- $A$ למטריצה משולשית עליונה עלינו לעבור מ- $A$ אל $B$ , ואז מ- $B$ אל מטריצה שאיכשהו תשנה את הרכיב של $A^{\prime}$ שבתוך $B$ ל- $B^{\prime}$ המשולשית. אי אפשר סתם להצמיד את $B$ על ידי $S$ כי $S$ בכלל לא מאותו סדר כמו $B$ ( $B$ מסדר $n\times n$ ), אבל אין בעיה להגדיר את המטריצה $Q=\left[\begin{array}{cc}1 & 0\\0 & S\end{array}\right]$ (כלומר – לקחנו את $S$ והוספנו לה עוד שורה ועמודה בהתחלה שבהן הכל 0 פרט לכניסה שעל האלכסון הראשי שהיא 1). כל מה שנשאר עכשיו הוא לחשב מה מקבלים אם מצמידים את $A$ על ידי $PQ$ , כלומר מהו $\left(PQ\right)^{-1}A\left(PQ\right)=Q^{-1}P^{-1}APQ$ .

נתחיל עם $P^{-1}AP$ שבאמצע – על פי הגדרה, זהו $B$ . אז עכשיו צריך להבין מהו $Q^{-1}BQ$ .

ראשית, שימו לב לכך ש- $Q^{-1}=\left[\begin{array}{cc}1 & 0\\0 & S^{-1}\end{array}\right]$ (אין כאן משהו מחוכם – חשבו את הכפל ותראו שזה עובד). כעת,

$Q^{-1}BQ=\left[\begin{array}{cc}1 & 0\\0 & S^{-1}\end{array}\right]\left[\begin{array}{cc}\lambda & u\\0 & A^{\prime}\end{array}\right]\left[\begin{array}{cc}1 & 0\\0 & S\end{array}\right]=\left[\begin{array}{cc}\lambda & v\\0 & S^{-1}A^{\prime}S\end{array}\right]=\left[\begin{array}{cc}\lambda & v\\0 & B^{\prime}\end{array}\right]$

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

הפולינום המינימלי

כעת אני רוצה לדבר על מושג הפולינום המינימלי של מטריצה ריבועית $A$ . נתחיל מכך שמרחב המטריצות מסדר $n\times n$ הוא מרחב וקטורי ממימד $n^{2}$ (אברי הבסיס הן בדיוק המטריצות שיש להן 1 בכניסה $ij$ לכל $1\le i,j\le n$ ו-0 בכל מקום אחר). בפרט, אם נתבונן בחזקות $I=A^{0},A^{1},A^{2},\dots,A^{n^{2}}$ , נקבל $n^{2}+1$ וקטורים (לא בהכרח שונים זה מזה) במרחב הוקטורי של המטריצות מסדר $n\times n$ – מכיוון שזו קבוצה גדולה יותר ממימד המרחב היא חייב להיות תלויה לינארית, כלומר $\sum_{i=0}^{n^{2}}\lambda_{i}A^{i}=0$ עבור מקדמים כלשהם $\lambda_{0},\lambda_{1},\dots,\lambda_{n^{2}}$ . בניסוח אחר זה אומר שאם מציבים את $A$ במקום $x$ בפולינום $\lambda_{n^{2}}x^{n^{2}}+\dots+\lambda_{1}x+\lambda_{0}$ מקבלים 0 (0 כאן הוא מטריצת האפס). כלומר, $A$ היא שורש של הפולינום $\lambda_{n^{2}}x^{n^{2}}+\dots+\lambda_{1}x+\lambda_{0}$ . זה רעיון קצת קשה לעיכול למי שהתרגל עד היום שבפולינומים מציבים רק מספרים, אבל למה להגביל את עצמנו? כל מה שנדרש ממשהו כדי שאפשר יהיה להציב אותו בתור $x$ הוא שיהיה עבורו מושג של חיבור, של כפל בסקלר (המקדמים של $x$ הם סקלרים), ומושג של חזקה (שבמקרה של מטריצות מושג בזכות זה שאפשר לכפול מטריצה בעצמה). בדיוק באותה שיטה אפשר גם להציב טרנספורמציה לינארית בפולינום.

העובדה שכל מטריצה מאפסת פולינום כלשהו היא לא טריוויאלית בכלל, למרות שכפי שראינו ההוכחה הייתה טריוואלית. כדי להבין עד כמה זה לא מובן מאליו כדאי לזכור שלמספרים ממשיים כמו $\pi$ ו- $e$ יש את התכונה המעניינת לפיה הם לא מאפסים אף פולינום במקדמים רציונליים – הם טרנסנדנטיים מעל הרציונליים (גם זו טענה לא טריוויאלית, ולמרבה הצער גם ההוכחה לא טריוויאלית). משראינו שכל מטריצה ריבועית מאפסת פולינום כלשהו, אפשר בהינתן $A$ לדבר על אוסף כל הפולינומים ש- $A$ מאפסת. זו קבוצה כלשהי של פולינומים ב- $\mathbb{F}\left[x\right]$ (חוג הפולינומים במשתנה יחיד עם מקדמים מ- $\mathbb{F}$ ) וראינו שהיא לא ריקה. את מה שקורה עכשיו אפשר לתאר על ידי רצף הקללות שמוכרות לכל מי שלמד קצת על חוגים: $\mathbb{F}\left[x\right]$ הוא תחום ראשי ואוסף כל הפולינומים ש- $A$ מאפסת הוא אידאל לא טריוויאלי ולכן נוצר על ידי פולינום מתוקן יחיד $p\left(x\right)$ ; לפולינום הזה קוראים הפולינום המינימלי של $A$ . ועכשיו נעבור להסבר בעברית עבור מי שמה שאמרתי לו כרגע נשמע כמו ג'יבריש.

ראשית, לפולינומים שמקדמיהם נלקחים מתוך שדה יש תכונה יפהפיה – אפשר לחלק אותם עם שארית בדיוק כמו שמחלקים מספרים שלמים עם שארית. בשלמים זה הולך ככה: אם $a,b$ הם שלמים אז קיימים $q,r$ שלמים ( $q$ הוא המנה ו- $r$ הוא השארית) כך ש- $a=bq+r$ , כך ש- $0\le r<\left|b\right|$ (השארית תמיד קטנה מהמספר שבו מחלקים). עבור פולינומים זה אותו הדבר: אם $a\left(x\right),b\left(x\right)$ הם שני פולינומים אז $a\left(x\right)=b\left(x\right)q\left(x\right)+r\left(x\right)$ כך ש- $r\left(x\right)$ הוא פולינום מדרגה קטנה יותר מדרגת $b\left(x\right)$ .

כעת, הבה וניקח את $p\left(x\right)$ להיות פולינום שונה מפולינום האפס שמאפס את $A$ והוא בעל הדרגה המינימלית מבין כל הפולינומים שמאפסים את $A$ (הדרגה יכולה להיות רק מספר טבעי ולכן תמיד יש מינימום שכזה – לכל היותר $n^{2}$ ). בנוסף נדרוש שהוא יהיה מתוקן – המקדם של החזקה הגבוהה ביותר בפולינום יהיה 1. את זה תמיד אפשר להשיג כשאנחנו מעל שדה: אם $\lambda_{k}x^{k}+\dots+\lambda_{1}x+\lambda_{0}$ הוא פולינום ו- $\lambda_{k}\ne0$ (והוא שונה מאפס, אחרת למה כתבנו אותו מלכתחילה? זה שהפולינום מדרגה $k$ פירושו ש- $x^{k}$ היא החזקה המקסימלית שהמקדם שלה איננו אפס) אז אפשר לחלק ב- $\lambda_{k}$ ולקבל פולינום מתוקן $x^{k}+\dots+\frac{\lambda_{1}}{\lambda_{k}}x+\frac{\lambda_{0}}{\lambda_{k}}$ . חישוב פשוט מראה שאם הפולינום אופס קודם על ידי $A$ , אז גם אחרי החלוקה ב- $\lambda_{k}$ $A$ עדיין יאפס אותו. מסקנה: קיים $p\left(x\right)$ שהוא פולינום מתוקן מדרגה מינימלית שמאפס את $A$ .

כעת שימו לב לקסם הבא: ניקח את $t\left(x\right)$ להיות פולינום אחר כלשהו שמאפס את $A$ , ונחלק אותו ב- $p\left(x\right)$ . נקבל ש- $t\left(x\right)=p\left(x\right)q\left(x\right)+r\left(x\right)$ , כך שמעלת $r\left(x\right)$ קטנה ממעלת $p\left(x\right)$ . אם נציב את $A$ בתור $x$ ונשתמש בכך ש- $t\left(A\right)=0$ וגם $p\left(A\right)=0$ נקבל ש- $r\left(A\right)=0$ , כלומר $r\left(x\right)$ הוא פולינום מדרגה קטנה מזו של $p\left(x\right)$ שגם כן מאופס על ידי $A$ . מכיון שבחרנו את $p\left(x\right)$ להיות בעל דרגה מינימלית מבין הפולינומים שאינם פולינום האפס שמאופסים על ידי $A$ , בהכרח $r\left(x\right)$ הוא פולינום האפס. במילים אחרות – אין שארית. במילים אחרות – $p\left(x\right)$ מחלק כל פולינום אחר שמאופס על ידי $A$ . זה גורר מייד ש- $p\left(x\right)$ הוא הפולינום היחיד שהוא גם מתוקן וגם מדרגה מינימלית שמאפס את $A$ : אם $t\left(x\right)$ מאותה דרגה כמו $p\left(x\right)$ אז מכך ש- $t\left(x\right)=p\left(x\right)q\left(x\right)$ ומשוויון הדרגות של $t\left(x\right),p\left(x\right)$ עולה שבהכרח $q\left(x\right)$ הוא פולינום ממעלה אפס, כלומר קבוע, כלומר $t\left(x\right)$ מתקבל על ידי כפל בקבוע של פולינום מתוקן, ולכן $t\left(x\right)$ לא יכול להיות פולינום מתוקן בעצמו.

ובכן, ל- $p\left(x\right)$ המדובר קוראים הפולינום המינימלי של $A$ . זה כבר הפולינום השני שאנחנו רואים שמוגדר עבור מטריצה $A$ – הראשון היה הפולינום האופייני של $A$ . קל לראות שהפולינום המינימלי נותן לנו יותר מידע במובן מסויים: למשל, למטריצות $\left[\begin{array}{cc}1 & 0\\0 & 1\end{array}\right]$ ו- $\left[\begin{array}{cc}1 & 1\\0 & 1\end{array}\right]$ (שאחת מהן לכסינה והשניה לא) יש את אותו פולינום אופייני, $\left(x-1\right)^{2}$ ; עם זאת, קל לראות בבדיקה ישירה שהפולינום המינימלי של המטריצה הראשונה הוא $\left(x-1\right)$ והפולינום המינימלי של המטריצה השניה הוא $\left(x-1\right)^{2}$ . הפולינום המינימלי הוא אכן כלי חשוב בהמשך הניתוח של צורות פשוטות שבהן ניתן להציג טרנספורמציות (או מטריצות פשוטות שאליהן מטריצה מסויימת דומה); למשל, נראה בהמשך שמטריצה היא לכסינה אם ורק אם הפולינום המינימלי שלה מורכב רק מגורמים לינאריים שונים, כלומר אין בו גורם מהצורה $\left(x-\lambda\right)^{k}$ עבור $k>1$ .

את הפולינום האופייני קל לחשב; לעומת זאת אין שיטה פשוטה לחישוב הפולינום המינימלי. עם זאת, אנחנו לא מגששים לגמרי בעלטה, בזכות משפט חשוב ומאוד לא טריוויאלי – משפט קיילי-המילטון. משפט זה אומר כי $A$ מאפסת את הפולינום האופייני שלה – אם מציבים את $A$ בתוך הפולינום האופייני מקבלים אפס. תכף נדבר על איך מוכיחים אותו, ובינתיים בואו נשים לב למסקנה מיידית ממנו (שהיא שקולה לו עצמו ולעתים קרובות מובאת בתור ניסוח המשפט) – הפולינום המינימלי מחלק את הפולינום האופייני. מכאן נובע שאם הפולינום האופייני הוא $\left(x-\lambda_{1}\right)^{k_{1}}\cdots\left(x-\lambda_{r}\right)^{k_{r}}$ אז הפולינום המינימלי הוא $\left(x-\lambda_{1}\right)^{t_{1}}\cdots\left(x-\lambda_{r}\right)^{t_{r}}$ כאשר $t_{i}\le k_{i}$ לכל $i$ (אותם שורשים, אולי עם ריבויים אלגבריים קטנים יותר). זה נותן לנו מייד אלגוריתם, לא הכי יעיל בעולם, למציאת הפולינום המינימלי: חשבו את הפולינום האופייני ואז תתחילו לעבור על פולינומים מהצורה $\left(x-\lambda_{1}\right)^{t_{1}}\cdots\left(x-\lambda_{r}\right)^{t_{r}}$ ותציבו בהם את $A$ (אפשר לעשות את המעבר הזה בצורה חכמה שתדרוש רק $k_{1}+k_{2}+\dots+k_{r}$ בדיקות לכל היותר – איך?).

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

משפט קיילי-המילטון

יפה. עכשיו אני רוצה להוכיח לכם שכל מטריצה מאפסת את הפולינום האופייני שלה. זה משפט שבמבט ראשון נראה טריוויאלי להוכחה: הפולינום האופייני של $A$ הוא $\left|xI-A\right|$ , אז נציב $x=A$ ונקבל מייד $\left|AI-A\right|=\left|A-A\right|=\left|0\right|=0$ . פשוט, לא? הו, לא, כל כך לא. ה"הוכחה" הזו שגויה לחלוטין, אבל היא מאוד, מאוד קורצת. קוראי הפוסט שחשבו בשלב זה או אחר של חייהם שהיא נכונה (בין אם כשלמדו לראשונה אלגברה לינארית ובין אם כרגע כשראו את המשפט לראשונה) מתבקשים להודיע על כך בתגובות.

טוב, למה ההוכחה הזו לא נכונה? ובכן, כי בביטוי $\left|xI-A\right|$ ה- $x$ הוא לא משתנה שמציבים בתוכו מטריצה, אלא משתנה שמציבים בתוכו סקלר. $xI$ היא לא "מה שמקבלים כשמכפילים את המטריצה שמוצבת ב- $x$ ב- $I$ " אלא "המטריצה שבה על האלכסון הראשי נמצא הסקלר שמציבים במקום $x$ וכל שאר הכניסות הן אפס". אם היינו מציבים את $A$ ב- $x$ אז $xI-A$ היה "מטריצה שבה כל כניסה על האלכסון הראשי מכילה עותק של $A$ , פחות $A$ עצמה" והביטוי הזה, שאנחנו לכאורה מצפים שיהיה שווה לאפס, בכלל לא היה מוגדר כי שתי המטריצות לא היו מאותו סדר. בקיצור, בלאגן. אז ההוכחה הנאיבית לא עובדת; מה כן עובד?

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

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

כעת אסמן ב- $K$ את קבוצת כל הפולינומים ב- $T$ מעל $\mathbb{F}$ , כלומר כל היצורים שמקבלים כשלוקחים פולינום ב- $\mathbb{F}\left[x\right]$ ומציבים בו את $T$ . שימו לב שאפשר לחבר ולכפול איברים בקבוצה הזו בדיוק כפי שעושים זאת עם פולינומים; במתמטית אומרים שהקבוצה הזו היא חוג. מבחינתנו במקרה הזה זה אומר ש- $K$ היא "כמעט שדה", פרט לכך שאי אפשר לחלק (אין הפיכים כפליים); באופן כללי חוגים יכולים להיות שונים עד מאוד משדות. כאן, בגלל ש- $K$ היא כמעט שדה, חלק לא מבוטל ממה שעשינו באלגברה לינארית מעל שדות עדיין עובד, אבל דברים כמו פתרון משוואות לינאריות כבר לא.

טוב, אקשן. בואו ניקח בסיס $B=\left\{ v_{1},\dots,v_{n}\right\}$ למרחב $V$ ונסמן $A=\left[T\right]_{B}$ . אז על פי הגדרה, $T\left(v_{i}\right)=\sum_{j=1}^{n}A_{ji}v_{i}$ (זוכרים? העמודה ה- $i$ של $A$ היא וקטור הקואורדינטות של $T\left(v_{i}\right)$ בבסיס $B$ ). את המשוואה הזו אפשר לכתוב גם כך: $\sum_{j=1}^{n}\left(\delta_{ij}T-A_{ji}I\right)v_{j}=0$ . כאן $\delta_{ij}$ היא הדלתא של קרונקר (שווה ל-1 רק אם $i=j$ ואחרת שווה ל-0), ואנחנו חושבים על כפל של $T$ ב- $v_{i}$ פשוט כהפעלה של $T$ על $v_{i}$ .

את המשוואה שלעיל קיבלנו לכל $1\le i\le n$ , כך שבעצם יש לנו $n$ משוואות. את כל זה אפשר לאגד למטריצה שחיה ב- $K_{n\times n}$ : $C_{ij}=\delta_{ij}T-A_{ji}I$ . הטענה הבסיסית היא ש- $\det C=p\left(T\right)$ , כאשר $p\left(x\right)$ הוא הפולינום האופייני של $T$ ; לא קשה לראות את זה אם מסתכלים על $C_{ij}$ שבה כל מופע של $T$ מוחלף ב- $x$ – הדטרמיננטה של זה היא בדיוק $\left|xI-A\right|$ , כלומר הפולינום האופייני של $A$ , שהיא מטריצה מייצגת של $T$ . במילים אחרות, כל מה שעשינו עד כה היה להסביר באופן פורמלי איך "להציב את $T$ ב- $x$ ", מה שמניב את המטריצה $C$ . אנחנו עדיין רוצים לראות שהדטרמיננטה של $C$ היא אפס, אבל צריך להיות זהירים כאן. הדטרמיננטה של $C$ היא לא סקלר. היא פולינום ב- $T$ . צריך לחדד את זה: $C$ מוגדרת לא מעל שדה $\mathbb{F}$ אלא מעל $K$ , שהוא אוסף הפולינומים ב- $T$ מעל $\mathbb{F}$ . לכן אי אפשר להשתמש מהשרוול בטענות שהוכחנו על דטרמיננטות כמו "אם המטריצה לא הפיכה אז הדטרמיננטה היא אפס"; צריך גישה קצת שונה.

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

כעת, מה שצריך לזכור הוא ש- $\det C$ יהיה בסופו של דבר פולינום ב- $T$ , ולכן טרנספורמציה לינארית מ- $V$ ל- $V$ . כדי להראות שטרנספורמציה היא טרנספורמציית האפס, די להראות שהיא מאפסת את כל האיברים של בסיס מסויים, למשל הבסיס $B$ . כלומר, די יהיה אם נראה ש- $\det C\left(v_{k}\right)=0$ לכל $k$ . זכרו שעל פי הבניה שלה, $C$ מקיימת $\sum_{j=1}^{n}C_{ij}v_{j}=0$ לכל $i$ . המשוואה הזו תיוותר נכונה גם אם נכפול אותה באיבר הקבוע $\left(\mbox{adj}C\right)_{ki}$ , כלומר $\sum_{j=1}^{n}\left(\mbox{adj}C\right)_{ki}C_{ij}v_{j}=0$ . עכשיו, אם נסכום את כל המשוואות שקיבלנו, לכל $i$ , נקבל:

$\sum_{i=1}^{n}\sum_{j=1}^{n}\left(\mbox{adj}C\right)_{ki}C_{ij}v_{j}=0$

ועם שינוי קטן של סדר הסכימה, זה אומר ש-

$\sum_{j=1}^{n}\left(\sum_{i=1}^{n}\left(\mbox{adj}C\right)_{ki}C_{ij}\right)v_{j}=0$

אבל מה זה $\sum_{i=1}^{n}\left(\mbox{adj}C\right)_{ki}C_{ij}$ אנחנו יודעים: זה בדיוק $\left(\left(\mbox{adj}C\right)C\right)_{kj}$ , ומכיוון ש- $\left(\mbox{adj}C\right)C=\det C\cdot I$ , הרי ש- $\left(\left(\mbox{adj}C\right)C\right)_{kj}=\delta_{kj}\det C$ . במילים אחרות, קיבלנו ש:

$\sum_{j=1}^{n}\left(\delta_{kj}\det C\right)v_{j}=0$

כלומר

$\det C\left(v_{k}\right)=0$

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

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

תגים: משפט קיילי-המילטון, מטריצה משולשית, ערכים עצמיים, פולינום מינימלי, פולינום אופייני
שייך לקטגוריות אלגברה לינארית | אין תגובות »