MHB Understanding Aut(G) Isomorphism to Z2

[mathmari]

Hey!

The automorphism group of the group $G$, $\text{Aut}(G)$, is the group of isomorphisms from $G$ to $G$, right? (Wondering)

How could we show that for example $\text{Aut}(\mathbb{Z})$ is isomorphic to $\mathbb{Z}_2$ ? (Wondering)
What function do we use? (Wondering)

 

[Deveno]

Automorphisms are isomorphisms, and as such they must take generators to generators.

How many generators does $\Bbb Z$ have?

 

[mathmari]

How many generators does $\Bbb Z$ have?

The generators of $\mathbb{Z}$ are $\pm 1$, right? (Wondering)

 

[Deveno]

The generators of $\mathbb{Z}$ are $\pm 1$, right? (Wondering)

Yep.

 

[mathmari]

What exactly do you mean by the following?

Automorphisms are isomorphisms, and as such they must take generators to generators.

(Wondering)

 

[Deveno]

Suppose $G$ is a cyclic group (this is the easiest case to talk about, and it applies here).

Then $G = \langle x\rangle$, for some $x \in G$.

I now claim, that if $\phi \in \text{Aut}(G)$, then $y = \phi(x)$ is *also* a generator of $G$.

For suppose $g$ is any element of $G$. Since $\phi$ is surjective (every automorphism is bijective), we have:

$g = \phi(a)$, for some $a \in G$. Since $G = \langle x\rangle$, we have $a = x^k$ for some $k \in \Bbb Z$.

Thus $g = \phi(a) = \phi(x^k) = \phi(x)^k$ (since $\phi$ is also a homomorphism)

$= y^k$, so $G \subseteq \langle y\rangle$.

Since $y \in G$, it's obvious that $\langle y\rangle \subseteq G$, thus $G = \langle y\rangle$, that is, $y$ also generates $G$.

 

[mathmari]

Suppose $G$ is a cyclic group (this is the easiest case to talk about, and it applies here).

Then $G = \langle x\rangle$, for some $x \in G$.

I now claim, that if $\phi \in \text{Aut}(G)$, then $y = \phi(x)$ is *also* a generator of $G$.

For suppose $g$ is any element of $G$. Since $\phi$ is surjective (every automorphism is bijective), we have:

$g = \phi(a)$, for some $a \in G$. Since $G = \langle x\rangle$, we have $a = x^k$ for some $k \in \Bbb Z$.

Thus $g = \phi(a) = \phi(x^k) = \phi(x)^k$ (since $\phi$ is also a homomorphism)

$= y^k$, so $G \subseteq \langle y\rangle$.

Since $y \in G$, it's obvious that $\langle y\rangle \subseteq G$, thus $G = \langle y\rangle$, that is, $y$ also generates $G$.

Ah ok... (Thinking)

So, the automorphism group of $G$ is the set of functions $\phi$ that send the generators of $G$ to the generators of $G$, right? (Wondering)

Since the generators of $\mathbb{Z}$ are $\pm 1$, we are looking for functions that send $1$ to $1$ or to $-1$ and $-1$ to $1$ or $-1$, or not? (Wondering)

Such a function is the identity function and the function $x\mapsto -x$, right? (Wondering)

 

[Deveno]

Ah ok... (Thinking)

So, the automorphism group of $G$ is the set of functions $\phi$ that send the generators of $G$ to the generators of $G$, right? (Wondering)

For cyclic groups, this is true. For finitely-generated groups in general, it's a bit more complicated.

Since the generators of $\mathbb{Z}$ are $\pm 1$, we are looking for functions that send $1$ to $1$ or to $-1$ and $-1$ to $1$ or $-1$, or not? (Wondering)

Yes.

Such a function is the identity function and the function $x\mapsto -x$, right? (Wondering)

Correct-the identity function is the identity element of the automorphism group, and the inversion map is the other element, of order $2$ (since $-(-x) = x = \text{id}(x)$).

 

[mathmari]

And how can we show that this is isomorphic is $\mathbb{Z}_2$ ? (Wondering)

 

[Deveno]

And how can we show that this is isomorphic is $\mathbb{Z}_2$ ? (Wondering)

Try this mapping:

$\text{id} \mapsto 0\text{ mod }2$
$\text{inv} \mapsto 1\text{ mod }2$

where $\text{id}(x) = x$, and $\text{inv}(x) = -x$.

It's clearly a bijection, so is it a homomorphism?

Specifically, (if we call our mapping $h$), you want to check that:

$h(\text{id}\circ\text{id}) = h(\text{id}) + h(\text{id})$
$h(\text{id}\circ\text{inv}) = h(\text{id}) + h(\text{inv})$
$h(\text{inv}\circ\text{id}) = h(\text{inv}) + h(\text{id})$
$h(\text{inv}\circ\text{inv}) = h(\text{inv}) + h(\text{inv})$

Alternatively, you could take "the high road", and show that ANY two groups of order two are isomorphic (and cyclic, as well!), and show that the set:

$S = \{\text{id},\text{inv}\}$ forms a group under the operation of functional composition.

 

[mathmari]

Try this mapping:

$\text{id} \mapsto 0\text{ mod }2$
$\text{inv} \mapsto 1\text{ mod }2$

where $\text{id}(x) = x$, and $\text{inv}(x) = -x$.

It's clearly a bijection

Why is it a bijection? (Wondering)

Is it because each function of $\text{Aut}(\mathbb{Z})$ is mapped to one element of $\mathbb{Z}_2$ ? (Wondering)

is it a homomorphism?

Specifically, (if we call our mapping $h$), you want to check that:

$h(\text{id}\circ\text{id}) = h(\text{id}) + h(\text{id})$
$h(\text{id}\circ\text{inv}) = h(\text{id}) + h(\text{inv})$
$h(\text{inv}\circ\text{id}) = h(\text{inv}) + h(\text{id})$
$h(\text{inv}\circ\text{inv}) = h(\text{inv}) + h(\text{inv})$

We have the following:

• $h(\text{id}\circ\text{id}) = h(\text{id}(\text{id}))=h(\text{id})=0\text{ mod }2=0\text{ mod }2+0\text{ mod }2=h(\text{id}) + h(\text{id})$
• $h(\text{id}\circ\text{inv}) = h(\text{id}(\text{inv}))=h(\text{id}(\text{inv}))=h(\text{inv})=1\text{ mod }2=0\text{ mod }2+1\text{ mod }2=h(\text{id}) + h(\text{inv})$
• $h(\text{inv}\circ\text{id}) = h(\text{inv}(\text{id})) =h(-\text{id})$
  
  To what is that equal? (Wondering)
  How do we get $h(\text{inv}) + h(\text{id})$ ? (Wondering)
• $h(\text{inv}\circ\text{inv}) = h(\text{inv}(\text{inv}))=h(-\text{inv})$
  
  To what is that equal? (Wondering)
  How do we get $h(\text{inv}) + h(\text{inv})$ (Wondering)

 

[Deveno]

Why is it a bijection? (Wondering)

Is it because each function of $\text{Aut}(\mathbb{Z})$ is mapped to one element of $\mathbb{Z}_2$ ? (Wondering)


We have the following:

• $h(\text{id}\circ\text{id}) = h(\text{id}(\text{id}))=h(\text{id})=0\text{ mod }2=0\text{ mod }2+0\text{ mod }2=h(\text{id}) + h(\text{id})$
• $h(\text{id}\circ\text{inv}) = h(\text{id}(\text{inv}))=h(\text{id}(\text{inv}))=h(\text{inv})=1\text{ mod }2=0\text{ mod }2+1\text{ mod }2=h(\text{id}) + h(\text{inv})$
• $h(\text{inv}\circ\text{id}) = h(\text{inv}(\text{id})) =h(-\text{id})$
  
  To what is that equal? (Wondering)
  How do we get $h(\text{inv}) + h(\text{id})$ ? (Wondering)
• $h(\text{inv}\circ\text{inv}) = h(\text{inv}(\text{inv}))=h(-\text{inv})$
  
  To what is that equal? (Wondering)
  How do we get $h(\text{inv}) + h(\text{inv})$ (Wondering)

Technically speaking something like $\text{inv}(\text{id})$ makes no sense: $\text{inv}$ is a function $\Bbb Z \to \Bbb Z$, and doesn't have functions as arguments (its domain elements) but rather integers.

For *functions* we don't define $f\circ g$ as $f(g)$, but rather:

$(f \circ g)(x) = f(g(x))$.

So, for example, to compute $\text{inv}\circ\text{id}$, we examine:

$(\text{inv}\circ\text{id})(x) = \text{inv}(\text{id}(x)) = \text{inv}(x) = -x$.

Thus $\text{inv}\circ\text{id} = \text{inv}$, since $\text{inv}\circ\text{id}$ and $\text{inv}$ have the same value, for every integer $x$.

See if this helps.

 

[mathmari]

Is it as followed? (Wondering)

• $h((\text{id}\circ\text{id})(x) )= h(\text{id}(\text{id}(x)))=h(\text{id}(x))=0\text{ mod }2=0\text{ mod }2+0\text{ mod }2=h(\text{id})(x) + h(\text{id})(x)$
• $h((\text{id}\circ\text{inv}(x)) = h(\text{id}(\text{inv}(x)))=h(\text{id}(-x))=h(-x)=h(\text{inv}(x))=1\text{ mod }2=0\text{ mod }2+1\text{ mod }2=h(\text{id})(x) + h(\text{inv})(x)$
• $h((\text{inv}\circ\text{id})(x)) = h(\text{inv}(\text{id}(x))) =h(\text{inv}(x))=1\text{ mod }2=1\text{ mod }2+0\text{ mod }2=h(\text{inv}(x)) + h(\text{id}(x))$
• $h((\text{inv}\circ\text{inv})(x)) = h(\text{inv}(\text{inv}(x)))=h(\text{inv}(-x))=h(x)=h(\text{id}(x))=0\text{ mod }2=1\text{ mod }2+1\text{ mod }2=h(\text{inv}) + h(\text{inv})$

 

[Deveno]

Is it as followed? (Wondering)

• $h((\text{id}\circ\text{id})(x) )= h(\text{id}(\text{id}(x)))=h(\text{id}(x))=0\text{ mod }2=0\text{ mod }2+0\text{ mod }2=h(\text{id})(x) + h(\text{id})(x)$
• $h((\text{id}\circ\text{inv}(x)) = h(\text{id}(\text{inv}(x)))=h(\text{id}(-x))=h(-x)=h(\text{inv}(x))=1\text{ mod }2=0\text{ mod }2+1\text{ mod }2=h(\text{id})(x) + h(\text{inv})(x)$
• $h((\text{inv}\circ\text{id})(x)) = h(\text{inv}(\text{id}(x))) =h(\text{inv}(x))=1\text{ mod }2=1\text{ mod }2+0\text{ mod }2=h(\text{inv}(x)) + h(\text{id}(x))$
• $h((\text{inv}\circ\text{inv})(x)) = h(\text{inv}(\text{inv}(x)))=h(\text{inv}(-x))=h(x)=h(\text{id}(x))=0\text{ mod }2=1\text{ mod }2+1\text{ mod }2=h(\text{inv}) + h(\text{inv})$

That's very close.

$h$ is a function $\text{Aut}(\Bbb Z) \to \Bbb Z_2$, so unlike in my previous example, $h$ *does* take functions as arguments, not numbers.

So to evaluate $h(\text{id}\circ\text{id})$, for example, you first have to find out which function $\text{id}\circ\text{id}$ is.

Now $(\text{id}\circ\text{id})(x) = \text{id}(\text{id}(x)) = \text{id}(x) = x$, so:

$\text{id}\circ\text{id}$ is the function $\Bbb Z \to \Bbb Z$ that maps $x \mapsto x$, and that function IS $\text{id}$.

That is: $\text{id}\circ\text{id} = \text{id}$.

Thus $h(\text{id}\circ\text{id}) = h(\text{id}) = [0]_2 = [0]_2 + [0]_2 = h(\text{id}) + h(\text{id})$

(here, $[0]_2$ is just a shorter way to write $0\text{ mod }2$).

So you're missing some "steps in the middle", but you've got the right idea.

If we were to make Cayley tables, our correspondence would look like this:

$\begin{array}{c|c|c|}
\circ&\text{id}&\text{inv}\\
\hline \text{id}&\text{id}&\text{inv}\\
\hline \text{inv}&\text{inv}&\text{id}\\
\hline \end{array} \stackrel{h}{\to}
\begin{array}{c|c|c|}
+&0&1\\
\hline 0&0&1\\
\hline 1&1&0\\
\hline \end{array}$

 

[mathmari]

We have the following:

$$(\text{id}\circ\text{id})(x)=\text{id}(\text{id}(x))=\text{id}(x)=x$$
So $$h(\text{id}\circ\text{id})=h(\text{id})=0\pmod 2=0\pmod 2+0\pmod 2=h(\text{id})+h(\text{id})$$

$$(\text{id}\circ\text{inv})(x)=\text{id}(\text{inv}(x))=\text{id}(-x)=-x=\text{inv}$$
So $$h(\text{id}\circ\text{inv})=h(\text{inv})=1\pmod 2=0\pmod 2+1\pmod 2=h(\text{id})+h(\text{inv})$$

$$(\text{inv}\circ\text{id})(x)=\text{inv}(\text{id}(x))=\text{inv}(x)$$
So $$h(\text{inv}\circ\text{id})=h(\text{inv})=1\pmod 2=1\pmod 2+0\pmod 2=h(\text{inv})+h(\text{id})$$

$$(\text{inv}\circ\text{inv})(x)=\text{inv}(\text{inv}(x))=\text{inv}(-x)=x$$
So $$h(\text{inv}\circ\text{inv})=h(\text{id})=0\pmod 2=1\pmod 2+1\pmod 2=h(\text{inv})+h(\text{inv})$$

So it is an homomorphism,.

Is everything correct? (Wondering)

 

[mathmari]

We have the following:

$$(\text{id}\circ\text{id})(x)=\text{id}(\text{id}(x))=\text{id}(x)=x$$
So $$h(\text{id}\circ\text{id})=h(\text{id})=0\pmod 2=0\pmod 2+0\pmod 2=h(\text{id})+h(\text{id})$$

$$(\text{id}\circ\text{inv})(x)=\text{id}(\text{inv}(x))=\text{id}(-x)=-x=\text{inv}$$
So $$h(\text{id}\circ\text{inv})=h(\text{inv})=1\pmod 2=0\pmod 2+1\pmod 2=h(\text{id})+h(\text{inv})$$

$$(\text{inv}\circ\text{id})(x)=\text{inv}(\text{id}(x))=\text{inv}(x)$$
So $$h(\text{inv}\circ\text{id})=h(\text{inv})=1\pmod 2=1\pmod 2+0\pmod 2=h(\text{inv})+h(\text{id})$$

$$(\text{inv}\circ\text{inv})(x)=\text{inv}(\text{inv}(x))=\text{inv}(-x)=x$$
So $$h(\text{inv}\circ\text{inv})=h(\text{id})=0\pmod 2=1\pmod 2+1\pmod 2=h(\text{inv})+h(\text{inv})$$

So it is an homomorphism,.

Is everything correct? (Wondering)

Or could I improve something? (Wondering) To show that $\text{Aut}(\mathbb{Z}_6)$ is isomorphic to $\mathbb{Z}_2$ do we use the following function?
$$\text{id}\mapsto 0\pmod 2 \\ f\mapsto 1\pmod 2$$
where $\text{id}(x)=x$ and $f(x)=5x$, since the possible generators of $\mathbb{Z}_6$ are $1,5$.

(Wondering)
And to show that $\text{Aut}(\mathbb{Z}_8)$ is isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_2$ do we use the following function?
$$\text{id}\mapsto (0,0) \\ f_1\mapsto (0,1) \\ f_2\mapsto (1,0) \\ f_3\mapsto (1,1)$$
where $\text{id}(x)=x, f_1(x)=x+2, f_2(x)=x+4, f_3(x)=x-2$, since the possible generators of $\mathbb{Z}_8$ are $1,3,5,7$.

(Wondering)

 

[Deveno]

1. Your functions are not automorphisms.

2. Your functions do not form a group, as they are not closed under composition.

 

[mathmari]

1. Your functions are not automorphisms.

Why aren't they automorphisms? (Wondering)

We have $$\text{id}(1)=1 \\ \text{id}(5)=5 \\ f(1)=5 \\ f(5)=5\cdot 5\equiv (-1)\cdot (-1)=1$$ or not? (Wondering)

 

[Deveno]

Why aren't they automorphisms? (Wondering)

We have $$\text{id}(1)=1 \\ \text{id}(5)=5 \\ f(1)=5 \\ f(5)=5\cdot 5\equiv (-1)\cdot (-1)=1$$ or not? (Wondering)

Let me clarify:

Your proposed mappings for $\text{Aut}(\Bbb Z_6)$ are correct, but not so much for $\text{Aut}(\Bbb Z_8)$

 

[mathmari]

Let me clarify:

Your proposed mappings for $\text{Aut}(\Bbb Z_6)$ are correct, but not so much for $\text{Aut}(\Bbb Z_8)$

But why? (Wondering)

We have the following:

$$\text{id}(i)=i, i=1,3,5,7 \\ f_1(1)=3 , f_1(3)=5, f_1(5)=7, f_1(7)=9\equiv 1 \\ f_2(1)=5, f_2(3)=7, f_2(5)=9\equiv 1, f_2(7)=11\equiv 3 \\ f_3(1)=-1\equiv 7 , f_3(3)=1, f_3(5)=3, f_3(7)=5$$

Or not? (Wondering)

 

[Deveno]

But why? (Wondering)

We have the following:

$$\text{id}(i)=i, i=1,3,5,7 \\ f_1(1)=3 , f_1(3)=5, f_1(5)=7, f_1(7)=9\equiv 1 \\ f_2(1)=5, f_2(3)=7, f_2(5)=9\equiv 1, f_2(7)=11\equiv 3 \\ f_3(1)=-1\equiv 7 , f_3(3)=1, f_3(5)=3, f_3(7)=5$$

Or not? (Wondering)

Let us consider, for a moment, the set of $\text{Hom}(\Bbb Z_n,\Bbb Z_n)$ (the set of homomorphisms from $\Bbb Z_n \to \Bbb Z_n$, of which the automorphisms are a subset).

Since $\Bbb Z_n$ is cyclic, every element is of the form $k = 1 + 1 + \cdots + 1$ ($k$ summands).

So if $\phi: \Bbb Z_n \to \Bbb Z_n$ is a homomorphism, then:

$\phi(k) = \phi(1) + \phi(1) + \cdots + \phi(1) = k\phi(1)$.

Since $\phi(1) \in \Bbb Z_n$, say $\phi(1) = a$, we can re-write $\phi$ as the mapping:

$k \mapsto ak$

So this is the form for ANY homomorphism $\Bbb Z_n \to \Bbb Z_n$, including the ones that are automorphisms.

Note that your $f_m$ do indeed map the generators of $\Bbb Z_8$ to other generators, but that alone does not make them HOMOMORPHISMS (they are not of the form listed above, except for the identity mapping).

 

[mathmari]

Since $\Bbb Z_n$ is cyclic, every element is of the form $k = 1 + 1 + \cdots + 1$ ($k$ summands).

Why does this stand? (Wondering)

Since $\phi(1) \in \Bbb Z_n$, say $\phi(1) = a$, we can re-write $\phi$ as the mapping:

$k \mapsto ak$

Which is the value of $a$ in this case? (Wondering)

Note that your $f_m$ do indeed map the generators of $\Bbb Z_8$ to other generators, but that alone does not make them HOMOMORPHISMS (they are not of the form listed above, except for the identity mapping).

So that a mapping is an homomorphism it has to be of the form $k\mapsto ak$, right? Or didn't you mean that form?

 

[Deveno]

Why does this stand? (Wondering)

Because $1$ is a generator of $\Bbb Z_n$ (under addition).

Which is the value of $a$ in this case? (Wondering)

That depends on the homomorphism.

So that a mapping is an homomorphism it has to be of the form $k\mapsto ak$, right? Or didn't you mean that form?

That is correct.

 

[mathmari]

Ah ok... So, do we consider the following function?

$$h:\text{Aut}(\mathbb{Z}_8)\rightarrow \mathbb{Z}_2\times\mathbb{Z}_2 \ \text{ with } \\ \text{id}\mapsto (0,0) \\ f_1\mapsto (0,1) \\ f_2\mapsto (1,0) \\ f_3\mapsto (1,1)$$ where $$\text{id}(x)=x, \ f_1(x)=3x, \ f_2(x)=5x\equiv -3x\ , f_3(x)=7x\equiv -x$$

(Wondering)

 

[Deveno]

Ah ok... So, do we consider the following function?

$$h:\text{Aut}(\mathbb{Z}_8)\rightarrow \mathbb{Z}_2\times\mathbb{Z}_2 \ \text{ with } \\ \text{id}\mapsto (0,0) \\ f_1\mapsto (0,1) \\ f_2\mapsto (1,0) \\ f_3\mapsto (1,1)$$ where $$\text{id}(x)=x, \ f_1(x)=3x, \ f_2(x)=5x\equiv -3x\ , f_3(x)=7x\equiv -x$$

(Wondering)

Much better. Do you think it is a coincidence that $U = \{1,3,5,7\}$ are the units of the multiplicative monoid of $\Bbb Z_8$?

 

[mathmari]

Do you think it is a coincidence that $U = \{1,3,5,7\}$ are the units of the multiplicative monoid of $\Bbb Z_8$?

I don't really know... (Thinking)
Do we have to show that the composition of each of the $\text{id}, f_1, f_2, f_3$ is equal to the corresponding composition of the elements of $\mathbb{Z}_2\times\mathbb{Z}_2$ ? (Wondering)

 

[Deveno]

I don't really know... (Thinking)
Do we have to show that the composition of each of the $\text{id}, f_1, f_2, f_3$ is equal to the corresponding composition of the elements of $\mathbb{Z}_2\times\mathbb{Z}_2$ ? (Wondering)

That would do the trick, yes (it would show it was a homomorphism). The corresponding "composition" in $\Bbb Z_2 \times \Bbb Z_2$ is "component-wise addition modulo 2".

A "lazier" way, would be to show that $\{\text{id},f_1,f_2,f_3\}$ is indeed a group:

1. Composition (of functions) is associative, so showing that the composition of any two elements in our set is again in our set (closure under composition) would be an associative binary operation.

(hint: the FAST way to do this, is show that, in general, the composition of any two automorphisms is again an automorphism. Then we just have to verify each of the $f_i$ for $i = 1,2,3$ is an automorphism (the identity mapping clearly is)).

2. The identity automorphism is clearly an identity for our group.

3. As each element of our set is bijective (assuming you have shown it is automorphism), it possesses an inverse function which is thus ALSO an automorphism, that is, our set $\{\text{id},f_1,f_2,f_3\}$ has all inverses.

Then, the next step is to show every non-identity element has order $2$ under composition, and boom! you're done.

Why? Because (up to isomorphism) there are just TWO groups of order $4$, the cyclic group of order $4$, and the Klein $4$-group, $V$ (for $viergruppe$, the German word for "four-group"), which is isomorphic to $\Bbb Z_2 \times \Bbb Z_2$.

The cyclic group has only one element of order 2 (the other two non-identity elements have order $4$), so actually it suffices to show that any two of your non-identity automorphisms have order 2 under composition.

Now, this is a rather "abstract" view, and if you feel more comfortable verifying the homomorphism property for all 16 possible compositions, go right ahead (you can reduce this to 10 possible compositions if you can show your automorphism group is abelian, and of these, 7 involve the identity automorphism, which should be trivial to show, leaving 3 "non-obvious compositions"

$f_1\circ f_2$
$f_1\circ f_3$
$f_2\circ f_3$).

It is instructive to convince yourself that:

1. Any group of 4 elements MUST be abelian. (Hint: pick $a\neq e \in G$ with $|G| = 4$. Then if $a$ has order $4$, $G$ is cyclic (why?). Otherwise, we have $b \not\in \langle a\rangle = \{e,a\}$, since the order of $a$ must then be 2. If $b$ has order $4$, we again have a cyclic group. So assume not. Now $ab$ must be an element of our group. Show that $ab \neq e$, and $ab \neq a$, and $ab \neq b$. Thus our group must be:

$G = \{e,a,b,ab\}$

Next show $ab = ba$ (same as above, show $ba = e, ba = a, ba = b$ are all impossible). Conclude $G$ is abelian, and that all of $a,b,ab$ have order $2$).

 

[mathmari]

Now, this is a rather "abstract" view, and if you feel more comfortable verifying the homomorphism property for all 16 possible compositions, go right ahead (you can reduce this to 10 possible compositions if you can show your automorphism group is abelian, and of these, 7 involve the identity automorphism, which should be trivial to show, leaving 3 "non-obvious compositions"

$f_1\circ f_2$
$f_1\circ f_3$
$f_2\circ f_3$).

It is instructive to convince yourself that:

1. Any group of 4 elements MUST be abelian. (Hint: pick $a\neq e \in G$ with $|G| = 4$. Then if $a$ has order $4$, $G$ is cyclic (why?). Otherwise, we have $b \not\in \langle a\rangle = \{e,a\}$, since the order of $a$ must then be 2. If $b$ has order $4$, we again have a cyclic group. So assume not. Now $ab$ must be an element of our group. Show that $ab \neq e$, and $ab \neq a$, and $ab \neq b$. Thus our group must be:

$G = \{e,a,b,ab\}$

Next show $ab = ba$ (same as above, show $ba = e, ba = a, ba = b$ are all impossible). Conclude $G$ is abelian, and that all of $a,b,ab$ have order $2$).

I will try first to verify the homomorphism property.
Any group of 4 elements is abelian.

We pick $a\neq e \in G$ with $|G| = 4$.

The possible orders of $a$ are the divisors of $4$, so the possible orders are $2$ and $4$. (It isn't $1$ since $a\neq e$.)

If $a$ has order $4$, $G$ is cyclic. I haven't understood why this stand... Could you explain it to me? (Wondering)
Is a cyclic group abelian? (Wondering)

If $a$ has order $2$, then there will be an element $b \not\in \langle a\rangle = \{e,a\}$. Why is there such a $b$ ? (Wondering)
The possible orders of $b$ are again $2$ and $4$.
If $b$ has order $4$, we again have a cyclic group.
Assume that the order of $b$ is $2$.
Since $a\in G$ and $b\in G$, $ab$ must be also an element of $G$.

Since $a,b\in $ then $a^{-1},b^{-1}\in G$.
When $ab=e$, then $aab=a\Rightarrow a^2b=a \Rightarrow b=a$, that cannot be true, since $b\notin \{a,e\}$.
When $ab=a$, then $aab=aa \Rightarrow a^2b=a^2 \Rightarrow b=e$, that cannot be true, since $b\notin \{a,e\}$.
When $ab=b$, then $abb=bb \Rightarrow ab^2=b^2 \Rightarrow a=e$, that cannot be true, since $a\neq e$.

Right? (Wondering)

Therefore, $ab \neq e$, and $ab \neq a$, and $ab \neq b$. That means that $G = \{e,a,b,ab\}$.

We have $$ab=x \Rightarrow aab=ax \Rightarrow a^2b=ax \Rightarrow b=ax\Rightarrow b^2=axb \Rightarrow e=axb$$

Is it correct so far? How could we continue? (Wondering) Having shown that $ab=ba$ do we conclude that $G$ is abelian? Or do we have to show it also for the multiplication of $ab$ with $a$ and $b$? (Wondering)

Since $ab\neq e$ and $(ab)^2=(ab)(ab)=abba=aea=aa=e$, we conclude that $ab$ has order $2$ since $a$ and $b$ have order $2$, right? (Wondering)

 

[Deveno]

I will try first to verify the homomorphism property.

That's fine.

Any group of 4 elements is abelian.

We pick $a\neq e \in G$ with $|G| = 4$.

The possible orders of $a$ are the divisors of $4$, so the possible orders are $2$ and $4$. (It isn't $1$ since $a\neq e$.)

If $a$ has order $4$, $G$ is cyclic. I haven't understood why this stand... Could you explain it to me? (Wondering)
Is a cyclic group abelian? (Wondering)

Yes, all cyclic groups are abelian. Can you prove this?

If $a$ has order $2$, then there will be an element $b \not\in \langle a\rangle = \{e,a\}$. Why is there such a $b$ ? (Wondering)

If $a$ has order 2, then the only powers of $a$ that are distinct are $e = a^0$ and $a = a^1$, since:

$a^2 = e$
$a^3 = a(a^2) = a$
$a^4 = (a^2)(a^2) = ee = e$
$a^5 = (a^3)(a^2) = ae = a$...and so on (so only two non-negative powers).

But if $a^2 = e$ then $a^{-1} = a$, and this is the unique inverse of $a$. So for any negative power:

$a^{-k} = (a^{-1})^k = a^k$, so we don't get any more powers here.

Since $G$ has four elements, and the subgroup generated by $a$ only has two elements, we must have something else in $G$, right?

The possible orders of $b$ are again $2$ and $4$.
If $b$ has order $4$, we again have a cyclic group.
Assume that the order of $b$ is $2$.
Since $a\in G$ and $b\in G$, $ab$ must be also an element of $G$.

Since $a,b\in $ then $a^{-1},b^{-1}\in G$.
When $ab=e$, then $aab=a\Rightarrow a^2b=a \Rightarrow b=a$, that cannot be true, since $b\notin \{a,e\}$.
When $ab=a$, then $aab=aa \Rightarrow a^2b=a^2 \Rightarrow b=e$, that cannot be true, since $b\notin \{a,e\}$.
When $ab=b$, then $abb=bb \Rightarrow ab^2=b^2 \Rightarrow a=e$, that cannot be true, since $a\neq e$.

Right? (Wondering)

Therefore, $ab \neq e$, and $ab \neq a$, and $ab \neq b$. That means that $G = \{e,a,b,ab\}$

Perfect.

We have $$ab=x \Rightarrow aab=ax \Rightarrow a^2b=ax \Rightarrow b=ax\Rightarrow b^2=axb \Rightarrow e=axb$$

Is it correct so far? How could we continue? (Wondering)

I would argue as follows:

$ba = e \implies bba = b \implies a = b$, contradiction.
$ba = a \implies baa = aa \implies b = e$, contradiction.
$ba = b \implies bba = bb \implies a = e$, contradiction.

Hence $ba = ab$.

(proving this is *possible* is shown by the example $\Bbb Z_2 \times \Bbb Z_2$ with $a = (1,0)$ and $b = (0,1)$).

Having shown that $ab=ba$ do we conclude that $G$ is abelian? Or do we have to show it also for the multiplication of $ab$ with $a$ and $b$? (Wondering)

Since $ab\neq e$ and $(ab)^2=(ab)(ab)=abba=aea=aa=e$, we conclude that $ab$ has order $2$ since $a$ and $b$ have order $2$, right? (Wondering)

Well it suffices to show that "everything commutes with everything", right?

$e$ clearly commutes with anything.

$a$ commutes with $a$: because $aa = aa$.

$a$ commutes with $b$: because $ab = ba$.

$a$ commutes with $ab$: because $a(ab) = a(ba) = (ab)a$.

Now we have already shown that $b$ commutes with $e$ and $a$, so we just need to show that $b$ commutes with itself (which is obvious) and $ab$:

$b(ab) = (ba)b = (ab)b$, done.

Finally, above we see that $ab$ commutes with $e,a$ and $b$, so the only thing we haven't checked is that $ab$ commutes with itself, which is again obvious:

$(ab)(ab) = (ab)(ab)$.

And, yes, your proof of the order of $ab$ is correct. Good job!

 

[mathmari]

Yes, all cyclic groups are abelian. Can you prove this?

Suppose that a group $G$ is cyclic, then it is generated by a generator, say $g$.
Then every element of $G$ can be written in the form $g^i$ for some $i$.
Suppose that $x,y\in G$ then $x=g^k$ and $y=g^m$.
We have $$xy=g^kg^m=g^{k+m}=g^{m+k}=g^mg^k=yx$$
Therefore, a cyclic group is abelian.

Is this correct? (Wondering)

If $a$ has order 2, then the only powers of $a$ that are distinct are $e = a^0$ and $a = a^1$, since:

$a^2 = e$
$a^3 = a(a^2) = a$
$a^4 = (a^2)(a^2) = ee = e$
$a^5 = (a^3)(a^2) = ae = a$...and so on (so only two non-negative powers).

But if $a^2 = e$ then $a^{-1} = a$, and this is the unique inverse of $a$. So for any negative power:

$a^{-k} = (a^{-1})^k = a^k$, so we don't get any more powers here.

Since $G$ has four elements, and the subgroup generated by $a$ only has two elements, we must have something else in $G$, right?

Ah ok... (Nerd)

I would argue as follows:

$ba = e \implies bba = b \implies a = b$, contradiction.
$ba = a \implies baa = aa \implies b = e$, contradiction.
$ba = b \implies bba = bb \implies a = e$, contradiction.

Hence $ba = ab$.

(proving this is *possible* is shown by the example $\Bbb Z_2 \times \Bbb Z_2$ with $a = (1,0)$ and $b = (0,1)$).

I see... (Nerd)

Well it suffices to show that "everything commutes with everything", right?

$e$ clearly commutes with anything.

$a$ commutes with $a$: because $aa = aa$.

$a$ commutes with $b$: because $ab = ba$.

$a$ commutes with $ab$: because $a(ab) = a(ba) = (ab)a$.

Now we have already shown that $b$ commutes with $e$ and $a$, so we just need to show that $b$ commutes with itself (which is obvious) and $ab$:

$b(ab) = (ba)b = (ab)b$, done.

Finally, above we see that $ab$ commutes with $e,a$ and $b$, so the only thing we haven't checked is that $ab$ commutes with itself, which is again obvious:

$(ab)(ab) = (ab)(ab)$.

I understand... (Smile)
So, having shown that a group of $4$ elements is abelian, we have that $\text{Aut}(\mathbb{Z}_8)$, which has $4$ elements, is abelian.

Therefore, $$\text{id}\circ f_i=f_i\circ \text{id} \\ f_i\circ f_j =f_j\circ f_i$$ for $i,j=1,2,3$ and $i\neq j$.

We have the following:
$$(\text{id}\circ \text{id})(x)=\text{id}(\text{id}(x))=\text{id}(x)=x$$
So, $\text{id}\circ\text{id}$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(\text{id}\circ\text{id})=h(\text{id})=(0,0)=(0,0)+(0,0)=h(\text{id})+h(\text{id})$. $$(f_1\circ f_1)(x)=f_1(f_1(x))=f_1(3x)=3( 3 x)=9x\equiv x$$
So, $f_1\circ f_1$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(f_1\circ f_1)=h(\text{id})=(0,0)=(0,1)+(0,1)=h(f_1)+h(f_1)$. $$(f_2\circ f_2)(x)=f_2(f_2 (x))=f_2(-3x)=-3(-3x)=9x\equiv x$$
So, $f_2\circ f_2$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(f_2\circ f_2)=h(\text{id})=(0,0)=(1,0)+(1,0)=h(f_2)+h(f_2)$. $$(f_3\circ f_3)(x)=f_3(f_3(x))=f_3(-x)=-(-x)=x$$
So, $f_3\circ f_3$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(f_3\circ f_3)=h(\text{id})=(0,0)=(1,1)+(1,1)=h(f_3)+h(f_3)$. $$(f_1 \circ f_2)(x)=f_1(f_2 (x))=f_1(-3x)=3(-3x)=-9x\equiv -x$$
So, $f_1\circ f_2$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto -x$, so it is the function $f_3$.
Therefore, we have $h(f_1\circ f_2)=h(f_3)=(1,1)=(0,1)+(1,0)=h(f_1)+h(f_2)$. $$(f_1\circ f_3)(x)=f_1(f_3(x))=f_1(-x)=3(-x)=-3x$$
So, $f_1\circ f_3$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto -3x$, so it is the function $f_2$.
Therefore, we have $h(f_1\circ f_3)=h(f_2)=(1,0)=(0,1)+(1,1)=h(f_1)+h(f_3)$. $$(f_2\circ f_3)(x)=f_2(f_3(x))=f_2(-x)=-3(-x)=3x$$
So, $f_2\circ f_3$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto 3x$, so it is the function $f_1$.
Therefore, we have $h(f_2\circ f_3)=h(f_1)=(0,1)=(1,0)+(1,1)=h(f_2)+h(f_3)$.
So, we have that $h$ is an homomorphism.

Is this correct? (Wondering)
Is $h$ 1-1 and onto because we have defined the function so that each element of $\text{Aut}(\mathbb{Z}_8)$ is mapped to one element in $\mathbb{Z}_2\times\mathbb{Z}_2$ and each element of $\mathbb{Z}_2\times\mathbb{Z}_2$ has its original in $\text{Aut}(\mathbb{Z}_8)$? (Wondering)

 

[Deveno]

Suppose that a group $G$ is cyclic, then it is generated by a generator, say $g$.
Then every element of $G$ can be written in the form $g^i$ for some $i$.
Suppose that $x,y\in G$ then $x=g^k$ and $y=g^m$.
We have $$xy=g^kg^m=g^{k+m}=g^{m+k}=g^mg^k=yx$$
Therefore, a cyclic group is abelian.

Is this correct? (Wondering)

Yes. Notice that all the "action" happens in the exponents-the "$x$" just acts as a placeholder, of sorts. So a cyclic group is abelian BECAUSE the integers are abelian (under addition). In fact, EVERY cyclic group is a homomorphic image of the integers-if it is an isomorphic image (1-1 and onto) it is isomorphic to the images. If it is just an image (only onto), it is a FINITE cyclic group (with the smallest (positive) "repeat" of powers being the ORDER), isomorphic to $\Bbb Z_n$ for some $n$.

Ah ok... (Nerd)



I see... (Nerd)

I understand... (Smile)

Cool.

So, having shown that a group of $4$ elements is abelian, we have that $\text{Aut}(\mathbb{Z}_8)$, which has $4$ elements, is abelian.

Therefore, $$\text{id}\circ f_i=f_i\circ \text{id} \\ f_i\circ f_j =f_j\circ f_i$$ for $i,j=1,2,3$ and $i\neq j$.

We have the following:
$$(\text{id}\circ \text{id})(x)=\text{id}(\text{id}(x))=\text{id}(x)=x$$
So, $\text{id}\circ\text{id}$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(\text{id}\circ\text{id})=h(\text{id})=(0,0)=(0,0)+(0,0)=h(\text{id})+h(\text{id})$. $$(f_1\circ f_1)(x)=f_1(f_1(x))=f_1(3x)=3( 3 x)=9x\equiv x$$
So, $f_1\circ f_1$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(f_1\circ f_1)=h(\text{id})=(0,0)=(0,1)+(0,1)=h(f_1)+h(f_1)$. $$(f_2\circ f_2)(x)=f_2(f_2 (x))=f_2(-3x)=-3(-3x)=9x\equiv x$$
So, $f_2\circ f_2$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(f_2\circ f_2)=h(\text{id})=(0,0)=(1,0)+(1,0)=h(f_2)+h(f_2)$. $$(f_3\circ f_3)(x)=f_3(f_3(x))=f_3(-x)=-(-x)=x$$
So, $f_3\circ f_3$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto x$, so it is the function $\text{id}$.
Therefore, we have $h(f_3\circ f_3)=h(\text{id})=(0,0)=(1,1)+(1,1)=h(f_3)+h(f_3)$. $$(f_1 \circ f_2)(x)=f_1(f_2 (x))=f_1(-3x)=3(-3x)=-9x\equiv -x$$
So, $f_1\circ f_2$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto -x$, so it is the function $f_3$.
Therefore, we have $h(f_1\circ f_2)=h(f_3)=(1,1)=(0,1)+(1,0)=h(f_1)+h(f_2)$. $$(f_1\circ f_3)(x)=f_1(f_3(x))=f_1(-x)=3(-x)=-3x$$
So, $f_1\circ f_3$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto -3x$, so it is the function $f_2$.
Therefore, we have $h(f_1\circ f_3)=h(f_2)=(1,0)=(0,1)+(1,1)=h(f_1)+h(f_3)$. $$(f_2\circ f_3)(x)=f_2(f_3(x))=f_2(-x)=-3(-x)=3x$$
So, $f_2\circ f_3$ is the function $\mathbb{Z}_8\rightarrow \mathbb{Z}_8$ that maps $x\mapsto 3x$, so it is the function $f_1$.
Therefore, we have $h(f_2\circ f_3)=h(f_1)=(0,1)=(1,0)+(1,1)=h(f_2)+h(f_3)$.
So, we have that $h$ is an homomorphism.

Is this correct? (Wondering)

Yes...verified in excruciating detail. You might look for short-cuts with large groups.

Is $h$ 1-1 and onto because we have defined the function so that each element of $\text{Aut}(\mathbb{Z}_8)$ is mapped to one element in $\mathbb{Z}_2\times\mathbb{Z}_2$ and each element of $\mathbb{Z}_2\times\mathbb{Z}_2$ has its original in $\text{Aut}(\mathbb{Z}_8)$? (Wondering)

Yes, this is clear to see.

 

[mathmari]

Yes. Notice that all the "action" happens in the exponents-the "$x$" just acts as a placeholder, of sorts. So a cyclic group is abelian BECAUSE the integers are abelian (under addition). In fact, EVERY cyclic group is a homomorphic image of the integers-if it is an isomorphic image (1-1 and onto) it is isomorphic to the images. If it is just an image (only onto), it is a FINITE cyclic group (with the smallest (positive) "repeat" of powers being the ORDER), isomorphic to $\Bbb Z_n$ for some $n$.

Ah ok... (Thinking)

You might look for short-cuts with large groups.

What do you mean? (Wondering)

 

[Deveno]

Ah ok... (Thinking)


What do you mean? (Wondering)

Well suppose you wanted to classify $\text{Aut}(\Bbb Z_{90})$. There's a LOT of products to check, right?

 

[mathmari]

Well suppose you wanted to classify $\text{Aut}(\Bbb Z_{90})$. There's a LOT of products to check, right?

Yes... What would we do in that case? (Wondering)

 

[Deveno]

maybe if $\text{Aut}(\Bbb Z_n) \cong (\Bbb Z_n)^{\times} = U(n)$ that would help?