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

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

 \begin{align}
\det(B)&= \sum_{j=1}^{n} (-1)^{i+j}  b_{i,j} m_{i, j},
\end{align}

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

 \begin{align}
\det(B)&= \sum_{i=1}^{n} (-1)^{i+j}  b_{i,j} m_{i, j}.
\end{align}

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

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

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

## Παραδείγματα
Ας εξετάσουμε τον πίνακα

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

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

:
\begin{align}
|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{align}


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

:
\begin{align}
|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{align}


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

## Απόδειξη
Έστω ότι ο 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}.  Καθένας από αυτούς έχει τη μορφή

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

για κάποια μετάθεση , και μια μοναδική και προφανώς σχετική μετάθεση \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 \le k \le 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,

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

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

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

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

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

### Παράδειγμα
Ας θεωρήσουμε τον πίνακα

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

Η ορίζουσα αυτού του πίνακα μπορεί να υπολογιστεί χρησιμοποιώντας το ανάπτυγμα του συντελεστή Λαπλάς κατά μήκος των δύο πρώτων γραμμών ως εξής. Αρχικά ας σημειωθεί ότι υπάρχουν 6 σύνολα δύο διαφορετικών αριθμών στο , δηλαδή έστω 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\}} = \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{align}
|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{align}

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

### Γενική δήλωση
Έστω B=[b_{ij}] ένας  πίνακας και S το σύνολο των -στοιχείων υποσυνόλων του , H ένα στοιχείο του. Τότε η ορίζουσα του B μπορεί να αναπτυχθεί κατά μήκος του  σειρές που προσδιορίζονται από το 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. Το ίδιο πράγμα ισχύει για οποιεσδήποτε σταθερές  στήλες.

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

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


```python3
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
```


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

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

* 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, , pp.&nbsp;265–267 ()
* Harvey E. Rose: *Linear Algebra. A Pure Mathematical Approach*. Springer 2002, , pp.&nbsp;57–60 ()
* 

 

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