הצגת המקור של הדף "מטריצה דו-סטוכסטית"

{{סימון מתמטי}}
ב[[מתמטיקה]], [[מטריצה ריבועית]] [[מספר ממשי|ממשית]] היא '''מטריצה דו-סטוכסטית''', אם כל רכיביה [[מספרים חיוביים ושליליים|אי-שליליים]], וסכום האיברים בכל שורה ובכל עמודה שלה הוא 1.

מטריצה <math>A</math> היא מטריצה דו-סטוכסטית [[אם ורק אם]] שתי המטריצות <math>A</math> ו-<math>A^T</math> הן [[מטריצה סטוכסטית|מטריצות סטוכסטיות]].

== הגדרה מתמטית ==
יהי <math>n\in \mathbb{N}</math> מספר טבעי ו-<math>A\in\mathbb{R}^{n\times n}</math> מטריצה ריבועית ממשית מגודל <math>n</math>. <math>A</math> תקרא '''מטריצה דו-סטוכסטית''' אם ורק אם היא מקיימת את שלושת התנאים הבאים:

# '''כל איבריה בין 0 ל-1''':  לכל <math>1\le i,j \le n</math> מתקיים כי <math>0\le A_{ij}\le 1</math>.
# '''סכום האיברים בכל עמודה שווה ל-1''': לכל <math>1\le j_0 \le n</math> מתקיים כי <math>\sum_{i=1}^n{A_{ij_0}}=1</math>.
# '''סכום האיברים בכל שורה שווה ל-1''': לכל <math>1\le i_0 \le n</math> מתקיים כי <math>\sum_{j=1}^n{A_{i_0j}}=1</math>.

נובע ישירות מההגדרה כי <math>A</math> דו-סטוכסטית אם ורק אם [[שחלוף (מתמטיקה)|המטריצה המשוחלפת]] שלה <math>A^T</math> היא מטריצה דו-סטוכסטית.

== תכונות ==

* כל [[מטריצת תמורה]] היא מטריצה דו-סטוכסטית. בפרט, [[מטריצת היחידה]] היא מטריצה דו-סטוכסטית.
* בהינתן <math>n\in \mathbb{N}</math> מספר טבעי ו-<math>A,B\in\mathbb{R}^{n\times n}</math> מטריצות דו-סטוכסטיות מתקיים כי [[כפל מטריצות|כפל המטריצות]] <math>AB</math> היא מטריצה דו-סטוכסטית.
* בהינתן <math>n\in \mathbb{N}</math> מספר טבעי, <math>A,B\in\mathbb{R}^{n\times n}</math> ו-<math>0\le\lambda\le 1</math>, המטריצה <math>\lambda A+(1-\lambda)B</math> היא מטריצה דו-סטוכסטית.
* בהינתן <math>n\in \mathbb{N}</math> מספר טבעי ו-<math>a,b\in\mathbb{R}^n</math> ניתן להוכיח כי <math>a</math> [[מיוריזציה|ממייר]] את <math>b</math> [[אם ורק אם]] קיימת מטריצה דו-סטוכסטית <math>D\in\mathbb{R}^{n\times n}</math> כך ש-<math>b=Da</math>.

==פאון בירקהוף ומשפט בירקהוף-פון נוימן==

אם מתייחסים ל-<math>\mathbb{R}^{n\times n}</math> כמרחב וקטורי <math>n^2</math> ממדי, ניתן להתייחס לאוסף המטריצות הדו-סטוכסטיות מסדר <math> n \times n </math> כ[[פוליטופ]] (פאון מממד כללי כלשהו) מממד <math> (n-1)^2 </math>.{{ביאור|במטריצה דו-סטוכסטית מממד <math>n\times n</math> ישנם <math>n^2</math> איברים, וישנם <math>2n-1</math> אילוצים: לכאורה ישנם <math>n</math> אילוצים על סכומי השורות ו-<math>n</math> אילוצים על סכומי העמודות, אולם למעשה יש אילוץ שנספר פעמיים, סכום כל האיברים במטריצה. לכן כמות דרגות החופש, ששווה לממד הפוליטופ, היא <math>n^2-2n+1=(n-1)^2</math>.}} פוליטופ זה נקרא '''[[פאון בירקהוף]]''', על שם ה[[מתמטיקאי]] [[גארט בירקהוף]].

'''משפט בירקהוף-פון נוימן''' קובע כי לכל <math>n\in \mathbb{N}</math> פאון בירקהוף הוא פאון [[קבוצה קמורה|קמור]] שקודקודיו הם מטריצות התמורה ה-<math>n</math> ממדיות. בניסוח מתמטי, לכל מטריצה דו-סטוכסטית <math>A\in\mathbb{R}^{n\times n}</math> קיימים <math>k\in \mathbb{N}</math>, <math>\lambda_1,\dots,\lambda_k\in\mathbb{R}</math> ו-<math>P_1,\dots,P_k\in\mathbb{R}^{n\times n}</math> כך ש:

# <math>\lambda_i> 0</math> לכל <math>1\le i\le k</math>
# <math>P_i</math> היא מטריצת תמורה לכל <math>1\le i\le k</math>
# <math>\sum_{i=1}^k{\lambda_i}=1</math>
# <math>\sum_{i=1}^k{\lambda_iP_i}=A</math>

המשפט ההפוך נכון גם הוא: מטריצה <math>A\in\mathbb{R}^{n\times n}</math> היא דו-סטוכסטית אם ורק אם היא נמצאת בפאון הקמור שקודקודיו הם מטריצות התמורה.

ה[[משפט (מתמטיקה)|משפט]] נקרא על שם גארט בירקהוף ו[[ג'ון פון נוימן]].

=== תקציר הוכחת משפט בירקהוף-פון נוימן ===
אם <math>A</math> היא מטריצת תמורה, הוכחת המשפט [[טריוויאלי]]ת.

אחרת, מגדירים <math>B_1 := A</math> ובונים [[גרף דו-צדדי]] המקשר בין קבוצת שורות המטריצה לקבוצת עמודות המטריצה, כאשר מותחים קשת בין שורה <math>i</math> לעמודה <math>j</math> אם מתקיים <math>A_{ij}\ne 0</math>. בגלל ש-<math>A</math> מטריצה דו-סטוכסטית, ניתן להוכיח כי היא מקיימת את התנאי של [[משפט החתונה]] ולכן ניתן לבנות [[שידוך (תורת הגרפים)|שידוך]] בין כל שורה לעמודה. עבור שורה <math>i</math> מסמנים ב-<math>j_i</math> את העמודה המשודכת לה.

מגדירים <math>\lambda:=\min(A_{1j_1},\dots,A_{nj_n})</math>, ומסמנים את השורה המתאימה ל-<math>\lambda</math> ב-<math>i_0</math>, כך ש-<math>A_{i_0j_{i_0}}=\lambda</math>. מתוך תכונות המטריצה הדו-סטוכסטית ואופן בחירת השורות והעמודות מתקיים כי <math>0<\lambda< 1</math>. בנוסף, בונים מטריצה <math>P\in\mathbb{R}^{n\times n}</math> שכל איבריה מתאפסים למעט בקואורדינטות <math>i,j_i</math>, שם היא מקבלת את הערך 1. מכיוון שאוסף הזוגות <math>(i,j_i)</math> הוא שידוך, <math>P</math> היא מטריצת תמורה.

מגדירים <math>B_2:=\frac{1}{1-\lambda}(B_1-\lambda P)</math>. קל לראות כי <math>B_2</math> אף היא מטריצה דו-סטוכסטית{{ביאור|<math>P</math> מטריצת תמורה ולכן דו-סטוכסטית, ולכן סכום כל שורה ועמודה של <math>\lambda P</math> הוא <math>\lambda</math>, ומכיוון ש-<math>B_1</math> דו-סטוכסטית, סכום כל שורה ועמודה של <math>B_1-\lambda P</math> שווה <math>1-\lambda</math>. המטריצה הנותרת אחרי הכפל בהופכי של הסקלר הזה היא מטריצה דו-סטוכסטית.}} אשר מתאפסת בכל הקואורדינטות שבהן <math>B_1</math> מתאפסת ובנוסף מתאפסת גם בקואורדינטה <math>(i_0,j_{i_0})</math> לפחות. אם <math>B_2</math> היא מטריצת תמורה, מסיימים. אחרת, חוזרים על התהליך עם <math>B_2</math> וממשיכים תוך איפוס איבר נוסף בכל צעד, עד שמגיעים למטריצת תמורה <math>B_k</math>.

לבסוף, על-ידי חישוב לאחור מתקבל כי כל המטריצות <math>B_1,\dots,B_k</math> ניתנות לייצוג כסכום ממושקל של מטריצות תמורה, ובפרט <math>B_1=A</math>.

המשפט ההפוך נובע ישירות מהתכונות שהוזכרו לעיל.

'''מ.ש.ל.'''

== שימושים ==
למטריצות דו-סטוכסטיות יש כמה תכונות ויישומים חשובים ב[[מתמטיקה]], [[פיזיקה]] [[מדעי המחשב|ומדעי המחשב]]. ב[[תורת ההסתברות]], מטריצות דו-סטוכסטיות משמשות לייצוג מעברים בין מצבים או אירועים שונים, וניתן להשתמש בהן למודל של התנהגות של [[שרשראות מרקוב]]. ב[[מכניקת הקוונטים]] משתמשים במטריצות דו-סטוכסטיות לתיאור התפתחות מצבים קוונטיים, והן קשורות למושג של [[מנהור קוונטי]].

במדעי המחשב, מטריצות דו-סטוכסטיות משמשות ב[[אלגוריתם|אלגוריתמים]] ל[[למידת מכונה]] ו[[ניתוח נתונים]], והן יושמו בתחומים כמו [[עיבוד שפה טבעית]], [[זיהוי עצמים]] ומערכות המלצות. הם משמשים גם באופטימיזציה קומבינטורית וניתוח רשת, שם ניתן להשתמש בהם כדי לייצג את המשקלים או החוזקות של קשרים בין צמתים שונים בגרף.

==קישורים חיצוניים==
* {{MathWorld}}

==ביאורים==
{{ביאורים}}

[[קטגוריה:מטריצות]]