נוסחת לייבניץ לדטרמיננטות

נוסחת לייבניץ לדטרמיננטות היא נוסחה באלגברה המבטאת את הדטרמיננטה של מטריצה ריבועית באמצעות תמורות של איברי המטריצה. היא נקראת על שם המתמטיקאי והפילוסוף גוטפריד וילהלם לייבניץ.

אם A היא מטריצה מסדר n×n, אז אם נסמן ב-a<sub>i,j</sub> את האיבר בשורה ה-i ובעמודה ה-j, הנוסחה היא:

:<math>\det(A) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i), i},</math>

כאשר sgn היא פונקציית הסימן של התמורות בחבורת התמורות S<sub>n</sub>, והיא מחזירה 1+ אם התמורה זוגית (כלומר אם היא מתקבלת מתמורת הזהות על ידי מספר זוגי של חילופים) ו-1- אם התמורה אי-זוגית. ויזואלית ניתן לדמות את הנוסחה כסכום מסומן של כל המכפלות האפשריות של n מאיברי המטריצה כאשר הם נבחרים כך שאין שניים באותה עמודה או שורה.

נוסחה זו היא הביטוי המתמטי היחיד המקבל כמשתנים את n<sup>2</sup> איברי המטריצה, ומהווה תבנית מולטי-ליניארית (הווה אומר, ליניארית בכל אחד מאיברי המטריצה), מתחלפת (אנטי-סימטרית) ומנורמלת. זו הגרסה הסגורה להגדרה הרקורסיבית של הדטרמיננטה באמצעות פיתוח למינורים לפי שורה או עמודה מסוימת.

את כמה מהתכונות הבסיסיות של הדטרמיננטה, כגון התאפסותה עבור מטריצה תלויית-שורות, ניתן להסביר כתוצא ישיר של הגדרה זו, וכפועל יוצא של הצורה המתמטית של הנוסחה. למשל, אם שתיים משורות המטריצה הריבועית זהות (עד כדי כפל בסקלר), אז מאנטי-סימטריות הדטרמיננטה נובע שאם נחליף בין השורות הזהות ערך הדטרמיננטה ישתנה מ- <math>det(A)</math> ל-<math>-det(A)</math>; אולם המטריצה נותרה אותו דבר (החלפנו שורות זהות), וכיוון שהמספר היחידי ששווה לנגדי של עצמו הוא 0 נובעת התאפסות הדטרמיננטה. בנימה דומה, כלל קרמר נובע ישירות ממולטי-ליניאריות הדטרמיננטה.

חישוב ישיר של הדטרמיננטה על פי נוסחת לייבניץ דורש באופן כללי <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>.

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

מולטי-ליניארית:
:<math>
\begin{align}
F(A^1, \dots, cA^j, \dots) & = \sum_{\sigma \in S_n} \sgn(\sigma) ca_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
& = c \sum_{\sigma \in S_n} \sgn(\sigma) a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
&=c F(A^1, \dots, A^j, \dots)\\
\\
F(A^1, \dots, b+A^j, \dots) & = \sum_{\sigma \in S_n} \sgn(\sigma)\left(b_{\sigma(j)} + a_{\sigma(j)}^j\right)\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
& = \sum_{\sigma \in S_n} \sgn(\sigma)
\left( \left(b_{\sigma(j)}\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right) + \left(a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right)\right)\\
& = \left(\sum_{\sigma \in S_n} \sgn(\sigma) b_{\sigma(j)}\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right)
 + \left(\sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i\right)\\
&= F(A^1, \dots, b, \dots) + F(A^1, \dots, A^j, \dots)\\
\\
\end{align}
</math>

מתחלפת:
:<math>
\begin{align}
F(\dots, A^{j_1}, \dots, A^{j_2}, \dots)
& = \sum_{\sigma \in S_n} \sgn(\sigma) \left(\prod_{i = 1, i \neq j_1, i\neq j_2}^n a_{\sigma(i)}^i\right) a_{\sigma(j_1)}^{j_1} a_{\sigma(j_2)}^{j_2}\\
\end{align}
</math>

לכל <math>\sigma \in S_n</math> תהי <math>\sigma'</math> ה-n-יה השווה ל-<math>\sigma</math> עם האינדקסים <math>j_1</math> ו-<math>j_2</math> מוחלפים.

:<math>
\begin{align}
F(A) & = \sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\left[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}+\sgn(\sigma')\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma'(i)}^{i}\right)a_{\sigma'(j_{1})}^{j_{1}}a_{\sigma'(j_{2})}^{j_{2}}\right]\\
& =\sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\left[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}-\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{2})}^{j_{1}}a_{\sigma(j_{1})}^{j_{2}}\right]\\
& =\sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)\left(a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}-a_{\sigma(j_{1})}^{j_{2}}a_{\sigma(j_{2})}^{j_{_{1}}}\right)\\
\\
\end{align}
</math>

לכן אם <math>A^{j_1} = A^{j_2}</math> אז <math>F(\dots, A^{j_1}, \dots, A^{j_2}, \dots)=0</math>.

לסיום, נקבל <math>F(I)=1</math>:

:<math>
\begin{align}\\
F(I) & = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n I^i_{\sigma(i)}\\
& = \sgn(\sigma) \prod_{i = 1}^n I^i_{\sigma(i)}\qquad\text{where }\sigma = (1, 2, \ldots, n). \text{ For other choices of }\sigma, I^i_{\sigma(i)}=0.\\
& = \prod_{i = 1}^n I_{i}^i\\
& = 1
\end{align}
</math>

לפיכך הפונקציות המולטי-ליניאריות ומתחלפות היחידות עם <math>F(I)=1</math> מוגבלות לצורה הפונקציונלית המוגדרת על ידי נוסחת לייבניץ, שלמעשה מקיימת את שלושת התנאים הללו.

== ראו גם ==
* דטרמיננטה
* כלל קרמר

קטגוריה:דטרמיננטות