Number of elements of order two in S_n

Posted: December 3, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: , ,

Problem 1. For an integer $n \ge 2,$ let $a_n$ be the number of elements of order two in the symmetric group $S_n.$ It is clear that $a_1=0.$ Show that for any integer $n \ge 2$ we have

$\displaystyle a_n=n!\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor}\frac{1}{2^kk!(n-2k)!}.$

Solution. We know that every element of $S_n$ can be written uniquely as a product of disjoint cycles (here “uniquely” means up to the order in which the cycles are written down). We also know that the order of a product of disjoint cycles is the least common divisor of the order of the cycles. So an element of $S_n$ has order two if and only if it’s a product of disjoint cycles of length two and that’s the number we need to find.
Let

$\displaystyle \sigma=(a_1 \ a_2)(a_3 \ a_4) \cdots (a_{2k-1} \ a_{2k})$

be a product of disjoint cycles of length two. Then obviously $1 \le k \le \lfloor \frac{n}{2} \rfloor.$ Now, there are $\displaystyle \binom{n}{2}$ ways to choose $(a_1 \ a_2)$ and $\displaystyle \binom{n-2}{2}$ ways to choose $\displaystyle (a_3 \ a_4)$ and $\displaystyle \binom{n-4}{2}$ ways to choose $\displaystyle (a_5 \ a_6)$ and … finally $\displaystyle \binom{n-2k+2}{2}$ ways to choose $\displaystyle (a_{2k-1} \ a_{2k}).$ So there are

$\displaystyle \frac{1}{k!}\binom{n}{2}\binom{n-2}{2} \binom{n-4}{2} \cdots \binom{n-2k+2}{2}$

possibilities for $\sigma$ and hence

$\displaystyle a_n=\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{k!}\binom{n}{2}\binom{n-2}{2} \binom{n-4}{2} \cdots \binom{n-2k+2}{2}=\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor}\frac{n!(n-2)!(n-4)! \cdots (n-2k+2)!}{2^kk!(n-2)!(n-4)!(n-6)! \cdots (n-2k)!}$

$\displaystyle =n!\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor}\frac{1}{2^kk!(n-2k)!}. \ \Box$

Problem 2. For any integer $n \ge 1,$ let $b_n$ be the number of solutions of the equation $x^2=1$ in the symmetric group $S_n,$ where $1$ is the identity element of $S_n.$ It is clear that $b_1=1$ and $b_2=2.$ Show that for any integer $n \ge 2$ we have

$b_{n+1}=b_n+nb_{n-1}.$

Solution. It is clear that $b_1=1, \ b_2=2.$ For $n \ge 2,$ let $B_n:=\{x \in S_n: \ x^2=1\}.$ So $b_n=|B_n|.$ Let $\sigma \in B_{n+1}$ and put $\sigma(n+1)=k.$ If $k=n+1,$ then there is $b_n$ possibilities for $\sigma.$ But if $1 \le k \le n,$ then, since $\sigma^2=1,$ we have $n+1=\sigma^2(n+1)=\sigma(k)$ and hence there will be $b_{n-1}$ possibilities for $\sigma.$
So $b_{n+1}=b_n+nb_{n-1}. \ \Box$

Problem 3. Let $\{a_n\},\{b_n\}$ be the sequences defined in Problem 1 and Problem 2, respectively. It is clear that $b_n=a_n+1$ and so since, by Problem 2, $\{b_n\}$ satisfies the recurrence relation $b_{n+1}=b_n+nb_{n-1},$ for all $n \ge 2,$ the sequence $\{a_n\}$ satisfies

$a_{n+1}=a_n+na_{n-1}+n \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

for all $n \ge 2.$ Prove $(*)$ using the formula for $a_n$ given in Problem 1.

Solution. I prove $(*)$ for $n$ even and I leave the proof for odd values of $n$ to the reader. So let $n=2m,$ where $m$ is a positive integer. Then, by Problem 1,

\displaystyle \begin{aligned} a_{2m+1}=(2m+1)!\sum_{k=1}^{m}\frac{1}{2^kk!(2m-2k+1)!}=(2m)!\sum_{k=1}^{m}\frac{2m+1}{2^kk!(2m-2k+1)!}=(2m)!\sum_{k=1}^{m}\frac{2m-2k+1+2k}{2^kk!(2m-2k+1)!}\end{aligned}

$\displaystyle =(2m)!\sum_{k=1}^m\frac{1}{2^kk!(2m-2k)!}+(2m)!\sum_{k=1}^m\frac{1}{2^{k-1}(k-1)!(2m-2k+1)!}$

$\displaystyle =a_{2m}+(2m)!\sum_{k=0}^{m-1}\frac{1}{2^kk!(2m-2k-1)!}=a_{2m}+(2m)!\left(\sum_{k=1}^{m-1}\frac{1}{2^kk!(2m-2k-1)!}+\frac{1}{(2m-1)!}\right)$

$=a_{2m}+2ma_{2m-1}+2m. \ \Box$

Exercise. In the solution of Problem 1, to find the number of possibilities for $\sigma,$ explain why we divided $\displaystyle \binom{n}{2}\binom{n-2}{2} \binom{n-4}{2} \cdots \binom{n-2k+2}{2}$ by $k!$.

Number of endomorphisms of a finite abelian group

Posted: October 9, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields

Recall that, given groups $G_1,G_2,$ the set of group homomorphisms $G_1 \to G_2$ is denoted by $\text{Hom}(G_1,G_2).$ If $G_1=G_2=G,$ then a group homomorphism $G \to G$ is called an endomorphism and, in this case, we write $\text{End}(G)$ instead of $\text{Hom}(G,G).$

Problem. i) Let $G_1,G_2$ be finite abelian groups. Find $|\text{Hom}(G_1,G_2)|.$

ii) Let $G$ be a finite abelian group. Find $\text{End}(G)$ and show that $|G|$ divides $|\text{End}(G)|.$

iii) Let $G$ be a finite abelian group of order $n.$ Show that $|\text{End}(G)|= n$ if and only if $G \cong \mathbb{Z}_n.$

Solution. i) By the fundamental theorem for finite abelian groups, we have

$G_1 \cong \mathbb{Z}_{m_1} \times \cdots \times \mathbb{Z}_{m_k}, \ \ \ G_2 \cong \mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_{\ell}}$

for some integers $m_1, \cdots, m_k,n_1, \cdots, n_{\ell} \ge 2.$ Then by the problems in this post and this post, we have

$\displaystyle \text{Hom}(G_1,G_2) \cong \text{Hom}(\mathbb{Z}_{m_1} \times \cdots \times \mathbb{Z}_{m_k},\mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_{\ell}}) \cong \prod_{1 \le i \le k, \ 1 \le j \le \ell}\text{Hom}(\mathbb{Z}_{m_i},\mathbb{Z}_{n_j})$

$\displaystyle \cong \prod_{1 \le i \le k, \ 1 \le j \le \ell}\mathbb{Z}_{\gcd(m_i,n_j)}.$

and so, by the problem is this post,

$\displaystyle |\text{Hom}(G_1,G_2)|=\prod_{1 \le i \le k, \ 1 \le j \le \ell}\gcd(m_i,n_j).$

That completes the solution of i).

Now let $G$ be a finite abelin group. Then, by the fundamental theorem for finite abelian groups,

$G \cong \mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_k},$

for some integers $n_1, \cdots, n_k \ge 2,$ where $n_i \mid n_{i+1}$ for all $i=1, \cdots , k-1.$ We can now solve ii) and iii).

ii) By i), we have

$\displaystyle \text{End}(G) =\text{Hom}(G,G) \cong \prod_{1 \le i,j \le k}\mathbb{Z}_{\gcd(n_i,n_j)}$

and so

$\displaystyle |\text{End}(G)|=\prod_{1 \le i,j \le k}\gcd(n_i,n_j).$

Thus, since $n_i \mid n_j$ whenever $i \le j,$ we have

$|\text{End}(G)|=n_1^k(n_1n_2^{k-1})(n_1n_2n_3^{k-2}) \cdots (n_1n_2 \cdots n_k)=n_1^{2k-1}n_2^{2k-3} \cdots n_k. \ \ \ \ \ \ \ \ \ (*)$

Since $|G|=n_1n_2 \cdots n_k,$ it’s clear from $(*)$ that $|G|$ divides $|\text{End}(G)|.$

iii) Using $(*)$ in ii), we have

$n=|G|=n_1n_2 \cdots n_k=|\text{End}(G)|= n_1^{2k-1}n_2^{2k-3} \cdots n_k$

if and only if $k=1,$ i.e. $n=n_1$ and so $G \cong \mathbb{Z}_{n_1}=\mathbb{Z}_n. \ \Box$

Example 1. Let $p$ be a prime number and suppose that $G$ is a group of order $p^2.$ Find $\text{End}(G)$ and $|\text{End}(G)|.$

Solution. We know that a group of order $p^2$ is abelian. Thus, by the fundamental theorem for finite abelian groups, either $G \cong \mathbb{Z}_{p^2}$ or $G \cong \mathbb{Z}_p \times \mathbb{Z}_p.$
So, by the second part of the above problem, if $G \cong \mathbb{Z}_{p^2},$ then $\text{End}(G) \cong \mathbb{Z}_{p^2}$ hence

$|\text{End}(G)|=p^2=|G|$

and if $G \cong \mathbb{Z}_p \times \mathbb{Z}_p,$ then $\text{End}(G) \cong \mathbb{Z}_p \times \mathbb{Z}_p \times \mathbb{Z}_p \times \mathbb{Z}_p$ hence

$|\text{End}(G)|=p^4=|G|^2. \ \Box$

Example 2. Find all finite abelian groups $G$ for which $|\text{End}(G)|=|G|^2.$

Solution. Again, by the fundamental theorem for finite abelian groups,

$G \cong \mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_k},$

for some integers $n_1, \cdots, n_k \ge 2,$ where $n_i \mid n_{i+1}$ for all $i=1, \cdots ,k-1.$ So, using the second part of the above problem, we want to have

$n_1^2n_2^2 \cdots n_k^2=|G|^2= |\text{End}(G)|=n_1^{2k-1}n_2^{2k-3} \cdots n_k.$

That obviously has no solution for $k=1$ and for $k \ge 2,$ it is equivalent to $n_k=n_1^{2k-3}n_2^{2k-5} \cdots n_{k-1}.$
So the set of groups that satisfy the condition is

$\{\mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_k}: \ \ \ k \ge 2, \ \ n_1 \mid n_2 \mid \cdots \mid n_{k-1}, \ \ n_k=n_1^{2k-3}n_2^{2k-5} \cdots n_{k-1}\}. \ \Box$

Exercise. Find all finite abelian groups $G$ for which $|\text{End}(G)|=|G|^3.$

Posted: October 5, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields

There are many infinite groups with this property that every element of the group has a finite order; for example, any direct product of infinitely many copies of a finite group.
Another example is the quotient group $G:=(\mathbb{Q}/\mathbb{Z},+),$ which is the subject of the following problem.

Problem. Consider the additive group $G:=\mathbb{Q}/\mathbb{Z}.$ Show that

i) $G$ is isomorphic to the multiplicative group of complex roots of unity

ii) every finitely generated subgroup of $G$ is cyclic

iii) $G$ has infinitely many non-cyclic subgroups $H_1, H_2, \cdots$ such that $H_i \cap H_j=(0)$ for all $i \ne j$

iv) for every integer $n \ge 1, \ G$ has a unique subgroup of order $n$

v) there is no unitary ring whose additive group is isomorphic to $G.$

Solution. i) Let $U$ be the multiplicative group of complex roots of unity, i.e.

$U=\{z \in \mathbb{C}: \ \ z^n=1, \ \ \text{for some integer} \ n \ge 1\}$

and define the map $f: G \to U$ by $f(q+\mathbb{Z})=e^{2\pi q i},$ for all $q \in \mathbb{Q}.$ See that $f$ is a group isomorphism.

ii) Let $H$ be a subgroup of $G$ generated by

$\displaystyle \frac{a_i}{b_i}+\mathbb{Z}, \ \ a_i,b_i \in \mathbb{Z}, \ i=1, \cdots , n$

and let $b:=b_1b_2 \cdots b_n.$ Let $K$ be the cyclic subgroup of $G$ generated by $\displaystyle \frac{1}{b}+\mathbb{Z}.$ Then for each $i$ we have $\displaystyle c_i:=\frac{b}{b_i} \in \mathbb{Z}$ and $\displaystyle \frac{a_i}{b_i}+\mathbb{Z}=\frac{a_ic_i}{b}+\mathbb{Z} \in K.$ Thus $H \subseteq K$ and hence $H$ is cyclic (because every subgroup of a cyclic group is cyclic).

iii) For any prime number $p$ let $H_p$ be the subgroup of $G$ generated by $\displaystyle \frac{1}{p^n}+\mathbb{Z}, \ \ n=1,2, \cdots.$ Suppose that $H_p$ is cyclic with the generator $\displaystyle h=\sum_{i=1}^m \frac{a_i}{p^{n_i}}+\mathbb{Z}, \ \ a_i \in \mathbb{Z}.$ Let $n:=\max\{n_1, \cdots , n_m\}.$ Then $\displaystyle h=\frac{a}{p^n}+\mathbb{Z}$ for some $a \in \mathbb{Z}.$ So since

$\displaystyle \frac{1}{p^{n+1}}+\mathbb{Z} \in H_p=\langle h \rangle,$

we must have $\displaystyle \frac{1}{p^{n+1}}+\mathbb{Z}=\frac{k}{p^n}+\mathbb{Z}$ for some integer $k.$ But then $\displaystyle \frac{k}{p^n}-\frac{1}{p^{n+1}} \in \mathbb{Z}$ and so $\displaystyle \frac{1}{p} \in \mathbb{Z},$ which is absurd. So $H_p$ is not cyclic. It’s easy to see that if $p \ne q$ are primes, then $H_p \cap H_q=(0).$

iv) Let $H$ be the subgroup of $G$ generated by $\displaystyle \frac{1}{n}+\mathbb{Z}.$ Clearly $|H|=n.$ Now suppose that $K$ is any subgroup of $G$ with $|K|=n.$ By ii), $K$ is cyclic and so it has a generator $\displaystyle \frac{a}{b}+\mathbb{Z},$ where $a,b \in \mathbb{Z}, \ \gcd(a,b)=1.$ Since $|K|=n,$ we have $\displaystyle \frac{na}{b} \in \mathbb{Z}$ and so $b \mid n.$ So $n=bc$ for some integer $c$ and hence

$\displaystyle \frac{a}{b}+\mathbb{Z}=\frac{ac}{n}+\mathbb{Z} \in H.$

Thus $K \subseteq H$ and hence $K=H$ because $|H|=|K|.$

v) Suppose that $R$ is a unitary ring and there exists an isomorphism of additive groups $f: G \to (R,+).$ Let $\displaystyle 1_R=f\left(\frac{a}{b}+\mathbb{Z}\right), \ \ a,b \in \mathbb{Z}, \ b > 0,$ and $\displaystyle r:=f\left(\frac{1}{b+1}+\mathbb{Z}\right).$ Then

$\displaystyle 0=f(a+\mathbb{Z})r=bf\left(\frac{a}{b}+\mathbb{Z}\right)r=b1_Rr=br=f\left(\frac{b}{b+1}+\mathbb{Z}\right)$

and so $\displaystyle \frac{b}{b+1} + \mathbb{Z}=0,$ i.e. $\displaystyle \frac{b}{b+1} \in \mathbb{Z},$ which is nonsense. This contradiction proves that $G$ and $(R,+)$ can’t be isomorphic. $\Box$

Exercise. This exercise is related to the second part of the above problem. Let $H$ be a subgroup of $\mathbb{Q}/\mathbb{Z}$ generated by $\displaystyle \frac{a_i}{b_i}+\mathbb{Z}, \ \ a_i,b_i \in \mathbb{Z}, \ b_i > 0, \ i=1, \cdots , n,$ and let $b:=\text{lcm}(b_1, \cdots , b_n).$ Is $H$ generated by $\displaystyle \frac{1}{b}+\mathbb{Z} \ ?$

Group homomorphism – direct product (2)

Posted: September 26, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields

Throughout this post, $G,G_1, \cdots , G_n$ are groups.

As always, for groups $G,H,$ the set of group homomorphisms $G \to H$ is denoted by $\text{Hom}(G,H).$

Notation. For any $i=1, \cdots , n,$ we have a group homomorphism $\mu_i: G_1 \times \cdots \times G_n \to G_i$ defined by

$\mu_i(x_1, \cdots , x_n)=x_i.$

Problem. Define the map

$\varphi: \text{Hom}(G,G_1 \times \cdots \times G_n) \to \text{Hom}(G,G_1) \times \cdots \times \text{Hom}(G,G_n)$

by

$\varphi(f)=(\mu_1f, \cdots , \mu_nf)$

for all $f \in \text{Hom}(G,G_1 \times \cdots \times G_n).$ Show that

i) $\varphi$ is one-to-one

ii) $\varphi$ is onto

iii) if $G_1, \cdots , G_n$ are abelian, then $\varphi$ is a group isomorphism.

Solution. i) Suppose that $\varphi(f)=\varphi(g)$ for some $f,g \in \text{Hom}(G,G_1 \times \cdots \times G_n).$ Then, by the definition of $\varphi,$ we have $\mu_if=\mu_ig$ for all $i=1, \cdots , n.$ Let $x \in G$ and suppose that

$f(x)=(y_1, \cdots , y_n), \ \ g(x)=(z_1, \cdots , z_n),$

where $y_i,z_i \in G_i.$ Then

$y_i=\mu_i(f(x))=(\mu_if)(x)=(\mu_ig)(x)=\mu_i(g(x))=z_i$

for all $i.$ So $f(x)=g(x)$ and hence $f=g$ proving that $\varphi$ is one-to-one.

ii) Let $f_i \in \text{Hom}(G,G_i), \ \ i=1, \cdots , n,$ and define $f: G \to G_1 \times \cdots \times G_n$ by

$f(x)=(f_1(x), \cdots , f_n(x)),$

for all $x \in G.$ It’s clear that $f$ is a homomorphism because each $f_i: G \to G_i$ is a homomorphism. Also $(\mu_i f)(x)=\mu_i(f(x))=f_i(x)$ for all $x \in G$ and hence $\mu_if=f_i.$ So

$\varphi(f)=(\mu_1f, \cdots , \mu_nf)=(f_1, \cdots , f_n)$

proving that $\varphi$ is onto.

iii) By i), ii), we only need to show that $\varphi$ is a group homomorphism. As I mentioned at the beginning of this post, since each $G_i$ is abelian, $\text{Hom}(G,G_i), \ i=1, \cdots , n,$ and $\text{Hom}(G,G_1 \times \cdots \times G_n)$ are all abelian groups too.
Now let $f,g \in \text{Hom}(G,G_1 \times \cdots \times G_n)$ and $x \in G.$ Let

$f(x)=(y_1, \cdots , y_n), \ \ g(x)=(z_1, \cdots , z_n).$

Then

$(\mu_ifg)(x)=\mu_i(fg(x))=\mu_i(f(x)g(x))=\mu_i(y_1z_1, \cdots , y_nz_n)=y_iz_i=(\mu_if)(x)(\mu_ig)(x)$

$=(\mu_if\mu_ig)(x)$

and so $\mu_ifg=\mu_if\mu_ig.$ Thus

$\varphi(fg)=(\mu_1fg, \cdots , \mu_nfg)=(\mu_1f\mu_1g, \cdots , \mu_nf\mu_ng)=(\mu_1f, \cdots , \mu_nf)(\mu_1g, \cdots , \mu_ng)$

$=\varphi(f)\varphi(g)$

and that means $\varphi$ is a group homomorphism. $\Box$

Remark. If $G,G_1, \cdots, G_n$ are all abelian groups, then by the above problem and the problem in the first part of this post, we have

$\text{Hom}(G_1 \times \cdots \times G_n,G) \cong \text{Hom}(G_1,G) \times \cdots \times \text{Hom}(G_n,G)$

and

$\text{Hom}(G,G_1 \times \cdots \times G_n) \cong \text{Hom}(G,G_1) \times \cdots \times \text{Hom}(G,G_n).$

Example. Find the number of group homomorphisms $\mathbb{Z}_2 \times \mathbb{Z}_2 \to S_3 \times S_3.$

Solution. By the above problem, parts i) and ii), there’s a bijection between $\text{Hom}(\mathbb{Z}_2 \times \mathbb{Z}_2, S_3 \times S_3)$ and $\text{Hom}(\mathbb{Z}_2 \times \mathbb{Z}_2, S_3) \times \text{Hom}(\mathbb{Z}_2 \times \mathbb{Z}_2, S_3).$ By Example 2 in this post, $|\text{Hom}(\mathbb{Z}_2 \times \mathbb{Z}_2, S_3)|=10$ and hence $|\text{Hom}(\mathbb{Z}_2 \times \mathbb{Z}_2, S_3 \times S_3)|=|\text{Hom}(\mathbb{Z}_2 \times \mathbb{Z}_2, S_3)|^2=100. \ \Box$

Group homomorphism – direct product (1)

Posted: September 26, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields

Throughout this post, $G,G_1, \cdots , G_n$ are groups.

As always, for groups $G,H,$ the set of group homomorphisms $G \to H$ is denoted by $\text{Hom}(G,H).$

Notation. For any $i=1, \cdots , n,$ we have a group homomorphism $\lambda_i: G_i \to G_1 \times \cdots \times G_n$ defined by

$\lambda_i(x_i)=(1, \cdots 1,x_i,1 \cdots , 1).$

See that $(x_1, \cdots , x_n)= \lambda_1(x_1) \cdots \lambda_n(x_n)$ for all $(x_1, \cdots , x_n) \in G_1 \times \cdots \times G_n.$

Problem. Define the map

$\varphi: \text{Hom}(G_1 \times \cdots \times G_n,G) \to \text{Hom}(G_1,G) \times \cdots \times \text{Hom}(G_n,G)$

by

$\varphi(f)=(f\lambda_1, \cdots , f\lambda_n)$

for all $f \in \text{Hom}(G_1 \times \cdots \times G_n,G).$ Show that

i) $\varphi$ is one-to-one

ii) if $G$ is abelian, then $\varphi$ is a group isomorphism.

Solution. i) Suppose that $\varphi(f)=\varphi(g)$ for some $f,g \in \text{Hom}(G_1 \times \cdots \times G_n,G).$ Then, by the definition of $\varphi,$ we have $f \lambda_i=g\lambda_i$ for all $i=1, \cdots , n$ and thus for $(x_1, \cdots , x_n) \in G_1 \times \cdots \times G_n,$ we have

$f(x_1, \cdots , x_n)=f(\lambda_1(x_1) \cdots \lambda_n(x_n))=f(\lambda_1(x_1)) \cdots f(\lambda_n(x_n))=g(\lambda_1(x_1)) \cdots g(\lambda_n(x_n))$

$=g(\lambda_1(x_1) \cdots \lambda_n(x_n))=g(x_1, \cdots , x_n)$

and so $f=g$ proving that $\varphi$ is one-to-one.

ii) We have already shown in i) that $\varphi$ is injective. So we only need to show that $\varphi$ is a an onto group homomorphism. Note that, as I mentioned at the beginning of this post, since $G$ is an abelian group, $\text{Hom}(G_i,G), \ i=1, \cdots , n,$ and $\text{Hom}(G_1 \times \cdots \times G_n,G)$ are all abelian groups too.

1) $\varphi$ is a group homomorphism. To prove this, let $f,g \in \text{Hom}(G_1 \times \cdots \times G_n,G)$ and $x_i \in G_i.$ Then

$(f\lambda_i g \lambda_i)(x_i)=(f\lambda_i)(x_i)(g\lambda_i)(x_i)=f(\lambda_i(x_i))g(\lambda_i(x_i))=fg(\lambda_i(x_i))=(fg\lambda_i)(x_i)$

and so $fg\lambda_i=f\lambda_ig\lambda_i$ for all $i=1, \cdots , n.$ Thus

$\varphi(fg)=(fg\lambda_1, \cdots , fg\lambda_n)=(f\lambda_1g\lambda_1, \cdots , f\lambda_ng\lambda_n)=(f\lambda_1, \cdots , f\lambda_n)(g\lambda_1, \cdots, g\lambda_n)$

$=\varphi(f)\varphi(g).$

2) $\varphi$ is onto. To prove this, let $f_i \in \text{Hom}(G_i,G), \ i=1, \cdots , n$ and define $f: G_1 \times \cdots \times G_n \to G$ by

$f(x_1, \cdots , x_n)=f_1(x_1) \cdots f_n(x_n)$

for all $x_i \in G_i, \ i=1, \cdots , n.$ Since each $f_i: G_i \to G$ is a group homomorphism and $G$ is abelian, $f$ is a group homomorphism and

$f\lambda_i(x_i)=f(1, \cdots , 1, x_i,1, \cdots, 1)=f_1(1) \cdots f_i(x_i) \cdots f_n(1)=f_i(x_i).$

So $f \lambda_i=f_i$ for all $i$ and hence

$\varphi(f)=(f\lambda_1, \cdots , f\lambda_n)=(f_1, \cdots , f_n)$

proving that $\varphi$ is onto. $\Box$

Example 1. i) Let $G$ be a finite abelian group and let $n \ge 2$ be an integer. Find the number of elements of $\text{Hom}(G,\mathbb{Z}_n)$ and $\text{Hom}(G,\mathbb{Z}).$

ii) Find the number of group homomorphisms $\mathbb{Z}_2 \times \mathbb{Z}_3 \times \mathbb{Z}_4 \to \mathbb{Z}_{10}.$

Solution. i) By the fundamental theorem for finite abelian groups, we have

$G=\mathbb{Z}_{m_1} \times \cdots \times \mathbb{Z}_{m_k}$

for some integers $m_1, \cdots , m_k \ge 2.$ Thus, by the above problem and the problem in this post, we have

$|\text{Hom}(G,\mathbb{Z}_n)|=|\text{Hom}(\mathbb{Z}_{m_1},\mathbb{Z}_n) \times \cdots \times \text{Hom}(\mathbb{Z}_{m_k},\mathbb{Z}_n)|=\prod_{i=1}^k |\text{Hom}(\mathbb{Z}_{m_i},\mathbb{Z}_n)|$

$=\prod_{i=1}^k \gcd(m_i,n).$

and

$|\text{Hom}(G,\mathbb{Z})|=|\text{Hom}(\mathbb{Z}_{m_1},\mathbb{Z}) \times \cdots \times \text{Hom}(\mathbb{Z}_{m_k},\mathbb{Z})|=\prod_{i=1}^k |\text{Hom}(\mathbb{Z}_{m_i},\mathbb{Z})|$

$=\prod_{i=1}^k |(0)|=1.$

ii) By i), the number is $\gcd(2,10)\gcd(3,10)\gcd(4,10)=4. \ \Box$

Remark. By the first part of the above problem, the map $\varphi$ is always one-to-one whether $G$ is abelian or not. But if $G$ is not abelian, then $\varphi$ need not be onto, as the next example shows.

Example 2. Let $A:=\text{Hom}(\mathbb{Z}_2,S_3)$ and $B:=\text{Hom}(\mathbb{Z}_2 \times \mathbb{Z}_2, S_3).$ Show that $|A|=4$ and $|B|=10.$

Solution.  A group homomorphism $f: \mathbb{Z}_2 \to S_3$ is determined by the value of $f(1).$ Since $1 \in \mathbb{Z}_2$ has order two, we either have $f(1)=1$ or $f(1)$ is an element of order two in $S_3.$ So since $S_3$ has exactly three elements of order two (what are they?), $|A|=4.$
To find $|B|,$ let $f: \mathbb{Z}_2 \times \mathbb{Z}_2 \to S_3$ be a non-trivial group homomorphism and $K:=\ker f.$ So $|K| < 4$ and since $S_3$ has no subgroup of order four, $f$ can’t be injective, i.e. $|K| > 1.$ So $|K|=2.$ Now, write

$\mathbb{Z}_2 \times \mathbb{Z}_2=\{1,x,y,xy\}$

where both $x,y$ have order two and $xy=yx.$ There are three possibilities for $K$

$K=\{1,x\}, \ \ K=\{1,y\}, \ \ K=\{1,xy\}.$

Suppose that $K=\{1,x\}.$ Then $f(xy)=f(y)$ and $f(y)$ is an element of order two in $S_3.$ Since $S_3$ has exactly three elements of order two, there are exactly three ways to define $f$ in this case. Similarly, there are three possibilities for $f$ if $K=\{1,y\}$ or $K=\{1,xy\}.$ Thus there are exactly nine non-trivial group homomorphisms from $\mathbb{Z}_2 \times \mathbb{Z}_2$ to $S_3,$ which means $|B|=10. \ \Box$

Note that, in Example 2, we have $|A \times A|=16> 10=|B|$ and so the map $\varphi,$ as defined in the above problem, is not onto in this case.

In the second part of this post, we study the relationship between $\text{Hom}(G, G_1 \times \cdots \times G_n)$ and $\text{Hom}(G,G_1) \times \cdots \times \text{Hom}(G,G_n).$

Group homomorphism – cyclic groups

Posted: September 24, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields

Given groups $G_1,G_2,$ the set of all group homomorphisms $G_1 \to G_2$ is  denoted by $\text{Hom}(G_1,G_2).$
Recall that if $G_2$ is abelian, then $\text{Hom}(G_1,G_2)$ has a natural abelian group structure defined by

$(fg)(x)=f(x)g(x), \ \ \ \ \ \forall f,g \in \text{Hom}(G_1,G_2), \ x \in G_1.$

In this post, we find $\text{Hom}(G_1,G_2)$ for cyclic groups $G_1,G_2.$

The important point is that if $(G_1,+)$ is a cyclic group generated by $g$ and if $G$ is any group, then a group homomorphism $f: G_1 \to G$ is completely determined by $f(g)$ because every element of $G_1$ is in the form $ng$ for some integer $n$ and $f(ng)=(f(g))^n.$

Remark 1. To keep it simple, in the solution of the following problem, we write $k$ for both $k \in \mathbb{Z}$ and the coset $k+\ell \mathbb{Z} \in \mathbb{Z}_{\ell}.$

Problem. Let $m, n \ge 2$ be integers and let $d:=\gcd(m,n).$ Show that

i) $\text{Hom}(\mathbb{Z}_m,\mathbb{Z}_n) \cong \mathbb{Z}_d$

ii) $\text{Hom}(\mathbb{Z}_n,\mathbb{Z}) =(0)$

iii) $\text{Hom}(\mathbb{Z},\mathbb{Z}_n) \cong \mathbb{Z}_n$

iv) $\text{Hom}(\mathbb{Z},\mathbb{Z}) \cong \mathbb{Z}.$

Solution. i) Let $f \in \text{Hom}(\mathbb{Z}_m,\mathbb{Z}_n)$ and $f(1)=k.$ Then $0=f(0)=f(m)=mf(1)=mk$ and thus $n \mid mk,$ which gives $\displaystyle \frac{n}{d} \mid k.$ Hence

$\displaystyle k=\frac{jn}{d}, \ \ 0 \le j \le d-1.$

So, since $f$ is completely determined by $k=f(1)$ and $k$ has $d$ possible values, there are $d$ possible ways to define $f.$ Finally, if $f \in \text{Hom}(\mathbb{Z}_m,\mathbb{Z}_n)$ is defined by $\displaystyle f(1)=\frac{jn}{d}$ for some $0 \le j \le d-1,$ then $f=jg,$ where $g \in \text{Hom}(\mathbb{Z}_m,\mathbb{Z}_n)$ is defined by $\displaystyle g(1)=\frac{n}{d}.$ That means $\text{Hom}(\mathbb{Z}_m,\mathbb{Z}_n)=\langle g \rangle \cong \mathbb{Z}_d.$

ii) Let $f \in \text{Hom}(\mathbb{Z}_n,\mathbb{Z})$ and $f(1)=k.$ Then $0=f(n)=nf(1)=nk$ and so $k=0$ implying that $f=0.$

iii) Let $f \in \text{Hom}(\mathbb{Z},\mathbb{Z}_n).$ Since $1 \in \mathbb{Z}$ has infinite order, $f(1)$ can be defined to be any element of $\mathbb{Z}_n$ and if $f(1)=k,$ then $f=kg,$ where $g \in \text{Hom}(\mathbb{Z},\mathbb{Z}_n)$ is defined by $g(1)=1.$ So $\text{Hom}(\mathbb{Z},\mathbb{Z}_n) =\langle g \rangle \cong \mathbb{Z}_n.$

iv) Same as iii). $\Box$

Remark 2. If $\gcd(m,n)=1,$ then, by the first part of the above problem, $\text{Hom}(\mathbb{Z}_m,\mathbb{Z}_n) \cong \mathbb{Z}_1=(0).$

Finite direct product of normal subgroups with trivial intersections

Posted: August 6, 2019 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: ,

Problem. Let $H_1, H_2, \cdots , H_k, \ \ k \ge 2,$ be some normal subgroups of a group $G$ and suppose that $H_i \cap H_j=\{1\}$ for all $i \ne j.$ Show that $G$ contains a subgroup isomorphic to $H_1 \times H_2 \times \cdots \times H_k$ if $k=2,$ but not necessarily if $k \ge 3.$

Solution. Suppose first that $k=2.$ Since $H_1,H_2$ are normal, $H_1H_2$ is a subgroup of $G$ and

$h_1h_2h_1^{-1}h_2^{-1} \in H_1 \cap H_2=\{1\},$

for all $h_1 \in H_1, h_2 \in H_2$ implying that $h_1h_2=h_2h_1.$ Thus the map

$f: H_1 \times H_2 \to H_1H_2$

defined by $f(h_1,h_2)=h_!h_2$ is an onto group homomorphism. Since $H_1 \cap H_2=\{1\}, \ f$ is also one-to-one, hence an isomorphism.

A counter-example for $k \ge 3$ is $G=\mathbb{Z}_2^{k-1},$ the direct product of $k-1$ copies of $\mathbb{Z}_2.$ Clearly every $1 \ne g \in G$ has order two. Now choose $k$ distinct elements

$g_1, \cdots , g_k \in G\setminus \{1\}$

(we can do that because $k < 2^{k-1}=|G|$) and let $H_i$ be the subgroup of $G$ generated by $g_i.$ Since $G$ is abelian, each $H_i$ is normal in $G$ and clearly $H_i \cap H_j=\{1\}$ for all $i \ne j$ because $H_i,H_j$ are distinct subgroups of order two. Now $H_1 \times H_2 \times \cdots \times H_k$ has $2^k > 2^{k-1}=|G|$ elements and so it can’t be isomorphic to a subgroup of $G. \ \Box$