Fòrmula de Leibniz per al càlcul de determinants

En àlgebra llineal, la fòrmula de Leibniz expressa el determinant d'una matriu quadrada en térmens de permutació dels elements de la matriu. La fòrmula deu el seu nom a Gottfried Leibniz, la fòrmula per a una matriu d'orde $n \times n$ és:

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

a on

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

i a on sgn és la funció signe de permutació en el grup de permutació S_n, que torna +1 si la permutació és parell i −1 si és impar.

Una atra notació comuna usada per a la fòrmula utilisa símbols de Levi-Civita i la notació d'Einstein, quedant:

\det (A) = ϵ^{i_{1} \dots i_{n}} a_{1 i_{1}} \dots a_{n i_{n}},

que pot ser més familiar per als físics.

Evaluar directament la fòrmula de Leibniz requerix $Ω (n! \cdot n)$ operacions en general. Açò és, necessita un número d'operacions asintóticamente proporcional a n factorial, ya que n! és el número de permutació d'orde n, lo que resulta aparatoso per a valors grans de n. En el seu lloc, el determinant es pot evaluar en O(n³) operacions per mig de la descomposició LU de la matriu ( $A = L U$ , normalment a través de l'eliminació gaussiana o métodos similars). En eixe cas, $\det A = (\det L) (\det U)$ , i els determinants de les matrius triangulars L i O seran els productes de les entrades de les seues respectives diagonals principals. En la pràctica d'àlgebra llineal, no obstant, rara volta es requerix el càlcul explícit del determinant. Vore, per eixemple, Trefethen i Bau (1997).

Declaració formal i prova

Teorema. Existix exactament una funció multilineal alternada:

F : 𝔐_{n} (𝕂) \to 𝕂

tal que $F (I) = 1$ .

Prova.

Existència: La funció $F = \det$ , definida per la fòrmula de Leibniz, deu complir estes tres propietats:

Multilinealidad (açò és, conserva la suma i el producte per escalar en cada component):

\begin{matrix} F (A^{1}, \dots, c A^{j}, \dots) & = \sum_{σ \in S_{n}} sgn (σ) c a_{σ (j)}^{j} \prod_{i = 1, i \neq j}^{n} a_{σ (i)}^{i} \\ = c \sum_{σ \in S_{n}} sgn (σ) a_{σ (j)}^{j} \prod_{i = 1, i \neq j}^{n} a_{σ (i)}^{i} \\ = c F (A^{1}, \dots, A^{j}, \dots) \end{matrix}

.

\begin{matrix} F (A^{1}, \dots, b + A^{j}, \dots) & = \sum_{σ \in S_{n}} sgn (σ) (b_{σ (j)} + a_{σ (j)}^{j}) \prod_{i = 1, i \neq j}^{n} a_{σ (i)}^{i} \\ = \sum_{σ \in S_{n}} sgn (σ) ((b_{σ (j)} \prod_{i = 1, i \neq j}^{n} a_{σ (i)}^{i}) + (a_{σ (j)}^{j} \prod_{i = 1, i \neq j}^{n} a_{σ (i)}^{i})) \\ = (\sum_{σ \in S_{n}} sgn (σ) b_{σ (j)} \prod_{i = 1, i \neq j}^{n} a_{σ (i)}^{i}) + (\sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} a_{σ (i)}^{i}) \\ = F (A^{1}, \dots, b, \dots) + F (A^{1}, \dots, A^{j}, \dots) \end{matrix}

.

Funció alternada (o siga, que si dos components són iguals, la funció s'anula).

\begin{matrix} F (\dots, A^{j_{1}}, \dots, A^{j_{2}}, \dots) & = \sum_{σ \in S_{n}} sgn (σ) (\prod_{i = 1, i \neq j_{1}, i \neq j_{2}}^{n} a_{σ (i)}^{i}) a_{σ (j_{1})}^{j_{1}} a_{σ (j_{2})}^{j_{2}} \end{matrix}

.

Per a qualsevol

σ \in S_{n}

, siga

σ^{'}

la permutació igual a

σ

llevat perque intercanvia les imàgens de

j_{1}

i

j_{2}

.

\begin{matrix} F (A) & = \sum_{σ \in S_{n}, σ (j_{1}) < σ (j_{2})} [sgn (σ) (\prod_{i = 1, i \neq j_{1}, i \neq j_{2}}^{n} a_{σ (i)}^{i}) a_{σ (j_{1})}^{j_{1}} a_{σ (j_{2})}^{j_{2}} + sgn (σ^{'}) (\prod_{i = 1, i \neq j_{1}, i \neq j_{2}}^{n} a_{σ^{'} (i)}^{i}) a_{σ^{'} (j_{1})}^{j_{1}} a_{σ^{'} (j_{2})}^{j_{2}}] \\ = \sum_{σ \in S_{n}, σ (j_{1}) < σ (j_{2})} [sgn (σ) (\prod_{i = 1, i \neq j_{1}, i \neq j_{2}}^{n} a_{σ (i)}^{i}) a_{σ (j_{1})}^{j_{1}} a_{σ (j_{2})}^{j_{2}} - sgn (σ) (\prod_{i = 1, i \neq j_{1}, i \neq j_{2}}^{n} a_{σ (i)}^{i}) a_{σ (j_{2})}^{j_{1}} a_{σ (j_{1})}^{j_{2}}] \\ = \sum_{σ \in S_{n}, σ (j_{1}) < σ (j_{2})} sgn (σ) (\prod_{i = 1, i \neq j_{1}, i \neq j_{2}}^{n} a_{σ (i)}^{i}) (a_{σ (j_{1})}^{j_{1}} a_{σ (j_{2})}^{j_{2}} - a_{σ (j_{1})}^{j_{2}} a_{σ (j_{2})}^{j_{_{1}}}) \end{matrix}

Per lo tant, si

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

llavors

F (\dots, A^{j_{1}}, \dots, A^{j_{2}}, \dots) = 0

.

Finalment, $F (I) = 1$ :

\begin{matrix} F (I) & = \sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} I_{σ (i)}^{i} \\ = \sum_{σ = (1, 2, \dots, n)} \prod_{i = 1}^{n} I_{i}^{i} \\ = 1 \end{matrix}

.

Singularitat: Siga $F$ una funció d'eixe tipo, i siga $A = (a_{i}^{j})_{i = 1, \dots, n}^{j = 1, \dots, n}$ una matriu $n \times n$ . Cride's $A^{j}$ a la $j$ -ésima columna de $A$ , i.i. $A^{j} = (a_{i}^{j})_{i = 1, \dots, n}$ de modo que $A = (A^{1}, \dots, A^{n}) .$

També, siga $E^{k}$ la $k$ -ésima columna de la matriu d'identitat, en forma de vector.

Ara s'escriu cada u dels vectores $A^{j}$ en térmens dels vectores $E^{k}$ , per eixemple:

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

.

Com $F$ és multilineal, es té

\begin{matrix} 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} (\prod_{i = 1}^{n} a_{k_{i}}^{i}) F (E^{k_{1}}, \dots, E^{k_{n}}) . \end{matrix}

Ara be, com $F$ és alternada, qualsevol combinació en índexs repetits és zero; per lo que el sumatorio pot reduir-se a les tuplas en índexs no repetits, és dir, a únicament les permutació:

F (A) = \sum_{σ \in S_{n}} (\prod_{i = 1}^{n} a_{σ (i)}^{i}) F (E^{σ (1)}, \dots, E^{σ (n)}),

a on $S_{n}$ és el grup simètric dels primers n sancers (és dir, el conjunt de totes les permutació dels primers n sancers). Com la funció $F$ és alternada, l'orde dels vectores $E^{1}, \dots, E^{n}$ només afecta per al signe del resultat, de manera que es pot extraure la permutació per la funció signe. Com $F (I) = 1$ :

\begin{matrix} F (A) & = \sum_{σ \in S_{n}} sgn (σ) (\prod_{i = 1}^{n} a_{σ (i)}^{i}) F (I) \\ = \sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} a_{σ (i)}^{i}, \end{matrix}

que és precisament la funció definida per la fòrmula de Leibniz.

Vore també

Matriu.
Regla de Sarrus.
Teorema de Laplace per al càlcul de determinants.
Regla de Cramer.

Referències

Lloyd N. Trefethen i David Bau, Numerical Linear Algebra (SIAM, 1997) ISBN 978-0898713619

Este artícul conté una traducció derivada de «Fórmula de Leibniz para el cálculo de determinantes» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.