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}}\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},$

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)=\epsilon _{i_{1}\cdots i_{n}}{a}_{1i_{1}}\cdots {a}_{ni_{n}},$

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

Avaliando diretamente a fórmula de Leibniz a partir da definição requer $\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}(\mathbb {K} )\rightarrow \mathbb {K}$

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=\left(A^{1},\dots ,A^{n}\right).$

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{aligned}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}},\dots ,E^{k_{n}}\right).\end{aligned}}$

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 $\operatorname {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{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{aligned}}$

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{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\sum _{\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},\dots ,b,\dots )+F(A^{1},\dots ,A^{j},\dots )\\\\\end{aligned}}$

• Alternando:

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

Para qualquer $\sigma \in S_{n}$ deixe $\sigma '$ seja a tupla igual a $\sigma$ com os índices $j_{1}$ e $j_{2}$ trocados.

${\begin{aligned}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}}\right]\\&=\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_{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)\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)\\\\\end{aligned}}$

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{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}}$

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}(\mathbb {K} )\rightarrow \mathbb {K}$

com essas três propriedades.