צורת ז'ורדן, התכל'ס

מבוא ובו סיפור חיים מרגש ומטריצות, הרבה מטריצות

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

נתחיל עם תיאור של מה זה בכלל. ההקשר הכללי שלנו הוא אלגברה לינארית, שאני מניח שכולכם מכירים; ההקשר הפרטני יותר הוא זה של צורות קנוניות של מטריצות/טרנספורמציות לינאריות, שגם אותו אני מניח שאתם מכירים. לכל הפחות, צריך להכיר את הנושא של לכסון מטריצות, כי זה בדיוק מה שצורת ז’ורדן באה להכליל. השורה התחתונה של מהי צורת ז’ורדן היא פשוטה להדהים. בלכסון מטריצות, הרעיון היה שאפשר למצוא עבור מטריצות \( A \) מסויימות מטריצה \( D \) אלכסונית ומטריצה \( P \) הפיכה, כך ש-\( D=P^{-1}AP \). בניסוח אחר: לטרנספורמציות לינאריות מסויימות היה אפשר למצוא בסיס שבו הן מיוצגות על ידי מטריצה \( D \) אלכסונית. הדגש היה על מסויימות; לא כל מטריצה/טרנספורמציה הייתה “לכסינה” בצורה הזו. צורת ז’ורדן באה לתת משהו שמתקיים לכל מטריצה או טרנספורמציה, בתנאי אחד: שהשדה שמעליו אנחנו עובדים הוא סגור אלגברית (אסביר את זה בהמשך). התוצאה היא כמעט אותה תוצאה, רק שבמקום \( D \) אלכסונית יש לנו \( J \) שהיא “כמעט אלכסונית” - פרט לאיברים על האלכסון, עשויים להופיע 1-ים במקומות שונים ומשונים על גבי האלכסון המשני שמעל האלכסון הראשי. זה הכל.

בשביל שתהיה לנו כל הזמן דוגמה כלשהי מול העיניים, הנה משהו קונקרטי:

\( A=\left(\begin{array}{rrrrrr}3 & 0 & 0 & 0 & 0 & 0\\0 & 2 & 0 & 0 & -1 & 0\\0 & 0 & 2 & 0 & 1 & 0\\0 & 0 & 0 & 2 & 0 & 1\\0 & 1 & 1 & 0 & 2 & 0\\0 & 0 & 0 & 0 & 0 & 2\end{array}\right) \)

\( J=\left(\begin{array}{rrrrrr}3 & 0 & 0 & 0 & 0 & 0\\0 & 2 & 1 & 0 & 0 & 0\\0 & 0 & 2 & 1 & 0 & 0\\0 & 0 & 0 & 2 & 0 & 0\\0 & 0 & 0 & 0 & 2 & 1\\0 & 0 & 0 & 0 & 0 & 2\end{array}\right) \)

\( P=\left(\begin{array}{rrrrrr}1 & 0 & 0 & 0 & 0 & 0\\0 & -1 & 0 & 1 & 0 & 0\\0 & 1 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0\\0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 1\end{array}\right) \)

שימו לב לצורה של \( J \). זה מה שנקרא מטריצת בלוקים. רובה אפסים, פרט לשלוש תת-מטריצות שהאלכסון הראשי שלהן נח על האלכסון הראשי של המטריצה: המטריצה \( \left(\begin{array}{c}3\end{array}\right) \) (מטריצה מסדר \( 1\times1 \)), המטריצה \( \left(\begin{array}{ccc}2 & 1 & 0\\0 & 2 & 1\\0 & 0 & 2\end{array}\right) \) והמטריצה \( \left(\begin{array}{cc}2 & 1\\0 & 2\end{array}\right) \). על מטריצה כזו אומרים שהיא מורכבת משלושה בלוקי ז'ורדן, שאחד מהם הוא מגודל 1 ומתאים לערך העצמי 3, השני הוא מגודל 3 ומתאים לערך העצמי 2, והשלישי הוא מגודל 2 ומתאים לערך העצמי 2. כלומר, בלוק ז’ורדן הוא בסך הכל מטריצה סקלרית (כלומר, כזו שבה על האלכסון הראשי יש ערך סקלרי קבוע כלשהו) ועוד מטריצה שבה על האלכסון המשני העליון יש 1-ים. כל צורת ז’ורדן היא משהו כזה: מטריצת בלוקים שבה הבלוקים הם בלוקי ז’ורדן. לב הרעיון הוא שכל מטריצה דומה למטריצת ז’ורדן יחידה, עד כדי זה שאפשר לשחק עם הסדר של העמודות. כלומר, אם נמיין את הבלוקים (למשל) על פי גודל הערך העצמי ואז על פי גדלי הבלוקים, נקבל ייצוג יחיד.

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

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

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

מציאת ערכים עצמיים זה עניין פשוט יחסית. נניח ש-\( A \) היא מטריצה מסדר \( n\times n \) מעל שדה \( \mathbb{F} \). אם \( Av=\lambda v \) אז על ידי העברת אגפים מקבלים ש-\( \left(A-\lambda I\right)v=0 \), כלומר \( v\in\ker\left(A-\lambda I\right) \). בפרט, זה אומר שהגרעין של המטריצה \( A-\lambda I \) אינו טריוויאלי, ולכן המטריצה הזו אינה הפיכה, ולכן הדטרמיננטה שלה היא אפס: \( \det\left(A-\lambda I\right)=0 \). זה מוביל להגדרה הבאה של הפולינום האופייני של מטריצה \( A \): \( p_{A}\left(x\right)=\det\left(xI-A\right) \). כאן \( xI-A \) היא מטריצה שהכניסות שלה לא שייכות סתם לאיזה שדה \( \mathbb{F} \) אלא ל-\( \mathbb{F}\left[x\right] \) - חוג הפולינומים מעל \( \mathbb{F} \). חישוב הדטרמיננטה עדיין מתבצע באותו האופן. מקבלים תמיד פולינום מתוקן (כלומר, כזה שבו המקדם המוביל הוא 1; זו הסיבה שלוקחים דטרמיננטה של \( xI-A \) ולא של \( A-xI \)) ממעלה \( n \). למשל, עבור המטריצה \( A \) בדוגמה שלנו, חישוב ישיר נותן \( p_{A}\left(x\right)=\left(x-3\right)\left(x-2\right)^{5} \). הפואנטה בפולינום האופייני הוא שהערכים העצמיים של \( A \) הם בדיוק השורשים של הפולינום הזה.

בדוגמה שלנו, הפולינום התפרק למכפלה של גורמים לינאריים, כלומר גורמים מהצורה \( \left(x-\lambda\right) \). חלק מהגורמים חזרו על עצמם - \( \left(x-2\right) \) הופיע 5 פעמים - אבל זו לא בעיה. מתי יש בעיה? אם יש לנו גורם שאנחנו לא יכולים לפרק יותר מעל השדה הנוכחי שלנו. נראה את הדוגמה הקלאסית לכך. נניח שאנחנו מעל השדה \( \mathbb{R} \) ונתבונן על המטריצה \( \left(\begin{array}{cc}0 & 1\\-1 & 0\end{array}\right) \). הפולינום האופייני שלה הוא \( \det\left(\begin{array}{cc}x & -1\\1 & x\end{array}\right)=x^{2}+1 \). מעל \( \mathbb{R} \) אי אפשר לפרק את הפולינום הזה לגורמים לינאריים. אם נעבור אל \( \mathbb{C} \) הפולינום יתפרק ל-\( \left(x-i\right)\left(x+i\right) \), ואלו אכן הערכים העצמיים של המטריצה הזו; אבל מעל \( \mathbb{R} \) אנחנו “תקועים”. כאן זה החיסרון היחיד של צורת ז’ורדן: אם הפולינום האופייני לא מתפרק לגורמים לינאריים, צורת ז’ורדן לא עובדת. אם נרחיב את השדה שמעליו אנחנו עובדים לשדה שבו הפולינום הזה מתפרק לגורמים לינאריים, אז מעל השדה המורחב הזה נוכל למצוא צורת ז’ורדן והכל יהיה טוב ויפה, אבל בלי זה אין על מה לדבר. לכן בכל הדיון על צורות ז’ורדן מניחים שהפולינום האופייני של המטריצה שלנו כן מתפרק לגורמים לינאריים (לפעמים פשוט מניחים שעובדים מעל השדה \( \mathbb{C} \) שכל פולינום מעליו מתפרק לגורמים לינאריים וחסל; זהו המשפט היסודי של האלגברה).

לכל שורש \( \lambda \) של הפולינום האופייני מגדירים את הריבוי האלגברי שלו להיות מספר הפעמים שבהן הגורם \( x-\lambda \) מופיע בפולינום האופייני. בדוגמה שלנו הריבוי האלגברי של 3 הוא 1 והריבוי האלגברי של 2 הוא 5. כמו כן, מגדירים את הריבוי הגאומטרי של \( \lambda \) בתור \( \dim\ker\left(A-\lambda I\right) \), שזו דרך אחרת לומר “המימד של תת-המרחב של הוקטורים העצמיים שמתאימים לערך \( \lambda \)”.

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

צורת ז’ורדן באה לטפל בסיטואציה שבה הריבוי הגיאומטרי קטן מהריבוי האלגברי. במצב הזה, אין לנו “מספיק” וקטורים עצמיים כדי לקבל בסיס, אז אנחנו מתחילים לחפש וקטורים במקומות נוספים. הנה הרעיון: אם עבור וקטורים עצמיים עבור \( \lambda \) חיפשנו איברים של \( \ker\left(A-\lambda I\right) \), הרי שעכשיו אנחנו נחפש איברים של \( \ker\left(A-\lambda I\right)^{k} \) עבור \( k\ge1 \). אבל לא מספיק לבחור “סתם” איברים של המרחבים הללו; צריך לבצע את הבחירה הזו בצורה זהירה למדי כדי לוודא שאנחנו אכן תופסים את כל מה שצריך לתפוס. אני אתן כבר עכשיו את הרעיון על קצה המזלג:

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

זה, על רגל אחת, האלגוריתם שלנו. הוא לא שונה כל כך ממה שקרה בסיטואציה של לכסון מטריצות: שם התחלנו מ-\( k=1 \), ולכן בסך הכל חיפשנו כמה שיותר וקטורים ב-\( \ker\left(A-\lambda I\right) \) כאשר תנאי ה”אינם שייכים” היה בדיוק התנאי שהוקטורים העצמיים שונים מ-0.

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

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

בהינתן מטריצה \( A \), הפולינום המינימלי \( m_{A}\left(x\right) \) שלה הוא פולינום מתוקן שמקיים \( m_{A}\left(A\right)=0 \) והוא מחלק כל פולינום אחר שמאפס את \( A \) - במילים יותר פורמליות, \( m_{A}\left(x\right) \) הוא היוצר של אידאל הפולינומים שמאפסים את \( A \) בחוג \( \mathbb{F}\left[x\right] \). העובדה שקיים כזה פולינום מובטחת מכך ש-\( \mathbb{F}\left[x\right] \) הוא תחום ראשי; לא אכנס כאן לפרטים. כלי מועיל מאוד בדרך למציאת הפולינום המינימלי הוא משפט קיילי המילטון שאומר ש-\( p_{A}\left(A\right)=0 \), כלומר הפולינום האופייני של מטריצה מאפס אותה, ולכן הפולינום המינימלי מחלק אותו; אפשר להראות שהפולינום המינימלי הוא בעל אותם גורמים לינאריים בדיוק כמו הפולינום האופייני, רק שהריבוי שלהם עשוי להיות קטן יותר (כלומר, מקטינים חלק מהחזקות, אבל לא מורידים חזקה כלשהי ל-0). לכן אפשר פשוט להציב את \( A \) בכל מני מועמדים אפשריים ולראות מה קורה (בהמשך נראה שיש דרך חכמה יותר למצוא את הפולינום המינימלי). בדוגמה שלנו, \( m_{A}\left(x\right)=\left(x-3\right)\left(x-2\right)^{3} \), כלומר הגורם \( \left(x-3\right) \) לא נעלם (אסור לו להיעלם) והגורם \( \left(x-2\right)^{5} \) איבד 2 ממעריך החזקה שלו והפך להיות \( \left(x-2\right)^{3} \).

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

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

בואו נראה מה שלושת אלו אומרים בדוגמה שלנו. עבור \( \lambda=3 \) קיים בפולינום האופייני הגורם \( \left(x-3\right) \) שהוא ממעלה 1, כלומר הריבוי האלגברי הוא 1 ולכן גם הריבוי הגאומטרי הוא 1. המסקנה היא שב-\( J \) יהיה בלוק ז’ורדן יחיד שמתאים ל-\( \lambda=3 \) ושהגודל שלו יהיה 1. זה אכן מה שקורה.

לגבי הערך העצמי \( \lambda=2 \), הריבוי האלגברי שלו הוא 5, ולכן סכום גדלי כל הבלוקים שלו יהיה 5. כמה בלוקים כאלו יהיו? בשביל זה צריך להפשיל שרוולים ולמצוא את הריבוי הגיאומטרי, כלומר לחשב את \( \dim\ker\left(A-2I\right) \), מה שאפשר לעשות על ידי דירוג מטריצות סטנדרטי. מקבלים ריבוי גיאומטרי 2, ולכן יהיו שני בלוקי ז’ורדן. זה זמן לא רע לעצור ולחשוב מה הם יכולים להיות. סכום הגדלים שלהם יהיה 5; בכמה דרכים אפשר לכתוב את 5 בתור סכום של שני מספרים טבעיים חיוביים? או \( 5=1+4 \) או \( 5=2+3 \). אלא שהמקרה הראשון נפסל בשל הפולינום המינימלי; הריבוי של \( \lambda=2 \) בפולינום המינימלי הוא 3 ולכן לא ייתכן שיש בלוק מגודל 4. לכן בהכרח האפשרות הנוספת היא הנכונה - יהיה לנו בלוק אחד מגודל 3 ובלוק אחר מגודל 2, וזה בדיוק מה שיש לנו. הנה כי כן, רק מהיכרות עם הפולינום האופייני והמינימלי של \( A \) כבר הבנו בדיוק איך צורת ז’ורדן שלה תיראה. אם אנחנו רוצים למצוא את \( P \) המז’רדנת, נצטרך לעבוד עוד קצת.

האם המידע שכתבתי למעלה זה כל המידע שאפשר לחלץ על צורת ז’ורדן מבלי לחשב את \( P \) במפורש? ובכן, לא. שמרתי את הדבר המסובך ביותר לסוף:

• לכל ערך עצמי \( \lambda \), מספר בלוקי ז'ורדן המתאימים ל-\( \lambda \) מגודל \( k \) לפחות הוא ההפרש \( \dim\ker\left(A-\lambda I\right)^{k}-\dim\ker\left(A-\lambda I\right)^{k-1} \).

עוד רגע אסביר את ההגיון מאחורי התכונה הזו, ויש בהחלט הגיון, אבל לפני כן בואו נעזור קצת למי שה”לפחות” הזה מציק לו ורוצה לדעת מה המספר בדיוק. הטיעון הוא קצת חמקמק, אז הנה דוגמה: נניח שאני יודע שיש בדיוק 5 בלוקים מגודל שהוא לפחות 3, ואני יודע שיש 2 בלוקים מגודל שהוא לפחות 4, כמה בלוקים מגודל בדיוק 3 יש? אני מקווה שאתם צועקים עלי “שלושה!”. איך ידעתם? כי אפשר לראות שבמעבר בין בלוקים מגודל לפחות 3 אל גודל לפחות 4 “איבדנו” 3 בלוקים; אלו חייבים להיות הבלוקים שגודלם הוא בדיוק 3.

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

• לכל ערך עצמי \( \lambda \), מספר בלוקי ז'ורדן המתאימים ל-\( \lambda \) מגודל \( k \) בדיוק הוא ההפרש \( 2\dim\ker\left(A-\lambda I\right)^{k}-\dim\ker\left(A-\lambda I\right)^{k+1}-\dim\ker\left(A-\lambda I\right)^{k-1} \).

תעשו לעצמכם את החשבון ותראו שאכן זה מה שיוצא.

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

עכשיו אני רוצה לעבור לדבר על האופן שבו מוצאים את \( P \), מה שישתלב יפה עם הסבר לגבי המקום שממנו כל התכונות הללו מגיעות מלכתחילה. כשמדברים על \( P \) קצת יותר קל לדעתי לחשוב על \( A \) לא בתור מטריצה שרוצים למצוא אחת שדומה לה, אלא בתור טרנספורמציה לינארית שאנחנו מחפשים בסיס \( P \) למרחב שבו היא מיוצגת על ידי מטריצה נחמדה - מטריצת בלוקים. מה הרעיון של מטריצת בלוקים שמייצגת טרנספורמציה לינארית? שכל בלוק מייצג תת-מרחב אינוריאנטי של הטרנספורמציה. אם \( T:V\to V \) היא טרנספורמציה ו-\( W \) הוא תת-מרחב של \( V \), אז \( W \) הוא \( T \)-אינוריאנטי אם \( T\left(W\right)\subseteq W \). זה אומר שאם כחלק מהבסיס \( P \) שלנו יש בסיס ל-\( W \), ושאר אברי \( P \) לא שייכים ל-\( W \), אז כשמייצגים את \( T \) באמצעות \( P \) נקבל בלוק שמתאים בדיוק ל-\( W \). בואו נראה את זה עם דוגמה פשוטה. נניח ש-\( V=W\oplus U \) כך ש-\( W,U \) הם \( T \)-אינוריאנטים, וניקח בסיס \( P=\left\{ w_{1},w_{2},u_{1},u_{2}\right\} \) שמורכב מאיחוד בסיסים של \( W,U \). לצורך הקונקרטיות נניח ש-\( T\left(w_{1}\right)=w_{1}+w_{2} \) ו-\( T\left(w_{2}\right)=2w_{1}-w_{2} \), וש-\( T\left(u_{1}\right)=3u_{2} \), \( T\left(u_{2}\right)=u_{1}-u_{2} \). אם נשב ונחשב את המטריצה המייצגת של \( T \) על פי \( P \) נקבל את המטריצה הבאה:

\( \left(\begin{array}{cccc}1 & 2 & 0 & 0\\1 & -1 & 0 & 0\\0 & 0 & 0 & 1\\0 & 0 & 3 & -1\end{array}\right) \)

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

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

\( \left(\begin{array}{ccc}\lambda & 1 & 0\\0 & \lambda & 1\\0 & 0 & \lambda\end{array}\right) \)

בואו נאמר שהבסיס שיצר אותו הוא \( \left\{ w_{1},w_{2},w_{3}\right\} \). עכשיו אנחנו מבינים את המשמעות של בלוק כזה - הוא אומר שהטרנספורמציה פועלת באופן הבא:

\( T\left(w_{1}\right)=\lambda w_{1} \)

\( T\left(w_{2}\right)=w_{1}+\lambda w_{2} \)

\( T\left(w_{3}\right)=w_{2}+\lambda w_{3} \)

נסתכל למשל על המשוואה האחרונה. אפשר לכתוב אותה גם בתור \( T\left(w_{3}\right)=w_{2}+\lambda I\left(w_{3}\right) \) כאשר \( I \) היא פונקצית הזהות. העברת אגפים תיתן \( w_{2}=\left(T-\lambda I\right)w_{3} \) (כן, אני קצת משנה את תפקידי הסוגריים, אתם חזקים, תתמודדו). באופן דומה, \( w_{1}=\left(T-\lambda I\right)w_{2} \) ואילו \( \left(T-\lambda I\right)w_{1}=0 \). מה שזה אומר בפועל הוא שתת-המרחב האינוריאנטי שנותן לו את בלוק הז’ורדן הזה נבנה מתוך וקטור \( w_{3} \) שאנחנו מוצאים בדרך קסם כלשהי (שעוד מעט תוסבר), ועליו אנחנו מפעילים שוב ושוב את \( \left(T-\lambda I\right) \) עד שלבסוף אנחנו מגיעים אל 0 (או, אם תרצו, עד שאנחנו מגיעים אל וקטור עצמי של \( T \) המתאים לערך העצמי \( \lambda \)). \( w_{3} \) הוא אותו וקטור ציקלי שהזכרתי קודם. שימו לב שכדי שהצורה היפה של בלוק ז’ורדן תתקבל אנחנו צריכים להקפיד על הסדר שבו הוקטורים מופיעים בבסיס: הוקטור הציקלי מופיע אחרון, והוקטורים שמתקבלים ממנו מופיעים לפניו, כשהסדר הוא מההפעלה האחרונה אל ההפעלה הראשונה.

זה מה שתיארתי קודם במה שקראתי לו “הרעיון על קצה המזלג”; עכשיו אנחנו גם מבינים למה צריך לעשות את זה. רק נשאר להבין איפה מוצאים את הוקטורים הציקליים המדוברים. ובכן, בואו נמשיך עוד קצת עם הדוגמה הנוכחית שלנו. ראינו ש-\( \left(T-\lambda I\right)w_{1}=0 \). דרך אחרת לכתוב את זה היא \( w_{1}\in\ker\left(T-\lambda I\right) \). ראינו גם ש-\( w_{1}=\left(T-\lambda I\right)w_{2} \), ולכן אם נפעיל את \( \left(T-\lambda I\right) \) על שני האגפים נקבל ש-\( \left(T-\lambda I\right)^{2}w_{2}=0 \), כלומר \( w_{2}\in\ker\left(T-\lambda I\right)^{2} \). בדומה \( w_{3}\in\ker\left(T-\lambda I\right)^{3} \). העיקרון הזה נכון באופן כללי: לכל ערך עצמי \( \lambda \) של \( T \), וקטור ציקלי שיוצר תת-מרחב מגודל \( k \) עשוי להסתתר לנו בתוך \( \ker\left(T-\lambda I\right)^{k} \). אז אלו המקומות שבהם אנחנו מחפשים את הוקטורים הציקליים שלנו. בואו נדבר שניה טרמינולוגיה: וקטור עצמי היה וקטור \( w\in\ker\left(T-\lambda I\right) \); לכן שם סביר לוקטור \( w\in\ker\left(T-\lambda I\right)^{k} \) הוא וקטור עצמי מוכלל. אם כדי ללכסן מטריצה חיפשנו בסיס שמורכב מוקטורים עצמיים שלה, כאן אנחנו מחפשים בסיס שמורכב מוקטורים עצמיים מוכללים שלה. הקושי הוא שלא כל “סתם” בסיס של וקטורים עצמיים מוכללים יעבוד; חייבים כזה שנבנה מתוך וקטורים עצמיים מוכללים ציקליים.

מבחינה חישובית, בינתיים הכל מאוד קל: למצוא איברים ב-\( \ker\left(T-\lambda I\right)^{k} \) זה בפועל לחשב חזקה של מטריצה סקלרית ולדרג אותה. להפעיל את \( \left(T-\lambda I\right) \) על וקטורים זה קל מאוד. אבל עדיין יש דברים לא ברורים. בתור התחלה, מאיפה מתחילים? נניח שאני יודע ש-\( \lambda \) הוא ערך עצמי של \( T \), אז אני הולך לחפש וקטור ציקלי ב-\( \ker\left(T-\lambda I\right)^{k} \). אבל עבור איזה \( k \)? שאני אקח באקראי \( k=1,000 \)? ובכן, כמובן שלא. ככל שמגדילים את \( k \), כך גם המרחב \( \ker\left(T-\lambda I\right)^{k} \) גדל, עד שמגיעים לנקודת שבת. אפשר להתחיל את החיפושים ממנה. לא קשה לראות שה-\( k \) שמתאים לנקודת השבת הזו הוא בדיוק החזקה \( k \) של הגורם \( \left(x-\lambda\right) \) בפולינום המינימלי של \( T \), מה שמחזיר אותנו לתכונות שראינו קודם. וקטור ציקלי שנמצא ב-\( \ker\left(T-\lambda I\right)^{k} \) יוצר בלוק מגודל לכל היותר \( k \); לכל היותר, כי הוא עשוי להיות שייך גם ל-\( \ker\left(T-\lambda I\right)^{k-1} \) ואז הסדרה שהוא ייצור תהיה מאורך קטן מ-\( k \). לעומת זאת, אם הוא שייך ל-\( \ker\left(T-\lambda I\right)^{k} \) אבל לא שייך ל-\( \ker\left(T-\lambda I\right)^{k-1} \) מובטח לנו שגודל הבלוק שהוא ייצור הוא בדיוק \( k \). זה מסביר לנו באופן מלא את התכונה של “גודל הבלוק המקסימלי שווה לחזקה של הגורם בפולינום המינימלי” וגם את התכונות המסובכות אחר כך שהתבססו על המימדים של \( \ker\left(T-\lambda I\right)^{k} \). כמו כן, מכיוון שהסדרה שיוצר וקטור ציקלי מסתיימת תמיד בוקטור עצמי, הרי שמספר הסדרות של וקטורים ציקליים בלתי תלויים - שהוא בדיוק מספר הבלוקים - יהיה שווה למספר הוקטורים העצמיים הבלתי תלויים, כלומר לריבוי הגיאומטרי של \( \lambda \). הכל מתחבר!

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

\( \left(\begin{array}{ccccc}2 & 1 & 0 & 0 & 0\\0 & 2 & 0 & 0 & 0\\0 & 0 & 2 & 1 & 0\\0 & 0 & 0 & 2 & 0\\0 & 0 & 0 & 0 & 2\end{array}\right) \)

זה אווילי, כי המטריצה הזו כבר נמצאת בצורת ז’ורדן. יש לנו שלושה בלוקים שכולם מתאימים לערך העצמי 2: שניים מגודל 2 ואחד מגודל 1. עדיין, בואו נראה מה קורה כשלוקחים את הפרוצדורה ומפעילים אותה על המקרה הזה. לא קשה לבדוק ולראות ש-\( \left(A-2I\right)^{2} \) היא מטריצת האפס, ולכן \( \ker\left(A-2I\right)^{2}=\mathbb{C}^{5} \) - המרחב כולו. יש לנו לכאורה חופש בחירה מוחלט לוקטורים שמתחשק לנו לקחת. אבל בפועל יש לנו שתי מגבלות. ראשית, אנחנו רוצים וקטורים שלא שייכים ל-\( \ker\left(A-2I\right) \), כי וקטורים כאלו יוצרים לנו בלוק מגודל 1 (כלומר, הסדרה שהם יוצרים תהיה מאורך 1 ותכיל רק את עצמם). זה מצמצם את חופש הבחירה שלנו: \( \ker\left(A-2I\right)=\left\{ \left(x,0,y,0,z\right)\ |\ x,y,z\in\mathbb{C}\right\} \) ולכן כל וקטור שניקח יהיה חייב להיות מהצורה \( \left(a_{1},a_{2},a_{3},a_{4},a_{5}\right) \) כך ש-\( a_{2}\ne0 \) או \( a_{4}\ne0 \).

יודעים מה? זה לא נשמע כמו מגבלה כל כך רצינית. לכאורה עדיין יש לנו המון וקטורים שאפשר לקחת. אבל האתגר הוא לקחת וקטורים שהשרשראות שהם יוצרים לא “יתנגשו”. בואו נראה מקרה שבו זה כן קורה. בתור וקטור אחד ניקח את \( v=\left(0,1,0,0,0\right) \), אבל בתור הוקטור השני, במקום לקחת את \( \left(0,0,0,1,0\right) \) המתבקש, אני אקח לצורך הדוגמה דווקא את \( u=\left(1,1,0,0,0\right) \). למה לא? שני הוקטורים הללו, \( v,u \), הם בלתי תלויים לינארית; המרחב שהם פורשים הוא ממימד 2. מה אמור לרמוז לנו ש”אסור” לקחת את \( u \)?

ובכן, בואו נסתכל על השרשרת ששני אלו מייצרים: \( \left(A-2I\right)v=\left(A-2I\right)u=\left(1,0,0,0,0\right) \). קיבלנו התנגשות באיבר השני בשרשרת. מה שזה אומר לנו בפועל הוא ששני הוקטורים הציקליים \( u,v \) מתאימים שניהם לאותו הבלוק. אני יכול להחליף את אחד מהם בשני ובסופו של דבר עדיין נקבל בסיס שנותן לנו את אותה צורת ז’ורדן. אבל אני לא יכול לדחוף ל-\( P \) את שניהם ביחד. כי כזכור, כדי שהעסק יעבוד אנחנו צריכים לדחוף כל וקטור ציקלי ואת כל מי שהוא יוצר. אז מה נעשה עם \( \left(1,0,0,0,0\right) \)? נדחוף אותו פעמיים? ככה נקבל מטריצה \( P \) לא הפיכה; “בסיס” \( P \) שהוא תלוי לינארית כי אותו איבר מופיע בו פעמיים. אז אולי נוסיף את \( \left(1,0,0,0,0\right) \) רק פעם אחת? אבל אז נקבל מעט מדי וקטורים עצמיים מוכללים מכדי לקבל בסיס. בקיצור, אסור באיסור חמור לקבל התנגשות. האופןש בו יכלנו לזהות ש-\( u \) הוא רע הוא על ידי כך שהיינו מזהים שאי שם בהמשך הוא ייתן לנו התנגשות עם \( v \).

מה הסיבה שבגללה קיבלנו התנגשות שכזו? ובכן, אם תחשבו על זה רגע, \( u=v+\left(1,0,0,0,0\right) \). כלומר, אפשר לחשוב על \( u \) הרע שלנו בתור \( v \) הטוב ועוד “תוספת”. עכשיו, אם נפעיל את \( \left(A-\lambda I\right) \) על \( u \), אז בזכות הלינאריות של טרנספורמציות לינאריות נקבל ש-\( \left(A-\lambda I\right)u=\left(A-\lambda I\right)v+\left(A-\lambda I\right)\left(1,0,0,0,0\right) \). אלא ש-\( \left(1,0,0,0,0\right)\in\ker\left(A-\lambda I\right) \) ולכן התוספת “תתבטל”. ונקבל התנגשות.

זה הרעיון שמתאר את הבעיה באופן כללי: שני וקטורים \( u,v\in\ker\left(A-\lambda I\right)^{k} \) הם “בעייתיים” אם מתקיים ש-\( u-v\in\ker\left(A-\lambda I\right)^{k-1} \). פירוש הדבר הוא שאם נפעיל את \( \left(A-\lambda I\right) \) עליהם \( k-1 \) פעמים, מתישהו נקבל התנגשות - לכן לא נצליח לקבל \( k \) וקטורים שונים. לתכונה הזו של ה”בעייתיות” יש טרמינולוגיה מאוד סטנדרטית במתמטיקה שבאה לתאר אותה, אם כי ייתכן שלרובכם היא לא מוכרת בהקשר של מרחבים וקטוריים: אומרים ש-\( u,v \) הם שקולים מודולו \( \ker\left(A-\lambda I\right)^{k-1} \). הטרמינולוגיה הזו מאפשרת לנו לנסח מאוד באלגנטיות את מה שצריך לעשות כדי למצוא את הוקטורים הציקליים של \( \ker\left(A-\lambda I\right)^{k} \): אנחנו צריכים למצוא בסיס עבור מרחב המנה \( \ker\left(A-\lambda I\right)^{k}/\ker\left(A-\lambda I\right)^{k-1} \), ואז להעביר את הבסיס הזה לקבוצת וקטורים ב-\( \ker\left(A-\lambda I\right)^{k} \). אני אסביר את הטרמינולוגיה הזו בהמשך, כי לטעמי זו הדרך הנכונה לתאר את מה שצריך לעשות, אבל כדי לא לכפות אותה עליכם אני אציג קודם כל את האלגוריתם הכללי עם הניסוחים המסורבלים שכופה עלינו ההתעלמות מהטרמינולוגיה הזו.

בואו רק נשלים את דוגמת הצעצוע שלנו. אני מניח שאנחנו מסכימים ששני הוקטורים הציקליים שעלינו לבחור ב-\( \ker\left(A-2I\right)^{2} \) הם הוקטורים \( v_{2}=\left(0,1,0,0,0,0\right) \) ו-\( u_{2}=\left(0,0,0,1,0\right) \). סימנתי אותם עם אינדקס 2, כי כזכור, בבסיס הסדור \( P \) שאני בונה הם מופיעים אחרי מי שמתקבלים מהם. ומי מתקבלים מהם?

\( v_{1}=\left(A-2I\right)v_{2}=\left(1,0,0,0,0\right) \)

\( u_{1}=\left(A-2I\right)u_{2}=\left(0,0,1,0,0\right) \)

אם כן, כרגע הבסיס הסדור שלי כולל את האיברים \( \left\{ v_{1},v_{2},u_{1},u_{2}\right\} \). עדיין חסר לי וקטור עצמי מוכלל אחד. האם פספסתי מישהו ב-\( \ker\left(A-2I\right)^{2} \)? התשובה היא לא. דרך פשוטה להיות בטוחים בכך: \( \dim\ker\left(A-2I\right)^{2}-\dim\ker\left(A-2I\right)=2 \) ולכן אני מצפה למצוא רק 2 וקטורים ציקליים “בלתי תלויים” שם. אם כן, מה נשאר? כרגע יש לי שני וקטורים בלתי תלויים ב-\( \ker\left(A-2I\right) \), אבל \( \dim\ker\left(A-2I\right)=3 \), כך שחסר לי וקטור. אז מה שאני אעשה הוא לקחת את הקבוצה \( \left\{ u_{1},v_{1}\right\} \), ולהשלים אותה לבסיס של \( \ker\left(A-2I\right) \). זה יניב לי את הוקטור \( \left(0,0,0,0,1\right) \), וכך קיבלנו לבסוף את \( P \) שלנו, שהיא פשוט הבסיס הסטנדרטי (מה שהוא לחלוטין לא מפתיע, כמובן, שהרי המטריצה שהתחלתי ממנה כבר הייתה בצורת ז’ורדן). ומה היה קורה אם הייתי בוחר, למשל, \( v_{2}=\left(1,1,0,0,0\right) \)? הייתי מקבל \( v_{1}=\left(1,0,0,0,0\right) \) ולכן שאר הבסיס שלי לא היה משתנה. אז הייתי מקבל בסיס קצת שונה, אבל הייצוג של המטריצה בבסיס הזה היה עדיין אותו ייצוג. באופן כללי בהינתן מטריצה \( A \), יש הרבה מטריצות מז’רדנות \( P \), כלומר הרבה מטריצות \( P \) שונות שעבורן \( P^{-1}AP=J \) כאשר \( J \) היא אותה צורת ז’ורדן של \( A \). אין עם זה בעיה.

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

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

נתחיל עם האלגוריתם הכללי. נתונה מטריצה \( A \) ואנחנו רוצים למצוא את צורת ז’ורדן שלה ומטריצה מז’רדנת. מה עושים?

1. נחשב את הפולינום האופייני \( p_{A}\left(x\right)=\det\left(xI-A\right) \) ונפרק אותו לגורמים לינאריים \( p_{A}\left(x\right)=\left(x-\lambda_{1}\right)^{k_{1}}\cdots\left(x-\lambda_{n}\right)^{k_{n}} \). אם הפולינום לא מתפרק לגורמים לינאריים מעל השדה אפשר לשכוח מצורת ז'ורדן. השורשים של הפולינום האופייני נקראים ערכים עצמיים של \( A \).
2. לכל ערך עצמי \( \lambda \) נסמן לצורך נוחות ב-\( B_{\lambda} \) את המטריצה \( B_{\lambda}\triangleq A-\lambda I \), וכעת:
   1. נחשב את \( \dim\ker B_{\lambda}^{k} \) עבור \( k=1,2,\dots \) עד אשר נמצא \( k \) כך ש-\( \dim\ker B_{\lambda}^{k+1}=\dim\ker B_{\lambda}^{k} \) (באופן שקול, אפשר למצוא את הפולינום המינימלי של \( A \) בדרך אחרת; \( k \) המבוקש היא החזקה של הגורם \( \left(x-\lambda\right) \)).
   2. נבנה באופן אינדוקטיבי סדרה של קבוצות \( P_{k}^{\lambda},P_{k-1}^{\lambda},P_{k-2}^{\lambda},\dots,P_{1}^{\lambda} \) באופן הבא: בתחילה, \( P_{k}^{\lambda}=\emptyset \). כעת, לכל \( t=k,k-1,\dots,1 \):
      1. נוסיף ל-\( P_{t}^{\lambda} \) איברים עד שיהיו בה \( \dim\ker B_{\lambda}^{t}-\dim\ker B_{\lambda}^{t-1} \) איברים בסך הכל, כך שאין שני איברים שונים \( v,u\in P_{t}^{\lambda} \) עבורם \( v-u\in\ker B_{\lambda}^{t-1} \). לאיברים שמתווספים בשלב הזה נקרא וקטורים ציקליים.
      2. לכל \( v\in P_{t}^{\lambda} \) נוסיף ל-\( P_{t-1}^{\lambda} \) את \( B_{\lambda}\cdot v \) (לוקטורים הללו לא נקרא וקטורים ציקליים).
   3. נגדיר \( P^{\lambda}=\bigcup_{t=1}^{k}P_{t}^{\lambda} \).
3. נגדיר \( P=\bigcup_{\lambda}P^{\lambda} \).
4. נסדר את איברי ב-\( P \) באופן הבא: נגדיר סדר כלשהו על הערכים העצמיים וכל הוקטורים שהתקבלו מערך עצמי \( \lambda \) יופיעו ביחד בהתאם לסדר הזה, ונגדיר סדר כלשהו על הוקטורים הציקליים שהתגלו במהלך האלגוריתם. אם \( v \) הוא וקטור ציקלי ששייך ל-\( P_{t}^{\lambda} \) אז נסדר את האיברים \( B^{t}v,B^{t-1}v,\dots,Bv,v \) בסדר הזה (כך ש-\( B^{t}v \) ראשון ו-\( v \) אחרון).

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

החלק היותר מעניין הוא זה שבו צריך לקחת את \( P_{t}^{\lambda} \), שאולי כבר יש בה כמה וקטורים שהגיעו מהשלב הקודם, ולהרחיב אותה כך שיהיו בה \( \dim\ker B_{\lambda}^{t}-\dim\ker B_{\lambda}^{t-1} \) וקטורים שהם “בלתי תלויים” במובן שאמרתי קודם - לא מתקיים \( v-u\in\ker B_{\lambda}^{t-1} \) לאף זוג וקטורים בתוכה. התשובה הפשוטה ביותר שאני מכיר היא זו: קחו בסיס ל-\( \ker B_{\lambda}^{t-1} \). הוסיפו לו את איברי \( P_{t}^{\lambda} \) הנוכחיים. קיבלתם קבוצה של וקטורים ב-\( \ker B_{\lambda}^{t} \) ואפשר להוכיח שהם תמיד יהיו בלתי תלויים לינארית. הרחיבו אותה לבסיס של \( \ker B_{\lambda}^{t} \). אברי הבסיס החדשים הם בדיוק האיברים שאתם רוצים להוסיף ל-\( P_{t}^{\lambda} \). כמובן, אני מניח שאתם כבר יודעים לפתור את בעיית ה”השלמה של קבוצת וקטורים לבסיס” - אבל זו בעיה הרבה יותר סטנדרטית באלגברה לינארית ולא אדבר עליה כאן.

למה זה עובד? פשוט מאוד: כי אם עבור \( v,u\in P_{t}^{\lambda} \) מתקיים ש-\( v-u\in\ker B_{\lambda}^{t-1} \), אז אפשר לכתוב את \( v-u \) כצירוף לינארי של הבסיס של \( \ker B_{\lambda}^{t-1} \), כלומר \( v-u=\sum\rho_{i}b_{i} \). נעביר אגפים והופס, \( v-u-\sum\rho_{i}b_{i}=0 \), קיבלנו צירוף לינארי של אברי בסיס של \( \ker B_{\lambda}^{t} \) שנותן 0. זה אפשרי רק אם כל המקדמים בצירוף הלינארי הזה הם 0, כלומר בפרט \( v-u=0 \), כלומר \( v=u \). אז רק רגע, אם זה כל כך פשוט, למה לא כתבתי את זה באלגוריתם מלכתחילה? ובכן, בגלל שאם אני הייתי קורא את זה באלגוריתם מלכתחילה, לא הייתי מבין מה לעזאזל הרעיון שמאחורי השלב הזה. אני מעדיף שהאלגוריתם יציג את הרעיון ולא את הפרטים של הביצוע הטכני שלו. פרט לכך, אל תדאגו - בניסוח עם מרחבי מנה, יופיע שם בדיוק הדבר הזה.

בואו נעבור, אם כן, לפתרון של הדוגמה מתחילת הפוסט. אקפוץ על השלב של חישוב הפולינום האופייני של \( A \): כפי שאמרתי קודם, מקבלים \( p_{A}\left(x\right)=\left(x-3\right)\left(x-2\right)^{5} \). סביר להתחיל עם הערך העצמי 3. עבורו, המטריצה \( B=\left(A-3I\right) \) יוצאת

\( B=\left(\begin{array}{rrrrrr}0 & 0 & 0 & 0 & 0 & 0\\0 & -1 & 0 & 0 & -1 & 0\\0 & 0 & -1 & 0 & 1 & 0\\0 & 0 & 0 & -1 & 0 & 1\\0 & 1 & 1 & 0 & -1 & 0\\0 & 0 & 0 & 0 & 0 & -1\end{array}\right) \)

דירוג מטריצות סטנדרטי יעביר אותנו למטריצה הבאה:

\( \left(\begin{array}{rrrrrr}0 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 1\end{array}\right) \)

ולכן \( \ker B=\mbox{span}\left\{ e_{1}\right\} \) כאשר \( e_{1}=\left(1,0,0,0,0,0\right) \) הוא וקטור של הבסיס הסטנדרטי. אם נחזור על התעלול עבור \( B^{2} \) נגלה שנקבל את אותו הדבר בדיוק - \( \ker B^{2}=\ker B^{1} \). זה כמובן לא אמור להפתיע אותנו בשום צורה - אנחנו יודעים שהגורם של \( \left(x-3\right) \) בפולינום האופייני הוא 1, ולכן זה גם הגורם בפולינום המינימלי, ולכן המרחב \( \ker B^{2} \) ממילא לא רלוונטי עבורנו. אם כן, אין לנו כמעט מה לעשות כאן: ב-\( P \) הסופי שלנו יהיה את \( e_{1} \), ואפשר לעבור לטפל בערך העצמי האחר, \( \lambda=2 \).

נגדיר אם כן \( B=\left(A-2I\right) \), נחשב חזקות של \( B \) ונקבל את המטריצות

\( B=\left(\begin{array}{rrrrrr}1 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & -1 & 0\\0 & 0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 1\\0 & 1 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\end{array}\right),B^{2}=\left(\begin{array}{rrrrrr}1 & 0 & 0 & 0 & 0 & 0\\0 & -1 & -1 & 0 & 0 & 0\\0 & 1 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\end{array}\right),B^{3}=\left(\begin{array}{rrrrrr}1 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\end{array}\right) \)

ובבירור \( B^{4}=B^{3} \) ולכן הסיפור ייתקע ב-\( B^{3} \) ומשם אנחנו צריכים להתחיל לחפש את הוקטורים הציקליים שלנו.

נפתח, אם כן, במציאת וקטורים ציקליים ב-\( \ker B^{3} \). אמרנו שהדרך לעשות זאת בפועל היא למצוא בסיס ל-\( \ker B^{2} \) ואז להשלים אותו לבסיס של \( \ker B^{3} \). מה יניב לנו דירוג מטריצות של \( B^{2} \)? את המטריצה הבאה:

\( \left(\begin{array}{rrrrrr}1 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\end{array}\right) \)

כלומר, \( \ker B^{2}=\left\{ \left(0,a,-a,b,c,d\right)\ |\ a,b,c,d\in\mathbb{C}\right\} \) - מרחב 4-ממדי. בתור בסיס שלו אפשר לקחת למשל את \( \left\{ e_{2}-e_{3},e_{4},e_{5},e_{6}\right\} \).

את \( B^{3} \) אין צורך לדרג - היא כבר מדורגת, ובבירור \( \ker B^{3}=\left\{ \left(0,a,f,b,c,d\right)\ |\ a,b,c,d,f\in\mathbb{C}\right\} \). כלומר, הוסרה המגבלה על הקואורדינטה השלישית להיות נגדית של השניה. אם כן, את מי אפשר להוסיף לבסיס \( \left\{ e_{2}-e_{3},e_{4},e_{5},e_{6}\right\} \)? אפשר להוסיף את \( e_{2} \) בלי לדאוג יותר מדי. קל לבדוק שהוא אכן בלתי תלוי בשאר הוקטורים. אם כן, \( e_{2} \) יהיה הוקטור הציקלי הראשון שלנו, זה שיצור בלוק ז’ורדן מסדר 3. בסימונים שלי, \( P_{3}=\left\{ e_{2}\right\} \).

עכשיו, נחשב את \( B\cdot e_{2}=e_{5} \) (זכרו - מטריצה כפול וקטור בסיס סטנדרטי זה פשוט לקחת את העמודה המתאימה). רעיונית אני יכול להמשיך עם זה, לחשב גם את \( B^{2}\cdot e_{2}=-e_{2}+e_{3} \) וכבר להגיד שאני מוסיף לבסיס שאני בונה את שלושת הוקטורים הללו, אבל בואו נרגיע רגע עם זה ונעבוד על פי האלגוריתם שלי. בסימונים שלי, \( P_{2}=\left\{ e_{5}\right\} \) בשלב הזה ואני צריך להרחיב אותה עוד קצת. מתחילים בלמצוא את \( \ker B \) על ידי דירוג של \( B \). מקבלים את המטריצה המדורגת

\( \left(\begin{array}{rrrrrr}1 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 1\\0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\end{array}\right) \)

כלומר, \( \ker B=\left\{ \left(0,a,-a,b,0,0\right)\ |\ a,b\in\mathbb{C}\right\} \) וזהו בבירור מרחב ממימד 2. לכן אנחנו רוצים להרחיב את \( P_{2} \) כך שיהיו בה \( \dim\ker B^{2}-\dim\ker B=4-2=2 \) וקטורים. נפעל כמו קודם: ניקח בסיס ל-\( \ker B \), נוסיף אליו את מי שכבר ב-\( P_{2} \), ואז נרחיב לבסיס של \( \ker B^{2} \). בסיס ל-\( \ker B \) הוא \( \left\{ e_{2}-e_{3},e_{4}\right\} \), ולכן אנחנו רוצים להרחיב את הקבוצה \( \left\{ e_{2}-e_{3},e_{4},e_{5}\right\} \) לבסיס עבור \( \ker B^{2} \). היי, זה בדיוק כמו הבסיס של \( \ker B^{2} \) שכבר מצאנו קודם חוץ מ-\( e_{6} \) שלא בפנים! איזה יופי, גילינו ש-\( e_{6} \) הוא הוקטור הציקלי השני שלנו. בסך הכל, \( P_{2}=\left\{ e_{5},e_{6}\right\} \) בסוף השלב הזה.

כעת אנו מחשבים את \( B\cdot e_{5}=-e_{2}+e_{3} \) ואת \( B\cdot e_{6}=e_{4} \) ומקבלים \( P_{1}=\left\{ -e_{2}+e_{3},e_{4}\right\} \). מכיוון ש-\( \dim\ker B=2 \) אין לנו עוד וקטורים שאנחנו רוצים להוסיף לקבוצה הזו - סיימנו. על ידי איחוד כל ה-\( P \)-ים שמצאנו וסידור על פי שיטת הסידור שבחרתי קודם, אני מקבל בסוף את הבסיס הסדור \( P=\left\{ e_{1},-e_{2}+e_{3},e_{5},e_{2},e_{4},e_{6}\right\} \). אם תסתכלו על המטריצה מתחילת הפוסט, זו בדיוק המטריצה הזו. סיימנו!

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

פרק חמישי ואחרון שבו האלגוריתם מקבל מנה אחת אפיים ואוי ואבוי טוב שזה נגמר נשבר לי מבדיחות הקרש הללו

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

ובכן, יהא \( V \) מרחב וקטורי ו-\( W\subseteq V \) תת-מרחב שלו. נגדיר יחס שקילות על הוקטורים של \( V \): \( v\equiv_{W}u \) אם ורק אם \( v-u\in W \). זה בבירור יחס שקילות בגלל תכונות סטנדרטיות של תת-מרחבים וקטוריים: \( 0\in W \) ולכן רפלקסיביות; אם \( v\in W \) גם \( -v\in W \) ולכן סימטריה; ו-\( W \) סגור לחיבור ולכן טרנזיטיביות (\( \left(v-w\right)=\left(v-u\right)+\left(u-w\right) \)). מחלקת השקילות של \( v \) היא אוסף כל האיברים השקולים לו: \( \left[v\right]_{W}\triangleq\left\{ u\in V\ |\ v\equiv_{W}u\right\} =\left\{ v+w\ |\ w\in W\right\} \). השוויון האחרון מצדיק את הסימון המקובל יותר, \( v+W \), עבור מחלקת השקילות הזו, שגם נקראת לפעמים קוסט של \( W \). כעת אנחנו מגדירים את מרחב המנה \( V/W \) בתור מרחב המנה של היחס - אוסף הקוסטים שלו. דהיינו, \( V/W\triangleq\left\{ v+W\ |\ v\in V\right\} \).

שימו לב לכך ש-\( V/W \) הוא לא תת-מרחב של \( V \). זה לא ייתכן כבר ברמה הסינטקטית: אברי \( V/W \) הם לא איברים של \( V \) אלא קבוצות של איברים של \( V \). אז איך נכון לחשוב על \( V/W \)? בתור מרחב שמתקבל מכך ש”מדביקים ביחד” איברים שונים של \( V \). הדוגמה הקלאסית היא עבור \( V=\mathbb{R}^{2} \) ו-\( W \) שהוא תת-מרחב ממימד 1, כלומר קו ישר ב-\( \mathbb{R}^{2} \). במקרה הזה, מחלקות השקילות של \( V/W \) יהיו בדיוק הישרים שמקבילים ל-\( V/W \). המרחב הזה איזומורפי ל-\( \mathbb{R}^{1} \) - תחשבו, למשל, שמעבירים כל ישר ב-\( V/W \) לנקודה שהוא חותך על ציר \( x \) (או, אם \( W \) הוא ציר \( x \), לנקודה שהוא חותך על ציר \( y \)).

דרך קצת יותר כללית להבין מרחבי מנה היא באמצעות משפט האיזומורפיזם הראשון, כשהוא מנוסח עבור מרחבים וקטוריים: אם \( T:V\to U \) היא טרנספורמציה לינארית כלשהי, אז \( V/\ker T\cong\mbox{Im}T \). כלומר, כדי להבין מרחב מנה \( V/W \) אפשר לחשוב על טרנספורמציה לינארית שמעבירה את אברי \( V \) למרחב כלשהו שנוח לנו לדמיין כך שהגרעין יוצא בדיוק \( W \). בעזרת המשפט הזה קל לראות שלמשל, אם \( V=W\oplus U \) אז \( V/W\cong U \) (עם ההעתקה \( T\left(v\right)=T\left(w+u\right)=u \), כאשר \( v=w+u \) היא ההצגה היחידה של \( v \) כצירוף לינארי של איבר מ-\( W \) ואיבר מ-\( U \)). באופן מפורש, האיזומורפיזם שולח את \( u\in U \) אל \( u+W\in V/W \) (ולהיפך: משפט האיזומורפיזם הראשון מראה שכל קוסט של \( W \) ניתן לכתיבה באופן יחיד בתור \( u+W \) עם \( u\in U \) ואז האיזומורפיזם מעביר את הקוסט אל \( u \)).

התוצאה האחרונה הזו גם מראה לנו כיצד ניתן למצוא בסיס ל-\( V/W \): אם נתון לנו כבר בסיס \( \left\{ w_{1},\dots,w_{k}\right\} \) עבור \( W \), אנחנו משלימים אותו לבסיס עבור \( V \), שנסמן \( \left\{ w_{1},\dots,w_{k},u_{1},\dots,u_{t}\right\} \). כעת נגדיר \( U=\mbox{span}\left\{ u_{1},\dots,u_{t}\right\} \) וקיבלנו ש-\( V=W\oplus U \). לכן \( U\cong V/W \), ולכן \( u_{1}+W,\dots,u_{t}+W \) הוא בסיס של \( V/W \) (התמונה של בסיס על ידי איזומורפיזם היא בסיס).

עכשיו, עם הטרמינולוגיה החדשה הזו, הנה ניסוח מחודש של האלגוריתם למציאת צורת ז’ורדן של \( A \):

1. נחשב את הפולינום האופייני \( p_{A}\left(x\right)=\det\left(xI-A\right) \) ונפרק אותו לגורמים לינאריים \( p_{A}\left(x\right)=\left(x-\lambda_{1}\right)^{k_{1}}\cdots\left(x-\lambda_{n}\right)^{k_{n}} \). אם הפולינום לא מתפרק לגורמים לינאריים מעל השדה אפשר לשכוח מצורת ז'ורדן. השורשים של הפולינום האופייני נקראים ערכים עצמיים של \( A \).
2. לכל ערך עצמי \( \lambda \) נסמן לצורך נוחות ב-\( B_{\lambda} \) את המטריצה \( B_{\lambda}\triangleq A-\lambda I \), ונסמן ב-\( V_{\lambda}^{k} \) את תת-המרחב \( V_{\lambda}^{k}\triangleq\ker B_{\lambda}^{k} \). כעת:
   1. נחשב את \( \dim\left(V_{\lambda}^{k+1}/V_{\lambda}^{k}\right) \) עבור \( k=1,2,\dots \) עד אשר נמצא \( k \) שהמימד שווה ל-0 עבורו.
   2. נבנה באופן אינדוקטיבי סדרה של קבוצות \( P_{k}^{\lambda},P_{k-1}^{\lambda},P_{k-2}^{\lambda},\dots,P_{1}^{\lambda} \) באופן הבא: בתחילה, \( P_{k}^{\lambda}=\emptyset \). כעת, לכל \( t=k,k-1,\dots,1 \):
      1. ניקח את קבוצת הקוסטים \( \left\{ v+V_{\lambda}^{t-1}\ |\ v\in P_{t}^{\lambda}\right\} \) ונרחיב אותה לבסיס של \( V_{\lambda}^{t}/V_{\lambda}^{t-1} \).
      2. נוסיף ל-\( P_{t}^{\lambda} \) את הנציגים של הקוסטים שהתווספו בשלב ההרחבה הזה. לאיברים הללו נקרא וקטורים ציקליים.
      3. לכל \( v\in P_{t}^{\lambda} \) נוסיף ל-\( P_{t-1}^{\lambda} \) את \( B_{\lambda}\cdot v \) (לוקטורים הללו לא נקרא וקטורים ציקליים).
   3. נגדיר \( P^{\lambda}=\bigcup_{t=1}^{k}P_{t}^{\lambda} \).
3. נגדיר \( P=\bigcup_{\lambda}P^{\lambda} \).
4. נסדר את איברי ב-\( P \) באופן הבא: נגדיר סדר כלשהו על הערכים העצמיים וכל הוקטורים שהתקבלו מערך עצמי \( \lambda \) יופיעו ביחד בהתאם לסדר הזה, ונגדיר סדר כלשהו על הוקטורים הציקליים שהתגלו במהלך האלגוריתם. אם \( v \) הוא וקטור ציקלי ששייך ל-\( P_{t}^{\lambda} \) אז נסדר את האיברים \( B^{t}v,B^{t-1}v,\dots,Bv,v \) בסדר הזה (כך ש-\( B^{t}v \) ראשון ו-\( v \) אחרון).

זו הגרסה הפשוטה ביותר של האלגוריתם שאני מסוגל לתאר. האם תוכלו לתת ניסוח טוב יותר? אשמח לשמוע.