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

A{displaystyle A}

is an

n×n{displaystyle ntimes n}

matrix, where

aij{displaystyle a_{ij}}

is the entry in the

i{displaystyle i}

-th row and

j{displaystyle j}

-th column of

A{displaystyle A}

, the formula is

det(A)=∑τ∈Snsgn⁡(τ)∏i=1nai,τ(i)=∑σ∈Snsgn⁡(σ)∏i=1naσ(i),i{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

sgn{displaystyle operatorname {sgn} }

is the sign function of permutations in the permutation group

Sn{displaystyle S_{n}}

, which returns

+1{displaystyle +1}

and

−1{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

det(A)=ϵi1⋯ina1i1⋯anin,{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

Ω(n!⋅n){displaystyle Omega (n!cdot n)}

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

n{displaystyle n}

factorial—because

n!{displaystyle n!}

is the number of order-

n{displaystyle n}

permutations. This is impractically difficult for even relatively small

n{displaystyle n}

. Instead, the determinant can be evaluated in

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

operations by forming the LU decomposition

A=LU{displaystyle A=LU}

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

detA=detL⋅detU{displaystyle det A=det Lcdot det U}

and the determinants of the triangular matrices

L{displaystyle L}

and

U{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

O(n3){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

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

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

F(I)=1{displaystyle F(I)=1}

.

Proof.

Uniqueness: Let

F{displaystyle F}

be such a function, and let

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

be an

n×n{displaystyle ntimes n}

matrix. Call

Aj{displaystyle A^{j}}

the

j{displaystyle j}

-th column of

A{displaystyle A}

, i.e.

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

, so that

A=(A1,…,An).{displaystyle A=left(A^{1},dots ,A^{n}right).}

Also, let

Ek{displaystyle E^{k}}

denote the

k{displaystyle k}

-th column vector of the identity matrix.

Now one writes each of the

Aj{displaystyle A^{j}}

‘s in terms of the

Ek{displaystyle E^{k}}

, i.e.

Aj=∑k=1nakjEk{displaystyle A^{j}=sum _{k=1}^{n}a_{k}^{j}E^{k}}

.

As

F{displaystyle F}

is multilinear, one has

F(A)=F(∑k1=1nak11Ek1,…,∑kn=1naknnEkn)=∑k1,…,kn=1n(∏i=1nakii)F(Ek1,…,Ekn).{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:

F(A)=∑σ∈Sn(∏i=1naσ(i)i)F(Eσ(1),…,Eσ(n)).{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

E{displaystyle E}

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

sgn⁡(σ){displaystyle operatorname {sgn}(sigma )}

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

F(A)=∑σ∈Snsgn⁡(σ)(∏i=1naσ(i)i)F(I)=∑σ∈Snsgn⁡(σ)∏i=1naσ(i)i{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

F(I){displaystyle F(I)}

is required to be equal to

1{displaystyle 1}

.

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

F(I)=1{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:

F(A1,…,cAj,…)=∑σ∈Snsgn⁡(σ)caσ(j)j∏i=1,i≠jnaσ(i)i=c∑σ∈Snsgn⁡(σ)aσ(j)j∏i=1,i≠jnaσ(i)i=cF(A1,…,Aj,…)F(A1,…,b+Aj,…)=∑σ∈Snsgn⁡(σ)(bσ(j)+aσ(j)j)∏i=1,i≠jnaσ(i)i=∑σ∈Snsgn⁡(σ)((bσ(j)∏i=1,i≠jnaσ(i)i)+(aσ(j)j∏i=1,i≠jnaσ(i)i))=(∑σ∈Snsgn⁡(σ)bσ(j)∏i=1,i≠jnaσ(i)i)+(∑σ∈Snsgn⁡(σ)∏i=1naσ(i)i)=F(A1,…,b,…)+F(A1,…,Aj,…){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:

F(…,Aj1,…,Aj2,…)=∑σ∈Snsgn⁡(σ)(∏i=1,i≠j1,i≠j2naσ(i)i)aσ(j1)j1aσ(j2)j2{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

σ∈Sn{displaystyle sigma in S_{n}}

let

σ′{displaystyle sigma ‘}

be the tuple equal to

σ{displaystyle sigma }

with the

j1{displaystyle j_{1}}

and

j2{displaystyle j_{2}}

indices switched.

F(A)=∑σ∈Sn,σ(j1)<σ(j2)[sgn⁡(σ)(∏i=1,i≠j1,i≠j2naσ(i)i)aσ(j1)j1aσ(j2)j2+sgn⁡(σ′)(∏i=1,i≠j1,i≠j2naσ′(i)i)aσ′(j1)j1aσ′(j2)j2]=∑σ∈Sn,σ(j1)<σ(j2)[sgn⁡(σ)(∏i=1,i≠j1,i≠j2naσ(i)i)aσ(j1)j1aσ(j2)j2−sgn⁡(σ)(∏i=1,i≠j1,i≠j2naσ(i)i)aσ(j2)j1aσ(j1)j2]=∑σ∈Sn,σ(j1)<σ(j2)sgn⁡(σ)(∏i=1,i≠j1,i≠j2naσ(i)i)(aσ(j1)j1aσ(j2)j2−aσ(j1)j2aσ(j2)j1)⏟=0, if Aj1=Aj2{displaystyle {begin{aligned}F(A)&=sum _{sigma in S_{n},sigma (j_{1})

Thus if

Aj1=Aj2{displaystyle A^{j_{1}}=A^{j_{2}}}

then

F(…,Aj1,…,Aj2,…)=0{displaystyle F(dots ,A^{j_{1}},dots ,A^{j_{2}},dots )=0}

.

Finally,

F(I)=1{displaystyle F(I)=1}

:

F(I)=∑σ∈Snsgn⁡(σ)∏i=1nIσ(i)i=∑σ∈Snsgn⁡(σ)∏i=1nδi,σ(i)=∑σ∈Snsgn⁡(σ)δσ,id{1…n}=sgn⁡(id{1…n})=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

F(I)=1{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

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

with these three properties.

See also[edit]

References[edit]