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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

**טענה 3:** הריבוי הגאומטרי של \rho הוא 1.

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

**טענה 4:** הריבוי האלגברי של \rho הוא 1.

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

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

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

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

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

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

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

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

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

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