# Using Todd-Coxeter algorithm to identify the group

From Artin's Algebra (6.9.2):

Use the Todd-Coxeter Algorithm to identify the group generated by two elements $x,y$, with the following relations: $x^2=y^2=1,xyx=yxy$.

To do so, I first need to choose a subgroup for which $G$ acts on its cosets. Then Todd-Coxeter algorithm will give the permutation representation $\rho$ of $G$. How do I ensure that the representation does not contain redundant relations?

For example, if I end up with $\rho(x)=\rho(y)=1$, then it is not the required identification. I think I need to make the representation faithful. So, which subgroup should I choose? Does any subgroup work?

Edit: Using the subgroup generated by $\{y\}$, I found $x=(1\ 2),y=(2\ 3)$. But still, I chose the subgroup at random. Had I choose $G$ as the subgroup, I'd end up with the trivial representation.

-

The kernel of the representation is contained in the subgroup you choose. A silly way to ensure the representation is faithful is to choose the subgroup $\{1\}$.

Since $\langle y\rangle$ has at most 2 elements, the kernel is either $\{1\}$, or $\{1,y\}$. Since $\rho(y) \neq 1$, the kernel is not $\{1,y\}$, so $\rho$ is faithful.

With hindsight, you can see that there are four subgroups that work: $\{1\}, \{1,x\}, \{1,y\}, \{1,xyx\}$ and two that do not work $\{1,xy,yx\}, \{1,x,y,xy,yx,xyx\}$. There are other ways to write down these subgroups, and different ways might cause T–C to take longer, but these are the only subgroups, and most (4) of them do not contain any normal subgroups of order greater than 1.

-

I did the T.C. version for finding the index of $H=\langle x\rangle$ of order $2$:

We see that $[G:H]=3$ SO $|G|=6$. Now:

$$1xy=1y=2\neq 3=2x=1yx$$

It means that $G\cong S_3$.

-