Τύπος του Λάιμπνιτς για τις ορίζουσες

Στην άλγεβρα, ο τύπος Λάιμπνιτς, που έλαβε το όνομά του προς τιμήν του Γκότφριντ Λάιμπνιτς, καθορίζει την ορίζουσα ενός τετραγωνικού πίνακα ως προς τις μεταθέσεις των στοιχείων του πίνακα. Αν ο $A$ είναι ένας $n\times n$ πίνακας, όπου $a_{ij}$ είναι η εγγραφή στην $i$-th γραμμή και $j$-th στήλη του $A$, ο τύπος είναι ο εξής

$\det(A)=\sum _{\tau \in S_{n}}\operatorname {sgn}(\tau )\prod _{i=1}^{n}a_{i\tau (i)}=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}a_{\sigma (i)i}$

όπου $\operatorname {sgn}$ είναι η συνάρτηση προσήμου των μεταθέσεων στην ομάδα μεταθέσεων $S_{n}$, η οποία επιστρέφει $+1$ και $-1$ για ζυγές και περιττές μεταθέσεις, αντίστοιχα.

Ένας άλλος συνήθης συμβολισμός που χρησιμοποιείται για τον τύπο είναι σε όρους του συμβόλου Λεβί-Κιβίτα και κάνει χρήση του συμβολισμού του αθροίσματος του Αϊνστάιν, όπου γίνεται

$\det(A)=\epsilon _{i_{1}\cdots i_{n}}{a}_{1i_{1}}\cdots {a}_{ni_{n}},$

που μπορεί να είναι πιο οικεία στους φυσικούς.

Η άμεση αξιολόγηση του τύπου Λάιμπνιτς από τον ορισμό απαιτεί $\Omega (n!\cdot n)$ πράξεις γενικά - δηλαδή έναν αριθμό πράξεων ασυμπτωτικά ανάλογο του $n$ παραγοντικό- επειδή $n!$ είναι ο αριθμός των μεταθέσεων τάξης-$n$. Αυτό είναι πρακτικά δύσκολο ακόμη και για σχετικά μικρά $n$. Αντ' αυτού, η ορίζουσα μπορεί να εκτιμηθεί σε $O(n^{3})$ πράξεις σχηματίζοντας την LU αποσύνθεση $A=LU$ (συνήθως μέσω απαλοιφής Γκάους ή παρόμοιων μεθόδων), οπότε $\det A=\det L\cdot \det U$ και οι ορίζουσες των τριγωνικών πινάκων $L$ και $U$ είναι απλά τα γινόμενα των διαγώνιων καταχωρήσεων τους. (Στις πρακτικές εφαρμογές της αριθμητικής γραμμικής άλγεβρας, ωστόσο, σπάνια απαιτείται ρητός υπολογισμός της ορίζουσας). Βλέπε, για παράδειγμα, Trefethen & Bau (1997). Η ορίζουσα μπορεί επίσης να εκτιμηθεί σε λιγότερες από $O(n^{3})$ πράξεις αναγάγοντας το πρόβλημα σε πολλαπλασιασμό πινάκων, αλλά οι περισσότεροι τέτοιοι αλγόριθμοι δεν είναι πρακτικοί.

Τυπική δήλωση και απόδειξη

Θεώρημα. Υπάρχει ακριβώς μία συνάρτηση $F:M_{n}(\mathbb {K} )\rightarrow \mathbb {K}$ η οποία είναι εναλλασσόμενη πολυγραμμική ως προς τις στήλες και τέτοια ώστε $F(I)=1$.

Απόδειξη.

Μοναδικότητα: Έστω $F$ μια τέτοια συνάρτηση, και έστω $A=(a_{i}^{j})_{i=1,\dots ,n}^{j=1,\dots ,n}$ ένας $n\times n$ πίνακας. Καλούμε $A^{j}$ την $j$-th στήλη του $A$, δηλαδή $A^{j}=(a_{i}^{j})_{i=1,\dots ,n}$, έτσι ώστε $A=\left(A^{1},\dots ,A^{n}\right).$

Επίσης, έστω $E^{k}$ το $k$-th διάνυσμα στήλης του πίνακα ταυτότητας.

Τώρα γράφουμε κάθε ένα από τα $A^{j}$ ως προς το $E^{k}$, δηλ.

$A^{j}=\sum _{k=1}^{n}a_{k}^{j}E^{k}$.

Καθώς η $F$ είναι πολυγραμμική, έχουμε

${\begin{aligned}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{aligned}}$

Από την εναλλαγή προκύπτει ότι κάθε όρος με επαναλαμβανόμενους δείκτες είναι μηδενικός. Το άθροισμα μπορεί επομένως να περιοριστεί σε πλειάδες με μη επαναλαμβανόμενους δείκτες, δηλαδή μεταθέσεις:

$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)}).$

Επειδή το F είναι εναλλασσόμενο, οι στήλες $E$ μπορούν να αντικατασταθούν μέχρι να γίνει η ταυτότητα. Η συνάρτηση προσήμου $\operatorname {sgn}(\sigma )$ ορίζεται για να μετρά τον αριθμό των απαραίτητων ανταλλαγών και να λαμβάνει υπόψη την αλλαγή προσήμου που προκύπτει. Τελικά παίρνουμε:

${\begin{aligned}F(A)&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\left(\prod _{i=1}^{n}a_{\sigma (i)}^{i}\right)F(I)\\&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}a_{\sigma (i)}^{i}\end{aligned}}$

καθώς το $F(I)$ απαιτείται να είναι ίσο με $1$.

Επομένως, καμία συνάρτηση εκτός από τη συνάρτηση που ορίζεται από τον τύπο Λάιμπνιτς δεν μπορεί να είναι μια πολυγραμμική εναλλασσόμενη συνάρτηση με $F\left(I\right)=1$.

Ύπαρξη: Μπορούμε τώρα να δείξουμε ότι η F, όπου F είναι η συνάρτηση που ορίζεται από τον τύπο του Λάιμπνιτς, έχει αυτές τις τρεις ιδιότητες.

Πολυγραμμικό

${\begin{aligned}F(A^{1},\dots ,cA^{j},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )ca_{\sigma (j)}^{j}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\\&=c\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )a_{\sigma (j)}^{j}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\\&=cF(A^{1},\dots ,A^{j},\dots )\\\\F(A^{1},\dots ,b+A^{j},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {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}}\operatorname {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}}\operatorname {sgn}(\sigma )b_{\sigma (j)}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\right)+\left(\sum _{\sigma \in S_{n}}\operatorname {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{aligned}}$

Εναλλασσόμενο

${\begin{aligned}F(\dots ,A^{j_{1}},\dots ,A^{j_{2}},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {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{aligned}}$

Για κάθε $\sigma \in S_{n}$ έστω $\sigma '$ η πλειάδα που ισούται με $\sigma$ με τους δείκτες $j_{1}$ και $j_{2}$ αλλαγμένους.

${\begin{aligned}F(A)&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\left[\operatorname {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}}+\operatorname {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}}\right]\\&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\left[\operatorname {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}}-\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\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})}\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)\underbrace {\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)} _{=0{\text{, if }}A^{j_{1}}=A^{j_{2}}}\\\\\end{aligned}}$

Έτσι, αν $A^{j_{1}}=A^{j_{2}}$ τότε $F(\dots ,A^{j_{1}},\dots ,A^{j_{2}},\dots )=0$.

Τέλος, $F(I)=1$:

${\begin{aligned}F(I)&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}I_{\sigma (i)}^{i}=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}\operatorname {\delta } _{i,\sigma (i)}\\&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\operatorname {\delta } _{\sigma ,\operatorname {id} _{\{1\ldots n\}}}=\operatorname {sgn}(\operatorname {id} _{\{1\ldots n\}})=1\end{aligned}}$

Έτσι, οι μόνες εναλλασσόμενες πολυγραμμικές συναρτήσεις με $F(I)=1$ περιορίζονται στη συνάρτηση που ορίζεται από τον τύπο του Λάιμπνιτς, και στην πραγματικότητα διαθέτει επίσης αυτές τις τρεις ιδιότητες. Επομένως, η ορίζουσα μπορεί να οριστεί ως η μόνη συνάρτηση $\det :M_{n}(\mathbb {K} )\rightarrow \mathbb {K}$ με αυτές τις τρεις ιδιότητες.

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Εσωτερικό γινόμενο
• Μιγαδικός αριθμός
• Πίνακας (μαθηματικά)
• Τετραγωνικός πίνακας
• Ορίζουσα
• Αντιστρέψιμος πίνακας
• Ιδιοτιμές και ιδιοδιανύσματα

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix Analysis
• The Concise Oxford Dictionary of Mathematics
• Numerical Methods I - Basis and Fundamentals
• A Modern Introduction to Linear Algebra
• Quantum Mechanics for Scientists and Engineers

Δημοσιεύσεις

• Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf. 
• Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9. 
• Gray, Lawrence F.; Flanigan, Francis J.; Kazdan, Jerry L.; Frank, David H.; Fristedt, Bert (1990), Calculus two: linear and nonlinear functions, Berlin: Springer-Verlag, σελ. 375, ISBN 0-387-97388-5, https://archive.org/details/calculustwolinea00flan/page/375 
• Axler, Sheldon Jay (2015). Linear Algebra Done Right (3rd έκδοση). Springer. ISBN 978-3-319-11079-0. 
• Bareiss, Erwin (1968), «Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination», Mathematics of Computation 22 (102): 565–578, doi:10.2307/2004533, https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf 
• Balcerzyk, Stanisław; Józefiak, Tadeusz (1989), Dimension, multiplicity and homological methods, Ellis Horwood Series: Mathematics and its Applications., Chichester: Ellis Horwood Ltd., ISBN 978-0-13-155623-2 

Παραπομπές

• Hazewinkel, Michiel, επιμ.. (2001), «Determinant», Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://www.encyclopediaofmath.org/index.php?title=Determinant&oldid=12692 
• Trefethen, Lloyd N.· Bau, David (1 Ιουνίου 1997). Numerical Linear Algebra. SIAM. ISBN 978-0898713619.