מטריצה דו-סטוכסטית

בערך זה
נעשה שימוש
בסימנים מוסכמים
מתחום המתמטיקה.
להבהרת הסימנים
ראו סימון מתמטי.

במתמטיקה, מטריצה ריבועית ממשית היא מטריצה דו-סטוכסטית, אם כל רכיביה אי-שליליים, וסכום האיברים בכל שורה ובכל עמודה שלה הוא 1.

מטריצה $A$ היא מטריצה דו-סטוכסטית אם ורק אם שתי המטריצות $A$ ו- $A^{T}$ הן מטריצות סטוכסטיות.

הגדרה מתמטית עריכה

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

כל איבריה בין 0 ל-1: לכל $1\leq i,j\leq n$ מתקיים כי $0\leq A_{ij}\leq 1$ .
סכום האיברים בכל עמודה שווה ל-1: לכל $1\leq j_{0}\leq n$ מתקיים כי $\sum _{i=1}^{n}{A_{ij_{0}}}=1$ .
סכום האיברים בכל שורה שווה ל-1: לכל $1\leq i_{0}\leq n$ מתקיים כי $\sum _{j=1}^{n}{A_{i_{0}j}}=1$ .

נובע ישירות מההגדרה כי $A$ דו-סטוכסטית אם ורק אם המטריצה המשוחלפת שלה $A^{T}$ היא מטריצה דו-סטוכסטית.

תכונות עריכה

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

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

אם מתייחסים ל- $\mathbb {R} ^{n\times n}$ כמרחב וקטורי $n^{2}$ ממדי, ניתן להתייחס לאוסף המטריצות הדו-סטוכסטיות מסדר $n\times n$ כפוליטופ (פאון מממד כללי כלשהו) מממד $(n-1)^{2}$ .^[א] פוליטופ זה נקרא פאון בירקהוף, על שם המתמטיקאי גארט בירקהוף.

משפט בירקהוף-פון נוימן קובע כי לכל $n\in \mathbb {N}$ פאון בירקהוף הוא פאון קמור שקודקודיו הם מטריצות התמורה ה- $n$ ממדיות. בניסוח מתמטי, לכל מטריצה דו-סטוכסטית $A\in \mathbb {R} ^{n\times n}$ קיימים $k\in \mathbb {N}$ , $\lambda _{1},\dots ,\lambda _{k}\in \mathbb {R}$ ו- $P_{1},\dots ,P_{k}\in \mathbb {R} ^{n\times n}$ כך ש:

$\lambda _{i}>0$ לכל $1\leq i\leq k$
$P_{i}$ היא מטריצת תמורה לכל $1\leq i\leq k$
$\sum _{i=1}^{k}{\lambda _{i}}=1$
$\sum _{i=1}^{k}{\lambda _{i}P_{i}}=A$

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

המשפט נקרא על שם גארט בירקהוף וג'ון פון נוימן.

תקציר הוכחת משפט בירקהוף-פון נוימן עריכה

אם $A$ היא מטריצת תמורה, הוכחת המשפט טריוויאלית.

אחרת, מגדירים $B_{1}:=A$ ובונים גרף דו-צדדי המקשר בין קבוצת שורות המטריצה לקבוצת עמודות המטריצה, כאשר מותחים קשת בין שורה $i$ לעמודה $j$ אם מתקיים $A_{ij}\neq 0$ . בגלל ש- $A$ מטריצה דו-סטוכסטית, ניתן להוכיח כי היא מקיימת את התנאי של משפט החתונה ולכן ניתן לבנות שידוך בין כל שורה לעמודה. עבור שורה $i$ מסמנים ב- $j_{i}$ את העמודה המשודכת לה.

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

מגדירים $B_{2}:={\frac {1}{1-\lambda }}(B_{1}-\lambda P)$ . קל לראות כי $B_{2}$ אף היא מטריצה דו-סטוכסטית^[ב] אשר מתאפסת בכל הקואורדינטות שבהן $B_{1}$ מתאפסת ובנוסף מתאפסת גם בקואורדינטה $(i_{0},j_{i_{0}})$ לפחות. אם $B_{2}$ היא מטריצת תמורה, מסיימים. אחרת, חוזרים על התהליך עם $B_{2}$ וממשיכים תוך איפוס איבר נוסף בכל צעד, עד שמגיעים למטריצת תמורה $B_{k}$ .

לבסוף, על-ידי חישוב לאחור מתקבל כי כל המטריצות $B_{1},\dots ,B_{k}$ ניתנות לייצוג כסכום ממושקל של מטריצות תמורה, ובפרט $B_{1}=A$ .

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

מ.ש.ל.

שימושים עריכה

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

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

ביאורים עריכה

^ במטריצה דו-סטוכסטית מממד $n\times n$ ישנם $n^{2}$ איברים, וישנם $2n-1$ אילוצים: לכאורה ישנם $n$ אילוצים על סכומי השורות ו- $n$ אילוצים על סכומי העמודות, אולם למעשה יש אילוץ שנספר פעמיים, סכום כל האיברים במטריצה. לכן כמות דרגות החופש, ששווה לממד הפוליטופ, היא $n^{2}-2n+1=(n-1)^{2}$ .
^ $P$ מטריצת תמורה ולכן דו-סטוכסטית, ולכן סכום כל שורה ועמודה של $\lambda P$ הוא $\lambda$ , ומכיוון ש- $B_{1}$ דו-סטוכסטית, סכום כל שורה ועמודה של $B_{1}-\lambda P$ שווה $1-\lambda$ . המטריצה הנותרת אחרי הכפל בהופכי של הסקלר הזה היא מטריצה דו-סטוכסטית.

[1] במטריצה דו-סטוכסטית מממד $n\times n$ ישנם $n^{2}$ איברים, וישנם $2n-1$ אילוצים: לכאורה ישנם $n$ אילוצים על סכומי השורות ו- $n$ אילוצים על סכומי העמודות, אולם למעשה יש אילוץ שנספר פעמיים, סכום כל האיברים במטריצה. לכן כמות דרגות החופש, ששווה לממד הפוליטופ, היא $n^{2}-2n+1=(n-1)^{2}$ .

[2] $P$ מטריצת תמורה ולכן דו-סטוכסטית, ולכן סכום כל שורה ועמודה של $\lambda P$ הוא $\lambda$ , ומכיוון ש- $B_{1}$ דו-סטוכסטית, סכום כל שורה ועמודה של $B_{1}-\lambda P$ שווה $1-\lambda$ . המטריצה הנותרת אחרי הכפל בהופכי של הסקלר הזה היא מטריצה דו-סטוכסטית.

[א]

[ב]