# Just the question

Let $$S = \{\sigma_j\}_{j=0}^M$$ be a set of permutations over $$n$$ elements that (i) have identity $$\sigma_0 = I$$, (ii) commute, and (iii) have no fixed points, i.e., $$\sigma (i) \neq i$$ for all $$I \neq \sigma \in S$$ and $$i \in \{0, \ldots, n-1\}$$.

Can we show that $$\langle S \rangle$$ is an Abelian group such that $$I \neq \sigma \in \langle S \rangle$$ has no fixed points? I'm pretty sure this is equivalent to saying $$\langle S \rangle$$ is also transitive (hence title and see also), but I can change the title if I am wrong.

## Context

My background is in quantum information, and I am interested in translating and simplifying various arguments of the so-called "Permutation matrix representation" form (see Eq. 1 and Appendix A in arXiv:1908.03740v). A discussion beyond the link seems like an unnecessary digression, but I am happy to provide more context if desired. But as a meta point, my group theory is very primitive (hence my proof attempt below), but I don't mind answers that use sophisticated results---though I would request a link to a reference, if possible.

## My attempt at a proof

We can show $$\langle S \rangle$$ is an Abelian group in two steps. First, let $$A = \{\sigma_0^{k_0} \ldots \sigma_M^{k_M}: k_i$$ non-negative integers$$\}$$ and $$\sigma, \sigma' \in A$$. Clearly, $$\sigma \sigma' = \sigma' \sigma \in A$$. Second, since $$\sigma \sigma^{-1} = I$$, then $$\sigma \sigma^{-1} \sigma' = \sigma' \sigma \sigma^{-1}$$ which implies $$\sigma^{-1} \sigma' = \sigma' \sigma^{-1}$$. Together, this shows we can write $$\langle S \rangle = \{\sigma_0^{k_0} \ldots \sigma_M^{k_M}: k_i \in Z\}$$, and hence, that $$\langle S \rangle$$ is an Abelian subgroup of $$S_n$$.

My problem is that my attempts to show $$I \neq \sigma \in \langle S \rangle$$ has no fixed points requires I already know the group is transitive and vice versa. In particular, suppose $$\sigma$$ has a fixed point. Then $$\sigma \sigma' (i) = \sigma' (i)$$ by assumption. If we can choose $$\sigma'$$ such that $$\sigma'(i)$$ hits all $$k \in \{0, \ldots, n-1\}$$, then we get that $$\sigma = I$$ which is a contradiction.

Since the above doesn't seem to work, is there an alternative approach, i.e., to show that $$| \langle S \rangle | = n$$ and that that + being Abelian is already enough? (see this post?) Or is my hope wrong from the start?

### Relevant Stack Exchange posts

• If $n = 2p$ with $p$ prime, and $\sigma$ is a product of two disjoint $p$-cycles (e.g. $n=6, \sigma=(1\,2\,3)(4\,5\,6)$), then no power of $\sigma$ except the identity has a fixed point, yet $\langle \sigma \rangle$ is not transitive. So I don't think your assertion of equivalence is true. Commented Jul 9 at 23:50
• Are you asking whether every non-identity element of $\langle S\rangle$ has no fixed points? Commented Jul 9 at 23:53
• @ZoeAllen Yes, that is what I ultimately what I want to show (if it's true at all). From arkeet's point, it seems being transitive is a red-herring. Commented Jul 9 at 23:55
• $(354) \in \langle (12)(345) \rangle$ Commented Jul 9 at 23:58
• @ZoeAllen Well, that's that in general, it seems. Would the question be more interesting and still solvable if I asked what additional constraints does S need for non-identity elements of $\langle S \rangle$ to have no fixed points? For some domain context, I was misled because I was focusing on S being a set of Pauli X strings (en.wikipedia.org/wiki/Pauli_matrices) (i.e. tensor products of X and 2 x 2 identity) where things do work out. Commented Jul 10 at 0:12

It is difficult for permutation actions to have the property that no non-identity element has fixed points. This property is called being free, and for a group $$G$$ acting on a set $$X$$ it is equivalent to any of the following conditions:

1. Every orbit is isomorphic to $$G$$ acting on itself by left multiplication.
2. $$X$$ admits a cartesian product decomposition $$G \times Y$$ where $$Y$$ is some other set (which can be identified with the set of orbits) and $$G$$ acts on the left factor by left multiplication.
3. Every stabilizer subgroup $$G_x = \{ g \in G : gx = x \}$$ is trivial.

In particular, if $$G$$ and $$X$$ are both finite, a necessary condition for $$X$$ to be free is that $$|G|$$ divides $$|X|$$.

I don't know any conditions on a set of permutations guaranteeing that they generate a group that acts freely; basically the issue, as you've run into, is that it's hard to control how many fixed points a complicated product of your generators has. Abelianness doesn't really seem to make it easier either, as far as I can tell. If you'd like to make progress on this it would help to get a lot more specific about what specific sets of permutations you're interested in.

Edit: Here is another necessary condition. When a group acts freely every element $$g$$ of the group has to have a cycle decomposition in which every cycle has the same length, namely the order of $$g$$. So at a minimum the generators need to have this property.

• I accepted this because it answers the question while providing useful links to related concepts I found helpful. I will think about what specific properties I can give the permutations, and if I run into trouble in the restricted case, I will open a separate question. Commented Jul 10 at 20:20