Recall that a permutation is a bijective function from n objects to those same n objects. Conventionally, we take those objects to be the integers 1, 2, 3... n. It's an interesting fact that permutations have a sign. For each permutation, the sign of that permutation is either 1 or -1, and when we compose 2 permutations, their signs multiply. The question is, why should this be true? That's the question asked by this math overflow post, and I'll try and give an answer here. Most of it is heavily based on / shamelessly copied from this answer by Bjorn Poonen, though I'll try to Mathologerize it somewhat and use more accessible terminology.

Draw a complete directed graph on n nodes. These nodes will be the n objects we are permuting. The graph is complete, so there is an edge between every two nodes. It's also directed, so each edge is pointing from one of those nodes to the other. Which way each particular edge points is arbitrary, we can choose it by a coin toss.

Let's consider what happens when we swap two nodes, x and y, in the graph, and compare the edges in the original graph with those in the new graph. Some edges will still be pointing in the same direction, while some will now be pointing in opposite directions. We can give a sign to each individual edge now. Edges that are pointing in the same direction get a sign of 1, while those pointing in opposite directions get a sign of -1. There will always be an odd number of edges pointing in opposite directions. In other words, the product of the signs of all the edges is -1.

The argument is that the edge {x,y} is now pointing in the opposite direction, so its sign is -1. Edges involving neither x nor y are unchanged, and their signs are all 1. The remaining edges are swapped in pairs: For any node z distinct from x and y, {x,z} and {y,z} are swapped. Therefore, {x,z} and {y,z} are either both changed, or both unchanged. Either way, their signs multiply out to 1. Final result: -1. In other words, the total number of changed edges that are now pointing the other way is odd.

This can be extended to an arbitrary permutation. Apply the permutation to the graph, and take the product of the signs of all the edges. The sign of the permutation is equal to this product. If there are an even number of edges pointing the other way, the sign of the permutation is 1, and if there are an odd number, the sign of the permutation is -1. As shown above, swaps have a sign of -1. We can also tell right away that the identity permutation (where all edges are undisturbed and thus have sign 1) has a sign of 1.

The first question here is whether this method of computing the sign always produces the same answer. Remember that we had a free choice when initially building our graph of which way the edges would point. Could that choice affect whether or not some permutations come out as "sign 1" or "sign -1". It turns out that it can't, but we'll have to prove it.

We can turn any initial choice of edges into any other initial choice of edges by flipping edges one at a time. As long as flipping a single edge doesn't change the answer, we can walk from any configuration to any other configuration by flipping edges one at a time, and be assured that the sign for our permutation that we're computing isn't changing.

Let π be the permutation whose sign we are trying to compute. Without loss of generality, suppose that the edge we want to flip points from x to y. We want to make it point from y to x. When we apply π, the edge {x,y} goes to {π(x),π(y)}. Flipping {x,y} means that if {π(x),π(y)} was previously pointing in the same direction as {x,y}, it's now pointing in the opposite direction and if it was previously pointing in the opposite direction, it's now pointing in the same direction. Either way, sign({π(x),π(y)}) goes to -sign({π(x),π(y)}). Also {π⁻¹(x),π⁻¹(y)} goes to {x,y} and we can similarly deduce that flipping the edge {x,y} takes sign({x,y}) to -sign({x,y}). The signs of all other edges are unaffected. Therefore the overall sign of the permutation π has been multiplied by (-1)² = 1. In other words, it is unaffected.

There is an edge case here: π may take the edge {x, y} to itself. In that case, there is no effect on that edge's sign from flipping its original direction, and all other edges remain unaffected. Overall, for both cases, we conclude that the sign of the permutation π is not dependent on which directions we choose to point the edges in.

The remaining question is: Why should the signs multiply when we compose permutations? Suppose we're composing the permutations π and ρ. As a shorthand, given an edge e={x,y} we'll define π(e)={π(x),π(y)} and similarly ρ(e)={ρ(x),ρ(y)}. Note that sign of an edge is particular to the permutation in question:

(The sign of an edge is also particular to which starting graph we choose. The starting graph for π will be the same as the starting graph for ρπ, and can have edge directions picked freely. The starting graph for ρ then has to be the graph we get after applying π to the original starting graph.)

Since an edge that's changed twice ends up back in the same direction as it was originally, we have the following identity, for all edges e:

The rest is just algebra...

So yeah, that's pretty much it. This way of thinking also lets us understand some other cool things about the sign of a permutation. For example, another answer to that stack exchange question gives the following formula, where x is a vector with n elements:

This can be proved by putting xⱼ at the jth node of the graph, pointing the edges from lower nodes to higher nodes, and observing that: