משפט פרון-פרובניוס

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

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

== המשפט ==
הגרסה הבסיסית של המשפט מטפלת במטריצה שרכיביה חיוביים.

משפט. תהי <math>A</math> מטריצה ריבועית ממשית, שכל רכיביה חיוביים (ממש). אז:
# יש לה ערך עצמי ממשי <math>r>0</math>, כך שכל ערך עצמי אחר הוא בעל ערך מוחלט קטן ממש מ-<math>r</math>. יתרה מזו,
# יש וקטור עצמי יחיד (עד כדי כפל בסקלר) מריבוי אלגברי 1 השייך ל-<math>r</math>, וכל רכיביו חיוביים (ממש); זהו הווקטור העצמי היחיד של <math>A</math> שכל רכיביו חיוביים.

טיעון פשוט יחסית מאפשר להכליל את התוצאה למטריצה פרמיטיבית: מטריצה אי שלילית שחזקה שלה היא חיובית ממש.

גרסה כללית יותר מרשה לערכים של המטריצה להתאפס. לשם כך אומרים ש-<math>A</math> מטריצה פריקה אם יש מטריצת פרמוטציה <math>P</math> כך ש-<math>PAP^{-1}</math> היא מטריצת בלוקים, שהבלוק השמאלי-תחתון שלה הוא אפס.

משפט פרון-פרובניוס. אם <math>A</math> מטריצה אי-פריקה שכל רכיביה אי שליליים, אז:
# יש לה ערך עצמי ממשי <math>r>0</math>, כך שכל ערך עצמי אחר הוא בעל ערך מוחלט קטן או שווה ל-<math>r</math>;
# יש סדר <math>h</math> כך שהספקטרום של <math>A</math> נשמר תחת סיבוב באחת-חלקי-<math>h</math> של המעגל. יתרה מזו,
# יש וקטור עצמי יחיד (עד כדי כפל בסקלר) השייך ל-<math>r</math>, וכל רכיביו חיוביים (ממש); זהו הווקטור העצמי היחיד של <math>A</math> שכל רכיביו חיוביים.

== רקע ותוצאות ==
הערכים העצמיים של כל מטריצה ריבועית <math>A</math> הם השורשים (המרוכבים) של הפולינום האופייני; הערך המוחלט הגדול ביותר בין השורשים האלה הוא הרדיוס הספקטרלי של המטריצה. הרדיוס הספקטרלי שולט בקצב הגידול של החזקות <math>A^n</math>: אם <math>r = \rho(A)</math> הוא הרדיוס הספקטרלי, אז הרכיבים בגבול <math>\lim_{n\to\infty} r^{-n}A^n</math> חסומים, ואם הריבוי הגאומטרי הוא 1, מובטח שהגבול הזה קיים, והוא מטריצה בעלת דרגה 1.

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

== הוכחה ==
להלן הוכחה עבור המקרה הבסיסי של מטריצות חיוביות. תהי <math>A\in M_{d}(\mathbb{R})</math> מטריצה חיובית. נבחין שלכל וקטור <math>v</math> אי שלילי שאינו 0, מכיוון ש-<math>A</math> מטריצה שכל אבריה חיוביים, נובע כי <math>Av</math> הוא וקטור שכל אבריו חיוביים.

יהי <math>\Delta</math> אוסף כל הווקטורים ב-<math>\mathbb{R}^d</math> האי שליליים שנמצאים על כדור היחידה. נשים לב שזוהי קבוצה קומפקטית.

טענה 1: יש ל-<math>A</math> וקטור עצמי חיובי <math>v</math> עם ערך עצמי חיובי <math>\rho</math>.

:הוכחה: נגדיר פונקציה <math>L:\Delta \to R_{>0}</math> המוגדרת באופן הבא: <math>L(x)=\min\{x_{i}}|x_{i}\neq 0}\}</math>, כלומר מסתכלים על הקואורדינטות החיוביות של x (יש כאלו בהכרח, מהגדרת <math>\Delta</math>) ולוקחים מהם את המינימום של המנה בין <math>Ax</math> ל-x בקואורדינטות אלו. זוהי פונקציה רציפה ולכן היא מקבלת מקסימום ב-<math>\Delta</math>. יהי <math>v\in\Delta></math> אם <math>L(v)=\rho</math> המקסימום הנ"ל, אז <math>(Av)_{i}\geq\rho v_{i}</math> לכל i.
:נטען ש-<math>v</math> הוא וקטור עצמי ביחס לערך העצמי <math>\rho</math>:
::נניח בשלילה כי <math>Av\neq \rho v</math>. לכן וקטור <math>w = Av-\rho v</math> הוא וקטור אי שלילי שאינו וקטור האפס. לכן הווקטור <math>Aw</math> הוא וקטור חיובי ואז יש <math>\epsilon > 0</math> כך ש-<math>Aw > \epsilon Av</math>. כלומר נקבל ש-<math>A(Av) > (\rho+\epsilon)Av</math>. יהי <math>u = \tfrac {Av}{||Av||}</math>. מקבלים ש-<math>u \in \Delta</math> מקיים <math>Au >(\rho + \epsilon)u</math> ולכן <math>L(u) > \rho + \epsilon</math> בסתירה למקסימליות של <math>v</math>. כמו כן <math>v</math> אי שלילי ולכן <math>Av=\rho v</math> חיובי ולכן <math>v</math> חיובי.

טענה 2: הרדיוס הספקטרלי של <math>A</math> הוא <math>\rho</math>.

:הוכחה: יהי <math>\mu</math> ערך עצמי של <math>A</math> עם וקטור עצמי מנורמל <math>y</math>. זאת אומרת: <math>Ay=\mu y</math>, או: לכל <math>i\in\{1,\dots,d\}</math>,
<math display="block">\mu y_{i}=\sum_{j}{A_{ij}y_{j}}.</math>
:מאי-שוויון המשולש מתקבל ש-<math>|\mu||y_{i}|\leq \sum_{j}|A_{ij}y_j|=\sum_{j}A_{ij}|y_j|</math> . יהי <math>u = |y|</math> הווקטור שערכיו הם הערכים המוחלטים של <math>y</math>. נובע מכך כי <math>u \in \Delta</math> ומתקיים: <math>|\mu|\leq L(u)\leq \rho</math> וסיימנו.

טענה 3: הריבוי הגאומטרי של <math>\rho</math> הוא 1.

:הוכחה: נניח בשלילה שיש וקטור <math>u</math> בלתי תלוי ב-<math>v</math> וקטור עצמי עבור <math>\rho</math>. בה"כ נניח שהוא ממשי (אחרת אפשר להסתכל על החלק הממשי והחלק המדומה בנפרד). הווקטור <math>v</math> הוא חיובי ולכן יש <math>\epsilon > 0</math> כך שהווקטור <math>w = v-\epsilon u</math> הוא וקטור אי שלילי עם קואורדינטה אחת לפחות שמתאפסת. מצד שני, <math>w</math> איננו וקטור האפס כי <math>u,v</math> בלתי תלויים ליניארית. מצד שני <math>w</math> הוא וקטור עצמי אי שלילי ביחס לערך העצמי <math>\rho</math>. לכן, כמו בטענה 1, נובע שהוא וקטור חיובי, בסתירה להנחה.

טענה 4: הריבוי האלגברי של <math>\rho</math> הוא 1.

:הוכחה: הרעיון הוא לקרב את <math>A</math> על ידי מטריצה ממשית <math>B</math> ששווה ל-<math>\rho</math> בקואורדינטה הראשונה ומתאפסת על שאר אברי העמודה והשורה הראשונות.

:כמו בטענה 1 אפשר למצוא וקטור עצמי שמאלי חיובי <math>w^T</math> של הערך העצמי <math>\rho</math> . יהי <math>U</math> המרחב המאונך ל-<math>w</math> במכפלה הפנימית הסטנדרטית כלומר <math>U =\{u\in \mathbb{R}^d|w^Tu=0\}</math>

:מקבלים שאם <math>u \in U</math> אז <math>w^TAu=w^T(\rho u)= \rho w^Tu=0</math> ולכן <math>Au \in U</math>. קיבלנו אם כן ש-<math>U</math> מרחב אינוורינטי ביחס ל-<math>A</math>. נשים לב ש-<math>w^Tv> 0</math> כי שני הווקטורים העצמיים חיוביים. לכן <math>v \not \in U</math> וניתן להשלים אותו לבסיס של <math>\mathcal{B}=\{v,b_{1},b_{2}...b_{d-1}\}</math> של <math>\mathbb{R}^d</math>. יהי <math>B</math> המטריצה <math>A</math> ביחס לבסיס <math>\mathcal{B}</math> אז נקבל ש-<math>B</math> מהצורה
<math display="block">B = \begin{pmatrix} \rho & 0 \\ 0 & C_{(d-1)*(d-1)} \end{pmatrix}</math>
:כאשר המטריצה <math>C</math> היא מטריצה ממשית. כיוון שהמטריצות <math>A,B</math> דומות, יש להן את אותו ריבוי אלגברי וגאומטרי (ריבוי גאומטרי 1) לערך העצמי <math>\rho</math>.
:הפולינום האופייני של <math>A</math> הוא <math>P_A(t)=P_B(t)=(t-\rho)P_C(t)</math>. נניח בשלילה שהריבוי האלגברי הוא יותר מ-1. נקבל ש-<math>\rho</math> הוא ערך עצמי של המטריצה <math>C</math> עם וקטור עצמי <math>v_C \in \mathbb{R}^{(d-1)}</math>.
:יהי <math>u = (0, v_C)^T \in \mathbb{R}^d</math>, אז <math>u,e_1</math> שני וקטורים עצמיים בלתי תלויים של <math>B</math> ולכן הריבוי הגאומטרי של <math>B</math> (ואז גם של <math>A</math>) הוא לפחות 2 בסתירה.

טענה 5: אם <math>u</math> הוא וקטור עצמי חיובי של <math>A</math> אז הוא כפולה חיוביות של <math>v</math>.

:הוכחה: יהי <math>\mu</math> הערך העצמי המתאים ל-<math>u</math>. מכיוון ש-<math>u</math> ו-<math>A</math> חיוביות נקבל ש-<math>0<\mu\leq \rho</math>. עבור <math>\epsilon > 0</math> קטן מספיק נקבל שהווקטור <math>w = v-\epsilon u</math> וקטור חיובי. עבור i מסוים נקבל ש-<math>(Aw)_i=\rho v_i - \epsilon \mu u_i \geq \rho (v-\epsilon u)_i=\rho w_i </math>. כמו בטענה הראשונה נקבל ממקסימליות ש-<math>\rho</math> ערך עצמי של <math>w</math> ולכן גם של <math>u</math>. כעת מה שנדרש להוכיח נובע ישירות מטענה 3.

טענה 6: אם <math>\mu</math> ערך עצמי של <math>A</math> השונה מ-<math>\rho</math> אז <math>|\mu| < \rho</math>.

:הוכחה: נניח בשלילה ש-<math>|\mu| = \rho</math> ויהי <math>y</math> וקטור עצמי מנורמל של <math>\mu</math> .יהי <math>u = |y|</math> הווקטור שערכיו הם הערכים המוחלטים של <math>y</math>. מקבלים:
<math display="block">(Au)_i = \sum_{j}{A_{ij}|y_{j}|} = \sum_{j}|{A_{ij}y_{j}|} \geq |\sum_{j}{A_{ij}y_{j}}|=\rho u_i</math>
:ממקסימליות <math>u</math> נקבל ש-<math>\rho</math> ערך עצמי המתאים לוקטור <math>u</math> ולכן האי שוויון לעיל הוא בעצם שוויון. לכן נקבל שכל האיברים <math>A_{ij}y_j</math> נמצאים על אותה הקרן היוצאת מ-0 במישור המרוכב. כיוון שאברי המטריצה <math>A</math> ממשיים וחיוביים נקבל שכל האיברים <math>y_j</math> על אותה הקרן היוצאת מ-0 במישור המרוכב. לכן יש <math>\theta</math> כך שהווקטור <math>z = e^{i\theta}y</math> הוא וקטור עצמי חיובי ומטענה 5 נקבל ש-<math>\rho = \mu</math> בסתירה.

==קישורים חיצוניים==
* 

==הערות שוליים==

קטגוריה:אלגברה ליניארית
קטגוריה:תהליכים סטוכסטיים