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

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

את המשפט הוכיח אוסקר פרון (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)$ הוא הרדיוס הספקטרלי, אז הרכיבים בגבול של $\ r^{-n}A^{n}$ חסומים, ואם הריבוי הגאומטרי הוא 1, מובטח שהגבול הזה קיים, והוא מטריצה בעלת דרגה 1.

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

הוכחה

נביא הוכחה^[1] עבור המקרה הבסיסי של מטריצות חיוביות. תהי $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\{{{\tfrac {(Ax)_{i}}{x_{i}}}|x_{i}\neq 0}\}$ , כלומר מסתכלים על הקואורדינטות החיוביות של x (יש כאלו מהגדרת $\Delta$ ) ולוקחים מהם את המינימום של המנה בין $Ax$ ל-x בקואורדינטות אלו. זוהי פונקציה רציפה ולכן היא מקבלת מקסימום ב- $\Delta$ . יהי $L(v)=\rho$ המקסימום הנ"ל. נטען ש- $v$ הוא וקטור עצמי ביחס לערך העצמי $\rho$ . כיוון ש- $L(v)=\rho$ נקבל ש- $(Av)_{i}\geq \rho v_{i}$ לכל i. נראה את הכיוון ההפוך. נניח בשלילה ש- $Av\neq \rho v$ . לכן נקבל שוקטור $w=Av-\rho v$ הוא וקטור אי שלילי שאינו וקטור האפס. לכן הווקטור $Aw$ הוא וקטור חיובי ואז יש $\epsilon >0$ כך ש- $Aw>\epsilon Av$ . כלומר נקבל ש- $A(Av)>(\rho +\epsilon )Av$ . יהי $u={\tfrac {Av}{||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\Rightarrow uy_{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^{T}u=0\}$

מקבלים שאם $u\in U$ אז $w^{T}Au=w^{T}(\rho u)=\rho w^{T}u=0$ ולכן $Au\in U$ . קיבלנו אם כן ש- $U$ מרחב אינוורינטי ביחס ל- $A$ . נשים לב ש- $w^{T}v>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<\mu \leq \rho$ . עבור $\epsilon >0$ קטן מספיק נקבל שהווקטור $w=v-\epsilon u$ וקטור חיובי עבור i מסוים נקבל ש- $(Aw)_{i}=\rho v_{i}-\epsilon \mu u_{i}\leq \rho (v-\epsilon u)_{i}=\rho w_{i}$ . כמו בטענה הראשונה נקבל ממקסמליות ש- $\rho$ ערך עצמי של $w$ ולכן גם של $u$ . כעת נקבל את הדרוש מטענה 3.

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

הוכחה: נניח בשלילה ש- $|\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$ בסתירה.