GATE CS Group Theory Previous Year Questions

GATE CS 2025 Set 1 | Question 49

MSQ · 2 marks

\(A = \{0, 1, 2, 3, \ldots\}\) is the set of non-negative integers. Let \(\mathrm{F}\) be the set of functions from \(A\) to itself. For any two functions, \(f_1, f_2 \in \mathrm{F}\), we define

\[(f_1 \odot f_2)(n) = f_1(n) + f_2(n)\]

for every number \(n\) in \(A\). Which of the following is/are CORRECT about the mathematical structure \((\mathrm{F}, \odot)\)?

\((\mathrm{F}, \odot)\) is an Abelian group. \((\mathrm{F}, \odot)\) is an Abelian monoid. \((\mathrm{F}, \odot)\) is a non-Abelian group. \((\mathrm{F}, \odot)\) is a non-Abelian monoid.

Explanation

Answer: (B)

Check the axioms for pointwise addition of functions from \(A\) to \(A\).

Closure: \(f_1(n) + f_2(n)\) is again a non-negative integer, so \(f_1 \odot f_2 \in \mathrm{F}\).
Associativity and commutativity come straight from ordinary addition at each \(n\).
Identity: the zero function \(z(n) = 0\) is in \(\mathrm{F}\), and \(f \odot z = f\).
Inverses fail: for the constant function \(f(n) = 1\), the inverse would need \(g(n) = -1\), which is not in \(A\).

So \((\mathrm{F}, \odot)\) is a commutative (Abelian) monoid but not a group. (A) and (C) are wrong because it is not a group; (D) is wrong because \(\odot\) is commutative.

Answer: B

GATE CS 2024 Set 1 | Question 52

MSQ · 2 marks

Consider the operators \(\lozenge\) and \(\square\) defined by \(a \mathbin{\lozenge} b = a + 2b\), \(a \mathbin{\square} b = ab\), for positive integers. Which of the following statements is/are TRUE?

Operator \(\lozenge\) obeys the associative law Operator \(\square\) obeys the associative law Operator \(\lozenge\) over the operator \(\square\) obeys the distributive law Operator \(\square\) over the operator \(\lozenge\) obeys the distributive law

Explanation

Answer: (B), (D)

(A) False: \((a \mathbin{\lozenge} b) \mathbin{\lozenge} c = a + 2b + 2c\), but \(a \mathbin{\lozenge} (b \mathbin{\lozenge} c) = a + 2(b + 2c) = a + 2b + 4c\).
(B) True: \(\square\) is ordinary multiplication, which is associative.
(C) False: \(a \mathbin{\lozenge} (b \mathbin{\square} c) = a + 2bc\), while \((a \mathbin{\lozenge} b) \mathbin{\square} (a \mathbin{\lozenge} c) = (a + 2b)(a + 2c)\). For \(a = b = c = 1\) these are 3 and 9.
(D) True: \(a \mathbin{\square} (b \mathbin{\lozenge} c) = a(b + 2c) = ab + 2ac = (a \mathbin{\square} b) \mathbin{\lozenge} (a \mathbin{\square} c)\). It also holds from the right, since \((b + 2c)a = ba + 2ca\).

So multiplication distributes over \(\lozenge\), because \(\lozenge\) is a linear combination of its operands, but not the other way round.

Answer: B, D

GATE CS 2024 Set 2 | Question 63

NAT · 2 marks

Let \(Z_n\) be the group of integers \(\{0, 1, 2, \ldots, n - 1\}\) with addition modulo \(n\) as the group operation. The number of elements in the group \(Z_2 \times Z_3 \times Z_4\) that are their own inverses is ________

Your answer

Explanation

Answer: 4

The product group works coordinate by coordinate, so \((x, y, z)\) is its own inverse exactly when \(2x \equiv 0 \pmod 2\), \(2y \equiv 0 \pmod 3\) and \(2z \equiv 0 \pmod 4\).

In \(Z_2\): both 0 and 1 work (2 choices).
In \(Z_3\): only 0 works, since \(2 \cdot 1 = 2\) and \(2 \cdot 2 = 4 \equiv 1\) (1 choice).
In \(Z_4\): 0 and 2 work (2 choices).

So there are \(2 \times 1 \times 2 = 4\) such elements: \((0,0,0), (0,0,2), (1,0,0), (1,0,2)\). The identity \((0,0,0)\) counts, since it is its own inverse.

Answer: 4