Fórmula de Leibniz para determinantes

Em á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 A for uma matriz n×n, onde a_i,j é a entrada na iésima ( $j$^a) linha e jésima coluna de A, a fórmula é

$\det (A)=\sum _{\tau \in S_n}\mathrm{sgn}(\tau )\prod _{i=1}^n{a}_{i,\tau (i)}=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{\sigma (i),i},$

onde sgn é a função de sinal de permutações no grupo de permutação S_n, que retorna +1 e -1 para permutações pares e ímpares, respectivamente.

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

$\det (A)={ϵ}_{i_1\cdots i_n}{a}_{1i_1}\cdots a_{n{i}_n},$

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

Avaliando diretamente a fórmula de Leibniz a partir da definição requer $\mathrm{\Omega }(n!\cdot n)$ operações em geral — isto é, várias operações assintoticamente proporcionais an fatorial - porque n! é o número de permutações de ordem n. Isso é impraticavelmente difícil para n grande. Em vez disso, o determinante pode ser avaliado em O(n³) operações formando a decomposição LU $A=LU$ (normalmente por meio de eliminação de Gauss ou métodos semelhantes), caso em que $\det A=(\det L)(\det U)$ e os determinantes das matrizes triangulares L e Usão simplesmente produtos de suas entradas diagonais. (Em aplicações práticas de álgebra linear numérica, no entanto, o cálculo explícito do determinante raramente é necessário.) Veja, por exemplo, Trefethen, Bau (1997).

Declaração formal e prova

Teorema

Existe exatamente uma função

$F:M_n(𝕂)\to 𝕂$

que é multilinear alternado em relação às colunas e de modo que $F(I)=1$.

Prova

Singularidade: Deixe $F$ ser essa função, e deixe $A=(a_i^j{)}_{i=1,\dots ,n}^{j=1,\dots ,n}$ seja uma matriz $n\times n$. Chame $A^j$ a coluna $j$^a de $A$, ou seja $A^j=(a_i^j{)}_{i=1,\dots ,n}$, a fim de que $A=(A^1,\dots ,A^n).$

Além disso, deixe $E^k$ denotar o vetor coluna $k$^a da matriz identidade.

Agora se escreve cada um dos $A^j$(s) em termos de $E^k$, ou seja

$A^j=\sum _{k=1}^n{a}_k^j{E}^k$.

Como $F$ é multilinear, um tem

$\begin{array}{cc}F(A)& =F(\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})\\ & =\sum _{k_1,\dots ,k_n=1}^n\left(\prod _{i=1}^n{a}_{k_i}^i\right)F(E^{k_1},\dots ,E^{k_n}).\end{array}$

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:

$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 $E$ pode ser trocado até se tornar a identidade. A função de signal $\mathrm{sgn}(\sigma )$ é definido para contar o número de trocas necessárias e levar em conta a mudança de sinal resultante. Finalmente consegue-se:

$\begin{array}{cc}F(A)& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\left(\prod _{i=1}^n{a}_{\sigma (i)}^i\right)F(I)\\ & =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{\sigma (i)}^i\end{array}$

pois $F(I)$ deve ser igual a $1$.

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

Existência

Mostramos agora que $F$, onde F é a função definida pela fórmula de Leibniz, possui essas três propriedades.

• Multilinear:

$\begin{array}{cc}F(A^1,\dots ,c{A}^j,\dots )& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )c{a}_{\sigma (j)}^j\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\\ & =c\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )a_{\sigma (j)}^j\prod _{i=1,i\ne 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}\mathrm{sgn}(\sigma )(b_{\sigma (j)}+a_{\sigma (j)}^j)\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\\ & =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )(\left(b_{\sigma (j)}\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\right)+\left(a_{\sigma (j)}^j\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\right))\\ & =(\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )b_{\sigma (j)}\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i)+(\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{\sigma (i)}^i)\\ & =F(A^1,\dots ,b,\dots )+F(A^1,\dots ,A^j,\dots )\\ \\ \end{array}$

• Alternando:

$\begin{array}{cc}F(\dots ,A^{j_1},\dots ,A^{j_2},\dots )& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}\\ \end{array}$

Para qualquer $\sigma \in S_n$ deixe ${\sigma }^{\prime }$ seja a tupla igual a $\sigma$ com os índices $j_1$ e $j_2$ trocados.

$\begin{array}{cc}F(A)& =\sum _{\sigma \in S_n,\sigma (j_1)<\sigma (j_2)}[\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}+\mathrm{sgn}({\sigma }^{\prime })\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{{\sigma }^{\prime }(i)}^i\right)a_{{\sigma }^{\prime }(j_1)}^{j_1}{a}_{{\sigma }^{\prime }(j_2)}^{j_2}]\\ & =\sum _{\sigma \in S_n,\sigma (j_1)<\sigma (j_2)}[\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}-\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_2)}^{j_1}{a}_{\sigma (j_1)}^{j_2}]\\ & =\sum _{\sigma \in S_n,\sigma (j_1)<\sigma (j_2)}\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)(a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}-a_{\sigma (j_1)}^{j_2}{a}_{\sigma (j_2)}^{j_{{}_1}})\\ \\ \end{array}$

Assim se $A^{j_1}=A^{j_2}$ então $F(\dots ,A^{j_1},\dots ,A^{j_2},\dots )=0$.

Finalmente, $F(I)=1$:

$\begin{array}{cc}F(I)& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{I}_{\sigma (i)}^i=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{\mathrm{\delta }}_{i,\sigma (i)}\\ & =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma ){\mathrm{\delta }}_{\sigma ,{\mathrm{id}}_{\{1\dots n\}}}=\mathrm{sgn}({\mathrm{id}}_{\{1\dots n\}})=1\end{array}$

Assim, as únicas funções multilineares alternadas com $F(I)=1$ estão restritas à função definida pela fórmula de Leibniz e, na verdade, também possuem essas três propriedades. Portanto, o determinante pode ser definido como a única função

$\det :M_n(𝕂)\to 𝕂$

com essas três propriedades.