Permutation Basics

Over at Chemical Quantum Images is a discussion on what Felix calls "the basics" of quantum theory, most of which went way over my head. Some of the definitions he gave are more mathemical than others. In particular, he defined the Slater determinant as

Apparently, this definition looks scary to some people (capital sigma's and pi's with sharp edges and pointy ends, and the mysterious sgn function!). But, aside from the fiddly constant at the front, the definition is friendly, I promise! It's just the definition of a garden-variety, common determinant¹.

Because I am trying to avoid studying physics², I thought I might spend some blog posts defining determinants and proving their properties before I start work. There may be summations and products, but there will be no hissy stylized S's here³.

Before determinants, though, we must discuss permutations.

Firstly, let be the set of (distinct) letters (or symbols). A permutation is a bijection

More intuitively, a permutation is when you have letters in a certain order (usually the canonical one, i.e. 1, 2, 3, ...), then you mix them up. For example, one possible permutation of 1, 2, 3 is 3, 1, 2. In other words, , , .

For simplicity, we may describe a permutation as follows:

Using the same example as before, this becomes

Since permutations are bijections, they have unique inverse permutations, denoted . Basically, read backwards. Using our example, . Overall, the example gives:

Now permutations are functions, so we can compose them: given permutations and , we define

Being lazy, often we omit the circle when writing compositions, and call the compositions "multiplications".

By inspection, there are permutations given letters. The set of all permutations under multiplication is known as the "symmetric group on letters", denoted , where a group is a mathematical construct satisfying the following three things:

1. The identity element, denoted or , is in the set. (True: take the permutation that leaves everything unchanged.)
2. Multiplication of elements in the set is associative. (Most functions that I know are associative under composition, including permutations.)
3. Every element in the set has an inverse, also in the set. (True: as discussed previously, a permutation is a bijection, and thus have an inverse that is also a permutation.)

Well, ok, one more thing: the set is closed under multiplication, i.e. the composition of two permutations is also a permutation. Which it is. Note that multiplication is not commutative - very important! By convention, we read multiplications from right to left (innermost function first), although not everybody does that. Also, note that we can describe powers of permutations:

Naturally, we define .

There is a special kind of permutation, called a cyclic permutation. Basically, we take some letters from , not necessarily all of them, and not necessarily in order. A cyclic permutation is the map

leaving all other letters unchanged. Such a map is also called a k-cycle. As a shortcut, we write out the cycle as follows:

Cycles where , i.e. , are called transpositions or transposes. Transposes where are called adjacent transposes.

It can be shown that any permutation can be factored into disjoint cycles that commute, and any cycle can be factored into transpositions. The former I won't prove (it's not that interesting) but the latter is beautifully simple: take

(Check it!) However, factorizations are not unique. On the other hand, for some reason the number of transpositions in the factorization of any permutation always has the same parity. But I'll talk about that in the next post, and too.

(I can't make the boxes go away. Sorry.)
¹Technically, there is another way to define determinants, i.e. recursively using the Laplacian expansion. But I like permutations better.
²I thought I'd never have to do physics (as physics) ever again, but this time it's a necessary evil. *Sigh*
³Of course, integrals are, in a sense, sums. And anyway, some integrals are actually fun to play with!