Question

There are two elements x,yx, y in a group (G,∗)(G, *) such that every element in the group can be written as a product of some number of xx's and yy's in some order. It is known that

x∗x=y∗y=x∗y∗x∗y=y∗x∗y∗x=ex * x = y * y = x * y * x * y = y * x * y * x = e

where ee is the identity element. The maximum number of elements in such a group is _____.

Official answer and solution
Official answer
4
From
Official GATE 2014 answer key

Solution

Use the group relations to deduce commutativity and find the presentation of the Klein four-group.

Given a group (G,∗)(G, *) generated by elements x,yx, y satisfying:

x2=e,y2=e,(xy)2=e,(yx)2=e.x^2 = e,\quad y^2 = e,\quad (xy)^2 = e,\quad (yx)^2 = e.
  1. Deduce Commutativity:

    • Since x2=ex^2 = e, x−1=xx^{-1} = x.
    • Since y2=ey^2 = e, y−1=yy^{-1} = y.
    • From (xy)2=e(xy)^2 = e:
      x∗y∗x∗y=e  ⟹  x∗y=(x∗y)−1=y−1∗x−1=y∗x.x * y * x * y = e \implies x * y = (x * y)^{-1} = y^{-1} * x^{-1} = y * x.
    • Hence, x∗y=y∗xx * y = y * x, which means the generators commute with each other.
  2. Determine the Elements of GG:

    • Since xx and yy commute, any word formed by combinations of xx and yy can be simplified to the canonical form xaybx^a y^b.
    • Since x2=ex^2 = e and y2=ey^2 = e, the exponents aa and bb can only take values in {0,1}\{0, 1\}.
    • This yields at most 2×2=42 \times 2 = 4 distinct elements:
      G={e,x,y,xy}.G = \{e, x, y, xy\}.
  3. This group presentation corresponds to the Klein four-group (V4≅Z2×Z2V_4 \cong \mathbb{Z}_2 \times \mathbb{Z}_2), which has order 4.

Therefore, the maximum number of elements in such a group is 4.

Final answer

4

Common trap

Assuming the dihedral group D4 with 8 elements without realizing (xy)^2 = e forces xy = yx.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2014 Computer Science and Information Technology (CS) Session 3
Question
60 of 65, printed as CS Q.50
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.