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.