פרמננטה

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

per(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n A_{i, \sigma(i)},

כאשר הסכום הוא על-פני התמורות \ \sigma \in S_n בחבורת התמורות. בפרט, הפרמננטה של מטריצה שרכיביה חיוביים, גם היא חיובית.

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

בערכים שיכולה הפרמננטה לקבל עוסקת השערת ואן דר ורדן, שהוצגה ב- 1926. לפי ההשערה, הפרמננטה של מטריצה דו-סטוכסטית שרכיביה חיוביים נמצאת בין \ \frac{n!}{n^n} (שהוא הערך שלה עבור מטריצה שכל רכיביה \ 1/n) ל- 1. את ההשערה הצליחו להוכיח רק ב- 1981, ופותריה זכו בשנה שלאחר מכן בפרס פולקרסון.

שפות אחרות