## 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!$.

## A little remark on coprime polynomials

Posted: November 21, 2019 in Elementary Algebra; Problems & Solutions, Rings and Modules
Tags:

Throughout this post, $F$ is a field and $R:=F[x]$ is the ring of polynomials in the variable $x$ over $F.$

We know that $f,g \in R$ are coprime if and only if there exist $u,v \in R$ such that $uf+vg=1.$ Are $u,v$ unique? Absolutely not, in fact there are infinitely many pairs $(u,v)$ that satisfy $uf+vg=1$ because if $(u,v)$ is one of those pairs and $w \in R,$ then $(u+wg,v-wf)$ is one of those pairs too. But under some conditions, we will have uniqueness, as the following problem shows.

Problem. If $f,g \in R$ are non-constant and coprime, then there exist unique $u,v \in R$ such that $uf+vg=1$ and $\deg u < \deg g, \ \deg v < \deg f.$

Solution. Since $f,g$ are coprime, there exist $u_1,v_1 \in R$ such that $u_1f+v_1g=1.$ Dividing $u_1, v_1$ by $g,f,$ respectively, gives $u,v,r,s \in R$ that satisfy the following conditions

i) $u_1=rg+u$ and $v_1=sf+v$

ii) $u=0$ or $\deg u < \deg g$ and $v=0$ or $\deg v < \deg f.$

Thus

$(r+s)fg + uf+vg=(u_1-u)f+(v_1-v)g+uf+vg=u_1f+v_1g=1. \ \ \ \ \ \ \ \ \ (*)$

Now, by ii), either $uf=0$ or $\deg(uf) < \deg (fg)$ and, similarly, either $vg=0$ or $\deg(vg) < \deg(fg).$ So if $r+s \ne 0,$ then $\deg((r+s)fg + uf+vg) \ge \deg(fg) > 0$ and that contradicts $(*).$ Therefore $r+s=0$ and hence $uf+vg=1$ and that proves the existance of $u,v$ as required. Note that since $f,g$ are non-constant, $u,v$ are non-zero.
To prove the uniqueness of $u,v,$ suppose that $u'f+v'g=1$ for some $u',v' \in R$ with $\deg u' < \deg g$ and $\deg v' < \deg f.$ Then $(u-u')f=(v'-v)g$ and thus, since $f,g$ are coprime, we must have $f \mid v'-v,$ which is impossible unless $v'=v$ because $\deg(v'-v) < \deg f.$ So $v'=v$ and hence $(u-u')f=0,$ which gives $u=u'$ and that proves the uniqueness of $u,v. \ \Box$

## 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} \ ?$

## In a finite commutative ring, number of nilpotents divides number of zero divisors

Posted: October 4, 2019 in Elementary Algebra; Problems & Solutions, Finite Rings
Tags: , ,

Problem. Let $R$ be a finite commutative ring with $1.$ Show that the number of nilpotent elements of $R$ divides the number of zero-divisors of $R.$

Solution. First two simple facts.

1) Every element of $R$ is either a zero-divisor or a unit. That’s because if $r \in R$ is not a zero-divisor, then $Rr=R$ (because $|Rr|=|R|$) and so $rx=1$ for some $x \in R.$

2) If $x \in R$ is nilpotent and $y \in R$ is a unit, then $x+y$ is a unit (see the lemma here).

Now let $N(R),Z(R),U(R)$ be the sets of nilpotents, zero-divisors and units of $R,$ respectively.
If $x \in N(R), y \in Z(R),$ then $z:=x+y \in Z(R)$ because if $x \notin Z(R),$ then $z \in U(R),$ by 1), and hence $y=z-x \in U(R),$ by 2), and that’s not possible because then $y \in Z(R) \cap U(R)=\emptyset.$ So for each $y \in Z(R),$ we have

$A_y:=\{x+y: \ \ x \in N(R)\} \subseteq Z(R)\}.$

Also, if $z \in Z(R),$ then $z=0+z \in A_z.$ So

$\displaystyle Z(R)=\bigcup_{y \in Z(R)}A_y. \ \ \ \ \ \ \ \ \ \ \ (*)$

Now, if $A_{y_1} \cap A_{y_2} \neq \emptyset,$ for some $y_1,y_2 \in Z(R),$ then $x_1+y_1=x_2+y_2$ for some $x_!,x_2 \in N(R)$ and that gives

$y_2=(x_1-x_2)+y_1 \in A_{y_1}, \ \ y_1=(x_2-x_1)+y_2 \in A_{y_2}$

hence $A_{y_1}=A_{y_2}.$ The result now follows from $(*)$ because clearly $|A_y|=|N(R)|$ for all $y \in Z(R). \ \Box$

Exercise. Let’s see what the result in the problem means for $R:=\mathbb{Z}/n\mathbb{Z},$ the ring of integers modulo $n.$ Let $n=p_1^{k_1} \cdots p_m^{k_m}$ be the prime factorization of $n$ and let $\varphi$ be the Euler’s totient function. Let $N(R), Z(R)$ be the sets of nilpotents and zero-divisors of $R,$ respectively. Show that

$\displaystyle |Z(R)|=n-\varphi(n), \ \ \ |N(R)|=\frac{n}{p_1 \cdots p_m}.$

So, by the result given in the above problem, $\displaystyle \frac{n}{p_1 \cdots p_m} \mid n-\varphi(n).$ Verify this result directly!

## 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).$