Leibnizův vzorec pro determinanty - Leibniz formula for determinants

v algebra, Leibnizův vzorec, pojmenovaný na počest Gottfried Leibniz, vyjadřuje určující a čtvercová matice z hlediska permutací prvků matice. Li A je n×n matice, kde A_i,j je položka v ith řádek a jth sloupec A, vzorec je

{displaystyle det (A) = součet _ {au v S_ {n}} operatorname {sgn} (au) prod _ {i = 1} ^ {n} a_ {i, au (i)} = součet _ {sigma v S_ {n}} operatorname {sgn} (sigma) prod _ {i = 1} ^ {n} a_ {sigma (i), i},}

kde sgn je znaková funkce z obměny v permutační skupina S_n, která vrací +1 a -1 pro sudé a liché permutace, resp.

Další běžná notace použitá pro vzorec je ve smyslu Symbol Levi-Civita a využívá Einsteinova součtová notace, kde se to stane

{displaystyle det (A) = epsilon _ {i_ {1} cdots i_ {n}} {a} _ {1i_ {1}} cdots {a} _ {ni_ {n}},}

což může být fyzikům více známé.

Přímé vyhodnocení Leibnizova vzorce z definice vyžaduje ${displaystyle Omega (n! cdot n)}$ operace obecně - to znamená řada operací asymptoticky úměrných n faktoriál -protože n! je číslo objednávky-n obměny. Pro velké je to neprakticky obtížné n. Místo toho lze determinant vyhodnotit v O (n³) operace vytvořením LU rozklad ${displaystyle A = LU}$ (obvykle prostřednictvím Gaussova eliminace nebo podobné metody), v takovém případě ${displaystyle det A = (det L) (det U)}$ a determinanty trojúhelníkových matic L a U jsou jednoduše produkty jejich diagonálních vstupů. (V praktických aplikacích numerické lineární algebry je však zřídka vyžadován explicitní výpočet determinantu.) Viz například Trefethen & Bau (1997).

Formální prohlášení a důkaz

Teorém.Existuje právě jedna funkce

{displaystyle F: M_ {n} (mathbb {K}) ightarrow mathbb {K}}

který je střídavý multilineární w.r.t. sloupce a podobně ${displaystyle F (I) = 1}$ .

Důkaz.

Jedinečnost: Nechat ${displaystyle F}$ být takovou funkcí a nechť ${displaystyle A = (a_ {i} ^ {j}) _ {i = 1, tečky, n} ^ {j = 1, tečky, n}}$ být ${displaystyle n imes n}$ matice. Volání ${displaystyle A ^ {j}}$ the ${displaystyle j}$ -tý sloupec ${displaystyle A}$ , tj. ${displaystyle A ^ {j} = (a_ {i} ^ {j}) _ {i = 1, tečky, n}}$ , aby ${displaystyle A = left (A ^ {1}, dots, A ^ {n} ight).}$

Také nechte ${displaystyle E ^ {k}}$ označit ${displaystyle k}$ -tý sloupcový vektor matice identity.

Nyní jeden píše každý z ${displaystyle A ^ {j}}$ je z hlediska ${displaystyle E ^ {k}}$ , tj.

{displaystyle A ^ {j} = součet _ {k = 1} ^ {n} a_ {k} ^ {j} E ^ {k}}

.

Tak jako ${displaystyle F}$ je multilineární, jeden má

{displaystyle {egin {aligned} F (A) & = Fleft (sum _ {k_ {1} = 1} ^ {n} a_ {k_ {1}} ^ {1} E ^ {k_ {1}}, tečky , součet _ {k_ {n} = 1} ^ {n} a_ {k_ {n}} ^ {n} E ^ {k_ {n}} ight) & = součet _ {k_ {1}, tečky, k_ {n} = 1} ^ {n} vlevo (prod _ {i = 1} ^ {n} a_ {k_ {i}} ^ {i} ight) Fleft (E ^ {k_ {1}}, tečky, E ^ {k_ {n}} hned) .end {zarovnáno}}}

Ze střídání vyplývá, že jakýkoli člen s opakovanými indexy je nula. Součet lze tedy omezit na n-tice s neopakujícími se indexy, tj. Permutacemi:

{displaystyle F (A) = součet _ {sigma v S_ {n}} vlevo (prod _ {i = 1} ^ {n} a_ {sigma (i)} ^ {i} ight) F (E ^ {sigma ( 1)}, tečky, E ^ {sigma (n)}).}

Protože F se střídá, sloupy ${displaystyle E}$ lze vyměnit, dokud se nestane identitou. The znaková funkce ${displaystyle operatorname {sgn} (sigma)}$ je definován tak, aby počítal potřebný počet swapů a zohlednil výslednou změnu znaménka. Jeden konečně dostane:

{displaystyle {egin {aligned} F (A) & = sum _ {sigma in S_ {n}} operatorname {sgn} (sigma) left (prod _ {i = 1} ^ {n} a_ {sigma (i)} ^ {i} ight) F (I) & = součet _ {sigma v S_ {n}} operatorname {sgn} (sigma) prod _ {i = 1} ^ {n} a_ {sigma (i)} ^ { i} konec {zarovnáno}}}

tak jako ${displaystyle F (I)}$ se musí rovnat ${displaystyle 1}$ .

Proto žádná funkce kromě funkce definované Leibnizovým vzorcem nemůže být multilineární střídavou funkcí s ${displaystyle Fleft (Iight) = 1}$ .

Existence: Nyní ukážeme, že F, kde F je funkce definovaná Leibnizovým vzorcem, má tyto tři vlastnosti.

Multilineární:

{displaystyle {egin {aligned} F (A ^ {1}, dots, cA ^ {j}, dots) & = sum _ {sigma in S_ {n}} operatorname {sgn} (sigma) ca_ {sigma (j) } ^ {j} prod _ {i = 1, ieq j} ^ {n} a_ {sigma (i)} ^ {i} & = csum _ {sigma v S_ {n}} operatorname {sgn} (sigma) a_ {sigma (j)} ^ {j} prod _ {i = 1, ieq j} ^ {n} a_ {sigma (i)} ^ {i} & = cF (A ^ {1}, tečky, A ^ {j}, tečky) F (A ^ {1}, tečky, b + A ^ {j}, tečky) & = součet _ {sigma v S_ {n}} operatorname {sgn} (sigma) vlevo ( b_ {sigma (j)} + a_ {sigma (j)} ^ {j} ight) prod _ {i = 1, ieq j} ^ {n} a_ {sigma (i)} ^ {i} & = součet _ {sigma in S_ {n}} operatorname {sgn} (sigma) left (left (b_ {sigma (j)} prod _ {i = 1, ieq j} ^ {n} a_ {sigma (i)} ^ { i} ight) + left (a_ {sigma (j)} ^ {j} prod _ {i = 1, ieq j} ^ {n} a_ {sigma (i)} ^ {i} ight) ight) & = left (sum _ {sigma in S_ {n}} operatorname {sgn} (sigma) b_ {sigma (j)} prod _ {i = 1, ieq j} ^ {n} a_ {sigma (i)} ^ {i } ight) + left (sum _ {sigma in S_ {n}} operatorname {sgn} (sigma) prod _ {i = 1} ^ {n} a_ {sigma (i)} ^ {i} ight) & = F (A ^ {1}, tečky, b, tečky) + F (A ^ {1}, tečky, A ^ {j}, tečky) konec {zarovnáno}}}

Střídavě:

{displaystyle {egin {aligned} F (tečky, A ^ {j_ {1}}, tečky, A ^ {j_ {2}}, tečky) & = součet _ {sigma v S_ {n}} operatorname {sgn} ( sigma) left (prod _ {i = 1, ieq j_ {1}, ieq j_ {2}} ^ {n} a_ {sigma (i)} ^ {i} ight) a_ {sigma (j_ {1})} ^ {j_ {1}} a_ {sigma (j_ {2})} ^ {j_ {2}} end {zarovnáno}}}

Pro všechny ${displaystyle sigma v S_ {n}}$ nechat ${displaystyle sigma '}$ být n-tice rovná ${displaystyle sigma}$ s ${displaystyle j_ {1}}$ a ${displaystyle j_ {2}}$ indexy přepnuty.

{displaystyle {egin {aligned} F (A) & = sum _ {sigma in S_ {n}, sigma (j_ {1})

Tedy pokud ${displaystyle A ^ {j_ {1}} = A ^ {j_ {2}}}$ pak ${displaystyle F (tečky, A ^ {j_ {1}}, tečky, A ^ {j_ {2}}, tečky) = 0}$ .

Konečně, ${displaystyle F (I) = 1}$ :

{displaystyle {egin {aligned} F (I) & = sum _ {sigma in S_ {n}} operatorname {sgn} (sigma) prod _ {i = 1} ^ {n} I_ {sigma (i)} ^ { i} = součet _ {sigma v S_ {n}} operatorname {sgn} (sigma) prod _ {i = 1} ^ {n} operatorname {delta} _ {i, sigma (i)} & = sum _ { sigma v S_ {n}} operatorname {sgn} (sigma) operatorname {delta} _ {sigma, operatorname {id} _ {{1ldots n}}} = operatorname {sgn} (operatorname {id} _ {{1ldots n} }) = 1end {zarovnáno}}}

Tedy jediné střídavé multilineární funkce s ${displaystyle F (I) = 1}$ jsou omezeny na funkci definovanou Leibnizovým vzorcem a ve skutečnosti má také tyto tři vlastnosti. Proto lze determinant definovat jako jedinou funkci

{displaystyle det: M_ {n} (mathbb {K}) ightarrow mathbb {K}}

s těmito třemi vlastnostmi.

Viz také

Reference

„Určující“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
Trefethen, Lloyd N .; Bau, David (1. června 1997). Numerická lineární algebra. SIAM. ISBN 978-0898713619.CS1 maint: ref = harv (odkaz)