פרמננטה

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

$per(A)=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}A_{i,\sigma (i)}$,

כאשר הסכום הוא על-פני התמורות $\ \sigma \in S_{n}$ בחבורת התמורות. בפרט, הפרמננטה של מטריצה שרכיביה חיוביים, גם היא חיובית. הפרמננטה הופיעה לראשונה במאמר שכתב אוגוסטין לואי קושי, ב-1812.

בעוד שלדטרמיננטה יש משמעות גאומטרית והיא קשורה ישירות בפתרון משוואות לינאריות (על-פי נוסחת קרמר), הפרמננטה שימושית בהקשרים שונים לחלוטין, כגון חישובי הסתברויות וספירת מסלולים בגרפים. שימוש נוסף הוא בעיית מציאת מספר השידוכים המושלמים בגרף דו צדדי. הבדל בולט אחר הוא העבודה שנדרש להשקיע בכל חישוב. למרות שבשני המקרים התוצאה תלויה ב-n עצרת מכפלות, את הדטרמיננטה אפשר לחשב בכ- $\ n^{3}$ פעולות באמצעות דירוג המטריצה המדוברת (ואף מהר יותר, באמצעות כפל מטריצות מהיר). לעומת זאת, לא ידועה שיטה מהירה לחישוב הפרמננטה. סיכום כל המכפלות השונות בזו אחר זו יהיה כרוך ב $\ {n!}$ פעולות וסיבוכיות האלגוריתם המהיר ביותר הידוע היא $\ {O(n2^{n})}$. יתירה מזאת, לזלי ואלינט הראה שזו בעיה NP-קשה. כלומר אם קיים אלגוריתם עם סיבוכיות פולינומית לחישוב של הפרמננטה, ינבע מכך כי P=NP, והדבר נכון אף למטריצות שאבריהן הן $\ 0$ או $\ 1$. בעיית חישוב הפרמננטה שייכת למחלקת הסיבוכיות P# והיא שלמה עבורה. מאידך ידוע אלגוריתם פולינומי אקראי לקירוב הפרמננטה.

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

דוגמאות

$\operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc,$ ו-$\operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei+bfg+cdh+ceg+bdi+afh.$.

לקריאה נוספת

• H. Minc, Permanents, Addison-Wesley, Reading, MA, 1978
• Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science 8: 189-201
• Mark Jerrum, Alistair Sinclair, Eric Vigoda (2004) "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", Journal of the ACM, Volume 51, Pages 671--697