Προβολή πηγαίου κώδικα για τη σελίδα Τύπος του Λάιμπνιτς για τις ορίζουσες

Στην [[άλγεβρα]], ο '''τύπος Λάιμπνιτς'''<ref>{{Cite web|url=https://www.cfm.brown.edu/people/dobrush/cs52/Mathematica/Part2/det.html|title=Linear Algebra with Mathematica|website=www.cfm.brown.edu|accessdate=2024-07-19}}</ref>, που έλαβε το όνομά του προς τιμήν του [[Γκότφριντ Λάιμπνιτς]], καθορίζει την [[ορίζουσα]] ενός [[Τετραγωνικός πίνακας|τετραγωνικού πίνακα]] ως προς τις μεταθέσεις των στοιχείων του πίνακα<ref>{{Cite web|url=http://publish.illinois.edu/ymb/files/2018/09/prasolov_linear_algebra_determinants.pdf|title=DETERMINANTS - University of Illinois Urbana-Champaign}}</ref>. Αν ο <math>A</math> είναι ένας <math>n \times n</math> πίνακας, όπου  <math>a_{ij}</math> είναι η εγγραφή στην <math>i</math>-th γραμμή και <math>j</math>-th στήλη του <math>A</math>, ο τύπος είναι ο εξής

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

όπου <math>\sgn</math> είναι η συνάρτηση προσήμου των μεταθέσεων στην ομάδα μεταθέσεων <math>S_n</math>, η οποία επιστρέφει <math>+1</math> και <math>-1</math> για ζυγές και περιττές μεταθέσεις, αντίστοιχα.

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

: <math>\det(A) = \epsilon_{i_1\cdots i_n} {a}_{1i_1} \cdots {a}_{ni_n},</math>

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

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

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

'''Θεώρημα.'''
Υπάρχει ακριβώς μία συνάρτηση <math> F : M_n (\mathbb K) \rightarrow \mathbb K</math> η οποία είναι εναλλασσόμενη πολυγραμμική ως προς τις στήλες και τέτοια ώστε <ref>{{Cite web|url=https://mast.queensu.ca/~ggsmith/Math110/notes12.pdf|title=More Determinants - 11.1.3 Theorem (Leibniz formula)}}</ref><ref>{{Cite book|title=Numerical Methods I - Basis and Fundamentals|first=Boris|last=Obsieger|publisher=university-books.eu|isbn=978-953-7919-02-3|date=2013-10-25|url=https://books.google.gr/books?id=wHCpLgiQnSkC&pg=PA100&dq=Leibniz+formula+for+determinants&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwi9rZam97GHAxVXbvEDHVo4C-AQ6AF6BAgIEAI#v=onepage&q=Leibniz%20formula%20for%20determinants&f=false}}</ref><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>-th στήλη του <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>-th διάνυσμα στήλης του πίνακα ταυτότητας.

Τώρα γράφουμε κάθε ένα από τα <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>

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

:<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> η πλειάδα που ισούται με <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)\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{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)}
= \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n \operatorname{\delta}_{i,\sigma(i)}\\
& = \sum_{\sigma \in S_n} \sgn(\sigma) \operatorname{\delta}_{\sigma,\operatorname{id}_{\{1\ldots n\}}}
= \sgn(\operatorname{id}_{\{1\ldots n\}})
= 1
\end{align}
</math>

Έτσι, οι μόνες εναλλασσόμενες πολυγραμμικές συναρτήσεις με <math>F(I)=1</math> περιορίζονται στη συνάρτηση που ορίζεται από τον τύπο του Λάιμπνιτς, και στην πραγματικότητα διαθέτει επίσης αυτές τις τρεις ιδιότητες. Επομένως, η [[ορίζουσα]] μπορεί να οριστεί ως η μόνη συνάρτηση <math> \det : M_n (\mathbb K) \rightarrow \mathbb K </math> με αυτές τις τρεις ιδιότητες.

==Δείτε επίσης==

* [https://books.google.gr/books?id=UBVH2Vpf6LYC&printsec=frontcover&dq=Algebraic+function+field&hl=el&newbks=1&newbks_redir=0&sa=X&redir_esc=y#v=onepage&q=Algebraic%20function%20field&f=false Field Arithmetic]
* [[Πραγματικό προβολικό επίπεδο]]
* [[Εσωτερικό γινόμενο]] 
* [[Μιγαδικός αριθμός]]
* [[Πίνακας (μαθηματικά)]]
* [[Τετραγωνικός πίνακας]]
* [[Ορίζουσα]]
* [[Αντιστρέψιμος πίνακας]]
* [[Ιδιοτιμές και ιδιοδιανύσματα]]

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

*[https://www.itia.ntua.gr/en/docinfo/1318/ English - Greek Dictionary of Pure and Applied Mathematics] Εθνικό Μετσόβιο Πολυτεχνείο
*[https://www.mas.ucy.ac.cy/georgios/bookfiles/dict1.pdf Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου]
* [https://books.google.gr/books?id=F4hRy1F1M6QC&pg=PA20&dq=Gram+matrix&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjPquKekY6HAxWRX_EDHWA-DZkQ6AF6BAgFEAI#v=onepage&q=Gram%20matrix&f=false Matrix Analysis]
* [https://books.google.gr/books?id=ZsiSvE0Z3s4C&pg=PA476&dq=Vector+projection&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjupaCX6KaHAxUySvEDHWJ8CQsQ6AF6BAgEEAI#v=onepage&q=Vector%20projection&f=false The Concise Oxford Dictionary of Mathematics]
* [https://books.google.gr/books?id=wHCpLgiQnSkC&pg=PA100&dq=Leibniz+formula+for+determinants&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjHmqKO87GHAxW7R_EDHQR3ARoQ6AF6BAgIEAI#v=onepage&q=Leibniz%20formula%20for%20determinants&f=false Numerical Methods I - Basis and Fundamentals]
* [https://books.google.gr/books?id=s7bMBQAAQBAJ&pg=PA160&dq=Scalar+multiplication&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwigzOvnn7CHAxUASfEDHZLwApkQ6AF6BAgHEAI#v=onepage&q=Scalar%20multiplication&f=false A Modern Introduction to Linear Algebra]
* [https://books.google.gr/books?id=pwrBp3ZGaUYC&pg=PA486&dq=Leibniz+formula+for+determinants&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjHmqKO87GHAxW7R_EDHQR3ARoQ6AF6BAgGEAI#v=onepage&q=Leibniz%20formula%20for%20determinants&f=false Quantum Mechanics for Scientists and Engineers]

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

* {{cite journal |last=Μαυρογιάννης |first=Ν. Σ. |title=Μία εισαγωγή στους μιγαδικούς αριθμούς |journal=Εκθέτης Φύλλα Μαθηματικής Παιδείας |year=2016 |month=Μαΐου |issue=16 |pages=1-8 |url=http://ekthetis.gr/Ekthetis016.pdf}}
* {{Cite book|title=Handbook of Mathematics|first=I. N.|last=Bronshtein|first2=K. A.|last2=Semendyayev|publisher=Springer Science & Business Media|isbn=978-3-662-21982-9|date=2013-06-29|url=https://books.google.gr/books?id=yojoCAAAQBAJ&printsec=frontcover&dq=Bronshtein+and+Semendyayev&hl=el&newbks=1&newbks_redir=0&sa=X&redir_esc=y#v=onepage&q=Bronshtein%20and%20Semendyayev&f=false}}
* {{citation |last1=Gray |first1=Lawrence F. |last2=Flanigan |first2=Francis J. |last3=Kazdan |first3=Jerry L. |last4=Frank |first4=David H. |last5=Fristedt |first5=Bert |title=Calculus two: linear and nonlinear functions |publisher=Springer-Verlag |location=Berlin |year=1990 |page=[https://archive.org/details/calculustwolinea00flan/page/375 375] |isbn=0-387-97388-5 |url-access=registration |url=https://archive.org/details/calculustwolinea00flan/page/375 }}
* {{Cite book|last=Axler|first=Sheldon Jay|title=Linear Algebra Done Right|url=https://archive.org/details/linearalgebradon0000axle|publisher=[[Springer Science+Business Media|Springer]]|year=2015|isbn=978-3-319-11079-0|edition=3rd|author-link=:en:Sheldon Axler}}
* {{citation|first=Erwin|last=Bareiss|title= Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination|pages=565–578|url=https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf |archive-url=https://web.archive.org/web/20121025053848/http://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf |archive-date=2012-10-25 |url-status=live|journal=Mathematics of Computation|year=1968|volume=22|issue=102|doi=10.2307/2004533|jstor=2004533}}
* {{Citation | last1=Balcerzyk | first1=Stanisław | last2=Józefiak | first2=Tadeusz | title=Dimension, multiplicity and homological methods | publisher=Ellis Horwood Ltd. | location=Chichester | series=Ellis Horwood Series: Mathematics and its Applications.  | isbn=978-0-13-155623-2 | year=1989}}

==Παραπομπές==
<references />

* {{SpringerEOM|title=Determinant|id=Determinant&oldid=12692}}
* {{cite book | title=Numerical Linear Algebra | url=https://archive.org/details/numericallineara0000tref | last1=Trefethen | first1=Lloyd N. | last2=Bau | first2=David | publisher=[[:en:Society for Industrial and Applied Mathematics|SIAM]] | date=June 1, 1997 | isbn=978-0898713619 }}

{{Authority control}} 
{{Portal bar|Μαθηματικά}}
{{DEFAULTSORT:Τύπος του Λάιμπνιτς για τις ορίζουσες}}

[[Κατηγορία:Γραμμική άλγεβρα]]
[[Κατηγορία:Αριθμητική γραμμική άλγεβρα]]
[[Κατηγορία:Αφηρημένη άλγεβρα]]
[[Κατηγορία:Θεωρία πινάκων]]
[[Κατηγορία:Ορίζουσες]]