Laplace expansion

Den här artikeln handlar om uttrycket av en determinant i termer av minderåriga. För approximation av radiella potentialer, se Laplace expansion (potential) .

Inom linjär algebra är Laplaceexpansionen , uppkallad efter Pierre-Simon Laplace , även kallad kofaktorexpansion , ett uttryck för determinanten för en n × n matris B som en viktad summa av minorer n − 1 ) × ( n − 1) , som är determinanter för vissa ( submatriser av B . Specifikt, för varje jag ,

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

där $B_{i,j}$ är inmatningen av den i: te raden och j :te kolumnen i B , och $M_{i,j}$ är determinanten för submatris erhållen genom att ta bort den i: te raden och den j: te kolumnen i B .

Termen $\displaystyle (-1)^{i+j}M_{i,j}}$$B_{i,j }$ kallas kofaktorn för i B .

Laplace-expansionen är ofta användbar i bevis, som till exempel för att tillåta rekursion på storleken på matriser. Det är också av didaktiskt intresse för sin enkelhet och som ett av flera sätt att se och beräkna determinanten. För stora matriser blir det snabbt ineffektivt att beräkna jämfört med Gaussisk eliminering .

Exempel

Tänk på matrisen

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

Determinanten för denna matris kan beräknas genom att använda Laplace-expansionen längs någon av dess rader eller kolumner. Till exempel ger en expansion längs den första raden:

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

Laplace-expansion längs den andra kolumnen ger samma resultat:

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

Det är lätt att verifiera att resultatet är korrekt: matrisen är singular eftersom summan av dess första och tredje kolumn är två gånger den andra kolumnen, och därför är dess determinant noll.

Bevis

Antag att $B$ är en n × n matris och $i,j\in \{1,2,\dots ,n\}.$ För tydlighetens skull märker vi även posterna i $B$ som utgör dess $i,j$ moll matris $M_{ij}$ as

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

Tänk på villkoren i expansionen av $|B|$ som har $b_{ij}$ som faktor. Var och en har formen

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

för någon permutation τ ∈ S _n med ${\displaystyle \tau (i)=j} ,$ och en unik och uppenbarligen relaterad permutation $\sigma \in S_{n- 1}$ som väljer samma mindre poster som τ . På liknande sätt bestämmer varje val av σ en motsvarande τ dvs överensstämmelsen $\sigma \leftrightarrow \tau$ är en bijektion mellan $S_{n-1}$ och $\{\tau \in S_{n}\colon \tau (i)=j\}.$ Med hjälp av Cauchys tvåradiga notation , den explicita relationen mellan $\tau$ och $\ sigma$ kan skrivas som

$\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}}$

där $(\leftarrow )_{j}$ är en tillfällig förkortning för en cykel $(n,n-1, \cdots ,j+1,j)$ . Denna operation minskar alla index större än j så att varje index passar i uppsättningen {1,2,...,n-1}

Permutationen τ kan härledas från σ enligt följande. Definiera $\sigma '\in S_{n}$ med $\sigma '(k)=\sigma (k)$ för $1\leq k\leq n-1$ och $\sigma '(n)=n$ . Då uttrycks ${\displaystyle \sigma '} som$

$\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}}$

Nu är operationen som tillämpar $(\leftarrow )_{i}$ först och sedan applicerar $\sigma '$ (Observera att tillämpa A före B är ekvivalent med att tillämpa invers av A till den övre raden av B i tvåradsnotation)

$\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 &(\ vänsterpil )_{j}(\tau (n))&n\end{pmatrix}}$

där $(\leftarrow )_{i}$$(n,n-1,\cdots , i+1,i)$ tillfällig förkortning för .

operationen som tillämpar $\tau$ först och sedan tillämpar $(\leftarrow )_{j}$ är

$(\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}}$

ovan två är lika, alltså,

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

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

där $(\rightarrow )_{j}$ är inversen av $(\leftarrow )_{j}$ som är $(j,j+1,\cdots,n)$ .

Således

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

Eftersom de två cyklerna kan skrivas som $ni$ respektive $nj$ transpositioner ,

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

Och eftersom kartan $\sigma \leftrightarrow \tau$ är bijektiv,

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

varav resultatet följer. På samma sätt gäller resultatet om indexet för den yttre summeringen ersattes med $j$ .

Laplace expansion av en determinant av komplementära minderåriga

Laplaces kofaktorexpansion kan generaliseras enligt följande.

Exempel

Tänk på matrisen

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

Determinanten för denna matris kan beräknas genom att använda Laplaces kofaktorexpansion längs de två första raderna enligt följande. Observera först att det finns 6 uppsättningar av två distinkta tal i {1, 2, 3, 4}, nämligen låt $S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2, 4\},\{3,4\}\right\}$ vara den tidigare nämnda uppsättningen.

Genom att definiera de komplementära kofaktorerna som ska vara

$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}},$

och tecknet på deras permutation att vara

$\varepsilon ^{\{j,k\},\{p,q\}}=\operatörsnamn {sgn} {\begin{bmatrix}1&2&3&4\\j&k&p&q\end{bmatrix}},{\text{ där }}p\neq j,q\neq k.$

Determinanten för A kan skrivas ut som

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

där $H^{\prime }$ är den komplementära uppsättningen till $H$ .

I vårt explicita exempel ger detta oss

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

Som ovan är det lätt att verifiera att resultatet är korrekt: matrisen är singular eftersom summan av dess första och tredje kolumn är två gånger den andra kolumnen, och därför är dess determinant noll.

Allmänt uttalande

Låt $B=[b_{ij}]$ vara en n × n matris och $S$ uppsättningen av k -elementdelmängder av {1, 2, ... , n } , $H$ ett element i den. Sedan kan determinanten för $B$ utökas längs de k rader som identifieras av $H$ enligt följande:

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

där $\varepsilon ^{H,L}$ är tecknet för permutationen som bestäms av $H$ och $L$ , lika med $(-1)^{\left(\sum _{h\in H}h\right)+\left(\sum _{\ell \in L}\ ell \right)}$ , $b_{H,L}$$H}$ i moll av $B$ som erhålls genom att rader och kolumner med index i $displaystyle$ och $L} raderas från B {\displaystyle B$ respektive, och $c_{H,L}$ (kallas komplementet till $b_{H,L}$ ) definierade som $b_{H',L'}$ , $H'$ och $L'$ är komplementet till H $\displaystyle H}$ respektive ${\displaystyle L} .$

Detta sammanfaller med satsen ovan när $k=1$ . Samma sak gäller för alla fasta k kolumner.

Beräkningskostnad

Laplace-expansionen är beräkningsineffektiv för högdimensionella matriser, med en tidskomplexitet O ( n !) i stor O-notation av . Alternativt kan användning av en sönderdelning till triangulära matriser som i LU-sönderdelningen ge determinanter med en tidskomplexitet på O ( n ³ ) . Följande Python- kod implementerar Laplace-expansion rekursivt :

 
    
        
         00

      0
        0
        
             def  determinant  (  M  ):  # Basfall för rekursiv funktion: 1x1 matris  om  len  (  M  )  ==  1  :  returnera  M  [  ][  ]  totalt  =  för  kolumn  ,  element  i  uppräkning  (  M  [  ]):  # Exkludera första raden och nuvarande kolumn.  K  =  [  x  [:  kolumn  ]  +  x  [        
                0   
              
      kolumn  +  1  :]  för  x  i  M  [  1  :]]  s  =  1  om  kolumn  %  2  ==  annat  -  1  totalt  +=  s  *  element  *  determinant  (  K  )  returnerar  totalt 

Se även

• Leibniz formel för determinanter
• Sarrus regel för $3\x3$ determinanter

•   David Poole: Linjär algebra. En modern introduktion . Cengage Learning 2005, ISBN 0-534-99845-3 , s. 265–267 ( begränsad onlinekopia , s. 265, på Google Books )
•   Harvey E. Rose: Linjär algebra. Ett rent matematiskt tillvägagångssätt . Springer 2002, ISBN 3-7643-6905-1 , s. 57–60 ( begränsad onlinekopia , s. 57, på Google Books )

externa länkar

• Laplace expansion i C (på portugisiska)
• Laplace-expansion i Java (på portugisiska)