8
$\begingroup$

I am a programmer and trying to write the Leibniz formula for determinants into C++ code, but I am unable to fully understand it. Can someone walk me through it?

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

$\endgroup$
  • 2
    $\begingroup$ What exactly don't you understand? $\endgroup$ – EuYu Mar 3 '13 at 10:12
  • 3
    $\begingroup$ And why are you doing this? It's a terrible way of calculating determinants, and better ways are available in hundreds of libraries. $\endgroup$ – Chris Eagle Mar 3 '13 at 10:14
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So what is a more efficient way to calculate the determinant? Because I choose this way because I thought it was verye fficient. $\endgroup$ – Cheiron Mar 3 '13 at 10:28
  • 5
    $\begingroup$ @Cheiron Gaussian Elimination is a fast and relatively simple way. The Leibniz formula is more of a theoretical tool, in fact it is probably one of the slowest ways to calculate the determinant. $\endgroup$ – EuYu Mar 3 '13 at 10:37
  • 3
    $\begingroup$ So, the next question is "why do you want to know if the matrix has an inverse". I hope it's not so that you can calculate the inverse, and then use it to solve systems of equations. That's a really bad way to solve systems of equations. And, you shouldn't be writing any of this stuff yourself, anyway. People with much more expertise than you have already written libraries to do this sort of thing, and those libraries have been battle-hardened from years of use. Don't try to re-invent the wheel. $\endgroup$ – bubba Mar 3 '13 at 11:36
  • 2
    $\begingroup$ @Cheiron just use elimination. It's not too hard, and if a matrix is not invertible you will find out along the way. $\endgroup$ – Henno Brandsma Mar 3 '13 at 12:20
  • 1
    $\begingroup$ @Cheiron -- OK. Fair enough. But the Leibnitz formula is still bad. Use elimination or LU decomposition. Then, as Henno said, you will find out during the computations that the matrix is singular (non-invertible) and you can raise an exception or return an error. $\endgroup$ – bubba Mar 4 '13 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.