Fórmula de Leibniz para el cálculo de determinantes

En álgebra lineal, la fórmula de Leibniz expresa el determinante de una matriz cuadrada en términos de permutaciones de los elementos de la matriz. La fórmula debe su nombre a Gottfried Leibniz, la fórmula para una matriz de orden $n\times n$ es:

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

donde

A=(a_{ij})_{i,j=1,\dots ,n}

y donde sgn es la función signo de permutaciones en el grupo de permutación S_n, que devuelve +1 si la permutación es par y −1 si es impar.

Otra notación común usada para la fórmula utiliza símbolos de Levi-Civita y la notación de Einstein, quedando:

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

que puede ser más familiar para los físicos.

Evaluar directamente la fórmula de Leibniz requiere $\Omega (n!\cdot n)$ operaciones en general. Esto es, necesita un número de operaciones asintóticamente proporcional a n factorial, ya que n! es el número de permutaciones de orden n, lo que resulta aparatoso para valores grandes de n. En su lugar, el determinante se puede evaluar en O(n³) operaciones mediante la descomposición LU de la matriz ( $A=LU$ , normalmente a través de la eliminación gaussiana o métodos similares). En ese caso, $\det A=(\det L)(\det U)$ , y los determinantes de las matrices triangulares L y U serán los productos de las entradas de sus respectivas diagonales principales. En la práctica de álgebra lineal, sin embargo, rara vez se requiere el cálculo explícito del determinante. Ver, por ejemplo, Trefethen y Bau (1997).

Declaración formal y prueba

Teorema. Existe exactamente una función multilineal alternada:

F:{\mathfrak {M}}_{n}(\mathbb {K} )\rightarrow \mathbb {K}

tal que $F(I)=1$ .

Prueba.

Existencia: La función $F=\det$ , definida por la fórmula de Leibniz, debe cumplir estas tres propiedades:

Multilinealidad (esto es, conserva la suma y el producto por escalar en cada componente):

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

.

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

.

Función alternada (o sea, que si dos componentes son iguales, la función se anula).

{\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 cualquier

\sigma \in S_{n}

, sea

\sigma '

la permutación igual a

\sigma

salvo porque intercambia las imágenes de

j_{1}

y

j_{2}

.

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

Por lo tanto, si

A^{j_{1}}=A^{j_{2}}

entonces

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 =(1,2,\dots ,n)}\prod _{i=1}^{n}I_{i}^{i}\\&=1\end{aligned}}

.

Singularidad: Sea $F$ una función de ese tipo, y sea $A=(a_{i}^{j})_{i=1,\dots ,n}^{j=1,\dots ,n}$ una matriz $n\times n$ . Llámese $A^{j}$ a la $j$ -ésima columna de $A$ , i.e. $A^{j}=(a_{i}^{j})_{i=1,\dots ,n}$ de modo que $A=\left(A^{1},\dots ,A^{n}\right).$

También, sea $E^{k}$ la $k$ -ésima columna de la matriz de identidad, en forma de vector.

Ahora se escribe cada uno de los vectores $A^{j}$ en términos de los vectores $E^{k}$ , por ejemplo:

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

.

Como $F$ es multilineal, se tiene

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

Ahora bien, como $F$ es alternada, cualquier combinación con índices repetidos es cero; por lo que el sumatorio puede reducirse a las tuplas con índices no repetidos, es decir, a únicamente las permutaciones:

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)}),

donde $S_{n}$ es el grupo simétrico de los primeros n enteros (es decir, el conjunto de todas las permutaciones de los primeros n enteros). Como la función $F$ es alternada, el orden de los vectores ${E^{1},\dots ,E^{n}}$ sólo afecta para el signo del resultado, de forma que se puede extraer la permutación por la función signo. Como $F(I)=1$ :