Permutation group

In mathematics, a permutation group is a special kind of group made from rearrangements of a set. These rearrangements are like shuffling a deck of cards. The group operation in a permutation group is doing one rearrangement after another.

The group of all possible rearrangements 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 a smaller group that is a subgroup of this symmetric group.

An important fact is that, by Cayley's theorem, every group can be shown as a permutation group. This makes permutation groups useful for studying many 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 are used in areas like 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 has a special permutation called the identity permutation, which leaves everything in its original place. 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 show 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 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 write this combination by placing the permutations next to each other. This shows the order in which we do the permutations.

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, 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 rearrange these items in different ways, called permutations. For example, one permutation might swap items 1 and 2 while leaving 3 and 4 where they are. Another might swap 3 and 4 instead. When we combine these swaps, we can change all four items at once.

These permutations form a group because combining them 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 (math)

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 the pieces of a group can be rearranged to follow the group's rules.

Each piece of the group works like a permutation, moving the pieces around.

For example, if we have a small group with four pieces, we can see each piece as a way to rearrange those four pieces. This idea shows that any group is really a permutation group, which is an important idea 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 perfect matching between the sets and a matching between the groups that keeps their actions the same. This means the way the groups move or rearrange their sets looks the same when we match each element correctly.

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 the same, 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 few 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 some parts of mathematical logic, especially when studying special kinds of patterns in large sets.

History

Main article: History of group theory

The study of groups in math started with permutation groups. In 1770, Lagrange looked at permutations while solving equations. By the mid-1800s, Camille Jordan wrote a book in 1870 that helped develop the theory of permutation groups. Later, Cayley showed that abstract groups and permutation groups are really the same idea. Interest in permutation groups grew again in the 1950s because of the work of H. Wielandt.