Leibniz formula for determinants

Short description: 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 is an n×n matrix, where aij is the entry in the i-th row and j-th column of A, the formula is[1]

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

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 even relatively small n. Instead, the determinant can be evaluated in O(n3) operations by forming the LU decomposition A=LU (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). The determinant can also be evaluated in fewer than O(n3) operations by reducing the problem to matrix multiplication, but most such algorithms are not practical.

## Formal statement and proof

Theorem. There exists exactly one function F:Mn(𝕂)->𝕂 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=(aij)i=1,…,nj=1,…,n be an n×n matrix. Call Aj the j-th column of A, i.e. Aj=(aij)i=1,…,n, so that A=(A1,…,An).

Also, let Ek denote the k-th column vector of the identity matrix.

Now one writes each of the Aj's in terms of the Ek, i.e.

Aj=∑k=1nakjEk.

As F is multilinear, one has

F(A)=F(∑k1=1nak11Ek1,…,∑kn=1naknnEkn)=∑k1,…,kn=1n(∏i=1nakii)F(Ek1,…,Ekn).

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)).

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

as F(I) is required to be equal to 1.

Therefore no function besides the function defined by the Leibniz Formula can be 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(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,…)

Alternating:

F(…,Aj1,…,Aj2,…)=∑σ∈Snsgn⁡(σ)(∏i=1,i≠j1,i≠j2naσ(i)i)aσ(j1)j1aσ(j2)j2

For any σ∈Sn let σ′ be the tuple equal to σ with the j1 and j2 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

Thus if Aj1=Aj2 then F(…,Aj1,…,Aj2,…)=0.

Finally, F(I)=1:

F(I)=∑σ∈Snsgn⁡(σ)∏i=1nIσ(i)i=∑σ∈Snsgn⁡(σ)∏i=1nδi,σ(i)=∑σ∈Snsgn⁡(σ)δσ,id{1…n}=sgn⁡(id{1…n})=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⁡:Mn(𝕂)->𝕂 with these three properties.

## See also

* Matrix
* Laplace expansion
* Cramer's rule

## References

* Hazewinkel, Michiel, ed. (2001), "Determinant", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Determinant&oldid=12692
* Trefethen, Lloyd N.; Bau, David (June 1, 1997). Numerical Linear Algebra. SIAM. ISBN 978-0898713619.

1. ↑ Strang, Gilbert (2016). Introduction to linear algebra (5th ed.). Wellesley: Cambridge press. pp. 260-262. ISBN 978-0-9802327-7-6.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Leibniz formula for determinants. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Leibniz_formula_for_determinants&oldid=4149119"