DG1, DG4 - Binary operations and Cayley tables | AQA A-Level Further Mathematics

What changes when an operation acts on a particular set rather than on any numbers you like? You will learn what makes a rule a binary operation, calculate with modular arithmetic and matrices, and construct and read Cayley tables without reversing the operands.

Closure and table construction

Can a rule combine two allowed inputs and produce a forbidden answer? Take the set $S=\{-1,1\}$ . Adding its elements can give $2$ , which is outside $S$ . Multiplying them always gives $-1$ or $1$ . The set matters as much as the rule.

Binary operation and closure

A binary operation on a set $S$ assigns exactly one element of $S$ to every ordered pair $(a,b)$ of elements of $S$ . The set is closed under the rule when every such output belongs to $S$ .

“Binary” means two inputs, not base-two arithmetic. A familiar rule may fail on a chosen set: division is not a binary operation on the real numbers because division by zero is undefined. Removing zero makes division defined for every pair of nonzero real numbers, with a nonzero real result.

A Cayley table records every output for a finite set. We use the row heading as the first operand and the column heading as the second. Keep the printed order of the headings; do not rearrange entries by size.

Worked example 1: finding a failure of closure

Question. Does ordinary addition define a binary operation on $S=\{-1,1\}$ ? Display all four outputs.

Plan. Use each element as a row input and combine it with each column input.

\begin{array}{c|rr} +&-1&1\\\hline -1&-2&0\\ 1&0&2 \end{array}

For example, row $-1$ , column $1$ contains $-1+1=0$ . None of these outputs belongs to $S$ .

Answer. No: $S$ is not closed under addition. The displayed array records the failure; it is not a Cayley table for a binary operation on $S$ .

Check. The single pair $(1,1)$ already gives $2\notin S$ , independently confirming the conclusion.

Keep the set and its heading order, but change only the rule to multiplication. This time every cell must stay in the set.

Worked example 2: constructing a closed table

Question. Construct the Cayley table for ordinary multiplication on $S=\{-1,1\}$ and establish closure.

Plan. Multiply the row input by the column input in each of the four cells.

\begin{array}{c|rr} \times&-1&1\\\hline -1&1&-1\\ 1&-1&1 \end{array}

The diagonal entries are $(-1)(-1)=1$ and $1(1)=1$ ; the other products are $-1$ .

Answer. The table above is complete. Every output is in $S$ , and every ordered pair has been checked, so multiplication is a binary operation on $S$ .

Check. A product of two signs is positive when the signs match and negative otherwise. This reproduces all four entries without recalculating the table row by row.

A single forbidden output disproves closure; proving closure needs every pair, or a general argument covering them all.

Watch out

Checking that a rule works for one pair does not establish closure. Check all pairs in a finite table, and check that every required output is defined as well as in the set.

Try a set with one extra boundary element.

Modular arithmetic

A clock returns to its starting label after a full circuit. Modular arithmetic does the same with integer labels: after calculating, replace the result by its remainder.

For an integer $n\ge2$ , use the representatives $0,1,\ldots,n-1$ . Write $a\equiv r\pmod n$ when $a-r$ is a multiple of $n$ . For example, $17\equiv2\pmod5$ , because $17-2=15$ . This congruence is a relation between integers; an operation such as $+_5$ returns one chosen representative.

Addition and multiplication modulo n

On $S_n=\{0,1,\ldots,n-1\}$ ,

a+_n b=\text{the remainder of }a+b\text{ on division by }n,

a\times_n b=\text{the remainder of }ab\text{ on division by }n.

Both outputs lie in $S_n$ . These definitions and notation are not supplied in the examination formula booklet.

The subscript tells you the modulus; it does not mean multiply or add $n$ . A remainder is at least zero and less than $n$ . For a negative integer, add a suitable multiple of $n$ : $-2\equiv3\pmod5$ , so its chosen representative is $3$ , not $-2$ .

Worked example 3: addition modulo 5

Question. Find $4+_5 4$ , and construct the $+_5$ row headed $4$ , with columns $0,1,2,3,4$ .

Plan. Add ordinarily, then remove whole multiples of $5$ .

4+4=8=1(5)+3\quad\Longrightarrow\quad4+_5 4=3.

The row is

\begin{array}{c|rrrrr} +_5&0&1&2&3&4\\\hline 4&4&0&1&2&3 \end{array}

For example, the column headed $1$ gives $4+1=5$ , whose remainder is $0$ .

Answer. $4+_5 4=3$ ; the row is $4,0,1,2,3$ .

Check. Each output differs from its ordinary sum by $0$ or $5$ , and each lies between $0$ and $4$ .

Keep the same operands, modulus and heading order. Changing addition to multiplication changes what you calculate before reducing.

Worked example 4: multiplication modulo 5

Question. Find $4\times_5 4$ , and construct the $\times_5$ row headed $4$ , with columns $0,1,2,3,4$ .

Plan. Multiply ordinarily, then replace each product by its remainder modulo $5$ .

4(4)=16=3(5)+1\quad\Longrightarrow\quad4\times_5 4=1.

The ordinary products are $0,4,8,12,16$ , giving

\begin{array}{c|rrrrr} \times_5&0&1&2&3&4\\\hline 4&0&4&3&2&1 \end{array}

Answer. $4\times_5 4=1$ ; the row is $0,4,3,2,1$ .

Check. Since $4\equiv-1\pmod5$ , multiplication by $4$ reverses the sign of each column label modulo $5$ , giving the same row.

A smaller chosen set may fail closure even though the full residue set is closed. For instance, $\{1,2,3,4\}$ is not closed under $+_5$ , because $1+_5 4=0$ is excluded.

Watch out

Wrong: $4\times_5 4=16$ . The ordinary product is an intermediate result. The operation's output is the representative $1$ .

Apply the same two-stage process with a new modulus.

Matrix multiplication as an operation

You already know how to multiply matrices: take a row of the first matrix against a column of the second. A set of matrices can be closed under that multiplication, just as a set of integers can.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics

Statistics

Discrete Mathematics

DG1, DG4 - Binary operations and Cayley tables

Closure and table construction

Modular arithmetic

Matrix multiplication as an operation

Continue this lesson.

Learn faster with Nova