Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Can you be more specific about the relation (?) you denote by "R;S"? This is not standard notation as far as I know. – Marc van Leeuwen Sep 11 '12 at 12:49
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. – Kevin Sep 11 '12 at 13:17
up vote 3 down vote accepted

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

share|cite|improve this answer
Thanks for you answer :)! – Kevin Sep 20 '12 at 8:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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