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.


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

  1. What does it mean to be a transitive permutation group?
  2. Show that $\sigma(a)\ne a,\forall\sigma\in G-\{1\}$ and all $a\in A$.where $G$ is abelian, transitive subgroup of $S_A$
  3. Show that any abelian transitive subgroup of $S_n$ has order $n$
  4. Showing that a transitive abelian permutation group is necessarily regular
  5. how many abelian transitive subgroups of $S_{n}$
  6. Every Transitive Permutation Group Has a Fixed Point Free Element
  • 1
    $\begingroup$ 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. $\endgroup$
    – arkeet
    Commented Jul 9 at 23:50
  • 1
    $\begingroup$ Are you asking whether every non-identity element of $\langle S\rangle$ has no fixed points? $\endgroup$
    – Zoe Allen
    Commented Jul 9 at 23:53
  • $\begingroup$ @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. $\endgroup$
    – nightshade
    Commented Jul 9 at 23:55
  • 5
    $\begingroup$ $(354) \in \langle (12)(345) \rangle$ $\endgroup$
    – Zoe Allen
    Commented Jul 9 at 23:58
  • $\begingroup$ @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. $\endgroup$
    – nightshade
    Commented Jul 10 at 0:12

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – nightshade
    Commented Jul 10 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .