Section 13.2 Composition
Composition may be a familiar idea from algebra. Suppose you have functions \(f\) and \(g\) such that \(f(x)=y\) and \(g(y)=z\text{.}\) Then you have a third function \(fg\) such that \(fg(x) = z\text{,}\) called the composition of \(f\) and \(g\text{.}\) You probably called \(fg\) something like \(g \circ f\) instead, but we have good reason to call it \(fg\text{.}\)
A composition of relations is the identical idea, but without the extra restrictions that make a relation into a function.
Definition 13.2.1.
Let \(R\) be a relation from \(X\) to \(Y\text{,}\) and \(S\) be a relation from \(Y\) to \(Z\text{.}\) Their composition is the relation
The composition of \(R\) with itself \(n\) times is denoted \(R^n\text{.}\)
Example 13.2.2.
Let \(R = \{ (x_1,y_2), (x_2,y_3), (x_3,y_1) \}\) be a relation from \(X=\{x_1,x_2,x_3\}\) to \(Y=\{y_1,y_2,y_3\}\text{,}\) and \(S = \{(y_1,z_1), (y_1,z_2), (y_2,z_2)\}\) be a relation from \(Y\) to \(Z=\{z_1,z_2\}\text{.}\) What is \(RS\text{?}\)
The relation \(RS\) is the set of all pairs \((x,z)\) for which there is a \(y\) “connecting” the \(x\) and the \(z\text{.}\) Looking at the given relations we may identify the following pairs: \((x_1,z_2)\) via \(y_2\text{,}\) \((x_3,z_1)\) via \(y_1\text{,}\) and \((x_3,z_2)\) also via \(y_1\text{.}\) Therefore
The following diagram illustrates this composition.
The composition is illustrated. Elements of \(X\text{,}\) drawn in a blue circle, are related via arrows to the corresponding elements of \(Y\text{,}\) drawn in a red circle. Elements of \(Y\) are related to elements of \(Z\text{,}\) drawn in a yellow circle. The composition is created by “gluing” arrows together.
Observe that \(SR\) does not exist because the codomain of \(S\) is not the domain of \(R\text{.}\)
You may tell yourself, “I don't want to draw this diagram every time I compute a composition.” And you may tell yourself, “If the relations involved were large, I would like to be able to make a computer do this job for me.” Fortunately this apparatus is already in place! Recall the criteria for a pair \((x_i,z_j)\) appearing in the composition for sets whose elements are labeled numerically:
“\(x_i\) is related to \(z_j\) if there exists a \(k\) such that \(x_k\) is related to \(y_k\) and \(y_k\) is related to \(z_k\text{.}\)”
You may recall this exact language has appeared before:
“The Boolean dot product of a row matrix \((A_i)\) and a column matrix \((C_j)\) is \(1\) if there exists a \(k\) such that \(A_k\) and \(C_k\) are both \(1\text{.}\)”
It is precisely the multiplication of Boolean matrices that will find the necessary \(y_k\)'s for us:
Theorem 13.2.4.
Let \(R\) and \(S\) be relations such that the composition \(RS\) exists. Then
i.e. the matrix for \(RS\) is the product of the matrix for \(R\) with the matrix for \(S\text{.}\)
Example 13.2.5.
In the last example we let \(R = \{ (x_1,y_2), (x_2,y_3), (x_3,y_1) \}\) be a relation from \(X=\{x_1,x_2,x_3\}\) to \(Y=\{y_1,y_2,y_3\}\text{,}\) and \(S = \{(y_1,z_1), (y_1,z_2), (y_2,z_2)\}\) be a relation from \(Y\) to \(Z=\{z_1,z_2\}\text{.}\)
The matrix for \(R\) is
and the matrix for \(S\) is
Their product is
which you should verify yourself is also the matrix for