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

If every element in group G is equals to its own inverse then Group G is abelian Group.

Proof:-

Let (G,*) is a group.

∴  if  a,b ∈ G  then  a⁻¹,b⁻¹ ∈ G //Bcoz in Group inverse exist for every element.

also if a*b ∈ G the (a * b)⁻¹ ∈ G //Bcoz in Group inverse exist for every element.

Given that a=a⁻¹ and b=b⁻¹

so we can write (a * b)=(a*b)⁻¹=b^{−1 *} a⁻¹=(b * a)

i.e, (G,*) is commutative. Hence (G,*) is abelian group.

---

Nice approach to tackle such problems.Thanks :-)

---

Also it is given that x*x=e

this means order of group is surely even( By lagrange's theorem)

Since, 3 elements of the group are confirm and they are x,y and e

The group must atleast 4 or 6 or 8...elements.

Now exactly how much?

That is well explained above

---

converse need not be true right?

---

@Sushmita,please state the converse statement

---

@Ayush Upadhyaya

Converse is: If G is an abelian group then then every element is inverse of itself.

This need not be true always.

---

@SachinMittal, in your answer you have said "This turns out to be abelian group." But how?
If you tell the proof is as given in the Rajesh's comment, then note that this proof says "If every element in group G is equals to its own inverse then Group G is abelian Group." So this proof assumes we know every element. However that is not the case in the given problem and we need to find every element in this question. So we cannot use Rajesh's theorem in this problem, right?

To repeat,
to find every element in the group, Sachin has assumed the fact the given group is abelian.
to prove given group is abelian, Rajest's theorem statement assumes we know all elemens in the group.

We cannot use one to prove other, right?

Thats why I believe, other answer is more correct, which is same as that of geeksforgeeks.

---

Very nice explanation

---

@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