Algebraic Structures and Groups Short Notes for GATE CS

Algebraic Structures and Groups short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Exam Pattern: The Two Operator Question

Exam Pattern

The Two Operator Question

Typical shape

You are given two custom operations, a domain, and several statements to judge.

Commutativity of the first operator

The Monoid Verdict

Conclusion: $(F, ⨀)$ is a Monoid

A monoid is a set $S$ with a binary operation $*$ satisfying three properties:

Closure: $a * b \in S$ for all $a, b \in S$ .
Associativity: $(a * b) * c = a * (b * c)$ for all $a, b, c \in S$ .
Identity: There exists $e \in S$ such that $a * e = e * a = a$ for all $a \in S$ .

Our Structure

Set: $F$ , all functions from $A = {0, 1, 2, \dots}$ to $A$ .

Operation: $(f_{1} ⨀ f_{2}) (n) = f_{1} (n) + f_{2} (n)$ .

Property	Status	Reason
Closure	Holds	Sum of non-negative integers is non-negative.
Associativity	Holds	Inherited from integer addition.
Identity	Holds	Constant zero function $e (n) = 0$ is in $F$ .

Verdict:

(F, ⨀)

is a Monoid.

Why It Is NOT a Group

The Missing Property: Inverses

A group is a monoid where every element has an inverse. For $(F, ⨀)$ to be a group, for every $f \in F$ , there must exist $g \in F$ such that:

f ⨀ g = e

where $e (n) = 0$ is the identity.

Evaluating at any $n$ :

f (n) + g (n) = 0 ⟹ g (n) = - f (n)

The Trap

Consider $f (n) = n + 1$ . Clearly $f \in F$ because it maps non-negative integers to non-negative integers.

To find its inverse $g$ , we need:

g (n) = - (n + 1)

At $n = 0$ , $g (0) = - 1$ . But $- 1 \in / A$ . Thus, $g \in / F$ .

Rule: If the codomain does not contain negative numbers, pointwise addition cannot form a group because additive inverses fall outside the set.

Only the identity function itself, $f (n) = 0$ , has an inverse in this set. Since not every element has an inverse, $(F, ⨀)$ is not a group.

Quick Revision Checklist

Summary

Quick Revision Checklist

(2^{X}, Δ)

Identity:

\emptyset

. Inverse:

A^{- 1} = A

. All elements are self-inverse.

Direct Product

G \times H

Order:

∣ G ∣ \cdot ∣ H ∣

. Identity:

(e_{G}, e_{H})

. Inverse:

(g^{- 1}, h^{- 1})

Counting Self-Inverses

Calculate

N_{i}

(count of

x^{2} = e

) for each component. Total =

\prod N_{i}

Z_{n}

(Addition)

Solve

2 x \equiv 0 (mod n)

Algebraic Structures and Groups: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Engineering Mathematics MCQ

Assertion (A): The number of self-inverse elements in $Z_{2} \times Z_{3} \times Z_{4}$ is 4.

Reason (R): An element $(x, y, z)$ is self-inverse if $2 x \equiv 0 (mod 2)$ , $2 y \equiv 0 (mod 3)$ , and $2 z \equiv 0 (mod 4)$ .

A.
A is true but R is false.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is false but R is true.
D.
Both A and R are true and R is the correct explanation of A.

Correct Answer:

Step-by-Step Solution

Key idea: In a direct product, an element is self-inverse iff each component is self-inverse.

Step 1: In $Z_{n}$ under addition, the self-inverse condition is $2 x \equiv 0 (mod n)$ . This makes R true.

Step 2: For $Z_{2}$ , $2 x \equiv 0 (mod 2) ⟹ x \in {0, 1}$ (2 solutions).

Step 3: For $Z_{3}$ , $2 y \equiv 0 (mod 3) ⟹ y = 0$ (1 solution).

Step 4: For $Z_{4}$ , $2 z \equiv 0 (mod 4) ⟹ z \in {0, 2}$ (2 solutions).

Step 5: Total self-inverse elements = $2 \times 1 \times 2 = 4$ . This makes A true.

Step 6: R correctly provides the method to compute A, so R is the correct explanation.

Answer: D

Question 2 · Engineering Mathematics MCQ

Consider the following:

Assertion (A): The index of a subgroup $H$ in a group $G$ of order 24, where $∣ H ∣ = 8$ , is 3.

Reason (R): The index of $H$ in $G$ is calculated as the order of $H$ divided by the order of $G$ .

Which option is correct?

A.
Both A and R are true and R is the correct explanation of A
B.
A is true but R is false
C.
Both A and R are true but R is NOT the correct explanation of A
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: The index of a subgroup is $∣ G ∣/∣ H ∣$ , not $∣ H ∣/∣ G ∣$ .

Step 1: Evaluate Assertion (A). The index of $H$ in $G$ is defined as $[G : H] = ∣ G ∣/∣ H ∣$ .

Step 2: Calculate the index: $24/8 = 3$ . Thus, Assertion (A) is true.

Step 3: Evaluate Reason (R). R states the index is $∣ H ∣/∣ G ∣$ . This is the reciprocal of the correct formula. Thus, Reason (R) is false.

Step 4: Conclude that A is true but R is false.

Answer: B

Question 3 · Engineering Mathematics MCQ

Let $a$ be an element of order 12 in an abelian group. Which of the following statements is TRUE?

A.
$o (a^{4}) = 4$
B.
$o (a^{5}) = 5$
C.
$o (a^{9}) = 9$
D.
$o (a^{8}) = 3$

Correct Answer:

Step-by-Step Solution

Key idea: The order of a power $a^{k}$ is given by $o (a^{k}) = \frac{o ( a )}{g c d ( o ( a ) , k )}$ .

Step 1: Recall the formula for the order of a power: $o (a^{k}) = \frac{n}{g c d ( n , k )}$ , where $n = o (a)$ .

Step 2: Here, $n = 12$ . We evaluate each option using the formula.

Step 3: For $a^{4}$ : $o (a^{4}) = 12/ g cd (12, 4) = 12/4 = 3$ . (Option A is false).

Step 4: For $a^{5}$ : $o (a^{5}) = 12/ g cd (12, 5) = 12/1 = 12$ . (Option B is false).

Step 5: For $a^{9}$ : $o (a^{9}) = 12/ g cd (12, 9) = 12/3 = 4$ . (Option C is false).

Step 6: For $a^{8}$ : $o (a^{8}) = 12/ g cd (12, 8) = 12/4 = 3$ . (Option D is true).

Answer: D

Question 4 · Engineering Mathematics MCQ

Let $A = {0, 1, 2, \dots}$ and $F$ be the set of all functions from $A$ to $A$ . Under pointwise addition $(f \oplus g) (n) = f (n) + g (n)$ , how many functions in $F$ possess an inverse?

A.
0
B.
1
C.
2
D.
infinitely many

Correct Answer:

Step-by-Step Solution

Key idea: For $f$ to have an inverse $g$ , we need $f \oplus g = e$ , where $e$ is the identity (zero function).

Step 1: Recall the identity. The identity function $e$ satisfies $f \oplus e = f$ for all $f$ . This means $f (n) + e (n) = f (n)$ , so $e (n) = 0$ for all $n$ . The identity is the zero function.

Step 2: Set up the inverse condition. For $f$ to have an inverse $g$ , we need $f \oplus g = e$ , i.e., $f (n) + g (n) = 0$ for all $n \in A$ .

Step 3: Analyze the constraint. Since $f (n) \in A$ and $g (n) \in A$ , both are non-negative integers. The sum $f (n) + g (n) = 0$ requires both $f (n) = 0$ and $g (n) = 0$ .

Step 4: Conclude. The only function satisfying this is $f (n) = 0$ for all $n$ , i.e., the zero function itself. So exactly 1 function has an inverse.

Answer: B

Question 5 · Engineering Mathematics MCQ

Match the group with its self-inverse condition.

List I:

P) $Z_{n}$ under addition

Q) $U (n)$ under multiplication

List II:

$x^{2} \equiv 1 (mod n)$
$2 x \equiv 0 (mod n)$

A.
P-2, Q-2
B.
P-1, Q-1
C.
P-2, Q-1
D.
P-1, Q-2

Correct Answer:

Step-by-Step Solution

Key idea: The self-inverse condition depends on the group's operation and identity.

Step 1: For $Z_{n}$ under addition, the identity is 0. The condition is $x + x = 0 ⟹ 2 x \equiv 0 (mod n)$ . This matches 2.

Step 2: For $U (n)$ under multiplication, the identity is 1. The condition is $x \times x = 1 ⟹ x^{2} \equiv 1 (mod n)$ . This matches 1.

Step 3: Therefore, P matches 2, and Q matches 1.

Answer: C

Question 6 · Engineering Mathematics MCQ

Consider the following:

Assertion (A): The number of generators of the cyclic group $Z_{12}$ is 4.

Reason (R): An element $k$ is a generator of $Z_{n}$ if and only if $g cd (k, n) = 1$ .

Which option is correct?

A.
Both A and R are true and R is the correct explanation of A
B.
Both A and R are true but R is NOT the correct explanation of A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: The number of generators of $Z_{n}$ is given by Euler's totient function $ϕ (n)$ .

Step 1: Evaluate Assertion (A). The number of generators of $Z_{12}$ is $ϕ (12)$ .

Step 2: Calculate $ϕ (12) = 12 \times (1 - 1/2) \times (1 - 1/3) = 12 \times (1/2) \times (2/3) = 4$ . So, A is true.

Step 3: Evaluate Reason (R). The condition for $k$ to be a generator of $Z_{n}$ is indeed $g cd (k, n) = 1$ . So, R is true.

Step 4: Check the link. R provides the exact mathematical condition used to compute the count in A. Thus, R is the correct explanation of A.

Answer: A

Question 7 · Engineering Mathematics MCQ

Let $G = Z_{15}$ be the group of integers modulo 15 under addition. How many elements in $G$ have an order of exactly 5?

A.
5
B.
4
C.
8
D.
15

Correct Answer:

Step-by-Step Solution

Key idea: In $Z_{n}$ , the number of elements of order $d$ is $ϕ (d)$ , provided $d$ divides $n$ .

Step 1: Identify $n = 15$ and the target order $d = 5$ .

Step 2: Check if $d$ divides $n$ . Since $5$ divides $15$ , elements of order 5 exist.

Step 3: The number of such elements is given by Euler's totient function $ϕ (d) = ϕ (5)$ .

Step 4: Since 5 is prime, $ϕ (5) = 5 - 1 = 4$ .

Answer: B

Question 8 · Engineering Mathematics MCQ

Let $A = {0, 1, 2, \dots}$ and $F$ be all functions from $A$ to $A$ . Under pointwise addition $(f \oplus g) (n) = f (n) + g (n)$ , which task is IMPOSSIBLE?

A.
Computing $(f \oplus g) (5)$ given $f$ and $g$
B.
Finding $e \in F$ such that $f \oplus e = f$ for all $f$
C.
For arbitrary $f \in F$ , finding $g \in F$ such that $f \oplus g = e$
D.
Checking if $f \oplus (g \oplus h) = (f \oplus g) \oplus h$

Correct Answer:

Step-by-Step Solution

Key idea: Check which task violates the properties of the structure.

Step 1: Evaluate option A. Computing $(f \oplus g) (5) = f (5) + g (5)$ is always possible given $f$ and $g$ . This is possible.

Step 2: Evaluate option B. The identity $e$ satisfies $f (n) + e (n) = f (n)$ , so $e (n) = 0$ for all $n$ . The zero function is in $F$ . This is possible.

Step 3: Evaluate option C. For arbitrary $f$ , finding $g$ such that $f \oplus g = e$ means $f (n) + g (n) = 0$ for all $n$ . If $f (n) > 0$ , then $g (n) = - f (n) < 0$ , which is not in $A$ . This is impossible for most $f$ .

Step 4: Evaluate option D. Since integer addition is associative, $f (n) + (g (n) + h (n)) = (f (n) + g (n)) + h (n)$ for all $n$ . This is possible.

Answer: C

Question 9 · Engineering Mathematics MCQ

Consider the following:

Assertion (A): The operation $*$ defined by $a * b = a + 2 b$ on integers is associative.

Reason (R): For associativity, we need $(a * b) * c = a * (b * c)$ for all $a, b, c$ .

Which option is correct?

A.
Both A and R are true and R is the correct explanation of A
B.
Both A and R are true but R is NOT the correct explanation of A
C.
A is false but R is true
D.
A is true but R is false

Correct Answer:

Step-by-Step Solution

Key idea: Check if $(a * b) * c = a * (b * c)$ using the given formula.

Step 1: Compute $(a * b) * c$ . First, $a * b = a + 2 b$ . Then $(a * b) * c = (a + 2 b) * c = (a + 2 b) + 2 c = a + 2 b + 2 c$ .

Step 2: Compute $a * (b * c)$ . First, $b * c = b + 2 c$ . Then $a * (b * c) = a * (b + 2 c) = a + 2 (b + 2 c) = a + 2 b + 4 c$ .

Step 3: Compare. $a + 2 b + 2 c \neq = a + 2 b + 4 c$ in general (e.g., let $c = 1$ : left gives $a + 2 b + 2$ , right gives $a + 2 b + 4$ ).

Step 4: Evaluate A and R. Since the two expressions are not equal, $*$ is not associative, so A is false. R correctly states the definition of associativity, so R is true.

Answer: C

Question 10 · Engineering Mathematics MCQ

Let $X$ be a set with 4 elements. The group $(2^{X}, Δ)$ is isomorphic to a direct product of copies of $Z_{2}$ . Which of the following is IMPOSSIBLE for this group?

A.
It contains an element of order 4.
B.
It has 16 elements.
C.
It is an Abelian group.
D.
Every element is its own inverse.

Correct Answer:

Step-by-Step Solution

Key idea: Isomorphism to $Z_{2} \times Z_{2} \times Z_{2} \times Z_{2}$ dictates the group's properties.

Step 1: Since $∣ X ∣ = 4$ , the group is isomorphic to $Z_{2}^{4}$ , which has $2^{4} = 16$ elements.

Step 2: In $Z_{2}$ , every non-identity element has order 2. Thus, in $Z_{2}^{4}$ , every element is its own inverse (order 1 or 2).

Step 3: Since $Z_{2}$ is Abelian, the direct product is also Abelian.

Step 4: Because the maximum order of any element is 2, it is impossible to contain an element of order 4.

Answer: A