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$.

  • 1
    $\begingroup$ Can you be more specific about the relation (?) you denote by "R;S"? This is not standard notation as far as I know. $\endgroup$ Sep 11, 2012 at 12:49
  • $\begingroup$ 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. $\endgroup$ Sep 11, 2012 at 13:17

1 Answer 1


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<n} (M_R)_{i,k} (M_S)_{k,j}$ 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<n$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.