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 ${\displaystyle A}$ is an ${\displaystyle n\times 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 L\cdot \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 n\times 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)&=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:

${\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 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.

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,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}}}$

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,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 ${\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})<\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)\underbrace {\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)} _{=0{\text{, if }}A^{j_{1}}=A^{j_{2}}}\\\\\end{aligned}}}$

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} _{\{1\ldots n\}}}=\operatorname {sgn}(\operatorname {id} _{\{1\ldots n\}})=1\end{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.

See also

• Matrix
• Laplace expansion
• Cramer's rule

References

• "Determinant", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Trefethen, Lloyd N.; Bau, David (June 1, 1997). Numerical Linear Algebra. SIAM. ISBN 978-0898713619.