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

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

מטריצה A היא דו-סטוכסטית אם ורק אם גם A וגם הטרנספוז שלה A^T הן מטריצות סטוכסטיות.

האוסף של כל המטריצות הדו-סטוכסטיות מסדר n×n יוצר פוליטופ (צבירה גיאומטרית) שנקרא פאון בירקהוף. לפאון הזה מימד (n-1)^2.

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

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

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

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

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

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

פאון בירקהוף הוא אוסף כל המטריצות הדו-סטוכסטיות. המשפט של בירקהוף-פון נוימן אומר: כל מטריצה דו-סטוכסטית היא ממוצע של מטריצות תמורה. כלומר אפשר לכתוב אותה כשקלול של כמה מטריצות תמורה.

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

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