in Set Theory & Algebra edited by
4,100 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$.

in Set Theory & Algebra edited by
by
4.1k views

1 comment

Note that the triangle graph repeat itself in every 3 cycle i.e., R^1=R^4=R^7=R^10=R^13=R^16  and pentagon graph repeat itself in every 5 cycle so R^1=R^6=R^11=R^16. So R^16 relation is exactly same as R(i.e., given in question).So R^1=R^16. Hence m=1 and n=16. But the question asks for min possible value. So we can find the same relation as R^0 which we can find in a similar way i.e.,

R^0=R^3=R^6=R^9=R^12=R^15 for triangle graph and R^0=R^5=R^10=R^15 for pentagon graph. So R^0=R^15. Hence m=0 and n=15.
1
1

4 Answers

15 votes
15 votes
Best answer

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

4 Comments

Amazing 👍
1
1
Crystal clear
1
1

Everything seems right, but the first line where we define RoS ,  shouldn’t the definition be :

RoS = { (x,z) | there is a y such that xSy and yRz } 

@sameer_hack

0
0
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:

1 comment

Not 15th power but 15k power of R where k=0,1,2......
3
3
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

4 Comments

@Sherrinford This should help you.

@Soumya29 You need to edit your answer as $R_2 $ not equal to $R_6$ but $R_1 $ equal to $R_6$

3
3

I did not get how (1,12) is a solution.

The first component repeats after every 3rd step.

And the second component repeats after every 5th step.

Both the component together form our relation. So they will be equal to original relation after every 15th step.

So (0,15) is one solution.

The other solution should be (1,16), (2,17) and so on....as it repeats after every 15th step.

In the below video also it is said that it repeats after every 15th step....

https://youtu.be/xuhZSt4Rw0k?t=746

So how (1,12) is a solution, Please someone explain.

 

2
2
Could someone please tell me why we’ve taken lcm here?
0
0
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$.

1 comment

Thank you @HitechGa, one doubt by observation, please tell me whether my assumption is right or not. in 1st component, there are 3 edges so repetition can be observed after 3 transitions, while in 2nd component, there are 5 edges so so repetition can be observed after 5 transitions. Is it a rule or theorem that if it’s a simple cycle graph, repetition can be observed after the given number of edges. i.e. for n edges => at R^n we will start getting same pattern. Thank you.

0
0

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true