# Find $f,g$ s.t. $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}.$

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.

• When I tried doing a quick program to find solutions by brute force, it seems to have found 30 solutions total. – Daniel Schepler Dec 11 '18 at 1:32
• I suggest you accept answers to your previous questions also, especially one of the answers to this one. – Shaun Dec 11 '18 at 1:43
• @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$. – user9077 Dec 11 '18 at 2:22

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.

• Your answer is essentially what I had in mind, @bof. Do you agree? – Shaun Dec 11 '18 at 2:58
• @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. – bof Dec 11 '18 at 3:05
• 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. – Shaun Dec 11 '18 at 3:08

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.

• 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. – user9077 Dec 11 '18 at 1:48
• You're right, @user9077; thank you. The order of the paragraphs is backward (modulo some minor editing). Give me a minute . . . – Shaun Dec 11 '18 at 1:51
• Is it okay now, @user9077? (For reference: Here's how it used to look.) – Shaun Dec 11 '18 at 1:53
• 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. – user9077 Dec 11 '18 at 2:16
• It's essentially bof's answer, @user9077. – Shaun Dec 11 '18 at 2:56

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$$.

• Thanks for the edit Shaun. Do you happen to know my friend Hadi Susanto? :D – user9077 Dec 11 '18 at 14:47
• 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 :) – Shaun Dec 13 '18 at 4:25