Leibniz formula for determinants – Wikipedia

Mathematics formula

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

${displaystyle A}$

is an

${displaystyle ntimes n}$

matrix, where

${displaystyle a_{ij}}$

is the entry in the

${displaystyle i}$

-th row and

${displaystyle j}$

-th column of

${displaystyle A}$

, the formula is

${displaystyle det(A)=sum _{tau in S_{n}}operatorname {sgn}(tau )prod _{i=1}^{n}a_{i,,tau (i)}=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i),,i}}$

where

${displaystyle operatorname {sgn} }$

is the sign function of permutations in the permutation group

${displaystyle S_{n}}$

, which returns

${displaystyle +1}$

and

${displaystyle -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

${displaystyle det(A)=epsilon _{i_{1}cdots i_{n}}{a}_{1i_{1}}cdots {a}_{ni_{n}},}$

which may be more familiar to physicists.

Directly evaluating the Leibniz formula from the definition requires

${displaystyle Omega (n!cdot n)}$

operations in general—that is, a number of operations asymptotically proportional to

${displaystyle n}$

factorial—because

${displaystyle n!}$

is the number of order-

${displaystyle n}$

permutations. This is impractically difficult for even relatively small

${displaystyle n}$

. Instead, the determinant can be evaluated in

${displaystyle O(n^{3})}$

operations by forming the LU decomposition

${displaystyle A=LU}$

(typically via Gaussian elimination or similar methods), in which case

${displaystyle det A=det Lcdot det U}$

and the determinants of the triangular matrices

${displaystyle L}$

and

${displaystyle 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). The determinant can also be evaluated in fewer than

${displaystyle O(n^{3})}$

operations by reducing the problem to matrix multiplication, but most such algorithms are not practical.

Formal statement and proof[edit]

Theorem.
There exists exactly one function

${displaystyle F:M_{n}(mathbb {K} )rightarrow mathbb {K} }$

which is alternating multilinear w.r.t. columns and such that

${displaystyle F(I)=1}$

.

Proof.

Uniqueness: Let

${displaystyle F}$

be such a function, and let

${displaystyle A=(a_{i}^{j})_{i=1,dots ,n}^{j=1,dots ,n}}$

be an

${displaystyle ntimes n}$

matrix. Call

${displaystyle A^{j}}$

the

${displaystyle j}$

-th column of

${displaystyle A}$

, i.e.

${displaystyle A^{j}=(a_{i}^{j})_{i=1,dots ,n}}$

, so that

${displaystyle A=left(A^{1},dots ,A^{n}right).}$

Also, let

${displaystyle E^{k}}$

denote the

${displaystyle k}$

-th column vector of the identity matrix.

Now one writes each of the

${displaystyle A^{j}}$

‘s in terms of the

${displaystyle E^{k}}$

, i.e.

${displaystyle A^{j}=sum _{k=1}^{n}a_{k}^{j}E^{k}}$

.

As

${displaystyle F}$

is multilinear, one has

${displaystyle {begin{aligned}F(A)&=Fleft(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}}right)=sum _{k_{1},dots ,k_{n}=1}^{n}left(prod _{i=1}^{n}a_{k_{i}}^{i}right)Fleft(E^{k_{1}},dots ,E^{k_{n}}right).end{aligned}}}$

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:

${displaystyle F(A)=sum _{sigma in S_{n}}left(prod _{i=1}^{n}a_{sigma (i)}^{i}right)F(E^{sigma (1)},dots ,E^{sigma (n)}).}$

Because F is alternating, the columns

${displaystyle E}$

can be swapped until it becomes the identity. The sign function

${displaystyle operatorname {sgn}(sigma )}$

is defined to count the number of swaps necessary and account for the resulting sign change. One finally gets:

${displaystyle {begin{aligned}F(A)&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(prod _{i=1}^{n}a_{sigma (i)}^{i}right)F(I)\&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i)}^{i}end{aligned}}}$

as

${displaystyle F(I)}$

is required to be equal to

${displaystyle 1}$

.

Therefore no function besides the function defined by the Leibniz Formula can be a multilinear alternating function with

${displaystyle Fleft(Iright)=1}$

.

Existence: We now show that F, where F is the function defined by the Leibniz formula, has these three properties.

Multilinear:

${displaystyle {begin{aligned}F(A^{1},dots ,cA^{j},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )ca_{sigma (j)}^{j}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}\&=csum _{sigma in S_{n}}operatorname {sgn}(sigma )a_{sigma (j)}^{j}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}\&=cF(A^{1},dots ,A^{j},dots )\\F(A^{1},dots ,b+A^{j},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(b_{sigma (j)}+a_{sigma (j)}^{j}right)prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}\&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(left(b_{sigma (j)}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}right)+left(a_{sigma (j)}^{j}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}right)right)\&=left(sum _{sigma in S_{n}}operatorname {sgn}(sigma )b_{sigma (j)}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}right)+left(sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i)}^{i}right)\&=F(A^{1},dots ,b,dots )+F(A^{1},dots ,A^{j},dots )\\end{aligned}}}$

Alternating:

${displaystyle {begin{aligned}F(dots ,A^{j_{1}},dots ,A^{j_{2}},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(prod _{i=1,ineq j_{1},ineq j_{2}}^{n}a_{sigma (i)}^{i}right)a_{sigma (j_{1})}^{j_{1}}a_{sigma (j_{2})}^{j_{2}}\end{aligned}}}$

For any

${displaystyle sigma in S_{n}}$

let

${displaystyle sigma ‘}$

be the tuple equal to

${displaystyle sigma }$

with the

${displaystyle j_{1}}$

and

${displaystyle j_{2}}$

indices switched.

${displaystyle {begin{aligned}F(A)&=sum _{sigma in S_{n},sigma (j_{1})$

Thus if

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

then

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

.

Finally,

${displaystyle F(I)=1}$

:

${displaystyle {begin{aligned}F(I)&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}I_{sigma (i)}^{i}=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}operatorname {delta } _{i,sigma (i)}\&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )operatorname {delta } _{sigma ,operatorname {id} _{{1ldots n}}}=operatorname {sgn}(operatorname {id} _{{1ldots n}})=1end{aligned}}}$

Thus the only alternating multilinear functions with

${displaystyle 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

${displaystyle det :M_{n}(mathbb {K} )rightarrow mathbb {K} }$

with these three properties.

See also[edit]

References[edit]