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

Στη γραμμική άλγεβρα, το ανάπτυγμα Λαπλάς, το οποίο πήρε το όνομά του από τον Πιερ-Σιμόν ντε Λαπλάς, και ονομάζεται επίσης ανάπτυγμα συμπαράγοντα, είναι μια έκφραση της ορίζουσας ενός Πρότυπο:Math-πίνακα Πρότυπο:Mvar ως σταθμισμένο άθροισμα ελάσσονων, που είναι οι ορίζουσες κάποιων Πρότυπο:Math-υποπινάκων του Πρότυπο:Mvar. Συγκεκριμένα, για κάθε Πρότυπο:Mvar, το ανάπτυγμα Λαπλάς κατά μήκος της Πρότυπο:Mvar-th γραμμής είναι η ισότητα

$\begin{array}{cc}\det (B)& =\sum _{j=1}^n(-1{)}^{i+j}{b}_{i,j}{m}_{i,j},\end{array}$

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

$\begin{array}{cc}\det (B)& =\sum _{i=1}^n(-1{)}^{i+j}{b}_{i,j}{m}_{i,j}.\end{array}$

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

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

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

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

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

$B=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right].$

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

$\begin{array}{cc}|B|& =1\cdot \left|\begin{array}{cc}5& 6\\ 8& 9\end{array}\right|-2\cdot \left|\begin{array}{cc}4& 6\\ 7& 9\end{array}\right|+3\cdot \left|\begin{array}{cc}4& 5\\ 7& 8\end{array}\right|\\ & =1\cdot (-3)-2\cdot (-6)+3\cdot (-3)=0.\end{array}$

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

$\begin{array}{cc}|B|& =-2\cdot \left|\begin{array}{cc}4& 6\\ 7& 9\end{array}\right|+5\cdot \left|\begin{array}{cc}1& 3\\ 7& 9\end{array}\right|-8\cdot \left|\begin{array}{cc}1& 3\\ 4& 6\end{array}\right|\\ & =-2\cdot (-6)+5\cdot (-12)-8\cdot (-6)=0.\end{array}$

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

Απόδειξη

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

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

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

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

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

$\sigma =\left(\begin{array}{cccccc}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{array}\right)$

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

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

${\sigma }^{\prime }=\left(\begin{array}{ccccccc}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{array}\right)$

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

${\sigma }^{\prime }(\leftarrow {)}_i=\left(\begin{array}{ccccccc}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{array}\right)$

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

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

$(\leftarrow {)}_j\tau =\left(\begin{array}{ccccccc}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{array}\right)$

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

$(\leftarrow {)}_j\tau ={\sigma }^{\prime }(\leftarrow {)}_i$

$\tau =(\to {)}_j{\sigma }^{\prime }(\leftarrow {)}_i$

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

Συνεπώς

$\tau =(j,j+1,\dots ,n){\sigma }^{\prime }(n,n-1,\dots ,i)$

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

$\mathrm{sgn}\tau =(-1{)}^{2n-(i+j)}\mathrm{sgn}{\sigma }^{\prime }=(-1{)}^{i+j}\mathrm{sgn}\sigma .$

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

$\begin{array}{cc}\sum _{i=1}^n\sum _{\tau \in S_n:\tau (i)=j}\mathrm{sgn}\tau b_{1,\tau (1)}\cdots b_{n,\tau (n)}& =\sum _{i=1}^n\sum _{\sigma \in S_{n-1}}(-1{)}^{i+j}\mathrm{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}}\mathrm{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{array}$

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

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

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

Παράδειγμα

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

$A=\left[\begin{array}{cccc}1& 2& 3& 4\\ 5& 6& 7& 8\\ 9& 10& 11& 12\\ 13& 14& 15& 16\end{array}\right].$

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

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

$b_{\{j,k\}}=\left|\begin{array}{cc}{a}_{1j}& a_{1k}\\ a_{2j}& a_{2k}\end{array}\right|,$

$c_{\{p,q\}}=\left|\begin{array}{cc}{a}_{3p}& a_{3q}\\ a_{4p}& a_{4q}\end{array}\right|,$

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

${\epsilon }^{\{j,k\},\{p,q\}}=\mathrm{sgn}\left[\begin{array}{cccc}1& 2& 3& 4\\ j& k& p& q\end{array}\right],\text{ where }p\ne j,q\ne k.$

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

$|A|=\sum _{H\in S}{\epsilon }^{H,H^{\prime }}{b}_H{c}_{H^{\prime }},$

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

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

$\begin{array}{cc}|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\}}\\ & =\left|\begin{array}{cc}1& 2\\ 5& 6\end{array}\right|\cdot \left|\begin{array}{cc}11& 12\\ 15& 16\end{array}\right|-\left|\begin{array}{cc}1& 3\\ 5& 7\end{array}\right|\cdot \left|\begin{array}{cc}10& 12\\ 14& 16\end{array}\right|+\left|\begin{array}{cc}1& 4\\ 5& 8\end{array}\right|\cdot \left|\begin{array}{cc}10& 11\\ 14& 15\end{array}\right|+\left|\begin{array}{cc}2& 3\\ 6& 7\end{array}\right|\cdot \left|\begin{array}{cc}9& 12\\ 13& 16\end{array}\right|-\left|\begin{array}{cc}2& 4\\ 6& 8\end{array}\right|\cdot \left|\begin{array}{cc}9& 11\\ 13& 15\end{array}\right|+\left|\begin{array}{cc}3& 4\\ 7& 8\end{array}\right|\cdot \left|\begin{array}{cc}9& 10\\ 13& 14\end{array}\right|\\ & =-4\cdot (-4)-(-8)\cdot (-8)+(-12)\cdot (-4)+(-4)\cdot (-12)-(-8)\cdot (-8)+(-4)\cdot (-4)\\ & =16-64+48+48-64+16=0.\end{array}$

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

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

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

$|B|=\sum _{L\in S}{\epsilon }^{H,L}{b}_{H,L}{c}_{H,L}$

όπου ${\epsilon }^{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^{\prime },L^{\prime }}$ , $H^{\prime }$ και $L^{\prime }$ είναι το συμπλήρωμα των $H$ και $L$ αντίστοιχα.

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

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

Το ανάπτυγμα Λαπλάς είναι υπολογιστικά αναποτελεσματικό για πίνακες μεγάλης διάστασης, με χρονική πολυπλοκότητα σε συμβολισμό μεγάλου O της τάξης τουΠρότυπο:Math. Εναλλακτικά, η χρήση μιας ανάλυσης σε τριγωνικούς πίνακες, όπως στην LU παραγοντοποίηση, μπορεί να δώσει ορίζουσες με χρονοπλοκότητα Πρότυπο:Math. Ο ακόλουθος κώδικας 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

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

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Citation
• Πρότυπο:Cite book
• Πρότυπο:Cite book
• Πρότυπο:Cite book
• Πρότυπο:Cite book

Δείτε επίσης

• 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, pp. 265–267 (Πρότυπο:Google books)
• Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, Πρότυπο:ISBN, pp. 57–60 (Πρότυπο:Google books)
• Πρότυπο:Citation