Conjugation

Definition 5.11.1   : If $g, h$ are two elements of a group $G$ then we call the element

$$g^h = h^{-1}*g*h$$

the conjugation of $g$ by $h$.

Note that $g^h=g$ if and only if $g, h$ commute. Thus the conjugates may be regarded as a rough measurement of the lack of commutativity.

Definition 5.11.2   : We say two elements $g_1, g_2$ of $G$ are conjugate if there is an element $h \in G$ such that $g_2=g_1^h$.

For those who have had some linear algebra, it may be helpful to think of the following. If $G$ is a group given as a collection of matrices (i.e., as a subgroup of $GL(n,\mathbb{R})$), then $g_1$ and $g_2$ are conjugate if they represent the same linear transformation - but with respect to two different bases. If $g_2=g_1^h$ then the two bases are: the standard basis and the basis given by the columns of $h$. (For a proof of this, see almost any text in linear algebra, for example [NJ].) We will illustrate the possible advantage of thinking this way in a moment. It turns out that it is easy to see when two permutations $g_1,g_2\in S_n$ are conjugate: they are conjugate if and only if the cycles in their respective disjoint cycle decompositions have the same length when arranged from shortest to longest. (The proof of this is left as an exercise.) For example, the elements

$$g_1=(6,9)(1,3,4)(2,5,7,8),\ \ \ \ \ \ \ \ \ g_2=(1,2)(3,4,5)(6,7,8,9)$$

are conjugate. Our comment above helps understand intuitively why $g_1$ and $g_2$ are conjugate: $g_1$ and $g_2$ are conjugate because the associated permutation matrix $P(g_2)$ ``represents the same operation as $P(g_1)$'', but with respect to a different basis. Notation: The set of equivalence classes of $G$ under the equivalence relation given by conjugation, will be denoted $G_*$. In [Si], §5.10D, D. Singmaster asks for the possible orders of the elements of the Rubik's cube group and how many elements of each order there are. This question of Singmaster motivates the following: Problem: Determine $p_G(t)$ for the Rubik's cube group.

Example 5.11.3   For $S_8$, the generating polynomial is

$$t+4t^2+2t^3+4t^4+t^5+5t^6+t^7+t^8+t^{10}+t^{12}+t^{15}$$

and for $S_{12}$ it is

$$\begin{array}{c} t+6t^2+4t^3+9t^4+2t^5+16t^6+t^7+4t^8+2t^9... ...\\ t^{24}+t^{28}+3t^{30}+t^{35}+t^{42}+t^{60}. \end{array}$$

(Both of these calculations were performed by MAPLE.) For example, it follows that there is an even permutation of order $42$ in $S_{12}$ and an odd permutation of order $15$ in $S_8$. Singmaster [Si] states that the maximal order in the Rubik's cube group is 1260. J. Butler found the following move of this order: $m=RU^2D^{-1}BD^{-1}$ (see [B], page 51, for another simple move of order $1260$). So, even though the size of the Rubik's cube group is enormous, about $4.3\times 10^{19}$, there are no moves of order more than $1.3\times 10^3$.

Definition 5.11.4   : Fix an element $g$ in a group $G$. The set

$$Cl(g)= Cl_G(g)= \{ h^{-1}*g*h \ \vert\ h \in G \}$$

is called the conjugacy class of $g$ in $G$. It is the equivalence class of the element $g$ under the relation given by conjugation.

Note that if $g_1\in G$ is conjugate to $g_2\in G$ then $Cl(g_1)=Cl(g_2)$. The polynomial

$$p_G(t)=\sum_{g\in G_*}t^{ord(g)},$$

is called the generating polynomial of the order function on $G$.

Theorem 5.11.5   Any finite group may be partitioned into its distinct conjugacy classes,

$$G=\cup_{g\in G_*}Cl(g).$$

If $H$ is a subgroup of $G$ and if $g$ is a fixed element of $G$ then the set

$$H^g = \{g^{-1}*h*g\ \vert\ h \in H \}$$

is a subgroup of $G$. Such a subgroup of $G$ is called a subgroup conjugate to $H$.

Exercise 5.11.6   Let $G=S_3$, the symmetric group on 3 letters, in the notation of the example above. Compute the conjugations

$$s_1^{s_2},\ \ \ \ \ s_2^{s_1}.$$

Exercise 5.11.7   Let $s=(1,2,5,3)$ and $r=(1,2,3)(4,5)$ be elements of $S_5$. Compute $r^{1}sr$ using Lemma 4.4.1.

Exercise 5.11.8   Find all elements in $S_{5}$ that are conjugate to the permutation $g=(1,2,3)(4,5)$.

Exercise 5.11.9   Find all elements in $S_{4}$ that are conjugate to the permutation $g=(1,2,3,4)$.

Exercise 5.11.10   The elements

$$g_1=(6,9)(1,3,4)(2,5,7,8),\ \ \ \ \ \ \ \ \ g_2=(1,2)(3,4,5)(6,7,8,9)$$

are conjugate. In other words, there is an $h\in S_9$ such that $g_2=g_1^h$. Find $h$.

Exercise 5.11.11   Let $R, U$ be as in the notation for the Rubik's cube moves introduced in the previous chapter. Determine the order of the move $R^U$.

Exercise 5.11.12   Let S be the set of all subgroups of G. We define a relation R on S by

$$R = \{ (H_1,H_2) \in S\times S \ \vert\ H_1 \ {\rm is\ conjugate\ to}\ H_2 \}.$$

Show that $R$ is an equivalence relation.

Exercise 5.11.13   Let $G = S_n$ and let $H = \langle g\rangle$ be a cyclic subgroup generated by a permutation $g$ of the set $\{1,2,...,n\}$. With respect to the equivalence relation in the previous problem, show that a subgroup $K$ of $G$ belongs to the equivalence class $[H]$ of $H$ in $G$ if any only if $K$ is cyclic and is generated by an element $k$ of $G$ conjugate to $g\in G$.

Exercise 5.11.14   Show that the notion of conjugate defines an equivalence relation. That is, show that (a) any element $g\in G$ is conjugate to itself (reflexive), (b) if $g$ is conjugate to $h$ ($g, h$ belonging to $G$) then $h$ is conjugate to $g$ (symmetry), (c) if $g_1$ is conjugate to $g_2$ and $g_2$ is conjugate to $g_3$ then $g_1$ is conjugate to $g_3$ (transitivity).

Exercise 5.11.15   Let $x,y\in Cl_G(g)$ show $ord(x)=ord(y)=ord(g)$. (This implies that $ord:G_*\rightarrow \mathbb{N}$, $ord(x)=ord(g)$, for any $x\in Cl_G(g)$, is a well-defined function.) Hint: Two elements which are conjugate must have the same order since $(h^{-1}gh)^n=(h^{-1}gh)(h^{-1}gh)... (h^{-1}gh)=h^{-1}g^nh$, for $n=1,2,...$ and $g,h\in G$.

Exercise 5.11.16   Show that two permutations $g_1,g_2\in S_n$ are conjugate: they are conjugate if and only if the cycles in their respective disjoint cycle decompositions have the same length when arranged from shortest to longest. (Hint: Use Lemma 4.4.1.)