0
$\begingroup$

I didn't get this thing. Let $R, S$ be two relations from $A \to A$ with $A$ being an arbitrary set. And $M_R$ and $M_S$ their relation matrixes defined as:

$(M_R)_{ij}=\left\{ \begin{array}{l l} 1 & \quad \text{if $iRj$}\\ 0 & \quad \text{otherwise}\\ \end{array} \right.$

$M_S$ and $M_{R \circ S}$ are defined analogue. Why it holds that $M_{R \circ S}=M_R \cdot M_S$ (no, not exactly, but I don't know how I can express this in a nice way)? This is my incomplete sort of proof. Can you give me some advice how to improve it?

Now $iR \circ Sj \Leftrightarrow \exists x : iRx \wedge xSj$. Suppose $\exists x : iRx \wedge xSj \Rightarrow (M_R)_{ix}=1, (M_S)_{xj}=1 \Rightarrow (M_R)_{ix} \cdot (M_S)_{xj} = 1$.

On the other hand, suppose $\neg(\exists x : iRx \wedge xSj) \Leftrightarrow \forall x: \neg iRx \vee \neg xSj \Rightarrow (M_R)_{ix} = 0 \vee (M_S)_{xj} = 0 \Rightarrow (M_R)_{ix} \cdot (M_S)_{xj} = 0$.

Therefor, if we take the product it will sum up all those things. If there exists such an $x$ for any $i,j$, there will turn up a number greater than $0$. Otherwise, if there does not exists such a number it will be a $0$. If we replace all those integers greater than $0$ by $1$, it is the matrix of the productrelation $R \circ S$.

  • 0
    Ah, I learned it as being standard notation. But more common is I guess $R \circ S$. It are arbitrary relations, from a arbitrary set A to itself.2012-09-11

1 Answers 1

3

Your proof is fine. In case it helps, here is how I would have written it up. To simplify notation, let's assume that $A$ is the set $\{0,1,\ldots,n-1\}$.

We have $(M_R M_S)_{i,j} = \sum_{k and because $(M_R)_{i,k}$ and $(M_S)_{k,j}$ are always zero or one, this sum is greater than zero if and only if there is a $k such that both $(M_R)_{i,k}$ and $(M_S)_{k,j}$ are equal to one. In other words, if and only if there is a $k< n$ such that $i \mathbin{R} k$ and $k \mathbin{R} j$. This is equivalent to $i \mathbin{(R \circ S)} j$, which in turn is equivalent to $(M_{R \circ S})_{i,j} = 1$.

I don't know if there is standard terminology for describing two matrices such that one is obtained from the other by replacing all the nonzero entries with ones, by the way. I have never heard "equivalent" used for this. It is probably best just to say explicitly what you mean, that is, $(M_{R \circ S})_{i,j} = 0$ if and only if $(M_R M_S)_{i,j} = 0$, and $(M_{R \circ S})_{i,j} = 1$ if and only if $(M_R M_S)_{i,j} > 0$.