What is the relationship between groups and permutations? The way I understand it, a permutation is a set of numbers that you can do things with. A group is a set of elements equipped with an operation. So how do they relate?
What operation would a permutation have on it? Do the group axioms apply to permutations?
$\endgroup$ 42 Answers
$\begingroup$A permutation isn't so much a set of numbers you can do things with, as a thing you can do with an ordered set of numbers. In particular, a permutation is a function that rearranges numbers (or other objects). Permutations are the elements in a permutation group, and the operation on the group is composition of those functions. The group axioms apply to sets of permutations with the operation of composition.
That's how permutations give rise to groups. The interesting fact going the other way (Cayley's Theorem) is that every group is isomorphic to a group of permutations. Thus, you can study groups by studying groups of permutations.
$\endgroup$ 5 $\begingroup$G Tony Jacobs' answer is spot on! Every group is isomorphic to a group of permutations. The proof of Cayley's theorem actually constructs a permutation from each group element, which is elegant and informative.
From a combinatorial perspective, groups were made to act on objects. In particular, every group action has a permutation representation. That is, a group action on an object $X$ can be viewed as a homomorphism from the group into $\text{Sym}(X)$. From a more practical perspective, group actions are used to study automorphisms (or symmetries) of objects. That is, the group action should respect the relation(s) of a given object. If a group $G$ is acting on another group $H$, we respect $H$'s operation. If a group is acting on a graph, we want it to respect the adjacency relation. By respecting the underlying relations, group actions become a powerful tool to leverage the symmetry of an object. One example is the study of vertex-transitive graphs. A graph $X$ is vertex transitive if $\text{Aut}(X)$ acts transitively on $V(X)$. The theory of vertex transitive graphs is well-understood. Godsil and Royle's text on Algebraic Graph Theory is a good reference for this.
$\endgroup$
