2
$\begingroup$

Let $f$ and $g$ be permutations such that

$$f \circ f = id,$$

$$g \circ g = id,$$

and

$$f\circ g =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 4 & 5 & 7 & 8 & 9 & 2 & 6 & 3 & 1 \end{pmatrix}.$$

Find $f$ and $g$.

I can solve it by a lot of guess work, but I wonder if there is some general method.

$\endgroup$
  • 2
    $\begingroup$ When I tried doing a quick program to find solutions by brute force, it seems to have found 30 solutions total. $\endgroup$ – Daniel Schepler Dec 11 '18 at 1:32
  • $\begingroup$ I suggest you accept answers to your previous questions also, especially one of the answers to this one. $\endgroup$ – Shaun Dec 11 '18 at 1:43
  • $\begingroup$ @DanielSchepler, your calculation agree with my solutions. As you can see from my answers the number of ways of choosing $f$ is $2\times 3\times 5=30$. $\endgroup$ – user9077 Dec 11 '18 at 2:22
2
$\begingroup$

A permutation $f$ is an involution if $f\circ f=id$.

As you know, any permutation can be written as a product of disjoint cycles; your permutation is $(1\ 10)(2\ 4\ 7)(3\ 5\ 8\ 6\ 9)$. In order to write an arbitrary permutation as a product of two involutions, it suffices (since disjoint permutations commute) to write a cycle of arbitrary length as a product of two involutions. A permutation is an involution if it's a product of disjoint cycles of length $2$. If you experiment a little with multiplying involutions, you might discover the following pattern: $$(1\ 2)\circ(2\ 3)=(1\ 2\ 3)\tag3$$ $$(1\ 2)(3\ 4)\circ(2\ 3)=(1\ 2\ 4\ 3)\tag4$$ $$(1\ 2)(3\ 4)\circ(2\ 3)(4\ 5)=(1\ 2\ 4\ 5\ 3)\tag5$$ $$(1\ 2)(3\ 4)(5\ 6)\circ(2\ 3)(4\ 5)=(1\ 2\ 4\ 6\ 5\ 3)\tag6$$ etc. So a cycle of any length can be obtained by multiplying two involutions. In particular, replacing $1,2,3$ by $2,4,7$ in $(3)$ we get $$(2\ 4\ 7)=(2\ 4)\circ(4\ 7);$$ replacing $1,2,4,5,3$ by $3,5,8,6,9$ in $(5)$ we get $$(3\ 5\ 8\ 6\ 9)=(3\ 5)(9\ 8)\circ(5\ 9)(8\ 6)=(3\ 5)(8\ 9)\circ(5\ 9)(6\ 8);$$ and of course $$(1\ 10)=(1\ 10)\circ id;$$ so $$(1\ 10)(2\ 4\ 7)(3\ 5\ 8\ 6\ 9)=(1\ 10)(2\ 4)(3\ 5)(8\ 9)\circ(4\ 7)(5\ 9)(6\ 8).$$

I.e., you can take $$f=(1\ 10)(2\ 4)(3\ 5)(8\ 9),\ g=(4\ 7)(5\ 9)(6\ 8).$$ Of course there are other solutions.

$\endgroup$
  • $\begingroup$ Your answer is essentially what I had in mind, @bof. Do you agree? $\endgroup$ – Shaun Dec 11 '18 at 2:58
  • $\begingroup$ @Shaun I don't know what you had in mind, but I'll take your word for it. By the way, I thought an "idempotent" was an element $a$ satisfying $a^2=a$. So in a group the only idempotent is the identity element. $\endgroup$ – bof Dec 11 '18 at 3:05
  • $\begingroup$ Thank you, @bof; and you're right: I meant involution of course. Here in England, it was late when I first wrote the answer and late when I came back to it. That's my excuse, anyway. $\endgroup$ – Shaun Dec 11 '18 at 3:08
2
$\begingroup$

There is a well-known algorithm for decomposing any given permutation as a product of (not necessarily disjoint) $2$-cycles/transpositions. Such a decomposition of a given $f\circ g$ would, in general, give strong hints about (if not completely determine) the nature of $f$ and $g$.

Why?

Because here $f,g$ are involutions: they square to the identity. Thus they're each (either trivial or) determined by a product of disjoint $2$-cycles (a.k.a. transpositions) (although they may share one or more of those cycles), which are themselves involutions.


See @bof's answer for the same approach, fleshed out.

$\endgroup$
  • 1
    $\begingroup$ Well what you are saying is true. But here apart from $f$ and $g$ are idempotent we don't know yet what they are. So we can not apply the algorithm to decompose $f$ and $g$ into transpositions. So I don't see how the algorithm help you in this problem. $\endgroup$ – user9077 Dec 11 '18 at 1:48
  • $\begingroup$ You're right, @user9077; thank you. The order of the paragraphs is backward (modulo some minor editing). Give me a minute . . . $\endgroup$ – Shaun Dec 11 '18 at 1:51
  • $\begingroup$ Is it okay now, @user9077? (For reference: Here's how it used to look.) $\endgroup$ – Shaun Dec 11 '18 at 1:53
  • $\begingroup$ I am not sure Shaun. Just give it a try if you can solve this particular problem using the idea that you have in your mind. $\endgroup$ – user9077 Dec 11 '18 at 2:16
  • $\begingroup$ It's essentially bof's answer, @user9077. $\endgroup$ – Shaun Dec 11 '18 at 2:56
2
$\begingroup$

Here is how I did it. First write $f\circ g$ as a product of disjoint cycles. So here $f\circ g=(1\, 10)(2\,4\,7)(3\,5\,8\,6\,9)$. Now

$$\begin{align} g\circ f &=f\circ(f\circ g)\circ f \\ &=f\circ(f\circ g)\circ f^{-1} \\ &=(f(1)\,f(10))(f(2)\, f(4)\,f(7))(f(3)\,f(5),f(8)\,f(6)\,f(9)). \end{align}$$

On the other hand $(f\circ g)^{-1}=g^{-1}\circ f^{-1}=g\circ f$. So from the provided $f\circ g$ we can invert it to get $g\circ f$ which is $$(1\,10)(2\,7\,4)(3\,9\,6\,8\,5)$$

Therefore $$(f(1)\,f(10))(f(2)\, f(4)\,f(7))(f(3)\,f(5),f(8)\,f(6)\,f(9))=(1\,10)(2\,7\,4)(3\,9\,6\,8\,5)$$ and we can define $f$ to satisfy this (notice $f$ is not unique). After this you can find your $g$.

$\endgroup$
  • $\begingroup$ Thanks for the edit Shaun. Do you happen to know my friend Hadi Susanto? :D $\endgroup$ – user9077 Dec 11 '18 at 14:47
  • $\begingroup$ You're welcome, @user9077. I believe he and I had a brief conversation last year, yeah; I don't know if he remembers it though. He seems friendly. By the way, I nearly missed your comment as you didn't use the @ thing (like I did in this comment with your username). Please be sure to use it in future :) $\endgroup$ – Shaun Dec 13 '18 at 4:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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