הצגת המקור של הדף "פרמננטה"

ב[[אלגברה ליניארית]] וב[[קומבינטוריקה]], ה'''פרמננטה''' של [[מטריצה]] היא גודל מספרי, המחושב על-פי נוסחה דומה לזו של ה[[דטרמיננטה]]. בעוד שב[[חישוב]] הדטרמיננטה, הנפוץ בהרבה, יש לחבר ולחסר את המכפלות של אברי המטריצה לסירוגין, הפרמננטה מוגדרת כסכום של כל המכפלות, ללא [[חיסור]]:
: <math> per(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n A_{i, \sigma(i)}</math>,
כאשר הסכום הוא על-פני התמורות <math>\ \sigma \in S_n</math> ב[[חבורת התמורות]]. בפרט, הפרמננטה של מטריצה שרכיביה חיוביים, גם היא חיובית. הפרמננטה הופיעה לראשונה במאמר שכתב [[אוגוסטן לואי קושי]], ב-[[1812]].

בעוד שלדטרמיננטה יש משמעות גאומטרית והיא קשורה ישירות בפתרון [[מערכת משוואות ליניארית|משוואות ליניאריות]] (על-פי [[נוסחת קרמר]]), הפרמננטה שימושית בהקשרים שונים לחלוטין, כגון חישובי הסתברויות וספירת מסלולים בגרפים. שימוש נוסף הוא בעיית מציאת מספר ה[[שידוך מושלם|שידוכים המושלמים]] ב[[גרף דו צדדי]]. הבדל בולט אחר הוא העבודה שנדרש להשקיע בכל חישוב. למרות שבשני המקרים התוצאה תלויה ב-n [[עצרת (מתמטיקה)|עצרת]] מכפלות, את הדטרמיננטה אפשר לחשב בכ- <math>\ n^3</math> פעולות באמצעות [[דירוג מטריצות|דירוג]] המטריצה המדוברת (ואף מהר יותר, באמצעות [[כפל מטריצות]] מהיר). לעומת זאת, לא ידועה שיטה מהירה לחישוב הפרמננטה. סיכום כל המכפלות השונות בזו אחר זו יהיה כרוך ב <math>\ {n!}</math> פעולות וסיבוכיות האלגוריתם המהיר ביותר הידוע היא <math>\ {O(n2^n)}</math>. יתירה מזאת, [[לזלי ואלינט]] הראה שזו בעיה [[NP-קשה]]. כלומר אם קיים [[אלגוריתם]] עם [[סיבוכיות]] פולינומית לחישוב של הפרמננטה, ינבע מכך כי [[P=NP]], והדבר נכון אף למטריצות שאבריהן הן <math>\ 0</math> או <math>\ 1</math>. בעיית חישוב הפרמננטה שייכת ל[[מחלקות סיבוכיות|מחלקת הסיבוכיות]] [[Sharp-P|P#]] והיא שלמה עבורה. מאידך ידוע אלגוריתם פולינומי אקראי לקירוב הפרמננטה. '''בעיית פוליה''' מבקשת למצוא, עבור מחלקות מסוימות של מטריצות, העתקה <math>T {:} \operatorname{M}_n(F) \rightarrow \operatorname{M}_m(F)</math> כך ש-<math>\operatorname{per}(A) = \det(T(A))</math>.

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

פרמננטה של ''n''×''n'' כל המטריצה של 1 היא מספר סידורים אפשריים של ''n'' [[צריח (שחמט)|צריחי]] שחמט שאינם תוקפים הדדית בעמדות הלוח בגודל ''n''×''n''.
<ref>{{Cite journal
|last1=Shevelev
|first1=V.S.
|year=1990
|title=On a representation of rook polinomials
|journal=Russian Mathematical Surveys
|volume=45
|issue=4
|pages=183–185
|url=https://www.mathnet.ru/eng/rm4775
|doi=10.1070/RM1990v045n04ABEH002387
|language=en
}}</ref>

== דוגמאות ==

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

==לקריאה נוספת==

*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) [http://doi.acm.org/10.1145/1008731.1008738 "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries"], ''Journal of the ACM,'' Volume 51, Pages 671--697

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

== הערות שוליים ==
{{הערות שוליים}}
[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:אלגברה ליניארית]]