Permutation group

In mathematics, a permutation group is a special kind of group made up of permutations of a set. Permutations are ways of rearranging the elements of a set, like shuffling a deck of cards. The group operation in a permutation group is the composition of these permutations, meaning doing one permutation after another.

The group of all possible permutations of a set is called the symmetric group of that set. For a set with n elements, this group is often written as S_n. A permutation group is simply a smaller group that is a subgroup of this symmetric group.

An important fact is that, by Cayley's theorem, every group can be represented as some permutation group, meaning permutation groups are very useful in studying all kinds of algebraic structures. The way a permutation group moves or rearranges the elements of a set is called its group action. These actions help us understand symmetries, solve problems in combinatorics, and have applications in many areas including physics and chemistry.

Basic properties and terminology

A permutation group is a special kind of group made up of permutations of a set. These permutations are ways of rearranging the elements of the set. The group follows certain rules: it includes a special permutation called the identity permutation, which leaves everything in its original place, and for every permutation in the group, there is another permutation that undoes it, called the inverse permutation.

We can describe permutation groups by their degree and order. The degree is the number of elements in the set being rearranged. The order is the total number of different permutations in the group. An important rule says that for a permutation group with degree n, its order must be a factor of n!, where n! is the number of all possible ways to arrange n elements.

Notation

Main article: Permutation § Notations

Permutations are ways to rearrange the items in a set. We can write them down in a special format called two-line notation. In this format, we list the items of the set in the first row, and then show where each item moves to in the second row.

For example, if we have the set {1, 2, 3, 4, 5}, a permutation might look like this: it tells us that 1 moves to 2, 2 moves to 5, 3 moves to 4, 4 moves to 3, and 5 moves to 1. There is also a shorter way to write permutations called cycle notation, where we group items that move in a circle. For the same permutation, we could write it as (125)(34), meaning 1 moves to 2, 2 moves to 5, and 5 moves back to 1, while 3 moves to 4 and 4 moves back to 3.

Composition of permutations–the group product

When we combine two permutations, we are basically doing one after the other. This is called their composition. For example, if we have two ways to rearrange a group of items, doing one way and then the other gives us a new way to arrange them.

Mathematicians find it helpful to write this combination without extra symbols, simply placing the permutations next to each other. This works because the order in which we do the permutations matters, and combining them this way keeps that order clear.

Neutral element and inverses

The identity permutation is like a "do-nothing" move. It leaves every element in its place and acts as the neutral element for combining permutations.

Because permutations are bijections — meaning each element has a unique match — they also have opposites called inverses. An inverse permutation undoes the effect of the original permutation. For example, if one permutation swaps the numbers 1 and 2, its inverse will swap them back to their original positions. This feature, along with the identity and a way to combine permutations, ensures that all permutations form a group.

Examples

Consider a set of four items labeled 1, 2, 3, and 4. We can create different ways to rearrange these items, called permutations. For example, one permutation might swap items 1 and 2 while leaving 3 and 4 in place. Another might swap 3 and 4 instead. When we combine these swaps, we can change all four items at once by swapping both pairs together.

These permutations form a group because combining them in different ways always gives us another permutation in the same set. This small group is known as the Klein group.

Another example comes from the symmetries of a square. If we label the corners of a square 1, 2, 3, and 4 going around, we can describe turns and flips of the square as permutations of these corners. Turning the square 90 degrees moves each corner to a new position, which we can write as a permutation. Flipping the square over also changes the positions of the corners in a way we can describe with permutations. All these symmetries together form another group called the dihedral group.

Main article: Klein group

Main articles: group of symmetries of a square, dihedral group

Group actions

Main article: Group action (mathematics)

In permutation groups, we talk about groups "acting" on sets. This means the group moves or changes the elements of the set in a special way. For example, the symmetries of a square can move its vertices around. This action follows two important rules: doing nothing to the set leaves it unchanged, and doing one movement after another is the same as doing a single combined movement.

Permutation groups have a natural way of acting on their sets, like moving the vertices of a square. But they can also act on other sets, such as the triangles or diagonals inside the square.

Transitive actions

The action of a group on a set is called transitive if any element of the set can be moved to any other element by some group operation. This means the set forms a single group-controlled "orbit." For example, the symmetries of a square are transitive on its vertices because any vertex can be moved to any other vertex through rotation or reflection.

A transitive permutation group is primitive if it does not preserve any special grouping of the set's elements, except for the most simple groupings. Otherwise, it is imprimitive. For instance, the symmetries of a square are imprimitive when acting on its vertices because they preserve the grouping of opposite vertices.

Cayley's theorem

Main article: Cayley's theorem

In mathematics, every group can be seen as a special kind of permutation group. This means that the elements of a group can be rearranged among themselves in a way that follows the group's rules. Specifically, each element of the group acts like a permutation, reshuffling the group's elements.

For instance, if we have a small group with four elements, we can see each element as a way to rearrange these four elements. This idea shows that any group is essentially a permutation group, which is a key insight from Cayley's theorem.

Isomorphisms of permutation groups

When we have two permutation groups acting on different sets, we can say they are "permutation isomorphic" if there is a one-to-one matching between the sets and a matching between the groups that keeps their actions aligned. This means the way the groups move or rearrange their sets looks the same when we carefully match each element.

If the sets are the same, this idea is like the groups being rearrangements of each other within the big group of all possible rearrangements. A special case happens when the groups are the same and the matching between them is the simplest possible — this shows that the group’s actions are equivalent, even if they look different at first. For example, the symmetries of a square can act on its corners or on its triangles in ways that match up perfectly when we correctly pair the corners with the triangles.

Oligomorphic groups

When a group acts on a set, it can also act on combinations of elements from that set. A group is called oligomorphic if, for any number of elements, it has only a limited number of ways to act on those combinations. This idea is mostly used when the set has infinitely many elements.

Oligomorphic groups are interesting because they help us understand certain areas of mathematical logic, especially when studying special kinds of patterns in infinite sets.

History

Main article: History of group theory

The study of groups in mathematics began with the study of permutation groups. In 1770, Lagrange studied permutations as part of solving equations. By the mid-1800s, a detailed theory of permutation groups was developed, mainly through the work of Camille Jordan in his 1870 book. Later, Cayley showed that abstract groups and permutation groups are essentially the same idea. Interest in permutation groups grew again in the 1950s through the work of H. Wielandt.