Skip to content

Groups and Monoids

Short Notes

Algebraic structures consisting of a non-empty set combined with one or more binary operations.

  • Closure: \(a * b \in S\).
  • Associativity: \((a * b) * c = a * (b * c)\).
  • Identity: \(\exists e\) such that \(a * e = e * a = a\).
  • Inverse: \(\exists a^{-1}\) such that \(a * a^{-1} = e\).

Hierarchy

  • Semigroup: Closure + Associativity.
  • Monoid: Semigroup + Identity.
  • Group: Monoid + Inverse.
  • Abelian Group: Group + Commutative (\(a * b = b * a\)).

Key Theories & Formulas

1. Group Properties

  • In a group, the identity element is unique.
  • Every element has a unique inverse.
  • Idempotent Law: The only idempotent element (\(x*x=x\)) in a group is the identity \(e\).
  • Cancellation Law: \(a * b = a * c \implies b = c\) (holds in groups).

2. Subgroups & Order

  • Order of Group \(|G|\): Number of elements in \(G\).
  • Order of Element \(|a|\): Smallest \(n\) s.t. \(a^n = e\).
  • Lagrange's Theorem: Order of a subgroup \(H\) divides the order of group \(G\). (\(|H|\) divides \(|G|\)).
  • Cyclic Group: A group generated by a single element (\(G = \langle a \rangle\)). Every cyclic group is Abelian.
  • Number of generators of a cyclic group of order \(n\) is \(\phi(n)\) (Euler's Totient Function).

Example Problems

Problem: Find the order of element 3 in the group \((\mathbb{Z}_7^*, \times_7)\).

  • \(\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}\). Identity is 1.
  • \(3^1 \equiv 3 \pmod 7\)
  • \(3^2 \equiv 9 \equiv 2 \pmod 7\)
  • \(3^3 \equiv 2 \times 3 \equiv 6 \pmod 7\)
  • \(3^4 \equiv 6 \times 3 \equiv 18 \equiv 4 \pmod 7\)
  • \(3^5 \equiv 4 \times 3 \equiv 12 \equiv 5 \pmod 7\)
  • \(3^6 \equiv 5 \times 3 \equiv 15 \equiv 1 \pmod 7\)
  • Order is 6. This means 3 is a generator for \(\mathbb{Z}_7^*\).

Hardest GATE Questions

Topic: Number of Subgroups

Tricky Question: How many subgroups does a group \(G\) of order 6 have, if \(G\) is non-abelian?

  • Analysis:
  • A non-abelian group of order 6 must be isomorphic to \(S_3\) (Symmetric group of degree 3).
  • Elements: \(\{e, (12), (13), (23), (123), (132)\}\).
  • Orders:
    • Order 1: \(\{e\}\) (1 subgroup)
    • Order 2: \(\{(12)\}, \{(13)\}, \{(23)\}\). Each generates a subgroup of size 2. (3 subgroups)
    • Order 3: \(\{(123), (132)\}\). Together with \(e\), they make a subgroup of size 3. (1 subgroup)
  • Lagrange's Theorem says subgroup sizes can be 1, 2, 3, 6.
  • Subgroup of order 6 is \(G\) itself. (1 subgroup)
  • Total: \(1 + 3 + 1 + 1 = 6\) subgroups.
  • Why it's hard: Requires knowing the structure of \(S_3\) and exhaustively counting based on element orders.

References