edited by
4,132 views
13 votes
13 votes

Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m < n$ and $R^m = R^n$.

edited by

4 Answers

Best answer
16 votes
16 votes

Understanding the definition :

For a given two relation R and S we define composition of R with S as,

$R\circ S = \{(x,z)~:~\exists y~\text{such that}~(x,y)\in R~\text{and}~(y,z)\in S\}$.

So composition of two relations gives us a relation such that the first element belongs to R and second element belongs to S and there is an element lets say $y$ such that in R we have $x$ related to y and in S in we have $y$ related to $z$. 

Understanding the symbols :

Here the power on relation signifies composition of relation R with itself. For any binary relation $R^0$ is an identity relation and $R^1=R$.

We can visualize each composition like these as a step we will take and go from an element to another. For $R^0$ means we are standing at a node and from there we are taking zero step and we see after taking zero step where we can reach. But taking zero step will lead nowhere and you will be at same node. That's one intuition we can why say $R^0$ should be an identity relation. So,

$R^0= \{ (a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g),(h,h) \}$

For some good intuition on why $R^0$ should be an identity relation you can check this link Link

Similarly for $R^1$ we stand at a node and see where can we go after taking 1 step. So after taking 1 step we get

$R^1= \{ (a,b),(b,c),(c,a),(a,b),(h,d),(d,e),(e,f),(f,g),(g,h) \}$ which equals R.

Now for $R^2$ we similarly check for 2 steps. So,

$R^2= \{ (a,c),(c,b),(b,a),(h,e),(d,f),(e,g),(f,h),(g,d),(h,e) \}$

Now try to remember the lcm problem which we used to solve during our school time. That two bell started ringing at the same time with a time interval of 4sec and 30 sec and when they will meet next? To solve this problem we calculate the lcm and then we get that at 60th second both will ring at same time.

Now for m=0 we have we have $R^0$ which is an identity relation we have seen above. So the next question obvious question is what should be n such that $R^0=R^n$.

Similarly like bell ringing problem if we see the first digraph then it has time interval of 3 ,i.e after 3 steps it will be same as earlier or after the 3 steps or $R^3$ we will get the identity relation back for first digraph. So we can say that, okay for m=0 and n=3 we have $R^m = R^n$ for the first digraph, but we have second digraph too. It should be also same as earlier i.e when m=0. And for the second digraph it will be same as earlier after 5 steps. So after 5 steps we have $R^m=R^n$ for second digraph. But we want $n$ such that the both digraph have $R^m=R^n$ at the same time. And so here the LCM comes into the picture. We know that the first digraph will be same as earlier after 3 steps and second will be same as earlier after 5 steps. Hence both will be same as earlier after LCM of 3 steps and 5 steps that is 15 steps.

Hence we can now safely conclude that for m=0 and n=15 we have $R^m=R^n$.

The question asked for smallest m and n and it took m as answer deciding factor so that’s why m=0 and n=15 the answer.

Understanding the question for m=1 and n=12

Its just like the both digraphs started at 1st second . So first one will complete its cycle at 4th second (since it has time interval 3) and similarly the second digraph will complete its cycle at 6(since it has time interval of 5) and so they will meet each other at the lcm of 4,6 and i.e 12.

selected by
29 votes
29 votes

First component repeats after every 3rd power of R,

R0 -> R1 -> R2 -> R0

R0 = R3 = R6 = ........

Second component repeats after every 5th power of R,

R0 -> R1 -> R2 -> R3 -> R4 -> R0

R0 = R5 = R10 = ........

The relation R is the combination of two components.

So R will repeat after every LCM(3,5) = 15th power of R.

Thus R0 = R15 = R30 = ........

So, m = 0 & n = 15.

For more information, watch this lecture:

9 votes
9 votes

For every non-empty set $A$, if $R$ is a binary relation on $A$ then-

$R^0$ is an identity relation on A which is defined as - $R^0= \{(x,x) \mid x \in A \}$

Also, if a relation has a cycle of length $n$ then its $n^{th}$ power is reflexive an identity relation. So for first component, $R^3$ is reflexive and hence $R^0=R^3.$ 
Similarly, for second component $R^0=R^5.$ 

$\text{LCM}$ of $3$ and $5$ is $15.$ So, $m = 0 \ and \ n=15.$
Check this for having some intuition behind $R^0$.

PS: Here, $R^1 = R^4; $ for first component and $R^1 = R^6$ for the second component and we get $m=1, n=\text{LCM}(4,6)=12.$ But question asks for smallest $m,n$ and that's why we go for $m=0, n=15.$

edited by
3 votes
3 votes

So the triangle relation, repeats in every $4$ th cycle.

The pentagon relation, repeats in every $6$ th cycle.

It is actually similar to the concept of time period. So the two relations will repeat in every $lcm(4,6)$ th cycle = $12$ th cycle.

So $m=1$ and $n=12$.

Related questions

20 votes
20 votes
6 answers
1
Kathleen asked Sep 26, 2014
3,711 views
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$
25 votes
25 votes
4 answers
2
18 votes
18 votes
5 answers
4
Kathleen asked Sep 25, 2014
9,333 views
Suppose $A$ is a finite set with $n$ elements. The number of elements in the largest equivalence relation of A is$n$$n^2$$1$$n+1$