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}}}\operatorname{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{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 $\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 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{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:

{\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}\\&=\sum _{{\sigma =(1,2,\dots ,n)}}\prod _{{i=1}}^{n}I_{{i}}^{i}\\&=1\end{aligned}}

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.

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.

This article is issued from Wikipedia - version of the 7/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Leibniz formula for determinants

Formal statement and proof

See also

References