Fórmula de Leibniz para determinantes - Leibniz formula for determinants

Na álgebra , a fórmula de Leibniz , batizada em homenagem a Gottfried Leibniz , expressa o determinante de uma matriz quadrada em termos de permutações dos elementos da matriz. Se for uma matriz, onde é a entrada na -ésima linha e -ésima coluna de , a fórmula é ${\ 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), \, eu},}$

onde é a função de sinal de permutações no grupo de permutações , que retorna e para permutações pares e ímpares , respectivamente. ${\ displaystyle \ operatorname {sgn}}$ ${\ displaystyle S_ {n}}$${\ displaystyle +1}$${\ displaystyle -1}$

Outra notação comum usada para a fórmula é em termos do símbolo Levi-Civita e faz uso da notação de soma de Einstein , onde se torna

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

o que pode ser mais familiar para os físicos.

Avaliar diretamente a fórmula de Leibniz a partir da definição requer operações em geral - isto é, um número de operações assintoticamente proporcional ao fatorial - porque é o número de permutações de ordens . Isso é impraticavelmente difícil, mesmo para os relativamente pequenos . Em vez disso, o determinante pode ser avaliada em operações formando a decomposição LU (tipicamente através de eliminação de Gauss ou métodos semelhantes), caso em que e os determinantes das matrizes triangulares e são simplesmente os produtos de seus elementos da diagonal. (Em aplicações práticas de álgebra linear numérica, entretanto, o cálculo explícito do determinante raramente é necessário.) Ver, por exemplo, Trefethen & Bau (1997) . O determinante também pode ser avaliado em menos de operações, reduzindo o problema à multiplicação de matrizes , mas a maioria desses algoritmos não é prática. ${\ 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})}$

Declaração formal e prova

Teorema. Existe exatamente uma função que é alternar colunas multilineares e tal . ${\ displaystyle F: M_ {n} (\ mathbb {K}) \ rightarrow \ mathbb {K}}$ ${\ displaystyle F (I) = 1}$

Prova.

Singularidade: Seja tal função e seja uma matriz. Chame a -ésima coluna de , ou seja , para que${\ displaystyle F}$${\ displaystyle A = (a_ {i} ^ {j}) _ {i = 1, \ dots, n} ^ {j = 1, \ dots, n}}$${\ displaystyle n \ times n}$${\ displaystyle A ^ {j}}$${\ displaystyle j}$${\ displaystyle A}$${\ displaystyle A ^ {j} = (a_ {i} ^ {j}) _ {i = 1, \ dots, n}}$${\ displaystyle A = \ left (A ^ {1}, \ dots, A ^ {n} \ right).}$

Além disso, vamos denotar o -ésimo vetor coluna da matriz identidade. ${\ displaystyle E ^ {k}}$${\ displaystyle k}$

Agora, cada um escreve cada um dos em termos de , ou seja, ${\ displaystyle A ^ {j}}$${\ displaystyle E ^ {k}}$

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

Como é multilinear, um tem ${\ displaystyle F}$

${\ displaystyle {\ begin {alinhados} F (A) & = F \ left (\ sum _ {k_ {1} = 1} ^ {n} a_ {k_ {1}} ^ {1} E ^ {k_ { 1}}, \ dots, \ sum _ {k_ {n} = 1} ^ {n} a_ {k_ {n}} ^ {n} E ^ {k_ {n}} \ right) = \ sum _ {k_ {1}, \ dots, k_ {n} = 1} ^ {n} \ left (\ prod _ {i = 1} ^ {n} a_ {k_ {i}} ^ {i} \ right) F \ left (E ^ {k_ {1}}, \ pontos, E ^ {k_ {n}} \ direita). \ End {alinhado}}}$

Da alternância, segue-se que qualquer termo com índices repetidos é zero. A soma pode, portanto, ser restrita a tuplas com índices não repetitivos, ou seja, permutações:

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

Como F está alternando, as colunas podem ser trocadas até que se torne a identidade. A função de sinal é definida para contar o número de trocas necessárias e levar em conta a mudança de sinal resultante. Finalmente consegue-se: ${\ displaystyle E}$ ${\ displaystyle \ operatorname {sgn} (\ sigma)}$

${\ displaystyle {\ begin {alinhados} 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 {alinhado}}}$

como é necessário para ser igual a . ${\ displaystyle F (I)}$${\ displaystyle 1}$

Portanto, nenhuma função além da função definida pela Fórmula de Leibniz pode ser uma função alternada multilinear com . ${\ displaystyle F \ left (I \ right) = 1}$

Existência: agora mostramos que F, onde F é a função definida pela fórmula de Leibniz, tem essas três propriedades.

Multilinear :

${\ displaystyle {\ begin {alinhados} 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 \ soma _ {\ sigma \ in 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}, \ dots) & = \ sum _ {\ sigma \ in 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}, \ pontos, b, \ pontos) + F (A ^ {1}, \ pontos, A ^ {j}, \ pontos) \\\\\ fim {alinhado}}}$

Alternando :

${\ displaystyle {\ begin {alinhados} 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 {alinhado }}}$

Para qualquer Vamos ser os tupla igual a com o e índices comutada. ${\ displaystyle \ sigma \ in S_ {n}}$${\ displaystyle \ sigma '}$${\ displaystyle \ sigma}$${\ displaystyle j_ {1}}$${\ displaystyle j_ {2}}$

${\ displaystyle {\ begin {alinhados} F (A) & = \ sum _ {\ sigma \ in 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_ {1})} ^ {j_ {1}} a _ {\ sigma' (j_ {2})} ^ {j_ {2}} \ direito] \\ & = \ sum _ {\ sigma \ em 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 \ in 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 {alinhado}}}$

Portanto, se então . ${\ displaystyle A ^ {j_ {1}} = A ^ {j_ {2}}}$${\ displaystyle F (\ dots, A ^ {j_ {1}}, \ dots, A ^ {j_ {2}}, \ dots) = 0}$

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

${\ displaystyle {\ begin {alinhados} 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 {alinhado}}}$

Assim, as únicas funções multilineares alternadas com são restritas à função definida pela fórmula de Leibniz e, de fato, também possui essas três propriedades. Portanto, o determinante pode ser definido como a única função com essas três propriedades. ${\ displaystyle F (I) = 1}$${\ displaystyle \ det: M_ {n} (\ mathbb {K}) \ rightarrow \ mathbb {K}}$

Veja também

• Matriz
• Expansão Laplace
• Regra de Cramer

Referências

• "Determinant" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Trefethen, Lloyd N .; Bau, David (1 de junho de 1997). Álgebra Linear Numérica . SIAM . ISBN 978-0898713619.