For $0\le k\le \lfloor n/2\rfloor$, first select an ordered list of $2k$ distinct entries. There are $n!/(n-2k)!$ lists. Pair consecutive entries to obtainEach product of $k$ disjoint transpositions is counted $2^{k}k!$ times: each pair has two orientations, and the $k$ pairs can be ordered in $k!$ ways. There is no other duplication, by uniqueness of the disjoint cycle decomposition. ThereforeIf $2k>n$, there are no such permutations. For $k=0$, $T_0=\{e\}$.

Let the lengths in the disjoint cycle decomposition of $\tau$ be ${\ell }_1,\dots ,{\ell }_s$, with fixed points contributing length one. Disjoint cycles commute, and ${\tau }^m=e$ if and only if every cycle raised to $m$ is the identity, equivalently ${\ell }_j$ divides $m$ for every $j$. Hence the order of a group element isIn particular, the identity has order one.

Conjugating a cycle simply relabels its entries. With permutations composed from right to left,This follows by applying each side to $\rho (a_j)$ and to points outside the displayed cycle. Consequently conjugation preserves the lengths in the disjoint cycle decomposition, including fixed points, and therefore preserves cycle type.

Conversely, suppose two permutations have the same cycle type. Pair their cycles of equal length, including their one-cycles. Define a bijection $\rho$ by mapping the entries of each cycle of the first permutation, in their cyclic order, to the entries of the paired cycle of the second. Because the cycles partition $\{1,\dots ,n\}$, these assignments combine into a permutation. The displayed identity then conjugates the first permutation to the second. Thus they are conjugate group elements exactly when their cycle types agree.

Put $L={\bigcap }_{i=1}^k{H}_i$. Repeated application of part (iv), or mathematical induction on $k$, givesPart (ii) therefore implies that $L$ is an infinite set. If $G\setminus U$ is nonempty, choose $g\notin U$. We claim its left coset $gL$ is wholly outside $U$. If $g\ell \in H_i$ for some $\ell \in L$, then $\ell \in H_i$ and closure under products and inverses would give $g=(g\ell ){\ell }^{-1}\in H_i$, a contradiction.

Thus $gL\subseteq G\setminus U$. Part (i) makes $gL$ infinite, so the complement is infinite. If there is no such $g$, the complement is empty. This proves the complement of a finite union of finite-index subgroups property:

Define a map between sets of left cosets byIt is well defined: replacing $g$ by $gu$ for $u\in H\cap K$ changes neither component. It is injective becauseThe Cartesian product on the right has at most $nm$ elements. ThereforeThis proves the basic bound for a finite intersection of finite-index subgroups.

Every left coset $kH$ with $k\in K$ is also a left coset of $H$ in $G$. Moreover equality of two such cosets means the same thing in $K$ and in $G$:Thus the map from the set of left cosets of $H$ in $K$ to the set of left cosets of $H$ in $G$, taking $kH$ to itself, is injective. Consequently the index of a subgroup satisfiesThese are sets of cosets; no normal subgroup assumption is needed.

Suppose $H$ were finite, say $|H|=r$. There are at most $n$ left cosets, each with $r$ elements by part (i), and they partition $G$. Hence $G$ would be a finite set with at most $nr$ elements. This contradicts the assumption that $G$ is an infinite group. Therefore $\boxed{H\text{ is infinite}}$.

For every $g\in G$, left multiplication gives a bijectionwhose inverse is $x\mapsto g^{-1}x$. Hence every left coset has the same cardinality as $H$. If $H$ is an infinite set, every left coset is infinite; if $H$ is a finite set, every left coset is finite. These are the only possibilities.

Neither $1$ nor $-1$ is divisible by a prime number, so both lie outside $U$. On the other hand, $0\in 2\mathbb{Z}\subseteq U$. If an integer $z$ has $|z|>1$, part (a)(i) supplies a prime number $p$ dividing the positive integer $|z|$; the same $p$ divides $z$, so $z\in p\mathbb{Z}\subseteq U$. These cases exhaust $\mathbb{Z}$, proving

The set $S_n$ is nonempty because $n\in S_n$. By the well-ordering principle for the natural numbers, it has a least element $p$. In particular $p>1$ and $p$ divides $n$.

If $p$ were not a prime number, it would have a positive integer divisor $d$ with $1<d<p$. Since $d$ divides $p$ and $p$ divides $n$, divisibility is transitive and $d$ divides $n$. This would put $d$ in $S_n$, contradicting the minimality of $p$. Hence $\boxed{p\text{ is prime}}$.

Yes: use the non-abelian group $H$ from part (a). Every element is $I_3+N$ for a strictly upper triangular matrix $N$ with $N^3=0$. In the finite field ${\mathbb{Z}}_3$, the binomial theorem for commuting matrices givesThus $\boxed{T(h)=I_3\text{ for all }h\in H}$. This constant identity-valued map is a group homomorphism, since $T(xy)=I_3=T(x)T(y)$. Part (a)(iv) already proves that $H$ is not an abelian group. Here $T$ is neither injective nor surjective, consistently with the preceding part.

If $T$ is a surjective group homomorphism, then $G=T(G)$, which is an abelian group by the preceding part.

If $T$ is an injective group homomorphism, then for all $a,b\in G$,because $T(a),T(b)$ lie in the abelian group $T(G)$. Injectivity gives $ab=ba$. Hence $\boxed{G\text{ is abelian in either case}}$.

Assume $T$ is a group homomorphism. For any $a,b\in G$, expanding $(ab{)}^3=a^3{b}^3$ and cancelling the initial $a$ and final $b$ gives the useful identityWe also need a consequence of compatibility with conjugation. Calculate the cube of $gz{g}^{-1}$ in two ways:Cancelling shows $g^2{z}^3=z^3{g}^2$. Thus the square of every element of $G$ commutes with every element of the image of a group homomorphism $J=T(G)$.

Now take any $x,y\in J$. In particular $x^{2}y=y{x}^2$. Applying (1) to $x,y$ and then using this commutation givesThis proves the abelian image of a cubing homomorphism property. Since the image of a group homomorphism is a subgroup, $\boxed{T(G)\text{ is an abelian group}}$.

Use the symmetric group $S_3$, composing permutations from right to left. Set $x=(12)$ and $y=(23)$. Each is a transposition, so $x^3=x$ and $y^3=y$, whereas $xy=(123)$ has order of a group element three. ConsequentlyThus the cubing map on $S_3$ is not a group homomorphism.

If $G$ is an abelian group, its elements commute, so for all $x,y\in G$,Thus $\boxed{T\text{ is a group homomorphism}}$. Also $T(e)=e^3=e$, as required.

Take $x=h(1,0,0)=I_3+E_{12}$ and $y=h(0,0,1)=I_3+E_{23}$. Their matrix products areThey differ in the $(1,3)$ entry because $E_{12}{E}_{23}=E_{13}$ whereas $E_{23}{E}_{12}=0$. Therefore $xy\ne yx$, and $\boxed{H\text{ is a non-abelian group}}$.

The identity is the identity matrixLeft or right matrix multiplication by it preserves every entry, as is also immediate from the product formula above.

Parametrize the matrices byDirect matrix multiplication givesThis proves closure. The identity matrix is $h(0,0,0)$, and the formulagives both a left and a right inverse, as substitution in the product formula verifies. Thus each element is an invertible matrix, and the subgroup test shows that $H$ is a subgroup of ${\mathrm{GL}}_3({\mathbb{Z}}_3)$. It is the unitriangular group ${\mathrm{UT}}_3({\mathbb{F}}_3)$ and has $3^3=27$ elements.

In the finite field ${\mathbb{Z}}_3=\{0,1,2\}$, perform ordinary addition and multiplication and then take the remainder modulo $3$. The tables areThe nonzero elements have multiplicative inverses $1^{-1}=1$ and $2^{-1}=2$.

Yes. Consider the following $n^2$ matrices:Each has only row $i$ nonzero and has $i$th diagonal entry $1$, so part (c)(ii) proves that it is a diagonalisable matrix. The collection is a spanning set, because it contains every $E_{ii}$ andThus it spans the matrix unit basis. A spanning set of $n^2$ vectors in an $n^2$-dimensional vector space is a basis. Alternatively, in a vanishing linear combination of $\mathcal{B}$, each off-diagonal entry first forces its own coefficient to be zero, and then each diagonal entry forces the remaining coefficient to be zero.