Leibniz formula for determinants

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 ai,j is the entry in the ith row and jth column of A, the formula is

$\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 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)=\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 $\Omega (n!\cdot 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 large 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 (1997).

Formal statement and proof

Theorem. There exists exactly one function

$F:M_{n}(\mathbb {K} )\rightarrow \mathbb {K}$ 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=(a_{i}^{j})_{i=1,\dots ,n}^{j=1,\dots ,n}$ be an $n\times n$ matrix. Call $A^{j}$ the $j$ -th column of $A$ , i.e. $A^{j}=(a_{i}^{j})_{i=1,\dots ,n}$ , so that $A=\left(A^{1},\dots ,A^{n}\right).$ Also, let $E^{k}$ denote the $k$ -th column vector of the identity matrix.

Now one writes each of the $A^{j}$ 's in terms of the $E^{k}$ , i.e.

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

As $F$ is multilinear, one has

{\begin{aligned}F(A)&=F\left(\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)F\left(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)=\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$ can be swapped until it becomes the identity. The sign function $\operatorname {sgn}(\sigma )$ is defined to count the number of swaps necessary and account for the resulting sign change. One finally gets:

{\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)$ 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\left(I\right)=1$ .

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

{\begin{aligned}F(A^{1},\dots ,cA^{j},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )ca_{\sigma (j)}^{j}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\\&=c\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )a_{\sigma (j)}^{j}\prod _{i=1,i\neq 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,i\neq j}^{n}a_{\sigma (i)}^{i}\\&=\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )\left(\left(b_{\sigma (j)}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\right)+\left(a_{\sigma (j)}^{j}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\right)\right)\\&=\left(\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )b_{\sigma (j)}\prod _{i=1,i\neq 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}} {\begin{aligned}F(\dots ,A^{j_{1}},\dots ,A^{j_{2}},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}\\\end{aligned}} For any $\sigma \in S_{n}$ let $\sigma '$ be the tuple equal to $\sigma$ with the $j_{1}$ and $j_{2}$ indices switched.

{\begin{aligned}F(A)&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\left[\operatorname {sgn} (\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}+\operatorname {sgn} (\sigma ')\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma '(i)}^{i}\right)a_{\sigma '(j_{1})}^{j_{1}}a_{\sigma '(j_{2})}^{j_{2}}\right]\\&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\left[\operatorname {sgn} (\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}-\operatorname {sgn} (\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{2})}^{j_{1}}a_{\sigma (j_{1})}^{j_{2}}\right]\\&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\operatorname {sgn} (\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)\left(a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}-a_{\sigma (j_{1})}^{j_{2}}a_{\sigma (j_{2})}^{j_{_{1}}}\right)\\\\\end{aligned}} Thus if $A^{j_{1}}=A^{j_{2}}$ then $F(\dots ,A^{j_{1}},\dots ,A^{j_{2}},\dots )=0$ .

Finally, $F(I)=1$ :

{\begin{aligned}\\F(I)&=\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )\prod _{i=1}^{n}I_{\sigma (i)}^{i}\\&=\operatorname {sgn} (\sigma )\prod _{i=1}^{n}I_{\sigma (i)}^{i}\qquad {\text{where }}\sigma =(1,2,\ldots ,n).{\text{ For other choices of }}\sigma ,I_{\sigma (i)}^{i}=0.\\&=\prod _{i=1}^{n}I_{i}^{i}\\&=1\end{aligned}} 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 :M_{n}(\mathbb {K} )\rightarrow \mathbb {K}$ with these three properties.