Understanding the Leibniz formula for determinants

Solution 1:

For one, but that might be irrelevant to you, this formula is not the way you want to actually compute determinants; there are much more efficient methods for that. But I will try to help you understand the formula.

We have an $n \times n$-matrix $A$. Its elements are $a_{i,j}$ as usual, or $a[i,j]$ in more C-like notation. The outer sum sums over all permutations (this set is $S_n$), so that is an outer loop. A permutation is just a reordering of the indices, like $(1,3,2)$ for $n=3$; for $n=3$ there are $3!$ permutations of the indices: $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$, and for $n$ indices there are $n!$ in general. Here we can interpret this as a function: $(3,2,1)$ is the function that sends $1$ to $3$, $2$ to $2$ and $3$ to $1$, e.g. Now, each permutation has a sign $\operatorname{sgn}(\sigma)$, which is either +1 or -1. The identity has sign +1, while interchanging two elements of a permutation changes the sign to the opposite one. So $(1,3,2), (3,2,1), (2,1,3)$ are odd permutations on $n=3$, because we interchanged one pair. One can prove that half the permutations are even (have sign +1), and the other half has sign -1.

Now for each permutation $\sigma$ we take the multiplication of the elements of $A$ as specified by the permutation, interpreted as a map. So $(1,3,2)$ is the map $1 \rightarrow 1, 2 \rightarrow 3, 3 \rightarrow 2$, so we get the product $a_{1,1}a_{3,2}a_{2,3}$, where the second index is the original, the first its image under $\sigma$.

The formula says that $\det(A)$ is the sum of all such products where we consider all permutations of the index set, and the products from an odd permutation get a minus sign.

So for $n=3$ we get $$\det(A) = a_{1,1}a_{2,2}a_{3,3} - a_{1,1}a_{2,3}a_{3,2} - a_{1,3}a_{2,2}a_{3,1} - a_{1,2}a_{2,1}a_{3,3} + a_{1,2}a_{2,3}a_{3,1} + a_{1,3}a_{2,1}a_{3,2}$$ where the minus signs correspond to the odd permutations from above.

So you need algorithms to enumerate all permutations, and compute their signs, and then loop over all these products. It's quite complicated to get right, and not very efficient. But this formula allows one to prove some facts for determinants, so it has its uses.