*71*

# Composition of Relations

Let A, B, and C be sets, and let R be a relation from A to B and let S be a relation from B to C. That is, R is a subset of A Ã— B and S is a subset of B Ã— C. Then R and S give rise to a relation from A to C indicated by Râ—¦S and defined by:

The relation Râ—¦S is known the composition of R and S; it is sometimes denoted simply by RS.

Let R is a relation on a set A, that is, R is a relation from a set A to itself. Then Râ—¦R, the composition of R with itself, is always represented. Also, Râ—¦R is sometimes denoted by R^{2}. Similarly, R^{3} = R^{2}â—¦R = Râ—¦Râ—¦R, and so on. Thus R^{n} is defined for all positive n.

**Example1:** Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider the relation R_{1} from X to Y and R_{2} from Y to Z.

R_{1}= {(4, a), (4, b), (5, c), (6, a), (6, c)} R_{2}= {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

Find the composition of relation **(i)** R_{1} o R_{2} **(ii)** R_{1}o R_{1}^{-1}

**Solution: **

(i) The composition relation R_{1} o R_{2} as shown in fig:

**R _{1} o R_{2}** = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}

(ii) The composition relation R_{1}o R_{1}^{-1} as shown in fig:

**R _{1}o R_{1}^{-1}** = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}

## Composition of Relations and Matrices

There is another way of finding Râ—¦S. Let M_{R} and M_{S} denote respectively the matrix representations of the relations R and S. Then

**Example **

**Solution:** The matrices of the relation R and S are a shown in fig:

(i) To obtain the composition of relation R and S. First multiply M_{R} with M_{S} to obtain the matrix M_{R} x M_{S} as shown in fig:

The non zero entries in the matrix M_{R} x M_{S} tells the elements related in RoS. So,

Hence the composition R o S of the relation R and S is

(ii) First, multiply the matrix M_{R} by itself, as shown in fig

Hence the composition R o R of the relation R and S is

(iii) Multiply the matrix M_{S} with M_{R} to obtain the matrix M_{S} x M_{R} as shown in fig:

The non-zero entries in matrix M_{S} x M_{R} tells the elements related in S o R.

Hence the composition S o R of the relation S and R is