Tag Archives: automorphism

The order of the Frobenius map on a finite field

Let \varphi denote the Frobenius map x \mapsto x^p on \mathbb{F}_{p^n}. Prove that \varphi is an automorphism and compute its order in \mathsf{Aut}(\mathbb{F}_{p^n}).

Recall that \varphi is a homomorphism. Moreover, if \alpha \in \mathsf{ker}\ \varphi, then \alpha^p = 0. Since fields contain no nontrivial zero divisors, we have \alpha = 0 (using induction if you want). So the kernel of \varphi is trivial, and thus \varphi is injective. Since \mathbb{F}_{p^n} is finite, \varphi is surjective, and so is a field isomorphism.

Next, we claim that \varphi^t(\alpha) = \alpha^{p^t} for all \alpha and all t \geq 1, and will show this by induction. The base case certainly holds, and if \varphi^t(\alpha) = \alpha^{p^t}, then \varphi^{t+1}(\alpha) = \varphi(\varphi^t(\alpha)) = \varphi(\alpha^{p^t}) = (\alpha^{p^t})^p = \alpha^{p^{t+1}} as desired.

Now \varphi^n(\alpha) = \alpha^{p^n} = \alpha, since the elements of \mathbb{F}_{p^n} are precisely the roots of x^{p^n}-x. So we have \varphi^n = 1.

If \varphi^t = 1, then we have \alpha^{p^t} - \alpha = 0 for all \alpha, so that each \alpha is a root of x^{p^t}-x. So x^{p^n-1}-1 divides x^{p^t-1}-1, and so p^n-1 divides p^t-1 (by this previous exercise) and then n divides t (by this previous exercise). In particular, n \leq t.

So n is the order of \varphi in \mathsf{Aut}(\mathbb{F}_{p^n}).

Exhibit a quadratic field as a field of matrices

Let K = \mathbb{Q}(\sqrt{D}), where D is a squarefree integer. Let \alpha = a+b\sqrt{D} be in K, and consider the basis B = \{1,\sqrt{D}\} of K over \mathbb{Q}. Compute the matrix of the \mathbb{Q}-linear transformation ‘multiplication by \alpha‘ (described previously) with respect to B. Give an explicit embedding of \mathbb{Q}(\sqrt{D}) in the ring \mathsf{Mat}_2(\mathbb{Q}).

We have \varphi_\alpha(1) = a+b\sqrt{D} and \varphi(\alpha)(\sqrt{D}) = bD + a\sqrt{D}. Making these the columns of a matrix M_\alpha, we have M_\alpha = \begin{bmatrix} a & bD \\ b & a \end{bmatrix}, and this is the matrix of \varphi_\alpha with respect to B. As we showed in the exercise linked above, \alpha \mapsto M_\alpha is an embedding of K in \mathsf{Mat}_2(\mathbb{Q}).

Compare to this previous exercise about \mathbb{Z}[\sqrt{D}].

Prove that a given map is a field automorphism

Prove directly that the map \varphi : \mathbb{Q}(\sqrt{2}) \rightarrow \mathbb{Q}(\sqrt{2}) given by a+b\sqrt{2} \mapsto a-b\sqrt{2} is a field isomorphism.

Note that elements of \mathbb{Q}(\sqrt{2}) can be written uniquely in the form a+b\sqrt{2} where a,b \in \mathbb{Q}, so that this rule indeed defines a function.

Now \varphi((a+b\sqrt{2}) + (c+d\sqrt{2})) = \varphi((a+c) + (b+d)\sqrt{2}) = (a+c) - (b+d)\sqrt{2} = (a-b\sqrt{2}) + (c-d\sqrt{2}) = \varphi(a+b\sqrt{2}) + \varphi(c+d\sqrt{2}), so that \varphi preserves addition.

Similarly, we have \varphi((a+b\sqrt{2})(c+d\sqrt{2})) = \varphi((ac+2bd) + (ad+bc)\sqrt{2}) = (ac+2bd) - (ad+bc)\sqrt{2} = (a-b\sqrt{2})(c-d\sqrt{2}) = \varphi(a+b\sqrt{2})\varphi(c+d\sqrt{2}), so that \varphi preserves multiplication.

Thus \varphi is a ring homomorphism, and hence a field homomorphism.

Note that if \varphi(a+b\sqrt{2}) = 0, then we have a-b\sqrt{2} = 0, and so if b = 0 we have a/b = \sqrt{2}, where a and b are rational numbers- a contradiction since \sqrt{2} is not rational. So b = 0, and thus a = 0, and we have \mathsf{ker}\ \varphi = 0. So \varphi is injective.

Finally, \varphi is surjective since we have \varphi(a+(-b)\sqrt{2}) = a+b\sqrt{2} for all a and b.

So \varphi is a field isomorphism.

An automorphism of Sym(6) that is not inner

This exercise exhibits an automorphism of S_6 that is not inner (hence it shows that [\mathsf{Aut}(S_6) : \mathsf{Inn}(S_6)] = 2. Let u_1 = (1\ 2)(3\ 4)(5\ 6), u_2 = (1\ 4)(2\ 5)(3\ 6), u_3 = (1\ 3)(2\ 4)(5\ 6), u_4 = (1\ 2)(3\ 6)(4\ 5), and u_5 = (1\ 4)(2\ 3)(5\ 6). Show that u_1, \ldots, u_5 satisfy the following relations:

  • u_i^2 = 1 for all i,
  • (u_iu_j)^2 = 1 for all i,j with |i-j| \geq 2, and
  • (u_iu_{i+1})^3 = 1 for all i \in \{1,2,3,4\}.

Deduce that S_6 = \langle u_1, \ldots, u_5 \rangle and that the map (1\ 2) \mapsto u_1, (2\ 3) \mapsto u_2, (3\ 4) \mapsto u_3, (4\ 5) \mapsto u_4, (5\ 6) \mapsto u_5 extends to an automorphism of S_6 (which is clearly not inner since it does not preserve cycle shape.

Showing that u_i satisfy the given relations is a straightforward computation. Moreover, they generate S_6 since u_3u_5u_1 = (6\ 5) and u_1u_2u_4 = (6\ 5\ 2\ 3\ 4\ 1).

Count the number of automorphisms of a group from a presentation

Use presentations to find the orders of the automorphism groups of Z_2 \times Z_4 and Z_4 \times Z_4.

We have Z_2 \times Z_4 = \langle a,b \ |\ a^2 = b^4 = 1, ab = ba \rangle.

Now any element x of order 4 and any element y of order 2 with x \neq y^2 generate Z_2 \times Z_4. There are 4 elements of order 4: b, b^3, ab, and ab^3. There are 2 elements of order 2: a, b^2, and ab^2. Once x is chosen, there are two choices for y, and each choice determines an automorphism. These are distinct by construction. Thus |\mathsf{Aut}(Z_2 \times Z_4)| = 8.

Now Z_4 \times Z_4 = \langle a,b \ |\ a^4 = b^4 = 1, ab = ba \rangle.

Any two elements of order 4, say x and y, generate Z_4 \times Z_4 provided \langle x \rangle \cap \langle y \rangle = 1. This group has 12 elements of order 4, and these intersect nontrivially pairwise. Thus once x is chosen, there are 8 choices for y. Thus |\mathsf{Aut}(Z_4 \times Z_4)| = 96.

Given an automorphism of order 2 of an elementary abelian group, the set of fixed points has bounded rank

Let V be an elementary abelian 2-group of rank r \geq 1, and let \varphi be an automorphism of V such that \varphi^2 = 1. Prove that the map \psi(v) = v + \varphi(v) is a homomorphism of V to itself and that every element in the image of \psi is fixed by \varphi. Deduce that the set of elements fixed by \varphi is an elementary abelian subgroup of rank t, where 2t \geq r.

First we show that \psi is a homomorphism. If v,w \in V, then \psi(v+w) = v+w + \varphi(v+w) = v + \varphi(v) + w + \varphi(w) = \psi(v) + \psi(w).

Now let F \subseteq V be the set of elements fixed by \varphi; it is clear that F is in fact a subgroup of V.

Now if v \in \mathsf{ker}\ \psi, then 0 = \psi(v) = v+\varphi(v), so that v = \varphi(v). Thus v \in F. Likewise, if v \in \mathsf{im}\ \psi, then v = w + \varphi(w) for some w, and we have \varphi(v) = \varphi(w) + \varphi^2(w) = w + \varphi(w) = v. Thus v \in F.

By the First Isomorphism Theorem, we have [V, \mathsf{ker}\ \psi] = |\mathsf{im}\ \psi|, and since everything is finite, |V| = |\mathsf{im}\ \psi| \cdot |\mathsf{ker}\ \psi| \leq |F|^2.

Now |V| = 2^r and |F| = 2^t, so that r \leq 2t, as desired.

Every automorphism of an elementary abelian p-group having p-power order has nontrivial fixed points

Let p be a prime, let V be a nontrivial elementary abelian p-group, and let \varphi be an automorphism of V of p-power order. Prove that \varphi has nontrivial fixed points.

Note that \langle \varphi \rangle \leq \mathsf{Aut}(V); use the inclusion map to construct P = V \rtimes \langle \varphi \rangle. Now P is a p-group, and V \leq P is normal, so that by Theorem 1, V \cap Z(P) is nontrivial.

Now let x \in V \cap Z(P) with x \neq 1. Then (x, \varphi) = (x,1)(1,\varphi) = (1,\varphi)(x,1) = (\varphi(x),\varphi). Comparing entries we see that x = \varphi(x).

For all n except 6, every automorphism of Sym(n) is inner

This exercise shows that for n \neq 6 every automorphism of S_n is inner. Fix an integer n \geq 2 with n \neq 6.

  1. Prove that every automorphism of a group G permutes the conjugacy classes of G. That is, if K \subseteq G is a conjugacy class and \varphi an automorphism of G, then \varphi[K] is a conjugacy class of G.
  2. Let K be the conjugacy class of transpositions in S_n and let L be the conjugacy class containing any element of order 2 in S_n that is not a transposition. Prove that |K| \neq |L|. Deduce that any automorphism of S_n sends transpositions to transpositions. [Hint: Use §4.3 #33.]
  3. Prove that for each \sigma \in \mathsf{Aut}(S_n), (1\ 2) \mapsto (a\ b_2), (1\ 3) \mapsto (a\ b_3), …, (1\ n) \mapsto (a\ b_n) for some distinct integers a, b_2, \ldots, b_n \in \{1,2,\ldots,n\}.
  4. Show that (1\ 2), (1\ 3), …, (1\ n) generate S_n and deduce that any automorphism of S_n is uniquely determined by its action on these elements. Use (c) to show that S_n has at most n! automorphisms. Conclude that \mathsf{Aut}(S_n) = \mathsf{Inn}(S_n) for n \neq 6.

  1. [Short way]

    Let \sigma be an automorphism of G, and let G \cdot a be a conjugacy class. Note that \sigma(g \cdot a) = \sigma(g^{-1}ag) = \sigma(g) \cdot \sigma(a), so that \sigma[G \cdot a] = \sigma[G] \cdot \sigma(a) = G \cdot \sigma(a). In particular, \sigma[G \cdot a] is a conjugacy class of G.

    [Long way]

    Let \sigma \in \mathsf{Aut}(G) and let K \subseteq G be a conjugacy class. We claim that \sigma[K] is a conjugacy class. Let a,b \in \sigma[K]. Then a = \sigma(x) and b = \sigma(y) for some x,y \in K. Since K is a conjugacy class, there exists an element z \in G such that zxz^{-1} = y; then \sigma(z)\sigma(x)\sigma(z)^{-1} = \sigma(y), so we have \sigma(z) a \sigma(z)^{-1} = b. Thus a and b are conjugate.

    Let a \in \sigma[K] and b \notin \sigma[K] and suppose that a and b are conjugate; then for some c \in G, cac^{-1} = b. Now since \sigma is surjective, we have a = \sigma(x), b = \sigma(y), and c = \sigma(z) for some x \in K, b \notin K, and c \in G. Now \sigma(zxz^{-1}) = \sigma(y), and since \sigma is injective, we have zxz^{-1} = y. Thus x and y are conjugate, a contradiction since K is a conjugacy class.

    Thus \sigma[K] is a conjugacy class for all automorphisms \varphi and conjugacy classes K. Moreover, we have \mathsf{id}[K] = K and (\varphi \circ \psi)[K] = \varphi[\psi[K]], so that \mathsf{Aut}(G) acts on the set of conjugacy classes of G by function application.

  2. We now prove some lemmas.

    Lemma 1: If k \geq 4, then \frac{2(2k-2)!}{k! \cdot 2^k} > 1. Proof: We proceed by induction on k. For the base case (k = 4) note that \frac{2(8-2)!}{4! \cdot 2^4} = \frac{2 \cdot 6!}{4! \cdot 2^4} = \frac{6 \cdot 5}{8} = \frac{15}{4} > 1. For the inductive step, suppose that the conclusion holds for some k \geq 4. Now note that the polynomial p(k) = 4k^2 - 4k - 2 has roots \frac{1 \pm \sqrt{3}}{2} and opens upward; thus for k \geq 4, p(k) > 0. Now 4k^2 - 2k > 2k + 2, so that \frac{2k(2k-1)}{2(k+1)} > 1. Thus 1 < \frac{2(2k-2)!}{k! \cdot 2^k} \cdot \frac{2k(2k-1)}{2(k+1)} = \frac{2(2(k+1) - 2)!}{(k+1)! \cdot 2^{k+1}}. By induction, the conclusion holds for all k \geq 4. \square

    Lemma 2: Suppose 4 \leq 2k \leq n. If \frac{2(n-2)!}{k! 2^k (n-2k)!} > 1, then \frac{2((n+1)-2)!}{k! 2^k ((n+1) - 2k)!} > 1. Proof: Note that 1 < k, so that 2 < 2k. Hence -2k + 1 < -1, so that n - 2k + 1 < n-1. Thus 1 < \frac{2(n-2)!}{k! 2^k (n-2k)!} \cdot \frac{n-1}{n+1-2k} = \frac{2((n+1)-2)!}{k! 2^k ((n+1)-2k)!}. \square

    Lemma 3: If n \geq 8 and 4 \leq 2k \leq n, then \frac{2(n-2)!}{k! 2^k (n-2k)!} > 1. Proof: We proceed by induction on n. For the base case (n = 8), there are three possibilities for k. If k = 2, we have \frac{2(8-2)!}{2! 2^2 (8-4)!} = \frac{15}{2} > 1. If k = 3, we have \frac{2(8-2)!}{3! 2^3 (8-6)!} = \frac{5}{2} > 1. For k = 4 the inequality holds by Lemma 1. Now for the inductive step, suppose that for some n \geq 8 the inequality holds for all 4 \leq 2k \leq n. If n is even, then 4 \leq 2k \leq n+1 if and only if 4 \leq 2k \leq n. Thus by Lemma 2, \frac{2((n+1)-2)!}{k! 2^k ((n+1)-2k)!} > 1 for all 4 \leq 2k \leq n+1. If n is odd, then 4 \leq 2k \leq n+1 if and only if 4 \leq 2k \leq n or 2k = n+1. In the first case, use Lemma 2 as before. In the second case, the inequality holds by Lemma 1. Thus for all 4 \leq 2k \leq n+1, we have \frac{2((n+1)-2)!}{k! 2^k ((n+1)-2k)!} > 1. By induction, the inequality holds for all n \geq 8 and all 4 \leq 2k \leq n. \square

    Lemma 4: If n \in \{ 4,5,7 \} and 4 \leq 2k \leq n, then \frac{2(n-2)!}{k! 2^k (n-2k)!} \neq 1. Proof: If n=4, then k = 2. Now \frac{2(4-2)!}{2! 2^2 (4-4)!} = \frac{1}{2} \neq 1. If n=5, then k=2. Now \frac{2(5-2)!}{2! 2^2 (5-4)!} = \frac{3}{2} \neq 1. If n=7, then k=2 or k=3. If k=2, then \frac{2(7-2)!}{2! 2^2 (7-4)!} = 5 \neq 1. If k=3, then \frac{2(7-2)!}{3! 2^3 (7-6)!} = 5 \neq 1. \square.

    Now we move to the main result. Note that if n is 2 or 3, then all elements of order 2 are transpositions; thus any automorphism of S_n sends transpositions to transpositions. Now if n \geq 4 and \sigma is an element of order 2, then \sigma is a product of k disjoint 2-cycles. If \sigma is not a transposition, then k \geq 2; note then that 4 \leq 2k \leq n. By §4.3 #33, the number of transpositions in S_n is \frac{n!}{2(n-2)!}, and the number of conjugates of \sigma is \frac{n!}{k! 2^k (n-2k)!}. These two numbers are not equal for n \neq 6 and all 4 \leq 2k \leq n, since otherwise we have \frac{2(n-2)!}{k! 2^k (n-2k)!} = 1, which contradicts Lemmas 3 and 4. Now if \varphi is an automorphism of S_n and K \subseteq S_n the conjugacy class of transpositions, then \varphi[K] is a conjugacy class of elements of order 2. If \varphi[K] \neq K, we have a contradiction since |K| \neq |\varphi[K]|. Thus every automorphism of S_n maps transpositions to transpositions if n \neq 6.

  3. We begin with some lemmas.

    Lemma 5: Let \varphi \in \mathsf{Aut}(G). Then for all x,y \in G, xy = yx if and only if \varphi(x)\varphi(y) = \varphi(y)\varphi(x). Proof: xy = yx if and only if \varphi(xy) = \varphi(yx) since \varphi is injective, if and only if \varphi(x)\varphi(y) = \varphi(y)\varphi(x) since \varphi is a homomorphism. \square

    Lemma 6: Let \varphi \in \mathsf{Aut}(S_n) with n \geq 3. Then |\bigcap_{k=2}^n M(\varphi((1\ k)))| = 1. Proof: For each k, \varphi((1\ k)) is a transposition by part (b). Thus |M(\varphi((1\ k)))| \leq 2. Suppose \bigcap_{k=2}^n M(\varphi((1\ k))) = \emptyset; then for some k \neq \ell, we have M(\varphi((1\ k))) \neq M(\varphi(1\ \ell)). But then \varphi((1\ k)) and \varphi((1\ \ell)) are disjoint and thus commute, a contradiction since (1\ k) and (1\ \ell) do not commute. Now suppose |\bigcap_{k=2}^n M(\varphi((1\ k)))| = 2; since each \varphi((1\ k)) is a transposition, we have \varphi((1\ k)) = \varphi((1\ \ell)) for all k and \ell, a contradiction since \varphi is injective and (since n \geq 3) there exist 2 \leq k, \ell \leq n with k \neq \ell. Thus |\bigcap_{k=2}^n M(\varphi((1\ k)))| = 1. \square

    Now to the main result. If n=2, then S_n has only the trivial automorphism, under which (1\ 2) \mapsto (1\ 2). If n \geq 3, then by part (b) each of \varphi((1\ k)) is a transposition for 2 \leq k \leq n, and by Lemma 6 the \varphi((1\ k)) move a common element a. Since \varphi is a bijection, the second element moved by the \varphi((1\ k)) are pairwise distinct. Thus for some distinct a,b_2,\ldots,b_n \in \{ 1,2,\ldots,n\} we have \varphi((1\ 2)) = (a\ b_2), \varphi((1\ 3)) = (a\ b_3), …, \varphi((1\ n)) = (a\ b_n).

  4. In §3.5 #3, we saw that S_n is generated by \{(a\ a+1) \ |\ 1 \leq a < n \}. Note that (a\ a+1) = (1\ a)(1\ a+1)(1\ a). Thus S_n = \langle \{ (1\ a) \ |\ 2 \leq a \leq n \} \rangle, and so any automorphism of S_n is uniquely determined by its action on these transpositions. By part (c), there are at most n! possible choices for the images of the (1\ k) under an automorphism \varphi (one for each assignment of the a,b_i to the integers \{1,2,\ldots,n\}). Thus \mathsf{Aut}(S_n) = \mathsf{Inn}(S_n) for n \neq 6.

Characterize the automorphisms of Cyc(n)

Let Z_n = \langle \alpha \rangle be a cyclic group of order n and for each integer a, define \sigma_a : Z_n \rightarrow Z_n by \sigma_a(x) = x^a.

  1. Prove that \sigma_a is an automorphism of Z_n if and only if a and n are relatively prime.
  2. Prove that \sigma_a = \sigma_b if and only if a \equiv b mod n.
  3. Prove that every automorphism of Z_n is equal to \sigma_a for some a.
  4. Prove that \sigma_a \circ \sigma_b = \sigma_{ab}. Deduce that the mapping \overline{a} \rightarrow \sigma_a is an isomorphism of (\mathbb{Z}/(n))^\times to Z_n.

  1. We saw in a previous theorem that this mapping is surjective; since Z_n is finite, it is bijective. By a previous theorem, \varphi is a homomorphism, thus an automorphism.
  2. (\Rightarrow) Suppose \sigma_a = \sigma_b. Then \sigma_a(\alpha) = \sigma_b(\alpha), so that \alpha^a = \alpha^b. Since |\alpha| = n, then, we have a \equiv b mod n. (\Leftarrow) Suppose a \equiv b mod n; then we have a-b = kn for some integer k, so that a = kn+b. Now for all x \in Z_n we have \sigma_a(x) = x^a = x^{kn+b} = x^b = \sigma_b(x); hence \sigma_a = \sigma_b.
  3. Let \varphi be an automorphism of Z_n. Now \varphi(\alpha) = \alpha^k for some k, since \alpha generates Z_n. Then \varphi(\alpha^i) = \varphi(\alpha)^i = \alpha^{ki} = (\alpha^i)^k = \sigma_k(\alpha^i) for all integers i; since every element of Z_n is of the form \alpha^i, we have that \varphi = \sigma_k.
  4. Define a mapping \Phi : (\mathbb{Z}/(n))^\times \rightarrow \mathsf{Aut}\ Z_n by \Phi(\overline{a}) = \sigma_a. By part 2 above, \Phi is well defined. Moreover, letting x \in Z_n be arbitrary, we have (\sigma_a \circ \sigma_b)(x) = \sigma_a(\sigma_b(x)) = \sigma_a(x^b) = (x^b)^a = x^{ab} = \sigma_{ab}(x). Thus \sigma_a \circ \sigma_b = \sigma_{ab}. In other words, \Phi(\overline{a} \overline{b}) = \Phi(\overline{a}) \Phi(\overline{b}). Thus \Phi is a homomorphism. Finally, by part 3 above, \phi is surjective. Since \mathsf{Aut}\ Z_n and (\mathbb{Z}/(n))^\times are finite \phi is bijective. Thus \Phi is an isomorphism.

Exhibit the automorphisms of ZZ/(48)

Let Z_{48} = \langle x \rangle. For which integers a does the map \varphi_a defined by \varphi_a(1) = x^a extend to an isomorphism \mathbb{Z}/(48) \rightarrow Z_{48}?

We know that \langle x \rangle = \langle x^a \rangle precisely when \mathsf{gcd}(a,n) = 1. That is, x^a is a generator of Z_{48} precisely when \mathsf{gcd}(a,n) = 1. Thus \varphi_a is an isomorphism precisely for 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, and 47.