Leibniz formula (determinant)

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 \times n$ matrix, where $a_$ is the entry in the $i$-th row and $j$-th column of $A$, the formula is
:$\det(A) = \sum_ \sgn(\tau) \prod_^n a_ = \sum_ \sgn(\sigma) \prod_^n a_$
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_ _ \cdots _,$
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 even relatively small $n$. Instead, the determinant can be evaluated in $O(n^3)$ operations by forming the LU decomposition $A = LU$ (typically via Gaussian elimination or similar methods), in which case $\det A = \det L \cdot \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, . The determinant can also be evaluated in fewer than $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 $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)_^$ be an $n \times n$ matrix. Call $A^j$ the $j$-th column of $A$, i.e. $A^j = (a_i^j)_$, 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_^n a_k^j E^k$.

As $F$ is multilinear, one has

:$\begin F(A)& = F\left(\sum_^n a_^1 E^, \dots, \sum_^n a_^n E^\right) = \sum_^n \left(\prod_^n a_^i\right) F\left(E^, \dots, E^\right). \end$

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_ \left(\prod_^n a_^i\right) F(E^, \dots , E^).$

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 F(A)& = \sum_ \sgn(\sigma) \left(\prod_^n a_^i\right) F(I)\\ & = \sum_ \sgn(\sigma) \prod_^n a_^i \end$

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.

Multilinear:
:$\begin F(A^1, \dots, cA^j, \dots) & = \sum_ \sgn(\sigma) ca_^j\prod_^n a_^i\\ & = c \sum_ \sgn(\sigma) a_^j\prod_^n a_^i\\ &=c F(A^1, \dots, A^j, \dots)\\ \\ F(A^1, \dots, b+A^j, \dots) & = \sum_ \sgn(\sigma)\left(b_ + a_^j\right)\prod_^n a_^i\\ & = \sum_ \sgn(\sigma) \left( \left(b_\prod_^n a_^i\right) + \left(a_^j\prod_^n a_^i\right)\right)\\ & = \left(\sum_ \sgn(\sigma) b_\prod_^n a_^i\right) + \left(\sum_ \sgn(\sigma) \prod_^n a_^i\right)\\ &= F(A^1, \dots, b, \dots) + F(A^1, \dots, A^j, \dots)\\ \\ \end$
Alternating:
:$\begin F(\dots, A^, \dots, A^, \dots) & = \sum_ \sgn(\sigma) \left(\prod_^n a_^i\right) a_^ a_^\\ \end$
For any $\sigma \in S_n$ let $\sigma'$ be the tuple equal to $\sigma$ with the $j_1$ and $j_2$ indices switched.
:
\begin
F(A) & = \sum_\left sgn(\sigma)\left(\prod_^na_^\right)a_^a_^+\sgn(\sigma')\left(\prod_^na_^\right)a_^a_^\right\
& =\sum_\left sgn(\sigma)\left(\prod_^na_^\right)a_^a_^-\sgn(\sigma)\left(\prod_^na_^\right)a_^a_^\right\
& =\sum_\sgn(\sigma)\left(\prod_^na_^\right)\underbrace_\\
\\
\end

Thus if $A^ = A^$ then $F(\dots, A^, \dots, A^, \dots)=0$.

Finally, $F(I)=1$:
:$\begin F(I) & = \sum_ \sgn(\sigma) \prod_^n I^i_ = \sum_ \sgn(\sigma) \prod_^n \operatorname_\\ & = \sum_ \sgn(\sigma) \operatorname_ = \sgn(\operatorname_) = 1 \end$

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.

See also

* Matrix
* Laplace expansion
* Cramer's rule

References

*
* {{cite book , title=Numerical Linear Algebra , last1=Trefethen , first1=Lloyd N. , last2=Bau , first2=David , publisher= SIAM , date=June 1, 1997 , isbn=978-0898713619

Determinants
Gottfried Wilhelm Leibniz
Linear algebra
Articles containing proofs