Binary Operations

Lessons

Senior 4 · Mathematics

Binary Operations

4 lessons

Lesson 3 of 4

Cayley tables and the group structure

25 min

Moves that can be combined and undone

Every twist of a Rubik's cube is a "move". Doing one move and then another is again a move; there is a move that changes nothing; and every move can be undone. The integers under addition, the turns of a clock and the symmetries of a triangle obey the same four rules. Whenever a set and an operation obey them, mathematicians call the pair a group. Recognising a group means that every theorem ever proved about groups applies at once.

Definition

Integers modulo $n$ : for an integer $n \ge 2$ , $\mathbb{Z}_n = \{0, 1, 2, \ldots, n - 1\}$ . Addition modulo $n$ , written $a +_{n} b$ , is the remainder when $a + b$ is divided by $n$ ; multiplication modulo $n$ , $a \times_n b$ , is the remainder when $a b$ is divided by $n$ .

Example: in $\mathbb{Z}_{12}$ , $9 +_{12} 5 = 2$ (the clock of Lesson 1, with 12 written as 0); in $\mathbb{Z}_7$ , $4 \times_7 5 = 20 - 14 = 6$ .

Definition

Group: a set $G$ with a binary operation $*$ is a group, written $(G, *)$ , if

closure: $a * b \in G$ for all $a, b \in G$ ;
associativity: $(a * b) * c = a * (b * c)$ for all $a, b, c \in G$ ;
identity: there is $e \in G$ with $e * a = a * e = a$ for all $a \in G$ ;
inverses: every $a \in G$ has an inverse $a' \in G$ with $a * a^{'} = a^{'} * a = e$ .

If also $a * b = b * a$ for all $a, b$ , the group is abelian (commutative). The number of elements of a finite group is its order.

Groups and non-groups

Set and operation	Group?	Reason
$(\mathbb{Z}, +)$	Yes, abelian	identity 0; inverse of $a$ is $- a$
$(\mathbb{N}, +)$	No	1 has no inverse in $\mathbb{N}$
$(\mathbb{Q}^*, \times)$	Yes, abelian	identity 1; inverse of $a$ is $\frac{1}{a}$
$(\mathbb{Z}, \times)$	No	2 has no inverse: $\frac{1}{2} \notin \mathbb{Z}$
$(\mathbb{R}, -)$	No	not associative, and no identity
$(\mathbb{Z}_n, +_n)$	Yes, abelian	identity 0; inverse of $a \ne 0$ is $n - a$

Associativity of $+_{n}$ and $\times_n$ is inherited from ordinary addition and multiplication: taking remainders at each step or only at the end gives the same result.

Worked example 1: $(\mathbb{Z}_4, +_4)$ is a group

$+_{4}$	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

Closure: every entry is in $\{0, 1, 2, 3\}$ .
Associativity: inherited from $+$ on $\mathbb{Z}$ .
Identity: the row and column of 0 repeat the headings, so $e = 0$ .
Inverses: find 0 in each row: $0^{'} = 0$ , $1^{'} = 3$ , $2^{'} = 2$ , $3^{'} = 1$ .

The table is symmetric, so $(\mathbb{Z}_4, +_4)$ is an abelian group of order 4.

Worked example 2: multiplication modulo 5 and modulo 4

(a) Is $(\{1, 2, 3, 4\}, \times_5)$ a group? (b) Is $(\{0, 1, 2, 3\}, \times_4)$ a group?

Solution (a) The table has rows 1, 2, 3, 4 / 2, 4, 1, 3 / 3, 1, 4, 2 / 4, 3, 2, 1. It is closed, associativity is inherited, the identity is 1, and every row contains 1: $1^{'} = 1$ , $2^{'} = 3$ (since $2 \times 3 = 6 = 5 + 1$ ), $3^{'} = 2$ , $4^{'} = 4$ . Yes, it is an abelian group.

(b) The identity would be 1, but the row of 0 is 0, 0, 0, 0: no element $x$ gives $0 \times_4 x = 1$ . Also $2 \times_4 2 = 0$ , and the row of 2 (0, 2, 0, 2) never contains 1. Not a group.

A group that is not abelian: the symmetries of a triangle

A symmetry of an equilateral triangle is a motion that puts it back exactly onto its own outline. There are six: the identity $e$ , the turns $r$ (120° anticlockwise) and $r^{2}$ (240° anticlockwise), and the flips $a$ , $b$ , $c$ in the three axes. The operation is composition: $x \circ y$ means "do $y$ first, then $x$ ".

Follow the corner positions to compose. For $r \circ a$ : the flip $a$ swaps positions 2 and 3, then $r$ moves 1 to 2, 2 to 3 and 3 to 1. Altogether, 1 goes to 2, 2 goes to 3 then to 1, and 3 goes to 2 then to 3: positions 1 and 2 swap and 3 stays, which is the flip $c$ . Working every pair the same way gives the Cayley table (row $x$ , column $y$ , entry $x \circ y$ ):

$\circ$	$e$	$r$	$r^{2}$	$a$	$b$	$c$
$e$	$e$	$r$	$r^{2}$	$a$	$b$	$c$
$r$	$r$	$r^{2}$	$e$	$c$	$a$	$b$
$r^{2}$	$r^{2}$	$e$	$r$	$b$	$c$	$a$
$a$	$a$	$b$	$c$	$e$	$r$	$r^{2}$
$b$	$b$	$c$	$a$	$r^{2}$	$e$	$r$
$c$	$c$	$a$	$b$	$r$	$r^{2}$	$e$

Composition of motions is associative, $e$ is the identity, and every row contains $e$ (each flip is its own inverse, and $r^{'} = r^{2}$ ). So this is a group of order 6. But it is not abelian: $r \circ a = c$ while $a \circ r = b$ . The order of operations matters, just as it does on a Rubik's cube.

Important

Theorem (cancellation and the Latin square). In a group, if $a * b = a * c$ then $b = c$ . Hence each element appears exactly once in every row and every column of a group's Cayley table.

Proof. Multiply on the left by $a^{'}$ : $a^{'} * (a * b) = a^{'} * (a * c)$ . By associativity, $(a^{'} * a) * b = (a^{'} * a) * c$ , so $e * b = e * c$ and $b = c$ . So the entries $a * x$ in row $a$ are all different; a row of $n$ different elements from a set of $n$ elements contains each element once. Columns are the same, cancelling on the right. $\blacksquare$

A table with a repeated entry in some row is therefore not a group table. (The converse is false: a Latin square still needs associativity to be a group table.)

Évariste Galois (1811–1832), drawn from memory by his brother Alfred in 1848. Galois was the first to use the word group (groupe) close to its modern technical sense, in his work on which polynomial equations can be solved by radicals. He died aged 20. Drawing: Alfred Galois, public domain, via Wikimedia Commons.

Tip

To test a finite table for a group, work in this order: (1) every entry in the set? (2) find $e$ : the row that copies the heading; (3) does $e$ appear in every row, in symmetric places? (4) is any element repeated in a row? If so, stop: not a group. Associativity cannot be read from a table at a glance; justify it from the operation (inherited from $+$ or $\times$ , or composition of motions).

Socratica: Abstract Algebra, the definition of a group. Watch for the four group axioms and for the examples that fail one of them.

✦

Practice

Use Cayley tables wherever they help.

Draw the table of $(\mathbb{Z}_5, +_5)$ and give the inverses of 2 and 4.
Is $(\{0, 2, 4\}, +_6)$ a group?
Explain why $(\mathbb{Q}^*, \div)$ is not a group.
Show that $(\{1, -1\}, \times)$ is a group.
$G = \{e, p, q, s\}$ is a group with identity $e$ and $p * p = q$ , $p * q = s$ . Complete its Cayley table.
In the triangle group, find $r \circ r \circ r$ , $a \circ a$ and the inverse of $r$ .
In the triangle group, solve $r \circ x = a$ .
A student's table for $\{e, u, v\}$ has the row of $u$ equal to $u, e, u$ . Without further work, explain why the table is not a group table.

Show answersHide answers

Rows: 0 1 2 3 4 / 1 2 3 4 0 / 2 3 4 0 1 / 3 4 0 1 2 / 4 0 1 2 3. $2^{'} = 3$ , $4^{'} = 1$ .
Yes. $2 + 4 = 6 \to 0$ , $4 + 4 = 8 \to 2$ , $2 + 2 = 4$ : closed; identity 0; $2^{'} = 4$ , $4^{'} = 2$ ; associativity inherited.
It is not associative: $(8 \div 4) \div 2 = 1$ but $8 \div (4 \div 2) = 4$ . (It also has only a right identity, 1.)
Table: $1 \times 1 = 1$ , $1 \times (-1) = -1$ , $(-1) \times (-1) = 1$ . Closed, associative, identity 1, each element its own inverse.
$p$ generates the group: $p^{2} = q$ , $p^{3} = s$ , $p^{4} = e$ . Rows: $e$ : e p q s; $p$ : p q s e; $q$ : q s e p; $s$ : s e p q.
$r \circ r \circ r = e$ (a full turn); $a \circ a = e$ ; $r^{'} = r^{2}$ .
$x = r' \circ a = r^2 \circ a = b$ . Check in the table: $r \circ b = a$ . ✓
$u$ appears twice in that row, but in a group each element appears exactly once in every row (cancellation).

Quick check

In the Cayley table of a group, how many times does each element appear in each row?

Key points

A group $(G, *)$ is closed and associative, has an identity, and every element has an inverse; abelian if also commutative.
$(\mathbb{Z}_n, +_n)$ is an abelian group; $(\{1, \ldots, p - 1\}, \times_p)$ is a group when $p$ is prime (Lesson 4 explains why).
In a group table each element appears exactly once in each row and column.
The six symmetries of an equilateral triangle form a group that is not abelian.

Sources and credits

Written by Ganzaa: the explanations, the diagram, the tables, the worked examples, the practice items and the questions.
Galois's dates and his use of the word "group": Évariste Galois, Wikipedia contributors, Wikipedia, CC BY-SA 4.0, adapted by Ganzaa.
Photo: Rubik's cube, Lars Karlsson (Keqs), Wikimedia Commons, CC BY-SA 3.0.
Drawing: Évariste Galois par son frère, Alfred Galois, 1848, Wikimedia Commons, public domain.
Video: Abstract Algebra: The definition of a Group, Socratica, embedded from YouTube.
This lesson adapts CC BY-SA material and is shared under CC BY-SA 4.0.

1Moves that can be combined and undone

2Groups and non-groups

3A group that is not abelian: the symmetries of a triangle

Moves that can be combined and undone

Groups and non-groups

A group that is not abelian: the symmetries of a triangle