MentoraLINEAR 2

שבוע 6 — הפולינום האופייני

הגדרה, מטריצות בלוקים, דמיון ופיבונאצ׳י

פולינום אופיינימטריצות בלוקיםנוסחת בינה

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

עד כה חיפשנו ערכים עצמיים בניחוש. הפולינום האופייני הופך את זה לאלגוריתם: הע"ע הם בדיוק השורשים של p_A(λ) = det(λI − A). לאורך הדרך מתגלה שהפולינום מקודד גם את העקבה וגם את הדטרמיננטה, ושהוא שמור תחת דמיון.

פולינום אופיינימטריצות בלוקיםנוסחת בינה

הגדרות (3)

הניסוח המלא מהמצגת
הגדרההפולינום האופייני
יהי F\mathbb{F} שדה. תהי A∈Mn(F)A\in M_n(\mathbb{F}) .
נגדיר את הפולינום האופייני של A\boldsymbol{A} באופן הבא: pA(λ)=det⁡(λIn−A)\boldsymbol{p_A}(\boldsymbol{\lambda})=\mathbf{\det}(\boldsymbol{\lambda I_n}-\boldsymbol{A})
הגדרהפולינומים - מטריצות שאיבריהן פולינומים
∙\bullet יהי F\mathbb{F} שדה. יהיו k,l∈Nk,l\in\mathbb{N} .
∙\bullet נסמן ב-Mk×l(F[x])\boldsymbol{M_{k\times l}}(\mathbb{F}[\boldsymbol{x}]) את קבוצת כל המטריצות מסדר k×lk\times l שאיבריהן הם פולינומים ב-F[x]\mathbb{F}[x] .
∙\bullet נסמן ב-Mk×l(Fn[x])\boldsymbol{M_{k\times l}}(\mathbb{F}_{\boldsymbol{n}}[\boldsymbol{x}]) את קבוצת כל המטריצות מסדר k×lk\times l שאיבריהן הם פולינומים ב-Fn[x]\mathbb{F}_n[x] .
הגדרהפולינום מתוקן (monicmonic)
∙\bullet יהי p(x)=a0+a1x+⋯+anxnp(x)=a_0+a_1x+\dots+a_nx^n פולינום ב-F[x]\mathbb{F}[x] .
∙\bullet נאמר ש-p(x)p(x) מתוקן (monicmonic) אם an=1Fa_n=1_{\mathbb{F}} .

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

ניסוחים בלבד — ההוכחות בלשונית ההרצאה
משפט 1הע"ע הם שורשים של הפולינום האופייניצריך לדעת להוכיח
יהי F\mathbb{F} שדה. תהי A∈Mn(F)A\in M_n(\mathbb{F}) ויהי λ∈F\lambda\in\mathbb{F} .
אזי: λ\lambda ע"ע של AA אם"ם pA(λ)=0Fp_A(\lambda)=0_{\mathbb{F}} .
למה 1דטרמיננטה של מטריצת פולינומים ממעלה ראשונהצריך לדעת להוכיח
יהי F\mathbb{F} שדה. יהי n∈Nn\in\mathbb{N} . תהי A∈Mn(F1[x])A\in M_n(\mathbb{F}_1[x]) .
אזי det⁡(A)∈Fn[x]\det(A)\in\mathbb{F}_n[x] .
משפט 2הפולינום האופייני הוא מתוקן ממעלה nnצריך לדעת להוכיח
יהי F\mathbb{F} שדה. יהי n∈Nn\in\mathbb{N} . תהי A∈Mn(F)A\in M_n(\mathbb{F}) .
אזי pAp_A הוא פולינום מתוקן ממעלה n\boldsymbol{n} .
משפט 3נוסחת BinetBinet לסדרת פיבונאצ'יצריך לדעת להוכיח
∙\bullet נתבונן בסדרת פיבונאצ'י המוגדרת על ידי נוסחת הנסיגה הבאה: {Fn=Fn−1+Fn−2∀n≥2F1=1F0=0\begin{cases}F_n=F_{n-1}+F_{n-2}\quad \forall n\ge2\\ F_1=1\\ F_0=0\end{cases}
∙\bullet אזי לכל n∈Nn\in\mathbb{N} מתקיים: Fn=(1+52)n−(1−52)n5\boldsymbol{F_n}=\dfrac{\left(\dfrac{\boldsymbol{1+\sqrt{5}}}{\boldsymbol{2}}\right)^{\boldsymbol{n}}-\left(\dfrac{\boldsymbol{1-\sqrt{5}}}{\boldsymbol{2}}\right)^{\boldsymbol{n}}}{\boldsymbol{\sqrt{5}}}
משפט 4הפולינום האופייני של מטריצת בלוקים משולשיתצריך לדעת להוכיח
∙\bullet תהי AA מטריצת בלוקים משולשית, שהבלוקים שלה הם מטריצות ריבועיות A1,…,AkA_1,\dots,A_k .
∙\bullet כלומר AA היא מהצורה: A=(A1∗…∗A2…⋮⋱∗0Ak)\boldsymbol{A}=\begin{pmatrix}A_1&*&\dots&*\\ &A_2&\dots&\vdots\\ &&\ddots&*\\ \boldsymbol{0}&&&A_k\end{pmatrix}
∙\bullet אזי: pA(λ)=pA1(λ)⋅⋯⋅pAk(λ)\boldsymbol{p_A}(\boldsymbol{\lambda})=\boldsymbol{p_{A_1}}(\boldsymbol{\lambda})\cdot\dots\cdot\boldsymbol{p_{A_k}}(\boldsymbol{\lambda})
מסקנה 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})

הערות (1)

הערה 1 — Mk×l(F[x])M_{k\times l}(\mathbb{F}[x]) הוא מ"ו
הקבוצה Mk×l(F[x])M_{k\times l}(\mathbb{F}[x]) היא מ"ו מעל F\mathbb{F} (ההוכחה דומה להוכחה עבור Mk×l(F)M_{k\times l}(\mathbb{F}) .)
הקבוצה Mk×l(Fn[x])M_{k\times l}(\mathbb{F}_n[x]) היא תמ"ו של Mk×l(F[x])M_{k\times l}(\mathbb{F}[x]) .

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

8 מסקנות · זה מה שכותבים בשורה הראשונה של הפתרון
נתונה A∈Mn(F)A\in M_n(\mathbb{F}) ומבקשים ערכים עצמיים
  • pA(λ)=det⁡(λIn−A)p_A(\lambda)=\det(\lambda I_n-A) — בסדר הזה, לא det⁡(A−λI)\det(A-\lambda I)
  • pAp_A מתוקן ממעלה nn בדיוק (משפט 2)
  • λ0\lambda_0 ע"ע אם"ם pA(λ0)=0p_A(\lambda_0)=0 (משפט 1)
  • ולכן ל-AA יש לכל היותר nn ע"ע שונים
בסדר ההפוך det⁡(A−λI)\det(A-\lambda I) הסימן מתהפך כאשר nn אי-זוגי והפולינום כבר אינו מתוקן. השורשים זהים — אבל הניסוח נחשב שגוי בקורס הזה.
רוצים לבדוק אם λ0\lambda_0 הוא ערך עצמי
  • מספיק להציב: pA(λ0)=0p_A(\lambda_0)=0 אם"ם λ0\lambda_0 ע"ע (משפט 1)
  • אין צורך לדרג מטריצה ואין צורך למצוא ו"ע
  • שקול לכך ש-λ0In−A\lambda_0I_n-A אינה הפיכה
AA משולשית (עליונה או תחתונה) או אלכסונית
  • הערכים העצמיים הם בדיוק איברי האלכסון (מסקנה 2)
  • pA(λ)=(λ−a11)⋯(λ−ann)p_A(\lambda)=(\lambda-a_{11})\cdots(\lambda-a_{nn}) — כבר מפורק
  • לאלכסונית: היא לכסינה והזוגות העצמיים הם (λj,e⃗j)(\lambda_j,\vec e_j) (מסקנה 1)
משולשית עם ערכים עצמיים על האלכסון אינה בהכרח לכסינה: (2102)\begin{pmatrix}2&1\\0&2\end{pmatrix} אינה לכסינה (תרגיל 1). קריאת הע"ע מהאלכסון היא רק חצי מהעבודה.
AA היא מטריצת בלוקים משולשית עם בלוקים ריבועיים A1,…,AkA_1,\dots,A_k
  • pA(λ)=pA1(λ)⋯pAk(λ)p_A(\lambda)=p_{A_1}(\lambda)\cdots p_{A_k}(\lambda) (משפט 4)
  • ולכן הע"ע של AA הם איחוד הע"ע של הבלוקים
  • ומטריצה גדולה מתפרקת לחישובים קטנים
המשפט דורש שהבלוקים באלכסון יהיו ריבועיים ושמתחת (או מעל) יהיו אפסים. חלוקה שרירותית לבלוקים אינה מספיקה.
נתון ש-A∼BA\sim B
  • pA(λ)=pB(λ)p_A(\lambda)=p_B(\lambda) (משפט 5)
  • ולכן אותם ערכים עצמיים, ואותם ריבויים בפולינום
  • ולכן גם אותו det⁡\det ואותו tracetrace
ההפך אינו נכון: I2I_2 ו-(1101)\begin{pmatrix}1&1\\0&1\end{pmatrix} בעלות אותו פולינום אופייני (λ−1)2(\lambda-1)^2 ואינן דומות. פולינום אופייני זהה הוא תנאי הכרחי בלבד.
עובדים מעל C\mathbb{C}
  • pAp_A מתפרק לגורמים לינאריים: pA(λ)=(λ−λ1)⋯(λ−λn)p_A(\lambda)=(\lambda-\lambda_1)\cdots(\lambda-\lambda_n) (מסקנה 5)
  • ולכן לכל A∈Mn(C)A\in M_n(\mathbb{C}) יש לפחות ערך עצמי אחד
  • זה נובע מהמשפט היסודי של האלגברה
מעל R\mathbb{R} ייתכן שאין ע"ע כלל (pA(λ)=λ2+1p_A(\lambda)=\lambda^2+1), ומעל Zp\mathbb{Z}_p בוודאי שלא. "יש ע"ע" הוא נכס של C\mathbb{C} בלבד.
ידועים kk ערכים עצמיים שונים של AA
  • (λ−λ1)⋯(λ−λk)(\lambda-\lambda_1)\cdots(\lambda-\lambda_k) מחלק את pAp_A (מסקנה 3)
  • ולכן אפשר לחלק את pAp_A בגורמים הידועים ולקבל פולינום ממעלה נמוכה יותר
  • ואם k=nk=n — מצאת את כל הע"ע ו-AA לכסינה (מסקנה 1, שבוע 5)
A∈M2(F)A\in M_2(\mathbb{F})
  • pA(λ)=λ2−trace(A)λ+det⁡(A)p_A(\lambda)=\lambda^2-trace(A)\lambda+\det(A) — חישוב ישיר של דטרמיננטת 2×22\times2
  • ולכן אפשר לכתוב את הפולינום בלי לפתוח דטרמיננטה
  • הע"ע הם שורשי המשוואה הריבועית הזאת

איך מפריכים

מהבדיקה הזולה ביותר לכיוון היקרה
להפריך ש-A∼BA\sim B (הרשימה המלאה, מהזול ליקר)
  1. 1סדר וגודל — דמיון מוגדר רק בין ריבועיות מאותו סדר.
  2. 2det⁡(A)\det(A) מול det⁡(B)\det(B).
  3. 3trace(A)trace(A) מול trace(B)trace(B).
  4. 4pAp_A מול pBp_B (משפט 5) — חזק יותר משני הקודמים, וסוגר גם מקרים שבהם det⁡\det ו-tracetrace שווים.
  5. 5אם גם הפולינומים זהים: בדקי אם אחת סקלרית והשנייה לא (משפט 2, שבוע 4) — זה מה שסוגר את I2I_2 מול (1101)\begin{pmatrix}1&1\\0&1\end{pmatrix}.
להפריך ש-λ0\lambda_0 הוא ערך עצמי של AA
  1. 1הציבי λ0\lambda_0 ב-pAp_A. אם pA(λ0)≠0p_A(\lambda_0)\neq0 — סיימת (משפט 1).
  2. 2שקול וזול לא פחות: הראי ש-λ0In−A\lambda_0I_n-A הפיכה, כלומר det⁡(λ0In−A)≠0\det(\lambda_0I_n-A)\neq0.
  3. 3למשולשית — פשוט השווי את λ0\lambda_0 לאיברי האלכסון (מסקנה 2).
להפריך שיש ל-AA ערך עצמי בשדה
  1. 1חשבי את pAp_A.
  2. 2הראי שאין לו שורש בשדה: מעל R\mathbb{R} — דיסקרימיננטה שלילית; מעל Zp\mathbb{Z}_p — הצבת כל pp האיברים.
  3. 3הסיקי: אין ע"ע, ולכן גם אין בסיס של ו"ע ו-AA אינה לכסינה מעל השדה הזה.
  4. 4צייני במפורש שמעל C\mathbb{C} המצב הפוך (מסקנה 5) — זה מה שהבודק מחפש.

איך מוכיחים

המהלכים שעובדים בשבוע הזה
למצוא את כל הערכים העצמיים של AA
  1. 1כתבי את λIn−A\lambda I_n-A (בסדר הזה).
  2. 2חשבי det⁡\det — ופתחי לפי שורה/עמודה עם הכי הרבה אפסים; אם יש מבנה בלוקים, השתמשי במשפט 4.
  3. 3פרקי את pAp_A לגורמים ומצאי את השורשים בשדה הנתון.
  4. 4בדיקה: סכום השורשים (עם ריבוי) =trace(A)=trace(A) ומכפלתם =det⁡(A)=\det(A) כאשר הפולינום מתפרק.
להוכיח טענה על הפולינום האופייני
  1. 1אם הטענה על דמיון — השתמשי ב-pP−1AP(λ)=det⁡(λI−P−1AP)=det⁡(P−1(λI−A)P)p_{P^{-1}AP}(\lambda)=\det(\lambda I-P^{-1}AP)=\det(P^{-1}(\lambda I-A)P) וכפליות det⁡\det.
  2. 2אם הטענה על מעלה/מקדמים — צטטי את למה 1 ומשפט 2 (pAp_A מתוקן ממעלה nn).
  3. 3אם הטענה על מבנה בלוקים — משפט 4.
  4. 4אם הטענה על פירוק — עברי ל-C\mathbb{C} והשתמשי במסקנות 4,5.
לקבוע לכסינות בעזרת הפולינום האופייני
  1. 1חשבי pAp_A ומצאי את השורשים בשדה.
  2. 2nn שורשים שונים — לכסינה, סיימת (מסקנה 1, שבוע 5).
  3. 3יש שורש חוזר — חשבי Vλ=Null(λI−A)V_\lambda=Null(\lambda I-A) עבורו וספרי מימדים.
  4. 4סכום מימדי המרחבים העצמיים =n=n — לכסינה; קטן מ-nn — לא לכסינה.

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

  • 1p_A(λ) = det(λI − A) — בסדר הזה. ההיפך הופך סימנים ומקלקל את המתוקנוּת.
  • 2p_A מתוקן ממעלה n. המקדם של λ^{n-1} הוא −tr(A), והמקדם החופשי הוא (−1)ⁿdet(A).
  • 3למטריצות דומות אותו פולינום אופייני — אבל ההפך לא נכון.
  • 4בפולינום של מטריצת בלוקים משולשית מכפילים את הפולינומים של הבלוקים.
מטלה 7
לתרגל את החומר של השבוע
שקפי הרצאה 6
המצגת המקורית במלואה
שבוע 5:לכסוןריבוי אלגברי וגיאומטרי:שבוע 7