Cayley’s Theorem: Powerful Permutations

Cayley’s Theorem: Powerful Permutations

We’ve discussed before how powerful isomorphisms can be, when we find them. Finding isomorphisms “from scratch” can be quite a challenge. Thankfully, Arthur Cayley proved one of the classic theorems of modern algebra that can help make our lives a bit easier. We’ll explore this theorem and note the power of groups of permutations

For the introduction to isomorphisms, check out this post. Cayley’s powerful theorem states the following:


Theorem (Cayley):   Every group is isomorphic to a group of permutations.


First, I’d like to highlight the beauty and simplicity of the statement. One sentence, no conditions. Every group. Not every finite group, not every commutative group. Every. Single. Group. That’s an extremely strong statement. Every mathematician hopes to write and prove a theorem this strong; I know I would die happy if I managed to do it. 

For this article, I actually want to spend time going through the proof of Cayley’s Theorem. It will be useful when we want to develop the notion of regular representations later. 

Permutations: what exactly are they?

We’ve discussed permutations before, but hadn’t formally defined them. We will here. Permutations are generally viewed as rearrangements of objects (typically integers). In other words, the permutation \begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} mixes up the numbers 1,2,3 and gives 2,3,1. Each number gets used, and mapped to a different number. 1 maps to 2, 2 maps to 3, and 3 maps to 1. In other words, if we started with the set A=\{1,2,3\}, a permutation maps the elements A to other elements in A.

Permutations are also reversible. We can always take any permutation and reverse it to get our original order back. Formally, we then define a permutation of a set A as a bijective function (or mapping) from the set A to itself. The mapping is one-to-one, meaning that if two input values are different, then their function values are different. It’s also surjective (also called onto), meaning that every element in A has something that maps to it.

Since we aren’t moving from one set to another, but rather staying in the same set, this is just a fancy way of saying that a permutation maps every element in our given set to only one other element in the given set, and that all set elements are used up. No one gets left out or not mapped somewhere (even if it maps to itself). 

We’ll need this more generic definition of a permutation as a function or mapping in the proof of Cayley’s Theorem.

Proof of Cayley’s Theorem

To prove this, we take some generic group G.1

OK, we have our group G. Now we have to show it’s isomorphic to a group of permutations. What group of permutations on what set? This proof is constructive, so we will construct a group of permutations and show that this constructed group is isomorphic to G. In other words, we’re going to 

(1) Construct the group of permutations that G will be isomorphic to, then

(2) Construct the isomorphism from G to the group of permutations we constructed in (1). 

The only set we have to work with is G itself, so let’s see what we can do with this. 

(1) Construct the group of permutations 

Let’s grab a random element in G and call it a. Now, we’ll define a function we’ll call \pi_{a}:G\to G that maps2 elements of G to other elements of G by 

\pi_{a}(x) = ax

For any other element x\in G, the function \pi_{a} just multiplies a on the left3 of x

To show this function \pi_{a} is a permutation according to our above definition, we need to show that the function is bijective and maps stuff in G to stuff in G. We already have that \pi_{a} maps stuff in G to other stuff in G, because we defined it that way. That problem is solved. Now we’ll show \pi_{a} is a bijective function by showing it’s injective (one-to-one) and surjective (onto):

(1) Injectivity of \pi_{a}:  To show injectivity, we need to show that if \pi_{a}(x_{1}) = \pi_{a}(x_{2}), then x_{1} = x_{2}. In other words, we’re showing that two different elements cannot map to the same thing. 

Now, in our specific case, if

\pi_{a}(x_{1}) = \pi_{a}(x_{2})

then

ax_{1} = ax_{2}

But we’re allowed to cancel those as by multiplying by the inverse of a on the left on both sides (just like in your high school algebra class)4, leaving

x_{1}=x_{2}

So our \pi_{a} is absolutely injective.

(2) Surjectivity of \pi_{a}: To show surjectivity, we take some y\in G, and we need to find the element x\in G that maps to this y. (This is formally known as finding the inverse image of y.) We know that 

y = e\cdot y

where e is our identity element5. Now, any element multiplied by its inverse (in any order) gives us the identity element (because that’s the definition of an inverse.), so let’s grab a and its inverse a^{-1}:

y = e\cdot y = (a\cdot a^{-1}) y = a\cdot (a^{-1}y)

By using the associativity laws we get free with the knowledge that G is a group, we can multiply a^{-1}y first, then multiply that result by a. But that element a^{-1}y yields y when multiplied by a, so we found our inverse image of y. Since y was generic, this reasoning is true for all elements of G, so we have that \pi_{a} is surjective.

With all that, we now can say that \pi_{a} is a permutation, because it fits the definition.

More Permutations!

The \pi_{a} was just a particular mapping defined by multiplying on the left by a fixed element a. We can define one of these permutations for every other element in G as well. So \pi_{b} multiplies stuff on the left by whatever b is, and so forth.

Let H = \{\pi_{n}:n\in G\} denote the set of all the permutations of G that involve multiplying on the left by some n \in G. Obviously, there are more possible permutations of the elements of G than what’s in this set H. The set of all possible permutations of a group (denoted S_{G}) is itself a group6, so if we just show that H is a subgroup (a subset of a group that is itself a group), then we’ve built a group of permutations from the group G.

To show that H is a subgroup of S_{G}, we have to show that the composition of two permutations in H is also an element of H, and that the inverse of every permutation in H is also in H. We’ll skip the formal proof here, since it doesn’t really add much to the discussion, other than to formally verify that H is a group and indeed a possible candidate for a group that our G could be isomorphic to. 

(2) Construct the isomorphism from G to H

With all the work we spent constructing H, we sure hope that we constructed something for G to be isomorphic to. If these two groups are isomorphic, then we need to construct a bijective function that maps elements of G to elements of H

(A note: this isomorphism f:G\to H takes elements in G and maps them to a function in H. We’re allowed to have functions that output functions.)

The most obvious mapping is to take an element a\in G and map it to its permutation \pi_{a} \in H. In other words, 

f(a) = \pi_{a}

Our f maps an element a to a function that says “multiply on the left by a”. So we defined a function whose output is itself a function with the rule “multiply on the left by the input element”. 

We already discussed how to verify that a function f is an isomorphism in the last post, so we won’t go through the details in this case. It’s quite straightforward, and doesn’t serve to illuminate anything further. Try it yourself as a short exercise to finish the formal proof.

Conclusion

We took a group G and constructed another group H  that consists of permutations of G and then showed those two groups were isomorphic. Since G was generic in every way, and H was constructed from that generic G, we just proved Cayley’s Theorem–that every group is isomorphic to some group of permutations. 

What’s this for? This seemed so utterly abstract as to be simply a curiosity (albeit a powerful one). We can use Cayley’s Theorem to develop a notion called the regular representation of a group, which in turn has applications in quantum chemistry and physics, particularly in the study of symmetries of a molecule, which in turn controls its vibrational spectrum. This molecular vibrational spectrum can be determined by IR spectroscopy, which then allows a chemist to determine the symmetries of a molecule. 

Groups also tend to arise in applications as actions on other things (in fact, a permutation is an action of sorts), so representations and their theory help us understand how these groups and their actions affect anything from differential equations to molecules.

(This article details some of these applications in more detail, though the level is quite advanced.)

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Footnotes

  1. This is important. We have to take a generic group with no specifications at all, or we aren’t really proving the theorem. I don’t know what’s in this group, what its operation is, or even if the group is finite, countably infinite, or uncountable.
  2. That’s what the arrow means in the notation. The function maps elements of G to elements in the target space G. It just so happens our target space is the same as our “input space”, or domain, so we don’t actually leave G
  3. The order of multiplication does matter here. We are not guaranteed commutativity, so we have to be very specific about which side we multiply a on.
  4. In high school algebra, we’d say “divide by a”. Division is really just “multiplying by a multiplicative inverse”.
  5. Since we’re dealing with a generic group, we use the letter e to denote the identity element under the general operation. In addition on the real numbers, e=0. In multiplication of integers, e=1. But here, we don’t even know what’s in this group, so we have to just give it a generic name.
  6. We’ll skip the proof. It’s just a straightforward verification of the definition of a group.
Comments are closed.