נוסחת לייבניץ לדטרמיננטות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הרחבה |
אין תקציר עריכה |
||
שורה 12:
חישוב ישיר של הדטרמיננטה על פי נוסחת לייבניץ דורש באופן כללי <math>\Omega(n! \cdot n)</math> פעולות ב[[שדה (מבנה אלגברי)|שדה]]; זהו תהליך לא יעיל בעבור מטריצות גדולות. בעזרת [[דירוג מטריצות]] ניתן להוריד זאת ל-(O(''n''<sup>3</sup>, זאת שכן הדטרמיננטה של [[מטריצה משולשית]] שווה למכפלת איברי האלכסון הראשי שלה, ואת הדטרמיננטה המקורית ניתן לשחזר באמצעות "זכירת" הפעולות האלמנטריות שביצענו עד כה אשר שינו את ערכה.
== ניסוח פורמלי והוכחה ==
{{פסקה בעבודה}}
'''משפט.'''
קיימת פונקציה יחידה
:<math> F : M_n (\mathbb K) \rightarrow \mathbb K </math>
אשר הינה מתחלפת, מולטי-לינארית ביחס לעמודות ושורות המטריצה, ומנורמלת כך ש-<math>F(I) = 1</math>.
'''הוכחה.'''
'''יחידות:''' תהי <math>F</math> פונקציה כזאת, ותהי <math>A = (a_i^j)_{i = 1, \dots, n}^{j = 1, \dots , n}</math> מטריצה מסדר <math>n \times n</math>. נקרא ל-<math>A^j</math> העמודה ה-<math>j</math> של <math>A</math>, כלומר <math>A^j = (a_i^j)_{i = 1, \dots , n}</math>, כך ש-<math>A = \left(A^1, \dots, A^n\right).</math>.
בנוסף, תהי <math>E^k</math> העמודה ה-<math>k</math> של [[מטריצת היחידה|מטריצת הזהות]].
כעת נרשום את כל אחת מהעמודות <math>A^j</math> במונחי העמודות <math>E^k</math>, כלומר
:<math>A^j = \sum_{k = 1}^n a_k^j E^k</math>.
כיוון ש-<math>F</math> היא מולטי-לינארית, מקבלים:
:<math>
\begin{align}
F(A)& = F\left(\sum_{k_1 = 1}^n a_{k_1}^1 E^{k_1}, \dots, \sum_{k_n = 1}^n a_{k_n}^n E^{k_n}\right)\\
& = \sum_{k_1, \dots, k_n = 1}^n \left(\prod_{i = 1}^n a_{k_i}^i\right) F\left(E^{k_1}, \dots, E^{k_n}\right).
\end{align}
</math>
כיוון ש-''F'' מתחלפת, כל איבר עם אינדקסים חוזרים הוא 0. הסכום לפיכך מוגבל ל-n-יות עם אינדקסים לא חוזרים, או במילים אחרות תמורות:
:<math>F(A) = \sum_{\sigma \in S_n} \left(\prod_{i = 1}^n a_{\sigma(i)}^i\right) F(E^{\sigma(1)}, \dots , E^{\sigma(n)}).</math>
כיוון ש-''F'' מתחלפת, העמודות <math>E</math> ניתנות לשחלוף עד אשר המטריצה הופכת למטריצת הזהות (הדבר שקול לכפל ב[[מטריצת תמורה]]). [[פונקציית הסימן]] <math>\sgn(\sigma)</math> מוגדרת כך שתמנה את מספר חילופי העמודות הנחוצים ותביא לשינוי הסימן. לבסוף מקבלים:
:<math>
\begin{align}
F(A)& = \sum_{\sigma \in S_n} \sgn(\sigma) \left(\prod_{i = 1}^n a_{\sigma(i)}^i\right) F(I)\\
& = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i
\end{align}
</math>
שכן <math>F(I)</math> מוגדרת כשווה ל-<math>1</math>.
לפיכך אף פונקציה אחרת חוץ מזו המוגדרת על ידי נוסחת לייבניץ יכולה להיות מולטי-לינארית, מתחלפת ומנורמלת כך ש-<math>F\left(I\right)=1</math>.
'''קיום''':
== ראו גם ==
| |||