# 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

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.