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

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En álgebra, la fórmula de Leibniz expresa el determinante de una Matriz cuadrada

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

En términos de permutaciones de los elementos de la matriz. Nombrado en honor de Gottfried Leibniz, la fórmula es:

\det(A) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i), i}

Para una matriz n×n, donde sgn es la Función signo de Permutaciones en el grupo de la permutación Sn que devuelve +1 y -1 para permutaciones pares e impares, respectivamente.

Otra notación común usada para la fórmula es en términos del símbolo de Levi-Civita y hace uso de la notación de Einstein, donde se convierte:

\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 Leibniz de la definicion requiere \Omega(n! \cdot n) operaciones en general —es decir un número de operaciones asintóticamente proporcionales a n factorial— porque n! es el número n de ordenes de permutaciones. Esto es prácticamente difícil para grandes n. En su lugar, el determinante se puede evaluar en O(n)3 operaciones mediante la formación de la Descomposición LU] A = LU (normalmente a través de la Eliminación gaussiana o métodos similares), en cuyo caso \det A = (\det L) (\det U) y los determinantes de las matrices triangulares L y U son simplemente los productos de sus entradas diagonales. (En los usos prácticos de álgebra lineal, sin embargo, raras vez requieren el cálculo explícito del determinante). Ver, por ejemplo, Trefethen y Bau (1997).

Declaración formal y prueba[editar]

Teorema. existe exactamenta una función:

 F : \mathfrak M_n (\mathbb K) \rightarrow \mathbb K

que es alterna multilineal columnas w.r.t. y de tal manera que F(I) = 1.

Prueba.

Singularidad: dejar a la F ser una función de este tipo, y dejar A = (a_i^j)_{i = 1, \dots, n}^{j = 1, \dots , n} ser una n \times n matriz. Llame A^j la j-la 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, deje que E^k denote la k columna-vector de la matriz de identidad.

Ahora se escribe cada uno de los A^j's en términos de la E^k, por ejemplo:

A^j = \sum_{k = 1}^n a_k^j E^k.

Como F es multilineal, uno tiene


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

A partir de la alternativa se sigue que cualquier plazo con índices repetidos es cero. Por consiguiente, la suma puede ser restringido a las tuplas con índices que no se repiten, es decir, 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)}).

Debido a que F es alterna, las columnas E pueden ser cambiadas hasta que se convierte en la identidad. La [[también permutaciones impares|Función signo]] se define para contar el número de intercambios necesarios y cuenta para el cambio de signo resultante. Uno finalmente obtiene:


\begin{align}
F(A)& = \sum_{\sigma \in S_n} \sgn(\sigma) \left(\prod_{i = 1}^n a_{\sigma(i)}^i\right) F(I)\\
& = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i
\end{align}

Como F(I) se requiere para ser igual a 1.

Por lo tanto ninguna función además de la función definida por la fórmula Leibniz es una función de alternación multilineal F\left(I\right)=1.

Existencia: Vamos a demostrar que F, dond F es la función definida por la fórmula de Leibniz, tiene estas tres propiedades.

Multilineal


\begin{align}
F(A^1, \dots, cA^j, \dots) & = \sum_{\sigma \in S_n} \sgn(\sigma) ca_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
& = c \sum_{\sigma \in S_n} \sgn(\sigma) a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
&=c F(A^1, \dots, A^j, \dots)\\
\\
F(A^1, \dots, b+A^j, \dots) & = \sum_{\sigma \in S_n} \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} \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} \sgn(\sigma) b_{\sigma(j)}\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right) 
  + \left(\sum_{\sigma \in S_n} \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{align}

Alterna:


\begin{align}
F(\dots, A^{j_1}, \dots, A^{j_2}, \dots)
& = \sum_{\sigma \in S_n} \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{align}

Para cualquier \sigma \in S_n permite \sigma' ser igual a la tupla \sigma con el j_1 j_2 los índices cambiaron.


\begin{align}
F(A) & = \sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\left[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}+\sgn(\sigma')\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\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[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}-\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\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})}\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\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{align}

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{align}\\
F(I) & = \sum_{\sigma \in S_n} \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{align}

Así, las únicas funciones que son multilineal que alternan con F(I)=1 se restringen a la función definida por la fórmula Leibniz, y que de hecho, también tiene estas tres propiedades. Por lo tanto el determinante se puede definir como la única función:

 \det : \mathfrak M_n (\mathbb K) \rightarrow \mathbb K

con estas tres propiedades.

Véase también[editar]

Referencias[editar]