At the risk of boggling the reader’s mind, we will now examine groups whose elements are functions. Recall that a permutation on a set \(A\) is a bijection from \(A\) into \(A\text{.}\) Suppose that \(A = \{1, 2, 3\}\text{.}\) There are \(3! = 6\) different permutations on \(A\text{.}\) We will call the set of all 6 permutations \(S_3\text{.}\) They are listed in the following table. The matrix form for describing a function on a finite set is to list the domain across the top row and the image of each element directly below it. For example \(r_1(1) = 2\text{.}\)
The operation that will give \(\left\{i,r_1,r_2,f_1,f_2,f_3\right\}\) a group structure is function composition. Consider the “product” \(r_1\circ f_3\text{:}\)
The images of 1, 2, and 3 under \(r_1\circ f_3\) and \(f_2\) are identical. Thus, by the definition of equality for functions, we can say \(r_1\circ f_3=f_2\) . The complete table for the operation of function composition is given in Table 15.3.2.
We don’t even need the table to verify that we have a group. Based on the following observations, the set of all permutations on any finite set will be a group.
Function composition is always associative.
The identity for the group is \(i\text{.}\) If \(g\) is any one of the permutations on \(A\) and \(x\in A\text{,}\)
A permutation, by definition, is a bijection. In Chapter 7 we proved that this implies that it must have an inverse and the inverse itself is a bijection and hence a permutation. Hence all elements of \(S_3\) have an inverse in \(S_3\text{.}\) If a permutation is displayed in matrix form, its inverse can be obtained by exchanging the two rows and rearranging the columns so that the top row is in order. The first step is actually sufficient to obtain the inverse, but the sorting of the top row makes it easier to recognize the inverse.
For example, let’s consider a typical permutation on \(\{1,2,3,4,5\}\text{,}\)\(f= \left(
\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
5 & 3 & 2 & 1 & 4 \\
\end{array}
\right)\text{.}\)
From Table 15.3.2, we can see that \(S_3\) is non-abelian. Remember, non-abelian is the negation of abelian. The existence of two elements that don’t commute is sufficient to make a group non-abelian. In this group, \(r_1\) and \(f_3\) is one such pair: \(r_1\circ f_3= f_2\) while \(f_3\circ
r_1= f_1\text{,}\) so \(r_1\circ f_3\neq f_3\circ r_1\text{.}\) Caution: Don’t take this to mean that every pair of elements has to have this property. There are several pairs of elements in \(S_3\) that do commute. In fact, the identity, \(i\text{,}\) must commute with everything. Also every element must commute with its inverse.
Definition15.3.5.Symmetric Group.
Let \(A\) be a nonempty set. The set of all permutations on \(A\) with the operation of function composition is called the symmetric group on \(A\text{,}\) denoted \(S_A\text{.}\)
The cardinality of a finite set \(A\) is more significant than the elements, and we will denote by \(S_n\) the symmetric group on any set of cardinality \(n\text{,}\)\(n\geq 1\text{.}\)
Our opening example, \(S_3\text{,}\) is the smallest non-abelian group. For that reason, all of its proper subgroups are abelian: in fact, they are all cyclic. Figure 15.3.7 shows the Hasse diagram for the subgroups of \(S_3\text{.}\)
Figure15.3.7.Lattice diagram of subgroups of \(S_3\)
The only abelian symmetric groups are \(S_1\) and \(S_2\) , with 1 and 2 elements, respectively. The elements of \(S_2\) are \(i = \left(
\begin{array}{cc}
1 & 2 \\
1 & 2 \\
\end{array}
\right)\) and \(\alpha = \left(
\begin{array}{cc}
1 & 2 \\
2 & 1 \\
\end{array}
\right)\text{.}\)\(S_2\) is isomorphic to \(\mathbb{Z}_2\text{.}\)
Theorem15.3.9.
For \(n \geq 1\text{,}\)\(\lvert S_n\rvert =n!\) and for \(n \geq 3\text{,}\)\(S_n\) is non-abelian.
The first part of the theorem follows from the extended rule of products (see Chapter 2). We leave the details of proof of the second part to the reader after the following hint. Consider \(f\) in \(S_n\) where \(f(1) = 2\text{,}\)\(f(2) = 3\text{,}\)\(f(3) = 1\text{,}\) and \(f(j) = j\) for \(3 < j \leq n\text{.}\) Therefore the cycle representation of \(f\) is \((1,2,3)\text{.}\) Now define \(g\) in a similar manner so that when you compare \(f(g(1))\) and \(g(f(1))\) you get different results.
Subsection15.3.2Cycle Notation
A second way of describing a permutation is by means of cycles, which we will introduce first with an example. Consider \(f\in S_8\) defined using the now-familiar matrix notation:
Consider the images of 1 when \(f\) is applied repeatedly. The images \(f(1)\text{,}\)\(f(f(1))\text{,}\)\(f(f(f(1))), \ldots\) are \(8, 3, 7, 1, 8, 3, 7,\ldots\text{.}\) In Figure 15.3.10(a), this situation is represented by a graph with vertices 1, 8, 3, and 7 and shows that the values that you get by repeatedly applying \(f\) cycle through those values. This is why we refer to this part of \(f\) as a cycle of length 4. Of course starting at 8, 3, or 7 also produces the same cycle with only the starting value changing.
Figure15.3.10.Representations of a cycle of length 4
Figure 15.3.10(a) illustrates how the cycle can be represented in a visual manner, but it is a bit awkward to write. Part (b) of the figure presents a more universally recognized way to write a cycle. In (b), a cycle is represented by a list where the image of any number in the list is its successor. In addition, the last number in the list has as its image the first number.
The other elements of the domain of \(f\) are never reached if you start in the cycle \((1,8,3,7)\text{,}\) and so looking at the images of these other numbers will produce numbers that are disjoint from the set \(\{1,8,3,7\}\text{.}\) The other disjoint cycles of \(f\) are (2), (4, 6), and (5). We can express \(f\) as a product of disjoint cycles: \(f= (1, 8, 3, 7)(2)(4, 6)(5)\) or \(f= (1,8,3,7)(4,6)\text{,}\) where the absence of 2 and 5 implies that \(f(2) = 2\) and \(f(5) = 5\text{.}\)
Note15.3.11.Disjoint Cycles.
We say that two cycles are disjoint if no number appears in both cycles, as is the case in our expressions for \(f\) above. Disjoint cycles can be written in any order. Thus, we could also say that \(f=(4,6)(1,8,3,7)\text{.}\)
Note15.3.12.Composition of Permutations.
We will now consider the composition of permutations written in cyclic form by an example. Suppose that \(f
= (1,8, 3, 7)(4, 6)\) and \(g = (1, 5, 6)(8, 3, 7, 4)\) are elements of \(S_8\text{.}\) To calculate \(f\circ g\text{,}\) we start with simple concatenation:
\begin{gather}
f \circ g = (1,8, 3, 7)(4, 6)(1,5,6)(8, 3, 7,4)\tag{15.3.1}
\end{gather}
Although this is a valid expression for \(f \circ g\text{,}\) our goal is to express the composition as a product of disjoint cycles as \(f\) and \(g\) were individually written. We will start by determining the cycle that contains 1. When combining any number of cycles, they are always read from right to left, as with all functions. The first cycle in (15.3.1) does not contain 1; thus we move on to the second. The image of 1 under that cycle is 5. Now we move on to the next cycle, looking for 5, which doesn’t appear. The fourth cycle does not contain a 5 either; so \(f\circ g(1) = 5\text{.}\)
At this point, we would have written “\(f \circ g = (1,5 \)” on paper. We repeat the steps to determine \(f\circ g(5)\text{.}\) This time the second cycle of (15.3.1) moves 5 to 6 and then the third cycle moves 6 to 4. Therefore, \(f\circ g(5) = 4\text{.}\) We continue until the cycle (1, 5, 4, 3) is completed by determining that \(f\circ g(3) = 1\text{.}\) The process is then repeated starting with any number that does not appear in the cycle(s) that have already been completed.
The final result for our example is \(f \circ g = (1, 5, 4, 3)(6, 8, 7)\text{.}\) Since \(f(2) = 2\) and \(g(2) = 2\text{,}\)\(f\circ g(2) = 2\) and we need not include the one-cycle (2) in the final result, although it can be included.
Notice that cyclic notation does not indicate the set which is being permuted. The examples above could be in \(S_5\text{,}\) where the image of 5 is 5. This ambiguity is usually overcome by making the context clear at the start of a discussion.
Definition15.3.14.Transposition.
A transposition is a cycle of length 2.
Observation15.3.15.About transpositions.
\(f= (1, 4)\) and \(g=(4,5)\) are transpositions in \(S_5\text{.}\) However, \(f\circ g = (1,4, 5)\) and \(g \circ f = (1, 5, 4)\) are not transpositions; thus, the set of transpositions is not closed under composition. Since \(f^2=f\circ f\) and \(g^2=g\circ
g\) are both equal to the identity permutation, \(f\) and \(g\) are their own inverses. In fact, every transposition is its own inverse.
Theorem15.3.16.Decomposition into Cycles.
Every cycle of length greater than 2 can be expressed as a product of transpositions.
We need only indicate how the product of transpositions can be obtained. It is easy to verify that a cycle of length \(k\text{,}\)\(\left(a_1, a_2, a_3, \ldots , a_k\right)\text{,}\) is equal to the following product of \(k-1\) transpositions:
Unlike the situation with disjoint cycles, we are not free to change the order of these transpositions.
Subsection15.3.3Parity of Permutations and the Alternating Group
A decomposition of permutations into transpositions makes it possible to classify them and identify an important family of groups.
The proofs of the following theorem appears in many abstract algebra texts.
Theorem15.3.17.
Every permutation on a finite set can be expressed as the product of an even number of transpositions or an odd number of transpositions, but not both.
Theorem 15.3.17 suggests that \(S_n\) can be partitioned into its “even” and “odd” elements. For example, the even permutations of \(S_3\) are \(i\text{,}\)\(r_1=(1,2,3)=(1,3)(1,2)\) and \(r_2=(1,3,2)=(1,2)(1,3)\text{.}\) They form a subgroup, \(\left\{i,r_1,r_2\right\}\) of \(S_3\text{.}\)
In general:
Definition15.3.18.The Alternating Group.
Let \(n \geq 2\text{.}\) The set of even permutations in \(S_n\) is a proper subgroup of \(S_n\) called the alternating group on \(\{1, 2, \ldots, n\}\text{,}\) denoted \(A_n\text{.}\)
We justify our statement that \(A_n\) is a group:
Theorem15.3.19.
Let \(n \geq 2\text{.}\) The alternating group is indeed a group and has order \(\frac{n!}{2}\text{.}\)
In this proof, the symbols \(s_i\) and \(t_i\) stand for transpositions and \(p\text{,}\)\(q\) are even nonnegative integers. If \(f, g \in A_n\text{,}\) we can write the two permutations as products of even numbers of transpositions, \(f=s_1s_2\cdots s_p\) and \(g=t_1t_2\cdots t_q\text{.}\) Then
Since \(p+q\) is even, \(f\circ g \in A_n\text{,}\) and \(A_n\) is closed with respect to function composition. With this, we have proven that \(A_n\) is a subgroup of \(S_n\) by Theorem 11.5.5.
To prove the final assertion, let \(B_n\) be the set of odd permutations and let \(\tau = (1,2)\text{.}\) Define \(\theta: A_n \to B_n\) by \(\theta(f) = f\circ \tau\text{.}\) Suppose that \(\theta(f) = \theta(g)\text{.}\) Then \(f\circ \tau = g\circ \tau \) and by the right cancellation law, \(f = g\text{.}\) Hence, \(\theta\) is an injection. Next we show that \(\theta\) is also a surjection. If \(h \in B_n\text{,}\)\(h\) is the image of an element of \(A_n\text{.}\) Specifically, \(h\) is the image of \(h\circ \tau\text{.}\)
Consider the sliding-tile puzzles pictured in Figure 15.3.21. Each numbered square is a tile and the dark square is a gap. Any tile that is adjacent to the gap can slide into the gap. In most versions of this puzzle, the tiles are locked into a frame so that they can be moved only in the manner described above. The object of the puzzle is to arrange the tiles as they appear in Configuration (a). Configurations (b) and (c) are typical starting points. We propose to show why the puzzle can be solved starting with (b), but not with (c).
Figure15.3.21.Configurations of the sliding tile puzzle
We will associate a change in the configuration of the puzzle with an element of \(S_{16}\text{.}\) Imagine that a tile numbered 16 fills in the gap. For any configuration of the puzzle, the identity \(i\text{,}\) is the function that leave the configurate “as is.” In general, if \(f \in S_{16}\text{,}\) and \(1 \leq k \leq 16\text{,}\)\(f(k)\) is the position to which the tile in position \(k\) is moved by \(f\) that appears in the position of \(k\) in configuration (a). If we call the functions that, starting with configuration (a), result in configurations (b) and (c) by the names \(f_1\) and \(f_2\text{,}\) respectively,
How can we interpret the movement of one tile as a permutation? Consider what happens when the 12 tile of \(i\) slides into the gap. The result is a configuration that we would interpret as \((12,16)\text{,}\) a single transposition. Now if we slide the 8 tile into the 12 position, the result is or \((8, 16, 12)\text{.}\) Hence, by “exchanging” the tiles 8 and 16, we have implemented the function \((8, 12) (12, 16) = (8, 12, 16)\text{.}\)
Figure15.3.22.The configuration \((8, 12, 16)\)
Every time you slide a tile into the gap, the new permutation is a transposition composed with the old permutation. Now observe that to start with initial configuration and terminate after a finite number of moves with the gap in its original position, you must make an even number of moves. Thus, configuration corresponding any permutation that leaves 16 fixed cannot be solved if the permutation is odd. Note that \(f_2\) is an odd permutation; thus, Puzzle (c) can’t be solved. The proof that all even permutations, such as \(f_1\text{,}\) can be solved is left to the interested reader to pursue.
Subsection15.3.4Dihedral Groups
Observation15.3.23.Realizations of Groups.
By now we’ve seen several instances where a group can appear through an isomorphic copy of itself in various settings. The simplest such example is the cyclic group of order 2. When this group is mentioned, we might naturally think of the group \(\left[\mathbb{Z}_2;+_2\right]\text{,}\) but the groups \([\{-1,1\};\cdot ]\) and \(\left[S_2;\circ \right]\) are isomorphic to it. None of these groups are necessarily more natural or important than the others. Which one you use depends on the situation you are in and all are referred to as realizations of the cyclic group of order 2. The next family of groups we will study, the dihedral groups, has two natural realizations, first as permutations and second as geometric symmetries.
The family of dihedral groups is indexed by the positive integers greater than or equal to 3. For \(k \geq 3\text{,}\)\(\mathcal{D}_k\) will have \(2k\) elements. We first describe the elements and the operation on them using geometry.
We can describe \(\mathcal{D}_n\) in terms of symmetries of a regular \(n\)-gon (\(n = 3\text{:}\) equilateral triangle, \(n = 4\text{:}\) square, \(n = 5\text{:}\) regular pentagon,\(\ldots \)). Here we will only concentrate on the case of \(\mathcal{D}_4\text{.}\) If a square is fixed in space, there are several motions of the square that will, at the end of the motion, not change the apparent position of the square. The actual changes in position can be seen if the corners of the square are labeled. In Figure 15.3.24, the initial labeling scheme is shown, along with the four axes of symmetry of the square.
Figure15.3.24.Axes of symmetry of the square
It might be worthwhile making a square like this with a sheet of paper. Be careful to label the back so that the numbers match the front. Two motions of the square will be considered equivalent if the square is in the same position after performing either motion. There are eight distinct motions. The first four are \(0{}^{\circ}\text{,}\)\(90{}^{\circ}\text{,}\)\(180{}^{\circ}\text{,}\) and \(270{}^{\circ}\) clockwise rotations of the square, and the other four are the \(180{}^{\circ}\) flips along the axes \(l_1\text{,}\)\(l_2\text{,}\)\(l_3\text{,}\) and \(l_4\text{.}\) We will call the rotations \(i, r_1\text{,}\)\(r_2\text{,}\) and \(r_3\text{,}\) respectively, and the flips \(f_1\text{,}\)\(f_2\text{,}\)\(f_3\text{,}\) and \(f_4\text{,}\) respectively. Figure 15.3.25 illustrates \(r_1\) and \(f_1\text{.}\) For future reference, we also include the permutations to which they correspond.
Figure15.3.25.Two elements of \(\mathcal{D}_4\)
What is the operation on this set of symmetries? We will call the operation “followed by” and use the symbol \(*\) to represent it. The operation will be to combine motions, applying motions from right to left, as with functions. We will illustrate how \(*\) is computed by finding \(r_1*f_1\text{.}\) Starting with the initial configuration, if you perform the \(f_1\) motion, and then immediately perform \(r_1\) on the result, we get the same configuration as if we just performed \(f_4\text{,}\) which is to flip the square along the line \(l_4\text{.}\) Therefore, \(r_1*f_1 = f_4\text{.}\) An important observation is that \(f_1*r_1 \neq f_4\text{,}\) meaning that this group is nonabelian. The reader is encouraged to verify this on their own.
We can also realize the dihedral groups as permutations. For any symmetric motion of the square we can associate with it a permutation. In the case of \(\mathcal{D}_4\text{,}\) the images of each of the numbers 1 through 4 are the positions on the square that each of the corners 1 through 4 are moved to. For example, since corner 4 moves to position 1 when you perform \(r_1\text{,}\) the corresponding function will map 4 to 1. In addition, 1 gets mapped to 2, 2 to 3 and 3 to 4. Therefore, \(r_1\) is the cycle \((1,2,3,4)\) . The flip \(f_1\) transposes two pairs of corners and corresponds to \((1,4)(2,3)\text{.}\) If we want to combine these two permutations, using the same names as with motions, we get
You might notice that we use a script \(D\text{,}\)\(\mathcal{D}\text{,}\) for the dihedral groups. Occasionally you might see an ordinary \(D\) in other sources for the dihedral groups. Don’t confuse it with the set of divisors of \(n\text{,}\) which we denote by \(D_n\text{.}\) Normally the context of the discussion should make the meaning of \(D_n\) clear.
An application of \(\mathcal{D}_4\) is in the design of a letter-facing machine. Imagine letters entering a conveyor belt to be postmarked. They are placed on the conveyor belt at random so that two sides are parallel to the belt. Suppose that a postmarker can recognize a stamp in the top right corner of the envelope, on the side facing up. In Figure 15.3.29, a sequence of machines is shown that will recognize a stamp on any letter, no matter what position in which the letter starts. The letter \(P\) stands for a postmarker. The letters \(R\) and \(F\) stand for rotating and flipping machines that perform the motions of \(r_1\) and \(f_1\text{.}\)
Figure15.3.29.A letter facer
The arrows pointing up indicate that if a letter is postmarked, it is taken off the conveyor belt for delivery. If a letter reaches the end, it must not have a stamp. Letter-facing machines like this have been designed (see [16]). One economic consideration is that \(R\)-machines tend to cost more than \(F\)-machines. \(R\)-machines also tend to damage more letters. Taking these facts into consideration, the reader is invited to design a better letter-facing machine. Assume that \(R\)-machines cost \(\$800\) and \(F\)-machines cost \(\$500\text{.}\) Be sure that all corners of incoming letters will be examined as they go down the conveyor belt.
Write \(f\text{,}\)\(g\text{,}\) and \(h\) from Exercise 1 as products of disjoint cycles and determine whether each is odd or even.
3.
Do the left cosets of \(A_3=\left\{i,r_1,r_2\right\}\) over \(S_3\) form a group under the induced operation on left cosets of \(A_3\text{?}\) What about the left cosets of \(\left\langle f_1\right\rangle\text{?}\)
\(S_3/A_3\) is a group of order two. The operation on left cosets of \(H=\left\langle f_1\right\rangle\) is not well defined and so a group cannot be formed from left cosets of \(H\text{.}\)
4.
In its realization as permutations, the dihedral group \(\mathcal{D}_3\) is equal to \(S_3\text{.}\) Can you give a geometric explanation why? Why isn’t \(\mathcal{D}_4\) equal to \(S_4\text{?}\)
5.
Complete the list of elements of \(\mathcal{D}_4\) and write out a table for the group in its realization as symmetries.
List the subgroups of \(\mathcal{D}_4\) in a lattice diagram. Are they all cyclic? To what simpler groups are the subgroups of \(\mathcal{D}_4\) isomorphic?
\begin{equation*}
\begin{array}{c|c}
\circ & \textrm{ }
\begin{array}{cccccccc}
i & r & r^2 & r^3 & f_1 & f_2 & f_3 & f_4 \\
\end{array}
\\
\hline
\begin{array}{c}
i \\
r \\
r^2 \\
r^3 \\
f_1 \\
f_2 \\
f_3 \\
f_4 \\
\end{array}
&
\begin{array}{cccccccc}
i & r & r^2 & r^3 & f_1 & f_2 & f_3 & f_4 \\
r & r^2 & r^3 & i & f_4 & f_3 & f_1 & f_2 \\
r^2 & r^3 & i & r & f_2 & f_1 & f_4 & f_3 \\
r^3 & i & r & r^2 & f_3 & f_4 & f_2 & f_1 \\
f_1 & f_3 & f_2 & f_4 & i & r^2 & r & r^3 \\
f_2 & f_4 & f_1 & f_3 & r^2 & i & r^3 & r \\
f_3 & f_2 & f_4 & f_1 & r^3 & r & i & r^2 \\
f_4 & f_1 & f_3 & f_2 & r & r^3 & r^2 & i \\
\end{array}
\\
\end{array}
\end{equation*}
A lattice diagram of its subgroups is
Figure15.3.30.Subgroups of \(\mathcal{D}_4\)
All proper subgroups are cyclic except \(\left\{i,r^2,f_1,f_2\right\}\)\(\textrm{ }\textrm{ }\)and \(\left\{i,r^2,f_3,f_4\right\}\text{.}\) Each 2-element subgroup is isomorphic to \(\mathbb{Z}_2\) ; \(\left\{i,r,r^2,r^3\right\}\) is isomorphic to \(\mathbb{Z}_4\) ; and \(\left\{i,r^2,f_1,f_2\right\}\)\(\textrm{ }\textrm{ }\)and \(\left\{i,r^2,f_3,f_4\right\}\) are isomorphic to \(\mathbb{Z}_2\times \mathbb{Z}_2\text{.}\)
6.
Design a better letter-facing machine (see Example 15.3.28). How can you verify that a letter-facing machine does indeed check every corner of a letter? Can it be done on paper without actually sending letters through it?
7.
Prove by induction that if \(r \geq 1\) and each \(t_i\text{,}\) is a transposition, then \(\left(t_1\circ t_2\circ \cdots \circ t_r\right){}^{-1}=t_r\circ \cdots \circ t_2\circ t_1\)
One solution is to cite Exercise 3 at the end of Section 11.3. It can be directly applied to this problem. An induction proof of the problem at hand would be almost identical to the proof of the more general statement. \(\left(t_1t_2\cdots t_r\right){}^{-1}= t_r{}^{-1}\cdots t_2{}^{-1}t_1{}^{-1}\quad\textrm{ by Exercise 3 of Section 11.3}\\
\\
\quad \quad = t_r\cdots t_2t_1\textrm{ }\textrm{ since} \textrm{ each} \textrm{ transposition} \textrm{ inverts} \textrm{ itself}.\textrm{ }\blacksquare\)
8.
How many elements are there in \(\mathcal{D}_5\) ? Describe them geometrically.
Part I: That \(\lvert S_k \rvert = k!\) follows from the Rule of Products.
Part II: Let \(f\) be the function defined on \(\{1,2,\textrm{ ...}, n\}\) by \(f(1)=2\text{,}\)\(f(2)=3\text{,}\)\(f(3)=1\text{,}\) and \(f(j) =j\) for \(4\leq j\leq n\text{;}\) and let \(g\) be defined by \(g(1) = 1\text{,}\)\(g(2) = 3\text{,}\)\(g(3) = 2\text{,}\) and \(g(j) =j\) for \(4\leq j\leq n\text{.}\) Note that \(f\) and \(g\) are elements of \(S_n\text{.}\) Next, \((f\circ g)(1) = f(g(1)) = f(1) = 2\text{,}\) while \((g \circ f)(1) = g(f(1)) = g(2) =
3\text{,}\) hence \(f\circ g\neq g\circ f\) and \(S_n\) is non-abelian for any \(n \geq 3\text{.}\)
10.
How many left cosets does \(A_n\text{,}\)\(n\geq 2\) have?
11.
Prove that \(f\circ r= r^{n-1}\circ f\) in \(\mathcal{D}_n\text{.}\)
12.
Prove that the tile puzzles corresponding to \(A_{16}\cap \left\{ \left.f \in S_{16} \right| f(16) = 16\right\}\) are solvable.
If \(f(16)\neq 16\text{,}\) how can you determine whether \(f\)’s puzzle is solvable?
13.
Prove that \(S_3\) is isomorphic to \(R_3\text{,}\) the group of \(3 \times 3\) rook matrices (see Section 11.2 exercises).
Prove that for each \(n \geq 2\text{,}\)\(R_n\) is isomorphic to \(S_n\text{.}\)
Both groups are non-abelian and of order 6; so they must be isomorphic, since only one such group exists up to isomorphism. The function \(\theta:S_3\to R_3\) defined by \(\begin{array}{cc}
\theta(i)=I & \theta\left(f_1\right)=F_1 \\
\theta\left(r_1\right)=R_1 & \theta\left(f_2\right)=F_2 \\
\theta\left(r_2\right)=R_2 & \theta\left(f_3\right)=F_3 \\
\end{array}\) is an isomorphism,
Recall that since every function is a relation, it is natural to translate functions to Boolean matrices. Suppose that \(f\in S_n\text{.}\) We will define its image, \(\theta(f)\text{,}\) by
