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

$\det(A) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i), i},$

where sgn is the sign function of permutations in the permutation group S_n, 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(n³) 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 alternate 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{align} 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{align}$

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 $\sgn(\sigma)$ is defined to count the number of swaps necessary and account for the resulting sign change. One finally gets:

$\begin{align} F(A)& = \sum_{\sigma \in S_n} \sgn(\sigma) \left(\prod_{i = 1}^n a_{\sigma(i)}^i\right) F(I)\\ & = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i \end{align}$

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

Therefore no function besides the function defined by the Leibniz Formula is 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.

Multilinear:

$\begin{align} F(A^1, \dots, cA^j, \dots) & = \sum_{\sigma \in S_n} \sgn(\sigma) ca_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\ & = c \sum_{\sigma \in S_n} \sgn(\sigma) a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\ &=c F(A^1, \dots, A^j, \dots)\\ \\ F(A^1, \dots, b+A^j, \dots) & = \sum_{\sigma \in S_n} \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} \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} \sgn(\sigma) b_{\sigma(j)}\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right) + \left(\sum_{\sigma \in S_n} \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{align}$

Alternating:

$\begin{align} F(\dots, A^{j_1}, \dots, A^{j_2}, \dots) & = \sum_{\sigma \in S_n} \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{align}$

For any $\sigma \in S_n$ let $\sigma'$ be the tuple equal to $\sigma$ with the $j_1$ and $j_2$ indices switched.

$\begin{align} F(A) & = \sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\left[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}+\sgn(\sigma')\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\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[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}-\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\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})}\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\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{align}$

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{align}\\ F(I) & = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n I_{\sigma(i)}^i\\ & = \sum_{\sigma = (1,2,\dots,n)} \prod_{i = 1}^n I_{i}^i\\ & = 1 \end{align}$

Thus the only functions which are multilinear alternating 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.

See also

• Matrix
• Laplace expansion
• Cramer's rule

References

• Hazewinkel, Michiel, ed. (2001), "Determinant", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Trefethen, Lloyd N.; Bau, David (June 1, 1997). Numerical Linear Algebra. SIAM. ISBN 978-0898713619.