I'm working on an assignment for my Discreet Mathematics and Logic class, and we're learning about Binary Relations. One question I'm failing to understand involves determining the result of operations with relationship matrices.
Here's an example:
The following matrices represent the following relations on a set $S = \{1, 2, 3\}$:
$$
R_1 = \{(1,1), (1,3), (2,1), (3,1), (3,2), (3,3)\}
\\
M_1 = \begin{bmatrix}1 & 0 & 1\\1 & 0 & 0\\1 & 1 & 1\end{bmatrix}
$$
$$
R_2 = \{(1,2),(2,1),(3,1),(3,2)\}
\\
M_2 = \begin{bmatrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0\end{bmatrix}
$$
For example, $M_1 \cup M_2$ is $\begin{bmatrix}1 & 1 & 1\\1 & 0 & 0\\ 1 & 1 & 1\end{bmatrix}$
and $M_1 \cap M_2$ is $\begin{bmatrix}0 & 0 & 0\\1 & 0 & 0\\1 & 1 & 0\end{bmatrix}$
This is the bit I'm having difficulty understanding:
What is the operation in $M_1\circ M_2$? I haven't seen this notation before?
Best Answer
Given a relation $R$ on $\{1,2,3\}$ we encode the relation into a matrix $M$ by setting $m_{ij}=1$ if $(i,j)\in R$ and $m_{ij}=0$ otherwise. Given two relations $R$ and $S$ on $\{1,2,3\}$ we can consider the composition $R\circ S$ where $(x,y)\in R\circ S$ iff there exists $z\in S$ such that $(x,z)\in S$ and $(z,y)\in R$. My guess is that $M_1\circ M_2$ is the encoding of such a composition.