MentoraLINEAR 2

שבוע 7 — ריבוי אלגברי וגיאומטרי

GM ≤ AM והקריטריון המלא ללכסינות

ריבוי אלגבריריבוי גיאומטריקריטריון לכסינות

רקע — על מה השבוע הזה

כאן מתקבל הקריטריון המלא ללכסינות. לכל ערך עצמי יש שני מספרים: כמה פעמים הוא מופיע כשורש (ריבוי אלגברי) וכמה ו"ע בת"ל הוא תורם (ריבוי גיאומטרי). לכסינות היא בדיוק השאלה האם יש מספיק ו"ע — כלומר האם GM = AM לכל ע"ע.

ריבוי אלגבריריבוי גיאומטריקריטריון לכסינות

הגדרות (2)

הניסוח המלא מהמצגת
הגדרהריבוי אלגברי
∙\bullet יהי p(x)∈F[x]p(x)\in\mathbb{F}[x] ויהי α∈F\alpha\in\mathbb{F} .
∙\bullet הריבוי האלגברי של α\alpha הוא: AM(α)=max{0≤l∈Z∣(x−α)l∣p(x)}\boldsymbol{AM}(\boldsymbol{\alpha})=\mathbf{max}\{\boldsymbol{0\le l}\in\mathbb{Z}\mid (\boldsymbol{x}-\boldsymbol{\alpha})^{\boldsymbol{l}}\mid \boldsymbol{p}(\boldsymbol{x})\}
הגדרהריבוי גיאומטרי
∙\bullet תהי A∈Mn(F)A\in M_n(\mathbb{F}) ויהי α∈F\alpha\in\mathbb{F} .
∙\bullet הריבוי הגיאומטרי של α\alpha הינו: GM(α)=dim Vα\boldsymbol{GM}(\boldsymbol{\alpha})=\boldsymbol{dim}\,\boldsymbol{V_\alpha}
∙\bullet כאשר VαV_\alpha הוא המרחב העצמי של α\alpha ביחס למטריצה AA .

משפטים ומסקנות (11)

ניסוחים בלבד — ההוכחות בלשונית ההרצאה
מסקנה 1ע"ע וז"ע של מטריצה אלכסוניתצריך לדעת להוכיח
∙\bullet תהי A=diag(λ1,…,λn)A=diag(\lambda_1,\dots,\lambda_n) מטריצה אלכסונית.
∙\bullet אזי AA לכסינה, הערכים העצמיים של AA הם λ1,…,λn\lambda_1,\dots,\lambda_n והזוגות העצמיים של AA הם (λ1,e⃗1),…,(λn,e⃗n)(\lambda_1,\vec{e}_1),\dots,(\lambda_n,\vec{e}_n) .
מסקנה 2ע"ע של מטריצה משולשית עליונה
∙\bullet תהי AA מטריצה משולשית עליונה. אזי הערכים העצמיים של AA הם איברי האלכסון שלה.
משפט 5למטריצות דומות יש אותו פולינום אופייניצריך לדעת להוכיח
יהי F\mathbb{F} שדה. יהי n∈Nn\in\mathbb{N} . תהיינה A,B∈Mn(F)A,B\in M_n(\mathbb{F}) , המקיימות A∼BA\sim B .
אזי pA(λ)=pB(λ)\boldsymbol{p_A}(\boldsymbol{\lambda})=\boldsymbol{p_B}(\boldsymbol{\lambda}) .
מסקנה 3פירוק חלקי של הפולינום האופייני
∙\bullet תהי A∈Mn(F)A\in M_n(\mathbb{F}) . נניח ש-λ1,…,λk\lambda_1,\dots,\lambda_k הם ערכים עצמיים שונים של AA .
∙\bullet אזי קיים k(x)∈F(x)k(x)\in\mathbb{F}(x) כך ש-pA(λ)=(λ−λ1)⋅⋯⋅(λ−λk)⋅k(x)p_A(\lambda)=(\lambda-\lambda_1)\cdot\dots\cdot(\lambda-\lambda_k)\cdot k(x)
מסקנה 4כל פולינום מעל המרוכבים מתפרק לגורמים לינאריים
∙\bullet יהי p(x)∈C[x]p(x)\in\mathbb{C}[x] . נניח ש-n=deg⁡p(x)≥1n=\deg p(x)\ge1 .
∙\bullet אזי קיימים α1,…,αn∈C\alpha_1,\dots,\alpha_n\in\mathbb{C} וקיים c∈Cc\in\mathbb{C} כך ש-p(x)=c(x−α1)⋅⋯⋅(x−αn)\boldsymbol{p}(\boldsymbol{x})=\boldsymbol{c}(\boldsymbol{x}-\boldsymbol{\alpha_1})\cdot\dots\cdot(\boldsymbol{x}-\boldsymbol{\alpha_n})
מסקנה 5הפ"א מתפרק לגורמים לינאריים מעל המרוכביםצריך לדעת להוכיח
∙\bullet תהי A∈Mn(C)A\in M_n(\mathbb{C}) .
∙\bullet אזי קיימים λ1,…,λn∈C\lambda_1,\dots,\lambda_n\in\mathbb{C} כך ש-pA(λ)=(λ−λ1)⋅⋯⋅(λ−λn)\boldsymbol{p_A}(\boldsymbol{\lambda})=(\boldsymbol{\lambda}-\boldsymbol{\lambda_1})\cdot\dots\cdot(\boldsymbol{\lambda}-\boldsymbol{\lambda_n})
משפט 1GM(α)=n−rank(αIn−A)GM(\alpha)=n-rank(\alpha I_n-A)צריך לדעת להוכיח
∙\bullet תהי A∈Mn(F)A\in M_n(\mathbb{F}) ויהי α∈F\alpha\in\mathbb{F} . אזי:
GM(α)=n−rank(α⋅In−A)\boldsymbol{GM}(\boldsymbol{\alpha})=\boldsymbol{n}-\boldsymbol{rank}(\boldsymbol{\alpha}\cdot\boldsymbol{I_n}-\boldsymbol{A})
משפט 2ר"ג ≤\le ר"אצריך לדעת להוכיח
יהי F\mathbb{F} שדה. יהי n∈Nn\in\mathbb{N} . תהי A∈Mn(F)A\in M_n(\mathbb{F}) . ויהי α∈F\alpha\in\mathbb{F} .
אזי GM(α)≤AM(α)\boldsymbol{GM}(\boldsymbol{\alpha})\le\boldsymbol{AM}(\boldsymbol{\alpha}) .
משפט 3איחוד הבסיסים של מרחבים עצמיים של ע"ע שונים הוא בת"לצריך לדעת להוכיח
∙\bullet יהי F\mathbb{F} שדה. יהי n∈Nn\in\mathbb{N} . תהי A∈Mn(F)A\in M_n(\mathbb{F}) .
∙\bullet יהיו λ1,…,λk∈F\lambda_1,\dots,\lambda_k\in\mathbb{F} ע"ע של AA השונים זה מזה.
∙\bullet יהיו Vλ1,Vλ2…,VλkV_{\lambda_1},V_{\lambda_2}\dots,V_{\lambda_k} המרחבים העצמיים המתאימים ל-λ1,…,λk\lambda_1,\dots,\lambda_k .
∙\bullet יהיו l1,…,lkl_1,\dots,l_k הריבויים הגיאומטריים של λ1,…,λk\lambda_1,\dots,\lambda_k בהתאמה.
∙\bullet נסמן: l1+l2+⋯+lk=rl_1+l_2+\dots+l_k=r
∙\bullet נסמן את הבסיסים של Vλ1,…,VλkV_{\lambda_1},\dots,V_{\lambda_k} באופן הבא:
v⃗1,…,v⃗l1∈Vλ1\vec{v}_1,\dots,\vec{v}_{l_1}\in V_{\lambda_1} בסיס ל-Vλ1V_{\lambda_1}
v⃗l1+1,…,v⃗l1+l2∈Vλ2\vec{v}_{l_1+1},\dots,\vec{v}_{l_1+l_2}\in V_{\lambda_2} בסיס ל-Vλ2V_{\lambda_2}
⋮\vdots
v⃗l1+l2+⋯+lk−1+1,…,v⃗r∈Vλk\vec{v}_{l_1+l_2+\dots+l_{k-1}+1},\dots,\vec{v}_r\in V_{\lambda_k} בסיס ל-VλkV_{\lambda_k}
∙\bullet אזי v⃗1,…,v⃗r\vec{v}_1,\dots,\vec{v}_r בת"ל.
משפט 4שלושה תנאים שקולים ללכסינותצריך לדעת להוכיח
∙\bullet יהי F\mathbb{F} שדה. יהי n∈Nn\in\mathbb{N} ותהי A∈Mn(F)A\in M_n(\mathbb{F}) .
∙\bullet יהיו λ1,…,λk∈F\lambda_1,\dots,\lambda_k\in\mathbb{F} כל הע"ע של AA השונים זה מזה.
∙\bullet יהיו l1,…,lkl_1,\dots,l_k הריבויים הגיאומטריים של λ1,…,λk\lambda_1,\dots,\lambda_k בהתאמה.
אזי שלושת התנאים הבאים שקולים:
1. l1+l2+⋯+lk=nl_1+l_2+\dots+l_k=n .
2. AA לכסינה.
3. הפולינום האופייני של AA מתפרק לגורמים לינאריים באופן הבא: pA(λ)=(λ−λ1)l1⋅⋯⋅(λ−λk)lkp_A(\lambda)=(\lambda-\lambda_1)^{l_1}\cdot\dots\cdot(\lambda-\lambda_k)^{l_k}
מסקנה 1מעל C\mathbb{C} : AA לכסינה אם"ם לכל ע"ע GM(λ)=AM(λ)GM(\lambda)=AM(\lambda)צריך לדעת להוכיח
∙\bullet תהי A∈Mn(C)A\in M_n(\mathbb{C}) . אזי AA לכסינה אם ורק אם לכל ערך עצמי λ\lambda של AA מתקיים GM(λ)=AM(λ)\boldsymbol{GM}(\boldsymbol{\lambda})=\boldsymbol{AM}(\boldsymbol{\lambda}) .

הערות (3)

הערה 1 — AM(α)≤deg⁡p(x)AM(\alpha)\le\deg p(x)
∙\bullet נשים לב שמתקיים: AM(α)≤deg⁡p(x)AM(\alpha)\le\deg p(x) .
הערה 2 — 0≤GM(λ)≤n0\le GM(\lambda)\le n ו-λ\lambda ע"ע אם"ם GM(λ)≥1GM(\lambda)\ge1
∙\bullet תהי A∈Mn(F)A\in M_n(\mathbb{F}) ויהי λ∈F\lambda\in\mathbb{F} . אזי מתקיים 0≤GM(λ)≤n0\le GM(\lambda)\le n .
∙\bullet בנוסף, λ\lambda ע"ע של AA אם"ם GM(λ)≥1GM(\lambda)\ge1 .
סיכום - תנאים שקולים ללכסינות מטריצה
∙\bullet יהי F\mathbb{F} שדה. יהי n∈Nn\in\mathbb{N} . תהי K∈Mn(F)K\in M_n(\mathbb{F}) .
∙\bullet KK לכסינה אם מתקיים אחד מהתנאים השקולים הבאים:
המטריצה KK דומה למטריצה אלכסונית
⇕\Updownarrow
קיים ל-Fn\mathbb{F}^n בסיס של וקטורים עצמיים של KK
⇕\Updownarrow
סכום הריבויים הגיאומטריים של כל הע"ע של KK הוא nn
⇕\Updownarrow
לכל ע"ע מתקיים: ר"א=ר"ג

אם נתון לי… אז אני יודעת

8 מסקנות · זה מה שכותבים בשורה הראשונה של הפתרון
λ\lambda ערך עצמי של A∈Mn(F)A\in M_n(\mathbb{F})
  • GM(λ)=dim⁡Vλ≥1GM(\lambda)=\dim V_\lambda\ge1 (הערה 2)
  • GM(λ)=n−rank(λIn−A)GM(\lambda)=n-rank(\lambda I_n-A) (משפט 1) — כך מחשבים בלי לפתור את המערכת
  • GM(λ)≤AM(λ)GM(\lambda)\le AM(\lambda) (משפט 2)
  • AM(λ)≤deg⁡pA=nAM(\lambda)\le\deg p_A=n
הכיוון הוא GM≤AMGM\le AM ולא הפוך. וגם: GM≥1GM\ge1 רק לערך עצמי אמיתי; ל-α\alpha שאינו ע"ע מתקיים GM(α)=0GM(\alpha)=0.
נתון ש-AM(λ)=1AM(\lambda)=1
  • 1≤GM(λ)≤AM(λ)=11\le GM(\lambda)\le AM(\lambda)=1 ולכן GM(λ)=1GM(\lambda)=1
  • אין מה לחשב עבור λ\lambda הזה — הוא לעולם אינו הגורם שמקלקל לכסינות
  • ולכן מתמקדים רק בשורשים עם ריבוי אלגברי ≥2\ge2
AA לכסינה
  • סכום הריבויים הגיאומטריים של כל הע"ע הוא nn (משפט 4)
  • pAp_A מתפרק לגורמים לינאריים: pA(λ)=(λ−λ1)l1⋯(λ−λk)lkp_A(\lambda)=(\lambda-\lambda_1)^{l_1}\cdots(\lambda-\lambda_k)^{l_k} כאשר li=GM(λi)l_i=GM(\lambda_i)
  • ולכן לכל ע"ע GM(λ)=AM(λ)GM(\lambda)=AM(\lambda)
  • איחוד הבסיסים של המרחבים העצמיים הוא בסיס של Fn\mathbb{F}^n (משפט 3)
לכל ע"ע של AA מתקיים GM(λ)=AM(λ)GM(\lambda)=AM(\lambda) וגם pAp_A מתפרק לגורמים לינאריים
  • AA לכסינה (משפט 4)
  • ואפשר לבנות PP מאיחוד הבסיסים של המרחבים העצמיים (משפט 3 מבטיח בת"ל)
מעל שדה כללי חייבים את שני התנאים. מעל C\mathbb{C} בלבד מספיק GM=AMGM=AM (מסקנה 1), כי שם הפירוק מובטח מראש.
קיים ערך עצמי עם GM(λ)<AM(λ)GM(\lambda)<AM(\lambda)
  • סכום הריבויים הגיאומטריים קטן מ-nn
  • ולכן AA אינה לכסינה (משפט 4) — ואין צורך לבדוק שאר הערכים העצמיים
סכום הריבויים האלגבריים של השורשים בשדה קטן מ-nn
  • pAp_A אינו מתפרק לגורמים לינאריים מעל השדה
  • ולכן AA אינה לכסינה מעל השדה הזה (משפט 4)
  • ייתכן שהיא כן לכסינה מעל C\mathbb{C}
נתונים בסיסים של מרחבים עצמיים של ערכים עצמיים שונים
  • האיחוד שלהם בת"ל (משפט 3)
  • ולכן מספיק לספור את המימדים — אין צורך לבדוק תלות לינארית בין הווקטורים
  • אם הסכום הוא nn — קיבלת בסיס של ו"ע
המטריצה תלויה בפרמטר aa
  • חשבי pAp_A כפונקציה של aa ומצאי מתי יש שורש כפול — רק שם הלכסינות מוטלת בספק
  • לכל ערך aa שבו כל הע"ע שונים — AA לכסינה מיידית
  • בערכים החריגים בלבד — חשבי GM=n−rank(λI−A)GM=n-rank(\lambda I-A) והשווי ל-AMAM
ה-rankrank עצמו משתנה עם aa — חייבים להציב את הערך הספציפי לפני הדירוג, לא לדרג עם פרמטר כללי.

איך מפריכים

מהבדיקה הזולה ביותר לכיוון היקרה
להפריך ש-AA לכסינה
  1. 1חשבי pAp_A ופרקי בשדה הנתון.
  2. 2אם הפירוק אינו לגורמים לינאריים (נשאר גורם ריבועי אי-פריק) — סיימת (משפט 4).
  3. 3אם כן מתפרק — אתרי שורש עם AM≥2AM\ge2. שורשים עם AM=1AM=1 לא יכולים לקלקל.
  4. 4לשורש כזה חשבי GM=n−rank(λIn−A)GM=n-rank(\lambda I_n-A) — דירוג אחד בלבד.
  5. 5אם GM<AMGM<AM — הופרך. נסחי: "GM(λ)=⋯<⋯=AM(λ)GM(\lambda)=\dots<\dots=AM(\lambda) ולכן AA אינה לכסינה".
להפריך ש-A∼BA\sim B כששני הפולינומים האופייניים שווים
  1. 1חשבי לשתיהן GMGM של אותו ערך עצמי: n−rank(λI−A)n-rank(\lambda I-A) מול n−rank(λI−B)n-rank(\lambda I-B).
  2. 2אם אחת לכסינה והשנייה לא — הן אינן דומות (לכסינות נשמרת תחת דמיון).
  3. 3אם אחת סקלרית והשנייה לא — משפט 2 של שבוע 4 סוגר מיד.

איך מוכיחים

המהלכים שעובדים בשבוע הזה
להוכיח ש-AA לכסינה ולמצוא P,DP,D
  1. 1חשבי pAp_A, פרקי, ורשמי לכל ע"ע את AMAM.
  2. 2nn ע"ע שונים — סיימת. אחרת המשיכי.
  3. 3לכל ע"ע חשבי GM=n−rank(λIn−A)GM=n-rank(\lambda I_n-A) והשווי ל-AMAM.
  4. 4אם לכל הע"ע GM=AMGM=AM והפירוק לינארי — לכסינה. מצאי בסיס לכל VλV_\lambda (פתרון המערכת ההומוגנית).
  5. 5אחדי את הבסיסים — הם בת"ל אוטומטית (משפט 3) — ובני PP; DD נכתבת באותו סדר עם ריבויים.
לחשב ריבוי גיאומטרי
  1. 1כתבי את λIn−A\lambda I_n-A עם הערך הספציפי.
  2. 2דרגי וספרי שורות לא אפסיות — זה rankrank.
  3. 3GM=n−rankGM=n-rank (משפט 1).
  4. 4בדיקת שפיות: 1≤GM≤AM1\le GM\le AM; אם קיבלת מחוץ לטווח — יש טעות בחישוב.
לנתח לכסינות של מטריצה עם פרמטר
  1. 1חשבי pAp_A עם הפרמטר ורשמי את הע"ע כפונקציות שלו.
  2. 2פתרי מתי שני ע"ע מתלכדים — קבלי רשימה סופית של ערכים חריגים.
  3. 3הכריזי: לכל שאר הערכים יש nn ע"ע שונים ולכן לכסינות.
  4. 4בכל ערך חריג בנפרד — הציבי, דרגי, חשבי GMGM והשווי ל-AMAM.
  5. 5סכמי בטבלה: הערכים שבהם לכסינה, והמטריצה האלכסונית הדומה בכל מקרה.

מסקנות — מה לוקחים מהשבוע

  • 1GM(λ) = n − rank(λI − A), ותמיד 1 ≤ GM(λ) ≤ AM(λ).
  • 2A לכסינה ⟺ p_A מתפרק לגורמים לינאריים וגם GM = AM לכל ע"ע ⟺ סכום ה-GM הוא n.
  • 3n ערכים עצמיים שונים ⇒ לכסינה. תנאי מספיק בלבד — לא הכרחי.
  • 4לכסינות תלויה בשדה. תמיד לשאול קודם: מעל איזה שדה עובדים?
מטלה 8
לתרגל את החומר של השבוע
שקפי הרצאה 7
המצגת המקורית במלואה
שבוע 6:הפולינום האופייניקיילי–המילטון ותת-מרחב שמור:שבוע 8