Leibniz formula for determinants

Template:Short description 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_{ij}$ is the entry in the $i$-th row and $j$-th column of $A$, the formula is

$\det (A)=\sum _{\tau \in S_n}\mathrm{sgn}(\tau )\prod _{i=1}^n{a}_{i\tau (i)}=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{\sigma (i)i}$

where $\mathrm{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)={ϵ}_{i_1\cdots i_n}{a}_{1i_1}\cdots a_{n{i}_n},$

which may be more familiar to physicists.

Directly evaluating the Leibniz formula from the definition requires $\mathrm{\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, Template:Harvtxt. 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(𝕂)\to 𝕂$ 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=(A^1,\dots ,A^n).$

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{array}{cc}F(A)& =F(\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})=\sum _{k_1,\dots ,k_n=1}^n\left(\prod _{i=1}^n{a}_{k_i}^i\right)F(E^{k_1},\dots ,E^{k_n}).\end{array}$

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

$\begin{array}{cc}F(A)& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\left(\prod _{i=1}^n{a}_{\sigma (i)}^i\right)F(I)\\ & =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{\sigma (i)}^i\end{array}$

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{array}{cc}F(A^1,\dots ,c{A}^j,\dots )& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )c{a}_{\sigma (j)}^j\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\\ & =c\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )a_{\sigma (j)}^j\prod _{i=1,i\ne 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}\mathrm{sgn}(\sigma )(b_{\sigma (j)}+a_{\sigma (j)}^j)\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\\ & =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )(\left(b_{\sigma (j)}\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\right)+\left(a_{\sigma (j)}^j\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i\right))\\ & =(\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )b_{\sigma (j)}\prod _{i=1,i\ne j}^n{a}_{\sigma (i)}^i)+(\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{\sigma (i)}^i)\\ & =F(A^1,\dots ,b,\dots )+F(A^1,\dots ,A^j,\dots )\\ \\ \end{array}$

Alternating:

$\begin{array}{cc}F(\dots ,A^{j_1},\dots ,A^{j_2},\dots )& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}\\ \end{array}$

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

$\begin{array}{cc}F(A)& =\sum _{\sigma \in S_n,\sigma (j_1)<\sigma (j_2)}[\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}+\mathrm{sgn}({\sigma }^{\prime })\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{{\sigma }^{\prime }(i)}^i\right)a_{{\sigma }^{\prime }(j_1)}^{j_1}{a}_{{\sigma }^{\prime }(j_2)}^{j_2}]\\ & =\sum _{\sigma \in S_n,\sigma (j_1)<\sigma (j_2)}[\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}-\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)a_{\sigma (j_2)}^{j_1}{a}_{\sigma (j_1)}^{j_2}]\\ & =\sum _{\sigma \in S_n,\sigma (j_1)<\sigma (j_2)}\mathrm{sgn}(\sigma )\left(\prod _{i=1,i\ne j_1,i\ne j_2}^n{a}_{\sigma (i)}^i\right)\underset{=0\text{, if }{A}^{j_1}=A^{j_2}}{\underbrace{(a_{\sigma (j_1)}^{j_1}{a}_{\sigma (j_2)}^{j_2}-a_{\sigma (j_1)}^{j_2}{a}_{\sigma (j_2)}^{j_{{}_1}})}}\\ \\ \end{array}$

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{array}{cc}F(I)& =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{I}_{\sigma (i)}^i=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{\mathrm{\delta }}_{i,\sigma (i)}\\ & =\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma ){\mathrm{\delta }}_{\sigma ,{\mathrm{id}}_{\{1\dots n\}}}=\mathrm{sgn}({\mathrm{id}}_{\{1\dots n\}})=1\end{array}$

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(𝕂)\to 𝕂$ with these three properties.

See also

• Matrix
• Laplace expansion
• Cramer's rule

References

• Template:SpringerEOM
• Template:Cite book