Are disjoint cycles a basis for a permutation? (or can be thought of as)

Question

Assume we write a permutation p as a disjoint cycle. i.e. p=(12)(346)(5).

Can we think of this process as decomposing p into a unique basis of smaller permutations, with $p_1=(12)$, $p_2=(346)$, $p_3=(5)$ being permutations in their own right, that make up p under function composition, regardless of order?

Is this in any way somehow related to disjoint cycles being a basis for the permutation? And if so, do you learn this later? Is it a known point of view?

Answer 1

The set of cycles can be thought of as a ${\bf generating}$ ${\bf set}$ of the group of permutations, i.e. any permutation can be written as a product of cycles. It is the closest thing to a basis for a general group.

However, you need to be careful since basis is something very particular. In general, you don't have unicity of the decomposition for generating set, even though for the permutations and cycles this is the case. I would be inclined to think that drawing too much parallels with basis in linear algebra could be misleading.

An intermediate case between linear algebra and groups, is finitely generated abelian groups, which can be thought of as "$\mathbb{Z}$-vector space" (the rigorous term is $\mathbb{Z}$-module since $\mathbb{Z}$ is not a field) where you get something which can be thought of as a kind of basis.

Fixing a generating set for a group $G$ allows you to :

• draw a Cayley graph for the group,
• compute morphisms from $G$,
• explicit computations with computers (at least for some finitely generated groups).

Answer 2

The decomposition of a permutation into disjoint cycles are unique up to order of cycles and cyclic permutations of numbers appear in presentations of each cycles. (That is, your permutation $(12)(346)(5)$ can be written as $(346)(12)(5)$ and $(12)(463)(5)$, for example.) This feature is closer to being a 'basis' rather than just being a generating set. (Note that permutation groups are slightly richer objects than bare abstract groups.)

Pushing this analogy forward, one might say the 'space' (set) of objects is 'direct sum' (disjoint union) of orbits of a permutation as a vector space is a direct sum of subspaces spanned by vectors of a basis.

The decomposition of integers into prime factors (the fundamental theorem of arithmetic) can be thought of as another analogy, e.g., $2\cdot3^2$ can be written as $3^2\cdot2$.

Anyway, analogy is analogy. It might be a helpful guide how to understand something new, but do not take it too seriously.

Answer 3

There is a way to give meaning to the statement that cycles are a basis for permutations. If you consider the symmetric collection (also known as species) of permutations, call it $P$, and let ${E}$ be the species of sets (i.e. ${E}(I) = \{I\}$ for any $I$), and finally if ${C}$ is the species of cycles over a set, then we have the identity

$$P = E \circ C$$ where $\circ$ is the substitution operation on species. This is simply a restatement that any permutation is uniquely a disjoint union of cycles, put in the form: $P$ is a free left $E$-set with basis $C$ under the composition product. This seems a bit capricious and tautological, but it scales very well if you want to analyse intricate combinatorial phenomena.