# Show that each composite function $f_i \circ f_j$ is one of the given functions

I'm just going through the problems that I got wrong on my discrete math exam, and I was not sure how to do this one. How would I go about making this chart? The chart has $f_1, \dots, f_5$ going across the top and down the side. I already got the question wrong, just want to know how to do it, in case it comes up again.

Let $A = \{1,2,3\}$ and define $f_1,f_2,f_3,f_4,f_5 \colon A \to A$ as follows: \begin{align} f_1 &= \{(1,1),(2,3),(3,2)\} \\ f_2 &= \{(1,3),(2,2),(3,1)\} \\ f_3 &= \{(1,2),(2,1),(3,3)\} \\ f_4 &= \{(1,2),(2,3),(3,1)\} \\ f_5 &= \{(1,3),(2,1),(3,2)\} \end{align} Show that each composite function $f_i\circ f_j$ is one of the given functions, or the identity, by completing a table. Find the inverse of those six functions that have inverses.

• Changing the second f_i to $f_j$ is a substantial change that shouldn't have gone without input from the OP. – Eric Stucky Apr 12 '16 at 19:54
• Yes, make a square table with the $f_i$ indexing the rows and columns. The entry for row $f_1$ and column $f_2$ will be $f_1\circ f_2 = \{(1,2),(2,3),(3,1)\} = f_4$, and the entry with row $f_2$ and column $f_1$ will be $f_2\circ f_1 = \{(1,3),(2,1),(3,2)\} = f_5$ and so on... – John Martin Apr 12 '16 at 19:55
• What was the math behind this? f1∘f2={(1,2),(2,3),(3,1)} – Jebus Crust Apr 12 '16 at 19:58
• @EricStucky “The table has $f_1,\dots,f_5$ going across the top and down the side”; I think that all compositions are to be taken into account. – egreg Apr 12 '16 at 20:00
• for the inverse, switch left and right elements of each pair. For example $f_4(3)=1$, hence the inverse $f_4^{-1}(1)=3$. So $(3,1)\in f_4$, hence $(1,3)\in f_4^{-1}$. If $f_4=\{(1,2),(2,3),(3,1)\}$ then $f_4^{-1}=\{(2,1),(3,2),(1,3)\}=\{(1,3),(2,1),(3,2)=f_5$. – Mirko Apr 12 '16 at 20:46

If $f_0=\{(1,1),(2,2),(3,3)\}$ is the identity map, the six maps $\{f_0,f_1,f_2,f_3,f_4,f_5\}$ are six bijective maps $A\to A$.

Since $|A|=3$, there are exactly $6=3!$ bijective maps $A\to A$, so the above set is the set of all permutations of $A$. Since the composition of two bijective maps is a bijective map, $f_i\circ f_j$ must belong to the set for any $i,j$, with $0\le i,j\le 5$.

You can fill in the composition table by hand. Some of the compositions are here: $$\begin{array}{c|cccccc} & f_0 & f_1 & f_2 & f_3 & f_4 & f_5 \\ \hline f_0 & & & & & & \\ f_1 & & & & & & \\ f_2 & & f_5 & & & & \\ f_3 & & & & & & \\ f_4 & & & f_1 & & & \\ f_5 & & & & & & \end{array}$$

• The part you explained makes sense to me, but I still do not understand how you are filling in that chart? – Jebus Crust Apr 12 '16 at 20:08
• @JebusCrust Composition of maps; $f_2\circ f_1(1)=f_2(1)=3$, $f_2\circ f_1(2)=f_2(3)=1$, $f_2\circ f_1(3)=f_2(2)=2$; therefore $f_2\circ f_1=f_5$. – egreg Apr 12 '16 at 20:12