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}n×n{displaystyle ntimes n} is an
aij{displaystyle a_{ij}} matrix, where
i{displaystyle i} is the entry in the
j{displaystyle j} -th row and
A{displaystyle A} -th column of
, 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} }Sn{displaystyle S_{n}} is the sign function of permutations in the permutation group
+1{displaystyle +1} , which returns
−1{displaystyle -1} and
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)}n{displaystyle 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
O(n3){displaystyle O(n^{3})} . Instead, the determinant can be evaluated in
A=LU{displaystyle A=LU} operations by forming the LU decomposition
detA=detL⋅detU{displaystyle det A=det Lcdot det U} (typically via Gaussian elimination or similar methods), in which case
L{displaystyle L} and the determinants of the triangular matrices
U{displaystyle U} and
O(n3){displaystyle O(n^{3})} 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
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(I)=1{displaystyle F(I)=1} which is alternating multilinear w.r.t. columns and such that
.
Proof.
Uniqueness: Let
F{displaystyle F}A=(aij)i=1,…,nj=1,…,n{displaystyle A=(a_{i}^{j})_{i=1,dots ,n}^{j=1,dots ,n}} be such a function, and let
n×n{displaystyle ntimes n} be an
Aj{displaystyle A^{j}} matrix. Call
j{displaystyle j} the
A{displaystyle A} -th column of
Aj=(aij)i=1,…,n{displaystyle A^{j}=(a_{i}^{j})_{i=1,dots ,n}} , i.e.
A=(A1,…,An).{displaystyle A=left(A^{1},dots ,A^{n}right).} , so that
Also, let
Ek{displaystyle E^{k}}k{displaystyle k} denote the
-th column vector of the identity matrix.
Now one writes each of the
Aj{displaystyle A^{j}}Ek{displaystyle E^{k}} ‘s in terms of the
, 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}sgn(σ){displaystyle operatorname {sgn}(sigma )} 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:
- 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)}1{displaystyle 1} is required to be equal to
.
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}}σ′{displaystyle sigma ‘} let
σ{displaystyle sigma } be the tuple equal to
j1{displaystyle j_{1}} with the
j2{displaystyle j_{2}} and
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}}}F(…,Aj1,…,Aj2,…)=0{displaystyle F(dots ,A^{j_{1}},dots ,A^{j_{2}},dots )=0} then
.
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}det:Mn(K)→K{displaystyle det :M_{n}(mathbb {K} )rightarrow mathbb {K} } 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.
Recent Comments