# 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. Commented Apr 12, 2016 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... Commented Apr 12, 2016 at 19:55
• What was the math behind this? f1∘f2={(1,2),(2,3),(3,1)} Commented Apr 12, 2016 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. Commented Apr 12, 2016 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$. Commented Apr 12, 2016 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}$$
• @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$. Commented Apr 12, 2016 at 20:12
In cycle notation: \begin{alignat}{1} &f_1=(23)\\ &f_2=(13)\\ &f_3=(12)\\ &f_4=(123)\\ &f_5=(132)\\ \end{alignat} By "completing a table etc." they mean to explicty prove that: $$\forall i,j\in A, \exists k\in A \text{ such that } f_if_j=f_k, \text{ or otherwise } f_if_j=()$$ In fact (composition is right to left): \begin{alignat}{1} &f_1^2=()\\ &f_1f_2=(123)=f_4\\ &f_1f_3=(132)=f_5\\ &f_1f_4=(13)=f_2\\ &f_1f_5=(12)=f_3\\ \\ &f_2f_1=(132)=f_5\\ &f_2^2=()\\ &f_2f_3=(123)=f_4\\ &f_2f_4=(12)=f_3\\ &f_2f_5=(23)=f_1\\ \\ &f_3f_1=(123)=f_4\\ &f_3f_2=(132)=f_5\\ &f_3^2=()\\ &f_3f_4=(23)=f_1\\ &f_3f_5=(13)=f_2\\ \\ &f_4f_1=(12)=f_3\\ &f_4f_2=(23)=f_1\\ &f_4f_3=(13)=f_2\\ &f_4^2=(132)=f_5\\ &f_4f_5=()\\ \\ &f_5f_1=(12)=f_3\\ &f_5f_2=(23)=f_1\\ &f_5f_3=(13)=f_2\\ &f_5f_4=()\\ &f_5^2=(123)=f_4\\ \end{alignat} Therefore, every $$f_i$$ has inverse; in particular, $$f_{1,2,3}$$ are self-inverses ("involutions"), whereas $$f_4$$ and $$f_5$$ are inverses each other.