Leibniz formula for determinants
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 A is an n×n matrix, where ai,j is the entry in the ith row and jth column of A, the formula is
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 n factorial—because n! is the number of order-n permutations. This is impractically difficult for large n. Instead, the determinant can be evaluated in O(n3) operations by forming the LU decomposition (typically via Gaussian elimination or similar methods), in which case and the determinants of the triangular matrices L and U 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, Trefethen & Bau (1997).
Formal statement and proof
Theorem. There exists exactly one function
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. The sign function is defined to count the number of swaps necessary and account for the resulting sign change. One finally gets:
as is required to be equal to .
Therefore no function besides the function defined by the Leibniz Formula is a multilinear alternating function with .
Existence: We now show that F, where F is the function defined by the Leibniz formula, has these three properties.
For any let be the tuple equal to with the and indices switched.
Thus if then .
Thus the only functions which are multilinear alternating with are restricted to the function defined by the Leibniz formula, and it in fact also has these three properties. Hence the determinant can be defined as the only function
with these three properties.