Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Leibniz formula for determinants
Résumé
In algebra, the Leibniz formula, named in honor of Gottfried Leibniz, expresses the determinant of a square matrix in terms of permutations of the matrix elements. If is an matrix, where is the entry in the -th row and -th column of , the formula is
where is the sign function of permutations in the permutation group , which returns and for even and odd permutations, respectively.
Another common notation used for the formula is in terms of the Levi-Civita symbol and makes use of the Einstein summation notation, where it becomes
which may be more familiar to physicists.
Directly evaluating the Leibniz formula from the definition requires operations in general—that is, a number of operations asymptotically proportional to factorial—because is the number of order- permutations. This is impractically difficult for even relatively small . Instead, the determinant can be evaluated in operations by forming the LU decomposition (typically via Gaussian elimination or similar methods), in which case and the determinants of the triangular matrices and are simply the products of their diagonal entries. (In practical applications of numerical linear algebra, however, explicit computation of the determinant is rarely required.) See, for example, . The determinant can also be evaluated in fewer than operations by reducing the problem to matrix multiplication, but most such algorithms are not practical.
Theorem.
There exists exactly one function which is alternating multilinear w.r.t. columns and such that .
Proof.
Uniqueness: Let be such a function, and let be an matrix. Call the -th column of , i.e. , so that
Also, let denote the -th column vector of the identity matrix.
Now one writes each of the 's in terms of the , i.e.
As is multilinear, one has
From alternation it follows that any term with repeated indices is zero. The sum can therefore be restricted to tuples with non-repeating indices, i.e. permutations:
Because F is alternating, the columns can be swapped until it becomes the identity.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.