פרמננטה

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

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

מקור: http://he.wikipedia.org../../../%D7%A4/%D7%A8/%D7%9E/%D7%A4%D7%A8%D7%9E%D7%A0%D7%A0%D7%98%D7%94.html

קטגוריות: קומבינטוריקה | אלגברה לינארית

פרמננטה

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

Views

ניווט

קהילה

חיפוש

שפות אחרות