Composition of Relations

Home → Composition of Relations

We assume that the reader is already familiar with the basic operations on binary relations such as the union or intersection of relations. Now we consider one more important operation called the composition of relations.

Definition

Let \(A, B\) and \(C\) be three sets. Suppose that \(R\) is a relation from \(A\) to \(B,\) and \(S\) is a relation from \(B\) to \(C.\)

The composition of \(R\) and \(S,\) denoted by \(S \circ R,\) is a binary relation from \(A\) to \(C,\) if and only if there is a \(b \in B\) such that \(aRb\) and \(bSc.\) Formally the composition \(S \circ R\) can be written as

\[S \circ R = \left\{ {\left( {a,c} \right) \mid \exists b \in B: {aRb} \land {bSc} } \right\},\]

where \(a \in A\) and \(c \in C.\)

The composition of binary relations is associative, but not commutative.

To denote the composition of relations \(R\) and \(S,\) some authors use the notation \(R \circ S\) instead of \(S \circ R.\) This is, however, inconsistent with the composition of functions where the resulting function is denoted by

\[y = f\left( {g\left( x \right)} \right) = \left( {f \circ g} \right)\left( x \right).\]

The composition of relations \(R\) and \(S\) is often thought as their multiplication and is written as

\[S \circ R = RS.\]

Powers of Binary Relations

If a relation \(R\) is defined on a set \(A,\) it can always be composed with itself. So, we may have

\[R \circ R = {R^2},\]

\[R \circ R \circ R = {R^3},\]

\[\underbrace {R \circ R \circ \ldots \circ R}_n = {R^n}.\]

Composition of Relations in Matrix Form

Suppose the relations \(R\) and \(S\) are defined by their matrices \(M_R\) and \(M_S.\) Then the composition of relations \(S \circ R = RS\) is represented by the matrix product of \(M_R\) and \(M_S:\)

\[{M_{S \circ R}} = {M_{RS}} = {M_R} \times {M_S}.\]

Recall that \(M_R\) and \(M_S\) are logical (Boolean) matrices consisting of the elements \(0\) and \(1.\) The multiplication of logical matrices is performed as usual, except Boolean arithmetic is used, which implies the following rules:

\[0 + 0 = 0,\;\;1 + 0 = 0 + 1 = 1,\;\;1 + 1 = 1;\]

\[0 \times 0 = 0,\;\;1 \times 0 = 0 \times 1 = 0,\;\;1 \times 1 = 1.\]

Example:

Consider the sets \(A = \left\{ {a,b} \right\},\) \(B = \left\{ {0,1,2} \right\}, \) and \(C = \left\{ {x,y} \right\}.\) The relation \(R\) between sets \(A\) and \(B\) is given by

\[R = \left\{ {\left( {a,0} \right),\left( {a,2} \right),\left( {b,1} \right)} \right\}.\]

The relation \(S\) between sets \(B\) and \(C\) is defined as

\[S = \left\{ {\left( {0,x} \right),\left( {0,y} \right),\left( {1,y} \right),\left( {2,y} \right)} \right\}.\]

To determine the composition of the relations \(R\) and \(S,\) we represent the relations by their matrices:

\[{M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 0&1&0 \end{array}} \right],\;\;{M_S} = \left[ {\begin{array}{*{20}{c}} 1&1\\ 0&1\\ 0&1 \end{array}} \right].\]

The matrix of the composition of relations \(M_{S \circ R}\) is calculated as the product of matrices \(M_R\) and \(M_S:\)

\[{M_{S \circ R}} = {M_R} \times {M_S} = \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 0&1&0 \end{array}} \right] \times \left[ {\begin{array}{*{20}{c}} 1&1\\ 0&1\\ 0&1 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {1 + 0 + 0}&{1 + 0 + 1}\\ {0 + 0 + 0}&{0 + 1 + 0} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 1&1\\ 0&1 \end{array}} \right].\]

In roster form, the composition of relations \(S \circ R\) is written as

\[S \circ R = \left\{ {\left( {a,x} \right),\left( {a,y} \right),\left( {b,y} \right)} \right\}.\]