GATE CSE 2014 Set 3 | Question: 50

Question

There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is known that
$$x*x=y*y=x*y*x*y=y*x*y*x=e$$
where $e$ is the identity element. The maximum number of elements in such a group is ____.

Comments

$\textbf{*}$	$\textbf{x}$	$\textbf{y}$	$\textbf{x*y}$	$\textbf{e}$
$\textbf{x}$	$e$	$x*y$	$y$	$x$
$\textbf{y}$	$x*y$	$e$	$x$	$y$
$\textbf{x*y}$	$y$	$x$	$e$	$x*y$
$\textbf{e}$	$x$	$y$	$x*y$	$e$

---

video solution

---

Here, the operation we are talking about is multiplication, right?

Then, the identity element should be 1. Now, x⁻¹ = x and also y⁻¹ = y. This will only satisfy for 2 numbers and they are 1 and -1. We won't get any other 2 numbers such that when we multiply it with itself, the result will be 1.

Also, apart from these 2 numbers, no other number can be generated as a product of 1's and -1's. So, shouldn't the maximum number of elements present in such a group be 2 only?

Where am I going wrong?

---

You are wrong in the first line only, * is not multiplication but it shows binary operation.

Answer 1

Now in the question, it is given that the $(G,∗)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order.

Now using the sort of knowledge of regular expressions all the elements of the group could be produced by expressions $(x^*y^*x^*)^*$, where $x^*$ means $0$ or more occurrences of $x$ as a product.

Now let us work out few things with the information which is given to us,

$$x*y=x*y*e=x*y*(y∗x∗y∗x) =x*(y*y)∗x∗y∗x$$$$=x*e∗x∗y∗x =x∗x∗y∗x=(x∗x)∗y∗x=e*y*x=y*x$$

So $$x*y=y*x \tag 1$$. [Just showing this does not mean that the group is abelian as $x$ and $y$ are specific two elements(as given in the question) and not arbitrary two elements]

Also $$x*y*x=(x*y)*x=(y*x)*x=y*(x*x)=y*e=y \tag 2$$

Similarly, $$y*x*y=y*(x*y)=y*(y*x)=(y*y)*x=e*x=x \tag 3$$

---

Now let us work with $(x^*y^*x^*)^*$

For the expression in parenthesis:

Case 1: If there is no $y$ then we have just $x^*$ inside the parenthesis.

Case 2: If there is odd number of $y$'s then it is equivalent to a single $y$. Why? See below:

$$y*y*y=(y*y)*y=e*y=y$$

$$(y*y*y)*y*y=y*y*y=y$$ and so on…

So the expression inside parenthesis becomes $x^*yx^*$

Case 3: If we have even no. of $y$’s then it is equivalent to having no $y$’s and the situation reduces to case 1.

$y*y=e$; $y*y*y*y=(y*y)*(y*y)=e*e=e$ and so on…

---

Now dealing with $x^*$

Just as in the case of $y$'s, having even number of $x$'s is equivalent to having no $x$'s and having odd number of $x$'s is equivalent to having only $1$ $x$.

So $x^*$ is equivalent to $x$ or $e$.

---

Now dealing with $x^*yx^*$.

$x^*yx^*$ is either $(y)$ or $(x*y)$ or $(y*x)$ or $(x*y*x)$. But $x*y*x=y$ from $(2)$. Also $x*y=y*x$ from $(1)$.

So effectively $x^*y^*x^*$ [the expression inside the parenthesis] gives only 4 values $(x)$ or $(e)$ or $(y)$ or $(x*y)$

So $(x^*y^*x^*)^* \equiv ( (x) + (e) + (y) + (x*y))^*$ [$+$ is regular expression or/union]

If we try out an explanation of the above $*$ closure we shall not get any new element other than $(x)$ or $(e)$ or $(y)$ or $(x*y)$. [It can easily be seen and you shall need $(3)$ to show $y*x*y=x$ in a combination].

So there are only $4$ elements in the group.

Answer 2

.