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

It is given that:

• $x$ is its own inverse.
• $y$ is its own inverse.
• $x*y$ is its own inverse.
• $y*x$ is its own inverse.

Now I will show you that $x*y$ and $y*x$ are essentially same.
 $x*y = x*e*y = x*(x*y*x*y)*y = (x*x)*y*x*(y*y) = e*y*x*e = y*x$     

 (Group is associative so I do not care about brackets)

This turns out to be abelian group. and $x*y$ is no different from $y*x$

Up to this point I have 4 elements - $x$, $y$, $e$, $x*y$.   $(G$ is abelian therefore $x*y$ is same as $y*x)$
Now see if you can have a new element. It is given that every element is product of some numbers of $x$ and $y$.
Lets try with $x$.
$x*\circ$, what u would like to put next to $x$ ?
If you put $x$ then there is no use and you have to start over again because of $x*x=e$ now you have to start all over again.
Put $y$ next to $x:$ $x*y$ (this element we already have, we want different element so try multiplying further.)
$x*y*\circ$, obviously you cannot put $y$, next to $x*y$ because it will be $x$ again: $x*y*y=x*e=x$
(you have to put alternate.)
Put $x$, next to $x*y$: $x*y*x$.
This is equal to $x*x*y$ because of commutative property. $x*y*x=x*x*y=y$.
I showed you that, once you get $x*y$ using $x$, you can not get next element by multiplying into $x*y$ further. Because of commutative property it will be again $x$ or $y$.

Similarly, if we start with $y$, we have the same issue.

This concludes that we can not generate further element and only four element can be there at max.
$\{x,y,x*y,e\}$.
There is a theorem for abelian group: If every element is its own inverse then Group $G$ is abelian. I am not sure if proof of that theorem relates to this problem somewhere, You can check it out. :)

Comments

@sushmita-Consider abelian group $(Z,+)$ Set of Integers over addition. It is Abelian group but for all elements except 0 $a^{-1}=-a$, but still this group is abelian.

An answer to your converse statement.

 

 

---

@Sachin Mittal 1 

I love to read your answers. They are better than anyone else. They are so simple that even a non-engineer could understand. Your answer on a number of conflict serializable schedule was unforgettable and now this answer. Simply amazing. No doubt your answers are lengthy but have quality in it rather than quantity.

---

@GateAspirant999

to find every element in the group, Sachin has assumed the fact the given group is abelian.

No. just using x*y = y*x and y*x=x*y.

we know x*y = y*x, so that’s legal to use without assuming given group is abelian group.

Answer 2

$x * x=e \quad\Rightarrow \text{x is its own inverse.}$

$y * y=e \quad\Rightarrow \text{y is its own inverse.}$

$(x * y)*(x*y)=e \quad\Rightarrow \text{(x*y) is its own inverse.}$

$(y*x)*(y*x)=e \quad\Rightarrow \text{(y*x) is its own inverse.}$

also $x*x*e=e*e$ can be rewritten as follows,

$x*y*y*x=e*y*y*e=[\therefore y*y=e ]$

$(x*y)*(y*x)=e$ shows that $(x*y) \text{ and }(y*x)$

are each other's inverse and we already know that $(x*y) \text{ and }(y*x)$ are inverse of its own.

As per $(G,*)$ to be group any element should have only one inverse element (unique).

This process $x*y=y*x$ (is one element).

So,the elements of such group are 4 which are $\{x,y,e,x*y\}$

And so the answer is 4.

Comments

can you explain just 1 step

how ?

x∗x∗e=e∗e can be rewritten

 x ∗ y∗y∗x =  e∗y∗y∗e     [∴y∗y=e]

Thank you.

---

In place of such a lengthy calculation can we not say that In​​ a group if every element has it's own inverse then that group is called abelian group. And abelian group always satisfies commutative property therefore X*Y=Y*X

---

@GateMaster Prime I was also confused about whether to put x*y or not. 

we can easily conclude that $(x*y)^{-1} = (x*y)$.
now we know $(x*y)^{-1} = y^{-1}*x^{-1}$. 
$x^{-1} = x$ and $ y^{-1} = y$
Therefore $y^{-1}*x^{-1} = x*y$ will be replaced by $y*x = x*y$. 

Hence no need to include $y*x$ if you have already included $x*y$.

Answer 3

the elements which are visible in this group at the first site are = {x, y, e, x*y, y*x}.

we can try generating other elements like
x*x
x*x*x
x*x*x*x
but these will simplify out to 
e
x
e
respectively.

Property of a Group is that There can be only one identity element in a group, and each element in a group has exactly one inverse element.

we try to obtain inverse of x*y :
x*x = e
x*x*y = e*y
x*xy*y = y*y
x*xy*y = e
x*x*xy*y = x*e
e*xy*y = x
xy*y*x = x*x
xy * yx = e

This shows us that x*y has another inverse which is y*x. But as per the properties of a Group an element has a unique inverse. We already know that x*y is its own inverse, this is given to us. This makes us to conclude that x*y and y*x are same elements. Since it is given that G is a group and x*y and y*x both are its elements. So to keep them as elements of a Group they must be the same.

Hence there are only 4 elements in the Group (G,*), which are = {x, y, e, x*y} or we can write this set G as = {x, y, e, y*x}

Comments

Nice explanation.

Answer 4

x* x=e, x is its own inverse 
y *y= e, y is its own inverse

(x *y)*( x* y)= e, x *y is its own inverse

(y* x)* (y* x)= e, y* x is its own inverse
also x* x* e= e*e can be rewritten as follows

x* y* y *x= e *y* y* e= e, (Since y *y= e)
(x* y)* (y* x)= e shows that (x *y) and (y *x)
are each other’s inverse and we already know that
(x *y) and (y* x) are inverse of its own.

As per (G,*) to be group any element should have
only one inverse element (unique)

This implies x *y= y* x (is one element)

So the elements of such group are 4 which are {x, y,e,x *y }.

 

Comments

how did you prove each element is its inverse?

You have just used elements given in the equation.Group may or may not have more elements