Leibnizův vzorec pro determinanty - Leibniz formula for determinants

V algebry se Leibniz vzorec , pojmenovaný ve cti Gottfried Leibniz , vyjadřuje determinant o čtvercové matice , pokud jde o permutací prvků matrice. Pokud je matice, kde je položka v -th řádku a -th sloupci , vzorec je ${\ displaystyle A}$${\ displaystyle n \ times n}$${\ displaystyle a_ {ij}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle A}$

${\ Displaystyle \ det (A) = \ sum _ {\ tau \ in S_ {n}} \ operatorname {sgn} (\ tau) \ prod _ {i = 1}^{n} a_ {i, \, \ tau (i)} = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1}^{n} a _ {\ sigma (i), \, i},}$

kde je funkce znamení z permutací ve skupině permutace , která vrací a pro sudé a liché permutací , resp. ${\ displaystyle \ operatorname {sgn}}$ ${\ displaystyle S_ {n}}$${\ displaystyle +1}$${\ Displaystyle -1}$

Další běžný zápis použitý pro vzorec je z hlediska symbolu Levi-Civita a využívá součtový zápis Einsteina , kde se stává

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

což může být fyzikům známější.

Přímé vyhodnocení Leibnizova vzorce z definice vyžaduje operace obecně- to znamená, že řada operací je asymptoticky úměrná faktoriálu- protože počet permutací objednávek . To je neprakticky obtížné i pro relativně malé . Místo toho může být determinant vyhodnocen v operacích vytvořením dekompozice LU (typicky pomocí Gaussovy eliminace nebo podobných metod), v takovém případě a determinantů trojúhelníkových matic a jsou jednoduše produkty jejich diagonálních záznamů. (V praktických aplikacích numerické lineární algebry je však explicitní výpočet determinantu vyžadován jen zřídka.) Viz například Trefethen & Bau (1997) . Determinant může být také vyhodnocen méně než operací snížením problému na násobení matice , ale většina takových algoritmů není praktická. ${\ Displaystyle \ Omega (n! \ cdot n)}$${\ displaystyle n}$ ${\ displaystyle n!}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle O (n^{3})}$ ${\ displaystyle A = LU}$${\ Displaystyle \ det A = \ det L \ cdot \ det U}$${\ displaystyle L}$${\ displaystyle U}$${\ displaystyle O (n^{3})}$

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

Teorém. Existuje přesně jedna funkce, která střídá víceřádkové sloupce wrt a podobné . ${\ Displaystyle F: M_ {n} (\ mathbb {K}) \ rightarrow \ mathbb {K}}$ ${\ displaystyle F (I) = 1}$

Důkaz.

Jedinečnost: Nechť je takovou funkcí a nechme být maticí. Zavolejte do -th sloupce , tj . Tak, že${\ displaystyle F}$${\ Displaystyle A = (a_ {i}^{j}) _ {i = 1, \ tečky, n}^{j = 1, \ tečky, n}}$${\ displaystyle n \ times n}$${\ displaystyle A^{j}}$${\ displaystyle j}$${\ displaystyle A}$${\ Displaystyle A^{j} = (a_ {i}^{j}) _ {i = 1, \ tečky, n}}$${\ Displaystyle A = \ left (A^{1}, \ dots, A^{n} \ right).}$

Také, ať naznačovat tý sloupcový vektor matice identity. ${\ displaystyle E^{k}}$${\ displaystyle k}$

Nyní se píše každé z pojmů , tj ${\ displaystyle A^{j}}$${\ displaystyle E^{k}}$

${\ Displaystyle A^{j} = \ sum _ {k = 1}^{n} a_ {k}^{j} E^{k}}$.

Stejně jako víceřádkový, jeden má ${\ displaystyle F}$

${\ Displaystyle {\ begin {aligned} F (A) & = F \ left (\ 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}} \ vpravo) = \ součet _ {k_ {1}, \ dots, k_ {n} = 1}^{n} \ left (\ prod _ {i = 1}^{n} a_ {k_ {i}}^{i} \ right) F \ left (E^{k_ {1}}, \ tečky, E^{k_ {n}} \ vpravo). \ End {aligned}}}$

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

${\ Displaystyle F (A) = \ sum _ {\ sigma \ in S_ {n}} \ left (\ prod _ {i = 1}^{n} a _ {\ sigma (i)}^{i} \ right ) F (E^{\ sigma (1)}, \ dots, E^{\ sigma (n)}).}$

Protože F se střídá, lze sloupce prohodit, dokud se nestane identitou. Funkce znak je definována tak, aby počítala počet nezbytných swapů a zohlednila výslednou změnu znaménka. Jeden nakonec dostane: ${\ displaystyle E}$ ${\ displaystyle \ operatorname {sgn} (\ sigma)}$

${\ displaystyle {\ begin {aligned} F (A) & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1}^{ n} a _ {\ sigma (i)}^{i} \ right) F (I) \\ & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1}^{n} a _ {\ sigma (i)}^{i} \ end {zarovnáno}}}$

jak je požadováno, aby se rovnalo . ${\ displaystyle F (I)}$${\ displaystyle 1}$

Proto žádná funkce kromě funkce definované Leibnizovým vzorcem nemůže být víceřádkovou střídavou funkcí s . ${\ Displaystyle F \ left (I \ right) = 1}$

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

Víceřádkový :

${\ Displaystyle {\ begin {aligned} F (A^{1}, \ dots, cA^{j}, \ dots) & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} ( \ sigma) ca _ {\ sigma (j)}^{j} \ prod _ {i = 1, i \ neq j}^{n} a _ {\ sigma (i)}^{i} \\ & = c \ součet _ {\ sigma \ v S_ {n}} \ operatorname {sgn} (\ sigma) a _ {\ sigma (j)}^{j} \ prod _ {i = 1, i \ neq j}^{n} a _ {\ sigma (i)}^{i} \\ & = cF (A^{1}, \ dots, A^{j}, \ dots) \\\\ F (A^{1}, \ dots , b+A^{j}, \ tečky) & = \ sum _ {\ sigma \ v S_ {n}} \ operatorname {sgn} (\ sigma) \ left (b _ {\ sigma (j)}+a_ { \ sigma (j)}^{j} \ right) \ prod _ {i = 1, i \ neq j}^{n} a _ {\ sigma (i)}^{i} \\ & = \ sum _ { \ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ left (\ left (b _ {\ sigma (j)} \ prod _ {i = 1, i \ neq j}^{n} a_ {\ sigma (i)}^{i} \ right)+\ left (a _ {\ sigma (j)}^{j} \ prod _ {i = 1, i \ neq j}^{n} a _ {\ sigma (i)}^{i} \ right) \ right) \\ & = \ left (\ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) b _ {\ sigma (j )} \ prod _ {i = 1, i \ neq j}^{n} a _ {\ sigma (i)}^{i} \ right)+\ left (\ sum _ {\ sigma \ in S_ {n} } \ operatorname {sgn} (\ sigma) \ prod _ {i = 1}^{n} a _ {\ sigma (i)}^{i} \ right) \\ & = F (A^{1}, \ tečky, b, \ tečky)+F (A^{1}, \ tečky, A^{j}, \ tečky) \\\\\ end {aligned}}}$

Střídání :

${\ displaystyle {\ begin {aligned} F (\ dots, A^{j_ {1}}, \ dots, A^{j_ {2}}, \ dots) & = \ sum _ {\ sigma \ in S_ { n}} \ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}}^{n} a _ {\ sigma (i) }^{i} \ right) a _ {\ sigma (j_ {1})}^{j_ {1}} a _ {\ sigma (j_ {2})}^{j_ {2}} \\\ end {zarovnáno }}}$

Pro jakýkoli pustíte být n-tice rovnat s a indexy zapnutý. ${\ displaystyle \ sigma \ v S_ {n}}$${\ Displaystyle \ sigma '}$${\ Displaystyle \ sigma}$${\ displaystyle j_ {1}}$${\ displaystyle j_ {2}}$

${\ Displaystyle {\ begin {aligned} F (A) & = \ sum _ {\ sigma \ v S_ {n}, \ sigma (j_ {1}) <\ sigma (j_ {2})} \ left [\ jméno operátora {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}}^{n} a _ {\ sigma (i)}^{i } \ right) a _ {\ sigma (j_ {1})}^{j_ {1}} a _ {\ sigma (j_ {2})}^{j_ {2}}+\ operatorname {sgn} (\ sigma ' ) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}}^{n} a _ {\ sigma '(i)}^{i} \ right) a_ { \ sigma '(j_ {1})}^{j_ {1}} a _ {\ sigma' (j_ {2})}^{j_ {2}} \ right] \\ & = \ sum _ {\ sigma \ v S_ {n}, \ sigma (j_ {1}) <\ sigma (j_ {2})} \ left [\ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}}^{n} a _ {\ sigma (i)}^{i} \ right) a _ {\ sigma (j_ {1})}^{j_ {1}} a _ {\ sigma (j_ {2})}^{j_ {2}}-\ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}}^{n} a _ {\ sigma (i)}^{i} \ right) a _ {\ sigma (j_ {2})}^{j_ {1}} a _ {\ sigma (j_ {1 })}^{j_ {2}} \ right] \\ & = \ sum _ {\ sigma \ v S_ {n}, \ sigma (j_ {1}) <\ sigma (j_ {2})} \ operatorname {sgn} (\ sigma) \ left (\ prod _ {i = 1, i \ neq j_ {1}, i \ neq j_ {2}}^{n} a _ {\ sigma (i)}^{i} \ right) \ underbrace {\ left (a _ {\ sigma (j_ {1})}^{j_ {1}} a _ {\ sigma (j_ {2})}^{j_ {2}}-a _ {\ sigma (j_ {1})}^{j_ {2}} a _ {\ sigma (j_ {2})}^{j _ {_ {1} }} \ right)} _ {= 0 {\ text {, if}} j_ {1} = j_ {2}} \\\\\ end {aligned}}}$

Pokud tedy ano . ${\ Displaystyle A^{j_ {1}} = A^{j_ {2}}}$${\ Displaystyle F (\ dots, A^{j_ {1}}, \ dots, A^{j_ {2}}, \ dots) = 0}$

Nakonec : ${\ displaystyle F (I) = 1}$

${\ Displaystyle {\ begin {aligned} F (I) & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1}^{n} I_ {\ sigma (i)}^{i} = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ prod _ {i = 1}^{n} \ operatorname {\ delta} _ {i, \ sigma (i)} \\ & = \ sum _ {\ sigma \ in S_ {n}} \ operatorname {sgn} (\ sigma) \ operatorname {\ delta} _ {\ sigma, \ operatorname {id} _ {\ {1 \ ldots n \}}} = \ operatorname {sgn} (\ operatorname {id} _ {\ {1 \ ldots n \}}) = 1 \ end {aligned}}}$

Jediné střídající se víceřádkové funkce s jsou tedy omezeny na funkci definovanou Leibnizovým vzorcem a ve skutečnosti má také tyto tři vlastnosti. Determinant lze tedy definovat jako jedinou funkci s těmito třemi vlastnostmi. ${\ displaystyle F (I) = 1}$${\ Displaystyle \ det: M_ {n} (\ mathbb {K}) \ rightarrow \ mathbb {K}}$

Viz také

• Matice
• Laplaceova expanze
• Cramerovo pravidlo

Reference

• "Determinant" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Trefethen, Lloyd N .; Bau, David (1. června 1997). Numerická lineární algebra . SIAM . ISBN 978-0898713619.