Laplaceova expanze - Laplace expansion

v lineární algebra, Laplaceova expanze, pojmenoval podle Pierre-Simon Laplace, také zvaný expanze kofaktoru, je výraz pro určující |B| z n × n matice B to je vážený součet determinantů n dílčí matice (nebo nezletilí ) z B, každá o velikosti (n − 1) × (n - 1). Laplaceova expanze je didakticky zajímavá pro svou jednoduchost a jako jeden z několika způsobů, jak zobrazit a vypočítat determinant. U velkých matic se rychle stává neefektivní počítat ve srovnání s používáním metod maticový rozklad.

Výpočet determinantu Laplaceovou expanzí využívá kofaktor a Méně důležitý. The i, j kofaktor matice B je skalární C_ij definován

${displaystyle C_ {ij} = (- 1) ^ {i + j} M_ {ij} ,,}$

kde M_ij je i, j Méně důležitý z B, to znamená, že determinant (n − 1) × (n - 1) matice, která je výsledkem smazání i-tá řada a j-tý sloupec B.

Pak je Laplaceova expanze dána následujícím

Teorém. Předpokládat ${displaystyle B = [b_ {ij}]}$ je ${displaystyle n imes n}$ matice a vyberte libovolnou pevnou ${displaystyle i, jin {1,2 ... n}}$. Předpokládat ${displaystyle i ^ {'}}$ je pevná volba ${displaystyle iin {1,2 ... n}}$. Pak jeho determinant ${displaystyle left | Bight | = det (B)}$ darováno:

${displaystyle {egin {aligned} det (B) & = left [(- 1) ^ {i ^ {'} + 1} b_ {i ^ {'} 1} det (M_ {i ^ {'} 1}) ight] + vlevo [(- 1) ^ {i ^ {'} + 2} b_ {i ^ {'} 2} det (M_ {i ^ {'} 2}) ight] cdots + vlevo [(- 1) ^ {i ^ {'} + n} b_ {1n} det (M_ {i ^ {'} n}) ight] & = součet _ {j = 1} ^ {n} (- 1) ^ {i ^ {'} + j} b_ {i ^ {'} j} det (M_ {i ^ {'} j}) end {zarovnáno}}}$

kde ${displaystyle det (M_ {ij})}$ je menší prvek ${displaystyle B_ {ij}}$, tj. determinant submatice ${displaystyle M_ {ij}}$ vytvořen odstraněním ${displaystyle i ^ {th}}$ řádek a ${displaystyle j ^ {th}}$ sloupec matice ${displaystyle B}$.

Příklady

Zvažte matici

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

Determinant této matice lze vypočítat pomocí Laplaceovy expanze podél kteréhokoli z jejích řádků nebo sloupců. Například expanze podél první řady přináší:

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

Laplaceova expanze podél druhého sloupce přináší stejný výsledek:

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

Je snadné ověřit, že výsledek je správný: matice ano jednotné číslo protože součet jeho prvního a třetího sloupce je dvakrát druhý sloupec, a proto je jeho determinant nulový.

Důkaz

Předpokládat ${displaystyle B}$ je n × n matice a ${displaystyle i, jin {1,2, tečky, n}.}$ Pro přehlednost označujeme také položky ${displaystyle B}$ které tvoří jeho ${displaystyle i, j}$ vedlejší matice ${displaystyle M_ {ij}}$ tak jako

${displaystyle (a_ {st})}$ pro ${displaystyle 1leq s, tleq n-1.}$

Zvažte podmínky v expanzi ${displaystyle | B |}$ které mají ${displaystyle b_ {ij}}$ jako faktor. Každý má formu

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

pro některé permutace τ ∈ S_n s ${displaystyle au (i) = j}$a jedinečná a evidentně související permutace ${displaystyle sigma v S_ {n-1}}$ který vybírá stejné vedlejší položky jako τ. Podobně každá volba σ určuje odpovídající τ tj. korespondence ${displaystyle sigma leftrightarrow au}$ je bijekce mezi ${displaystyle S_ {n-1}}$ a ${displaystyle {au in S_ {n} dvojtečka au (i) = j}.}$Výslovný vztah mezi ${displaystyle au}$ a ${displaystyle sigma}$ lze psát jako

${displaystyle sigma = {egin {pmatrix} 1 & 2 & cdots & i & cdots & n-1 au (1) (leftarrow) _ {j} & au (2) (leftarrow) _ {j} & cdots & au (i + 1) (leftarrow) _ {j} & cdots & au (n) (leftarrow) _ {j} end {pmatrix}}}$

kde ${displaystyle (leftarrow) _ {j}}$ je dočasná zkratková notace pro a cyklus ${displaystyle (n, n-1, cdots, j + 1, j)}$.Tato operace sníží všechny indexy větší než j, takže každý index zapadne do množiny {1,2, ..., n-1}

Obměna τ lze odvodit z σ jak následuje. Definujte ${displaystyle sigma 'v S_ {n}}$ podle ${displaystyle sigma '(k) = sigma (k)}$ pro ${displaystyle 1leq kleq n-1}$ a ${displaystyle sigma '(n) = n}$. Pak ${displaystyle sigma '}$ je vyjádřena jako

${displaystyle sigma '= {egin {pmatrix} 1 & 2 & cdots & i & cdots & n-1 & n au (1) (leftarrow) _ {j} & au (2) (leftarrow) _ {j} & cdots & au (i + 1) (leftarrow) _ {j} & cdots & au (n) (leftarrow) _ {j} & nend {pmatrix}}}$

Nyní operace, která platí ${displaystyle (leftarrow) _ {i}}$ nejprve a poté použít ${displaystyle sigma '}$ je (Všimněte si, že použití A před B je ekvivalentní použití inverzní funkce A na horní řadu B v Cauchyho dvouřádkový zápis )

${displaystyle sigma '(leftarrow) _ {i} = {egin {pmatrix} 1 & 2 & cdots & i + 1 & cdots & n & i au (1) (leftarrow) _ {j} & au (2) (leftarrow) _ {j} & cdots & au ( i + 1) (leftarrow) _ {j} & cdots & au (n) (leftarrow) _ {j} & nend {pmatrix}}}$

kde ${displaystyle (leftarrow) _ {i}}$ je dočasná zkratková notace pro ${displaystyle (n, n-1, cdots, i + 1, i)}$.

operace, která se použije ${displaystyle au}$ nejprve a poté použít ${displaystyle (leftarrow) _ {j}}$ je

${displaystyle (leftarrow) _ {j} au = {egin {pmatrix} 1 & 2 & cdots & i & cdots & n-1 & n au (1) (leftarrow) _ {j} & au (2) (leftarrow) _ {j} & cdots & n & cdots & au ( n-1) (leftarrow) _ {j} & au (n) (leftarrow) _ {j} end {pmatrix}}}$

výše dva jsou tedy stejné,

${displaystyle (leftarrow) _ {j} au = sigma '(leftarrow) _ {i}}$

${displaystyle au = (ightarrow) _ {j} sigma '(leftarrow) _ {i}}$

kde ${displaystyle (ightarrow) _ {j}}$ je inverzní k ${displaystyle (leftarrow) _ {j}}$ který je ${displaystyle (j, j + 1, cdots, n)}$.

Tím pádem

${displaystyle au, = (j, j + 1, ldots, n) sigma '(n, n-1, ldots, i)}$

Protože dva cykly lze zapsat jednotlivě jako ${displaystyle n-i}$ a ${displaystyle n-j}$ transpozice,

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

A protože mapa ${displaystyle sigma leftrightarrow au}$ je bijektivní,

${displaystyle {egin {aligned} sum _ {au in S_ {n}: au (i) = j} operatorname {sgn} au, b_ {1, au (1)} cdots b_ {n, au (n)} & = součet _ {i = 1} ^ {n} součet _ {sigma v S_ {n-1}} (- 1) ^ {i + j} operatorname {sgn} sigma, b_ {ij} a_ {1, sigma ( 1)} cdots a_ {n-1, sigma (n-1)} & = součet _ {i = 1} ^ {n} b_ {ij} (- 1) ^ {i + j} součet _ {sigma v S_ {n-1}} operatorname {sgn} sigma, a_ {1, sigma (1)} cdots a_ {n-1, sigma (n-1)} & = součet _ {i = 1} ^ {n} b_ {ij} (- 1) ^ {i + j} M_ {ij} konec {zarovnáno}}}$

z čehož vyplývá výsledek. Podobně platí výsledek, pokud byl index vnějšího součtu nahrazen ${displaystyle j}$.

Laplaceova expanze determinantu doplňkovými nezletilými

Expanzi kofaktorů Laplaces lze zobecnit následovně.

Příklad

Zvažte matici

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

Determinant této matice lze vypočítat pomocí Laplaceova kofaktorového rozšíření podél prvních dvou řádků následujícím způsobem. Nejprve si všimněte, že v souboru je 6 sad dvou odlišných čísel {1, 2, 3, 4}, jmenovitě nechat ${displaystyle S = left {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} ight}}$ být výše uvedená sada.

Definováním doplňkových kofaktorů, které mají být

${displaystyle b _ {{j, k}} = {egin {vmatrix} a_ {1j} & a_ {1k} a_ {2j} & a_ {2k} end {vmatrix}},}$

${displaystyle c _ {{p, q}} = {egin {vmatrix} a_ {3p} & a_ {3q} a_ {4p} & a_ {4q} konec {vmatrix}},}$

a znamení jejich obměny

${displaystyle varepsilon ^ {{j, k}, {p, q}} = {mbox {sgn}} {egin {bmatrix} 1 & 2 & 3 & 4 j & k & p & qend {bmatrix}}, {ext {where}} peq j, qeq k.}$

Determinant A lze zapsat jako

${displaystyle | A | = součet _ {Hin S} varepsilon ^ {H, H ^ {prime}} b_ {H} c_ {H ^ {prime}},}$

kde ${displaystyle H ^ {prime}}$ je doplňkovou sadou ${displaystyle H}$.

V našem výslovném příkladu nám to dává

${displaystyle {egin {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] & = {egin {vmatrix} 1 & 2 5 & 6end {vmatrix}} cdot {egin {vmatrix} 11 & 12 15 & 16end {vmatrix}} - {egin {vmatrix} 1 & 3 5 & 7end {vmatrix}} cdot {egin {vmatrix} 10 & 12 14 & 16end {vmatrix}} + {egin {vmatrix} 1 & 4 5 & 8end {vmatrix}} cdot {egin {vmatrix} 10 & 11 14 & 15end {vmatrix}} + {egin { vmatrix} 2 & 3 6 & 7end {vmatrix}} cdot {egin {vmatrix} 9 & 12 13 & 16end {vmatrix}} - {egin {vmatrix} 2 & 4 6 & 8end {vmatrix}} cdot {egin {vmatrix} 9 & 11 13 & 15end {vmatrix}} + { egin {vmatrix} 3 a 4 7 a 8end {vmatrix}} cdot {egin {vmatrix} 9 a 10 13 a 14end {vmatrix}} [5pt] & = - 4cdot (-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 {zarovnáno}}}$

Jak je uvedeno výše, je snadné ověřit, zda je výsledek správný: matice ano jednotné číslo protože součet jeho prvního a třetího sloupce je dvakrát druhý sloupec, a proto je jeho determinant nulový.

Obecné prohlášení

Nechat ${displaystyle B = [b_ {ij}]}$ být n × n matice a ${displaystyle S}$ soubor k-prvkové podmnožiny {1, 2, ... , n}, ${displaystyle H}$ prvek v něm. Pak determinant ${displaystyle B}$ lze rozšířit podél k řádky označené ${displaystyle H}$ jak následuje:

${displaystyle | B | = součet _ {Lin S} varepsilon ^ {H, L} b_ {H, L} c_ {H, L}}$

kde ${displaystyle varepsilon ^ {H, L}}$ je znaménko permutace určené ${displaystyle H}$ a ${displaystyle L}$, rovná ${displaystyle (-1) ^ {left (sum _ {hin H} hight) + left (sum _ {ell in L} ell ight)}}$, ${displaystyle b_ {H, L}}$ menší čtverec z ${displaystyle B}$ získáno odstraněním z ${displaystyle B}$ řádky a sloupce s indexy v ${displaystyle H}$ a ${displaystyle L}$ respektive a ${displaystyle c_ {H, L}}$ (nazývá se doplňkem ${displaystyle b_ {H, L}}$) definováno jako ${displaystyle b_ {H ', L'}}$ , ${displaystyle H '}$ a ${displaystyle L '}$ je doplňkem ${displaystyle H}$ a ${displaystyle L}$ resp.

To se shoduje s teorémem výše, když ${displaystyle k = 1}$. Totéž platí pro všechny pevné k sloupce.

Výpočetní výdaje

Laplaceova expanze je výpočetně neúčinná pro matice vysokých dimenzí, s a časová složitost v velká O notace z ${displaystyle O (n!)}$. Alternativně lze použít rozklad na trojúhelníkové matice jako v LU rozklad může poskytnout determinanty s časovou složitostí ${displaystyle O (n ^ {3})}$.^[1] Následující Krajta kód implementuje Laplaceovu expanzi rekurzivně^{[Citace je zapotřebí ]}:

def určující(M):    # Základní případ rekurzivní funkce: matice 2x2 (taková, že det (M) = ad - cb)    -li len(M) == 2:        vrátit se (M[0][0] * M[1][1]) - (M[0][1] * M[1][0])    jiný:        celkový = 0        pro sloupec, živel v vyjmenovat(M[0]):            # Vyloučit první řádek a aktuální sloupec.            K. = [X[:sloupec] + X[sloupec + 1 :] pro X v M[1:]]            # Vzhledem k tomu, že prvek je v řádku 1, je znaménko záporné, pokud je index lichý.            -li sloupec % 2 == 0:                celkový += živel * určující(K.)            jiný:                celkový -= živel * určující(K.)        vrátit se celkový

Viz také

• Leibnizův vzorec pro determinanty
• Pravidlo Sarrus pro ${displaystyle 3 imes 3}$ determinanty

Reference

• David Poole: Lineární algebra. Moderní úvod. Cengage Learning 2005, ISBN  0-534-99845-3, str. 265–267 (omezené online kopírování, str. 265, v Knihy Google )
• Harvey E. Rose: Lineární algebra. Čistý matematický přístup. Springer 2002, ISBN  3-7643-6905-1, str. 57–60 (omezené online kopírování, str. 57, v Knihy Google )

externí odkazy

• Laplaceova expanze v C (v portugalštině)
• Expanze Laplace v Javě (v portugalštině)