Ανάπτυγμα Λαπλάς

Στη γραμμική άλγεβρα, το ανάπτυγμα Λαπλάς, το οποίο πήρε το όνομά του από τον Πιερ-Σιμόν ντε Λαπλάς, και ονομάζεται επίσης ανάπτυγμα συμπαράγοντα, είναι μια έκφραση της ορίζουσας ενός n × n-πίνακα B ως σταθμισμένο άθροισμα ελάσσονων, που είναι οι ορίζουσες κάποιων (n - 1) × (n - 1)-υποπινάκων του B. Συγκεκριμένα, για κάθε i, το ανάπτυγμα Λαπλάς κατά μήκος της i-th γραμμής είναι η ισότητα

${\begin{aligned}\det(B)&=\sum _{j=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j},\end{aligned}}$

όπου $b_{i,j}$ είναι η καταχώρηση της i-th γραμμής και της j-th στήλης του B, και $m_{i,j}$ είναι η ορίζουσα του υποπίνακα που προκύπτει με την αφαίρεση της i-th γραμμής και της j-th στήλης του B. Ομοίως, το ανάπτυγμα Λαπλάς κατά μήκος της j-th στήλης είναι η ισότητα

${\begin{aligned}\det(B)&=\sum _{i=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j}.\end{aligned}}$

(Κάθε ταυτότητα συνεπάγεται την άλλη, αφού οι ορίζουσες ενός πίνακα και του Ανάστροφού του είναι οι ίδιες.)

Ο συντελεστής $(-1)^{i+j}m_{i,j}$ του $b_{i,j}$ στο παραπάνω άθροισμα ονομάζεται συμπαράγοντας του $b_{i,j}$ στο B.

Το ανάπτυγμα Λαπλάς είναι συχνά χρήσιμο σε αποδείξεις, όπως, παραδείγματος χάριν, για να επιτραπεί η αναδρομή στο μέγεθος των πινάκων. Έχει επίσης διδακτικό ενδιαφέρον για την απλότητά του και ως ένας από τους διάφορους τρόπους προβολής και υπολογισμού του προσδιοριστή. Για μεγάλους πίνακες, ο υπολογισμός του γίνεται γρήγορα αναποτελεσματικός σε σύγκριση με την απαλοιφή του Γκάους.

Παραδείγματα

Ας εξετάσουμε τον πίνακα

$B={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.$

Η ορίζουσα αυτού του πίνακα μπορεί να υπολογιστεί χρησιμοποιώντας το ανάπτυγμα Λαπλάς κατά μήκος οποιασδήποτε από τις γραμμές ή τις στήλες του. Παραδείγματος χάριν, ένα ανάπτυγμα κατά μήκος της πρώτης γραμμής δίνει:

${\begin{aligned}|B|&=1\cdot {\begin{vmatrix}5&6\\8&9\end{vmatrix}}-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+3\cdot {\begin{vmatrix}4&5\\7&8\end{vmatrix}}\\[5pt]&=1\cdot (-3)-2\cdot (-6)+3\cdot (-3)=0.\end{aligned}}$

Το ανάπτυγμα Λσπλάς κατά μήκος της δεύτερης στήλης δίνει το ίδιο αποτέλεσμα:

${\begin{aligned}|B|&=-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+5\cdot {\begin{vmatrix}1&3\\7&9\end{vmatrix}}-8\cdot {\begin{vmatrix}1&3\\4&6\end{vmatrix}}\\[5pt]&=-2\cdot (-6)+5\cdot (-12)-8\cdot (-6)=0.\end{aligned}}$

Είναι εύκολο να επαληθευτεί ότι το αποτέλεσμα είναι σωστό: ο πίνακας είναι αντιστρέψιμος πίνακας επειδή το άθροισμα της πρώτης και της τρίτης στήλης του είναι διπλάσιο της δεύτερης στήλης, και επομένως ο προσδιοριστής του είναι μηδέν.

Απόδειξη

Έστω ότι ο $B$ είναι ένας n × n πίνακας και $i,j\in \{1,2,\dots ,n\}.$ Για λόγους σαφήνειας ονομάζουμε επίσης τις καταχωρήσεις του $B$ που συνθέτουν τον $i,j$ ελάσσονα πίνακα $M_{ij}$ ως εξής

$(a_{st})$ for $1\leq s,t\leq n-1.$

Ας εξετάσουμε τους όρους στο ανάπτυγμα του $|B|$ που έχουν ως παράγοντα το $b_{ij}$. Καθένας από αυτούς έχει τη μορφή

$\operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{i,j}\cdots b_{n,\tau (n)}=\operatorname {sgn} \tau \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}$

για κάποια μετάθεση τ ∈ S_n, και μια μοναδική και προφανώς σχετική μετάθεση $\sigma \in S_{n-1}$ η οποία επιλέγει τις ίδιες δευτερεύουσες καταχωρήσεις με την τ Ομοίως κάθε επιλογή του σ καθορίζει ένα αντίστοιχο τ, δηλαδή η αντιστοιχία $\sigma \leftrightarrow \tau$ είναι μια αμφίρριψη μεταξύ $S_{n-1}$ και $\{\tau \in S_{n}\colon \tau (i)=j\}.$ Χρησιμοποιώντας τον συμβολισμό δύο γραμμών του Κωσύ, η ρητή σχέση μεταξύ $\tau$ και $\sigma$ μπορεί να γραφεί ως εξής

$\sigma ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))\end{pmatrix}}$

όπου $(\leftarrow )_{j}$ είναι μια προσωρινή συντομογραφία για έναν κύκλο $(n,n-1,\cdots ,j+1,j)$. Αυτή η πράξη μειώνει όλους τους δείκτες μεγαλύτερους από j έτσι ώστε κάθε δείκτης να χωράει στο σύνολο {1,2,...,n-1}

Η μετάθεση τ μπορεί να προκύψει από την σ ως εξής. Ορίζουμε το $\sigma '\in S_{n}$ με $\sigma '(k)=\sigma (k)$ για $1\leq k\leq n-1$ και $\sigma '(n)=n$. Τότε το $\sigma '$ εκφράζεται ως εξής

$\sigma '={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}$

Τώρα, η πράξη που εφαρμόζει πρώτα το $(\leftarrow )_{i}$ και μετά το $\sigma '$ είναι (Σημειώστε ότι η εφαρμογή του Α πριν από το Β είναι ισοδύναμη με την εφαρμογή του αντίστροφου του Α στην πάνω σειρά του Β σε συμβολισμό δύο γραμμών)

$\sigma '(\leftarrow )_{i}={\begin{pmatrix}1&2&\cdots &i+1&\cdots &n&i\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}$

όπου $(\leftarrow )_{i}$ είναι προσωρινή συντομογραφία για $(n,n-1,\cdots ,i+1,i)$.

η πράξη που εφαρμόζει πρώτα το $\tau$ και στη συνέχεια το $(\leftarrow )_{j}$ είναι

$(\leftarrow )_{j}\tau ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &n&\cdots &(\leftarrow )_{j}(\tau (n-1))&(\leftarrow )_{j}(\tau (n))\end{pmatrix}}$

τα δύο παραπάνω είναι ίσα, άρα,

$(\leftarrow )_{j}\tau =\sigma '(\leftarrow )_{i}$

$\tau =(\rightarrow )_{j}\sigma '(\leftarrow )_{i}$

όπου $(\rightarrow )_{j}$ είναι το αντίστροφο του $(\leftarrow )_{j}$ που είναι $(j,j+1,\cdots ,n)$.

Συνεπώς

$\tau \,=(j,j+1,\ldots ,n)\sigma '(n,n-1,\ldots ,i)$

Δεδομένου ότι οι δύο κύκλοι μπορούν να καταγραφούν αντίστοιχα ως μεταθέσεις $n-i$ και $n-j$,

$\operatorname {sgn} \tau \,=(-1)^{2n-(i+j)}\operatorname {sgn} \sigma '\,=(-1)^{i+j}\operatorname {sgn} \sigma .$

Και αφού η απεικόνιση $\sigma \leftrightarrow \tau$ είναι αμφιρριπτική,

${\begin{aligned}\sum _{i=1}^{n}\sum _{\tau \in S_{n}:\tau (i)=j}\operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{n,\tau (n)}&=\sum _{i=1}^{n}\sum _{\sigma \in S_{n-1}}(-1)^{i+j}\operatorname {sgn} \sigma \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}\sum _{\sigma \in S_{n-1}}\operatorname {sgn} \sigma \,a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}M_{ij}\end{aligned}}$

από το οποίο προκύπτει το αποτέλεσμα. Ομοίως, το αποτέλεσμα ισχύει αν ο δείκτης του εξωτερικού αθροίσματος αντικατασταθεί με $j$.

Ανάπτυγμα Λαπλάς μιας ορίζουσας με συμπληρωματικά ελάσσονες

Το ανάπτυγμα του Λαπλάς με συμπαράγοντες μπορεί να γενικευτεί ως εξής.

Παράδειγμα

Ας θεωρήσουμε τον πίνακα

$A={\begin{bmatrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{bmatrix}}.$

Η ορίζουσα αυτού του πίνακα μπορεί να υπολογιστεί χρησιμοποιώντας το ανάπτυγμα του συντελεστή Λαπλάς κατά μήκος των δύο πρώτων γραμμών ως εξής. Αρχικά ας σημειωθεί ότι υπάρχουν 6 σύνολα δύο διαφορετικών αριθμών στο {1, 2, 3, 4},, δηλαδή έστω $S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\}$ το προαναφερθέν σύνολο.

Με τον ορισμό των συμπληρωματικών συμπαράγοντων να είναι

$b_{\{j,k\}}={\begin{vmatrix}a_{1j}&a_{1k}\\a_{2j}&a_{2k}\end{vmatrix}},$

$c_{\{p,q\}}={\begin{vmatrix}a_{3p}&a_{3q}\\a_{4p}&a_{4q}\end{vmatrix}},$

και το πρόσημο της αντιμετάθεσής τους να είναι

$\varepsilon ^{\{j,k\},\{p,q\}}=\operatorname {sgn} {\begin{bmatrix}1&2&3&4\\j&k&p&q\end{bmatrix}},{\text{ where }}p\neq j,q\neq k.$

Η ορίζουσα του A μπορεί να γραφτεί ως εξής

$|A|=\sum _{H\in S}\varepsilon ^{H,H^{\prime }}b_{H}c_{H^{\prime }},$

όπου $H^{\prime }$ είναι το συμπληρωματικό σύνολο του $H$.

Στο ρητό παράδειγμά μας, αυτό δίνει

${\begin{aligned}|A|&=b_{\{1,2\}}c_{\{3,4\}}-b_{\{1,3\}}c_{\{2,4\}}+b_{\{1,4\}}c_{\{2,3\}}+b_{\{2,3\}}c_{\{1,4\}}-b_{\{2,4\}}c_{\{1,3\}}+b_{\{3,4\}}c_{\{1,2\}}\\[5pt]&={\begin{vmatrix}1&2\\5&6\end{vmatrix}}\cdot {\begin{vmatrix}11&12\\15&16\end{vmatrix}}-{\begin{vmatrix}1&3\\5&7\end{vmatrix}}\cdot {\begin{vmatrix}10&12\\14&16\end{vmatrix}}+{\begin{vmatrix}1&4\\5&8\end{vmatrix}}\cdot {\begin{vmatrix}10&11\\14&15\end{vmatrix}}+{\begin{vmatrix}2&3\\6&7\end{vmatrix}}\cdot {\begin{vmatrix}9&12\\13&16\end{vmatrix}}-{\begin{vmatrix}2&4\\6&8\end{vmatrix}}\cdot {\begin{vmatrix}9&11\\13&15\end{vmatrix}}+{\begin{vmatrix}3&4\\7&8\end{vmatrix}}\cdot {\begin{vmatrix}9&10\\13&14\end{vmatrix}}\\[5pt]&=-4\cdot (-4)-(-8)\cdot (-8)+(-12)\cdot (-4)+(-4)\cdot (-12)-(-8)\cdot (-8)+(-4)\cdot (-4)\\[5pt]&=16-64+48+48-64+16=0.\end{aligned}}$

Όπως και παραπάνω, είναι εύκολο να επαληθεύσετε ότι το αποτέλεσμα είναι σωστό: ο πίνακας είναι αντιστρέψιμος επειδή το άθροισμα της πρώτης και της τρίτης στήλης του είναι διπλάσιο της δεύτερης στήλης, και επομένως η ορίζουσα του είναι μηδέν.

Γενική δήλωση

Έστω $B=[b_{ij}]$ ένας n' × n πίνακας και $S$ το σύνολο των k-στοιχείων υποσυνόλων του {1, 2, ... , n}, $H$ ένα στοιχείο του. Τότε η ορίζουσα του $B$ μπορεί να αναπτυχθεί κατά μήκος του k σειρές που προσδιορίζονται από το $H$ ως εξής:

$|B|=\sum _{L\in S}\varepsilon ^{H,L}b_{H,L}c_{H,L}$

όπου $\varepsilon ^{H,L}$ είναι το πρόσημο της αντιμετάθεσης που καθορίζεται από $H$ και $L$, ίσο με $(-1)^{\left(\sum _{h\in H}h\right)+\left(\sum _{\ell \in L}\ell \right)}$, $b_{H,L}$ το ελάσσονα τετράγωνο του $B$ που λαμβάνεται διαγράφοντας από το $B$ γραμμές και στήλες με δείκτες στο $H$ και $L$ αντίστοιχα, και $c_{H,L}$ (που ονομάζεται συμπλήρωμα του $b_{H,L}$) που ορίζονται ως $b_{H',L'}$ , $H'$ και $L'$ είναι το συμπλήρωμα των $H$ και $L$ αντίστοιχα.

Αυτό συμπίπτει με το παραπάνω θεώρημα όταν $k=1$. Το ίδιο πράγμα ισχύει για οποιεσδήποτε σταθερές k στήλες.

Υπολογιστική δαπάνη

Το ανάπτυγμα Λαπλάς είναι υπολογιστικά αναποτελεσματικό για πίνακες μεγάλης διάστασης, με χρονική πολυπλοκότητα σε συμβολισμό μεγάλου O της τάξης τουO(n!). Εναλλακτικά, η χρήση μιας ανάλυσης σε τριγωνικούς πίνακες, όπως στην LU παραγοντοποίηση, μπορεί να δώσει ορίζουσες με χρονοπλοκότητα O(n³). Ο ακόλουθος κώδικας Python υλοποιεί το ανάπτυγμα Λαπλάς:

def determinant(M):
    # Base case of recursive function: 1x1 matrix
    if len(M) == 1: 
        return M[0][0]

    total = 0
    for column, element in enumerate(M[0]):
        # Exclude first row and current column.
        K = [x[:column] + x[column + 1 :] for x in M[1:]]
        s = 1 if column % 2 == 0 else -1 
        total += s * element * determinant(K)
    return total

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

• Μαυρογιάννης, Ν. Σ. (Μαΐου 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. 
• Belevitch V (1950). «Theory of 2n-terminal networks with applications to conference telephony». Electrical Communication 27: 231–244. 
• Bareiss, E. H. (1969), «Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices», Numerische Mathematik 13 (5): 404–424, doi:10.1007/BF02163269 
• Golub, Gene H.· Van Loan, Charles F. (1996). Matrix Computations (3rd έκδοση). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9. 
• Horn, Roger A.· Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. ISBN 0-521-38632-2. 
• Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 978-0-13-307505-2. 
• Smith, Steven W. (1999). «Chapter 8: The Discrete Fourier Transform». The Scientist and Engineer's Guide to Digital Signal Processing (Second έκδοση). San Diego, Calif.: California Technical Publishing. ISBN 978-0-9660176-3-2. 

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Μιγαδικός αριθμός
• Αντιερμιτιανός πίνακας
• Μέγιστος κοινός διαιρέτης
• Υπολογιστική βιολογία
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Συμμετρικός πίνακας
• Πίνακας γειτνίασης
• Πολλαπλασιασμός πινάκων
• Επαναλαμβανόμενη συνάρτηση
• Ιδιοτιμές και ιδιοδιανύσματα
• Θεωρία γράφων
• Θεωρία πιθανοτήτων
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

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

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Foundation Mathematics for Computer Science: A Visual Approach
• Multidimensional Statistical Analysis and Theory of Random Matrices ...
• Quantum Probability and Spectral Analysis of Graphs.
• Symplectic Methods in Harmonic Analysis and in Mathematical Physics...
• Lie Groups: An Introduction Through Linear Groups
• Matrix Algebra: Theory, Computations, and Applications in Statistics ..
• Calculus: Theory and Applications, Τόμος 2
• Special Matrices Of Mathematical Physics: Stochastic, Circulant And Bell ...

Παραπομπές

• David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, (ISBN 0-534-99845-3), pp. 265–267 (restricted online copy, σ. 265, στα Google Books)
• Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, (ISBN 3-7643-6905-1), pp. 57–60 (restricted online copy, σ. 57, στα Google Books)
• 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