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
det ( A ) = ∑ σ ∈ S n sgn ( σ ) ∏ i = 1 n a σ ( i ) , i , where sgn is the sign function of permutations in the permutation group Sn, which returns +1 and −1 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
det ( A ) = ϵ i 1 ⋯ i n a 1 i 1 ⋯ a n i n , which may be more familiar to physicists.
Directly evaluating the Leibniz formula from the definition requires Ω ( n ! ⋅ n ) 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 A = L U (typically via Gaussian elimination or similar methods), in which case det A = ( det L ) ( det U ) 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).
Theorem. There exists exactly one function
F : M n ( K ) → K which is alternating multilinear w.r.t. columns and such that F ( I ) = 1 .
Proof.
Uniqueness: Let F be such a function, and let A = ( a i j ) i = 1 , … , n j = 1 , … , n be an n × n matrix. Call A j the j -th column of A , i.e. A j = ( a i j ) i = 1 , … , n , so that A = ( A 1 , … , A n ) .
Also, let E k denote the k -th column vector of the identity matrix.
Now one writes each of the A j 's in terms of the E k , i.e.
A j = ∑ k = 1 n a k j E k .
As F is multilinear, one has
F ( A ) = F ( ∑ k 1 = 1 n a k 1 1 E k 1 , … , ∑ k n = 1 n a k n n E k n ) = ∑ k 1 , … , k n = 1 n ( ∏ i = 1 n a k i i ) F ( E k 1 , … , E k n ) . 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:
F ( A ) = ∑ σ ∈ S n ( ∏ i = 1 n a σ ( i ) i ) F ( E σ ( 1 ) , … , E σ ( n ) ) . Because F is alternating, the columns E can be swapped until it becomes the identity. The sign function sgn ( σ ) is defined to count the number of swaps necessary and account for the resulting sign change. One finally gets:
F ( A ) = ∑ σ ∈ S n sgn ( σ ) ( ∏ i = 1 n a σ ( i ) i ) F ( I ) = ∑ σ ∈ S n sgn ( σ ) ∏ i = 1 n a σ ( i ) i as F ( I ) is required to be equal to 1 .
Therefore no function besides the function defined by the Leibniz Formula is a multilinear alternating function with F ( I ) = 1 .
Existence: We now show that F, where F is the function defined by the Leibniz formula, has these three properties.
Multilinear:
F ( A 1 , … , c A j , … ) = ∑ σ ∈ S n sgn ( σ ) c a σ ( j ) j ∏ i = 1 , i ≠ j n a σ ( i ) i = c ∑ σ ∈ S n sgn ( σ ) a σ ( j ) j ∏ i = 1 , i ≠ j n a σ ( i ) i = c F ( A 1 , … , A j , … ) F ( A 1 , … , b + A j , … ) = ∑ σ ∈ S n sgn ( σ ) ( b σ ( j ) + a σ ( j ) j ) ∏ i = 1 , i ≠ j n a σ ( i ) i = ∑ σ ∈ S n sgn ( σ ) ( ( b σ ( j ) ∏ i = 1 , i ≠ j n a σ ( i ) i ) + ( a σ ( j ) j ∏ i = 1 , i ≠ j n a σ ( i ) i ) ) = ( ∑ σ ∈ S n sgn ( σ ) b σ ( j ) ∏ i = 1 , i ≠ j n a σ ( i ) i ) + ( ∑ σ ∈ S n sgn ( σ ) ∏ i = 1 n a σ ( i ) i ) = F ( A 1 , … , b , … ) + F ( A 1 , … , A j , … ) Alternating:
F ( … , A j 1 , … , A j 2 , … ) = ∑ σ ∈ S n sgn ( σ ) ( ∏ i = 1 , i ≠ j 1 , i ≠ j 2 n a σ ( i ) i ) a σ ( j 1 ) j 1 a σ ( j 2 ) j 2 For any σ ∈ S n let σ ′ be the tuple equal to σ with the j 1 and j 2 indices switched.
F ( A ) = ∑ σ ∈ S n , σ ( j 1 ) < σ ( j 2 ) [ sgn ( σ ) ( ∏ i = 1 , i ≠ j 1 , i ≠ j 2 n a σ ( i ) i ) a σ ( j 1 ) j 1 a σ ( j 2 ) j 2 + sgn ( σ ′ ) ( ∏ i = 1 , i ≠ j 1 , i ≠ j 2 n a σ ′ ( i ) i ) a σ ′ ( j 1 ) j 1 a σ ′ ( j 2 ) j 2 ] = ∑ σ ∈ S n , σ ( j 1 ) < σ ( j 2 ) [ sgn ( σ ) ( ∏ i = 1 , i ≠ j 1 , i ≠ j 2 n a σ ( i ) i ) a σ ( j 1 ) j 1 a σ ( j 2 ) j 2 − sgn ( σ ) ( ∏ i = 1 , i ≠ j 1 , i ≠ j 2 n a σ ( i ) i ) a σ ( j 2 ) j 1 a σ ( j 1 ) j 2 ] = ∑ σ ∈ S n , σ ( j 1 ) < σ ( j 2 ) sgn ( σ ) ( ∏ i = 1 , i ≠ j 1 , i ≠ 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 ) Thus if A j 1 = A j 2 then F ( … , A j 1 , … , A j 2 , … ) = 0 .
Finally, F ( I ) = 1 :
F ( I ) = ∑ σ ∈ S n sgn ( σ ) ∏ i = 1 n I σ ( i ) i = sgn ( σ ) ∏ i = 1 n I σ ( i ) i where σ = { 1 , 2 , … , n } . For other choices of σ , I σ ( i ) i = 0. = ∏ i = 1 n I i i = 1 Thus the only alternating multilinear functions with F ( I ) = 1 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
det : M n ( K ) → K with these three properties.
