4
$\begingroup$

Given an integer $k\geq 2$, do there exist $k$ permutations $\pi_1,...,\pi_n$ which are non identities such that composing all permutations (multiplying) in any order always results in the identity permutation?

For $k=2$, i figured that the answer is yes because i can pick a random permutation and find its inverse and its done. Also, for $k>2$ and even, i can form a pair with a permutation and its inverse and so I end up having composition of identities. However, what about $k>2$ and odd??

$\endgroup$
3
  • $\begingroup$ I don't quite understand. Pick $k-1$ permutations, their product is a permutation. Whatever that is, find its inverse, make that the $k$th permutation, and their product should be the identity. $\endgroup$ May 1, 2017 at 18:19
  • $\begingroup$ @Justin i think i meed to be more clear. I meant that the permutations would give you an identity in any order $\endgroup$ May 1, 2017 at 18:21
  • $\begingroup$ @Justin which makes my solution for $k>2$ and even wrong. $\endgroup$ May 1, 2017 at 18:23

1 Answer 1

3
$\begingroup$

Yes. There are two approaches. In the spirit of your pairing, not that on three elements you can go $(1\ 2\ 3)\to (2\ 1\ 3) \to (3\ 1 \ 2)$ and permute back to $(1\ 2\ 3)$. Now for a large odd number, do this once and as many pairs as needed.

Another way is to pick $n-2$ permutations at random. Pick the $n-1$st not to be the inverse of the product, so the product of the first $n-1$ is not the identity. It will be a permutation and have an inverse in the permutation group, so take that inverse for the last permutation.

Now that you require the permutations be multiplied in any order, your solution for even works as long as you can reuse permutations. Take $k/2$ copies of a permutation and $k/2$ copies of its inverse. As elements of a group commute with their inverses, you can multiply these in any order to get the identity. If you have at least five elements you can do odd. Take three copies of the rotation of three elements and $k-3$ copies of the swap of elements four and five. As these are disjoint, they commute. If you want to avoid reusing permutations, even still works if you have enough elements. Take a pair of a permutation of three elements and its inverse $k/2$ times with the pairs affecting pairwise disjoint sets of elements. I don't know if you can do odd in any order without reuse.

$\endgroup$
4
  • $\begingroup$ @RossMilikan do these permutations lead to the identity regardless of the order we compose them? $\endgroup$ May 1, 2017 at 18:26
  • $\begingroup$ No, but see my last paragraph. $\endgroup$ May 1, 2017 at 18:28
  • $\begingroup$ @RossMilikan I am guessing your argument can be generalized for not only just 3 correct? For example, if i have enough elements, get the rotations of for example 5 elements and the remaining permutations to be rotations any other elements other than 1-5? $\endgroup$ May 1, 2017 at 18:40
  • $\begingroup$ I don't know that without reusing permutations you can find three (or any odd number) that can be multiplied in any order to get the identity. My argument for 3 used the same permutation three times. $\endgroup$ May 1, 2017 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.