3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ could be hadamard/schur element-wise product. makes sense in the context of logical AND or in set theory, cap. $\endgroup$ Commented Nov 6, 2017 at 18:07
  • $\begingroup$ My interpretation above makes sense if the matrices encoded binary presence of elements in a set and we wanted to take a cap of two such sets. But I see now that it was about a relation, something that obviously flew over my head at the time. $\endgroup$ Commented Nov 6, 2017 at 18:24

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This seems to make more sense than the suggestion above of @mathreadler, since that would seem to give the intersection of the two matrices. $\endgroup$
    – Lubin
    Commented Nov 6, 2017 at 18:15
  • $\begingroup$ Yes @Lubin is right it seems I misunderstood it. I did not read thoroughly enough but thought each element of the matrix was an element in a set 1 encoding present and 0 encoding absent, but I see now it was some way to represent a relation. $\endgroup$ Commented Nov 6, 2017 at 18:21
  • $\begingroup$ This was exactly it! Thank you! $\endgroup$
    – Sam Weaver
    Commented Nov 6, 2017 at 18:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .