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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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