R1={(a,b),(b,c),(c,a)}

R2={(a,c),(b,a),(c,b)}

R3={(a,a),(b,b),(c,c)}

R4={(a,b),(b,c),(c,a)}

so for 1st digraph m=1 and n=4 R1=R4 this what you want to say.?

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

7 votes

Best answer

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.$ LCM of $3$ and $5$ is $15.$

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

$\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 = R4; R_2 = R_6$ and we get $m=1, n=12.$ But question asks for smallest $m,n.$

0

+Saumya29

R1={(a,b),(b,c),(c,a)}

R2={(a,c),(b,a),(c,b)}

R3={(a,a),(b,b),(c,c)}

R4={(a,b),(b,c),(c,a)}

so for 1st digraph m=1 and n=4 R1=R4 this what you want to say.?

R1={(a,b),(b,c),(c,a)}

R2={(a,c),(b,a),(c,b)}

R3={(a,a),(b,b),(c,c)}

R4={(a,b),(b,c),(c,a)}

so for 1st digraph m=1 and n=4 R1=R4 this what you want to say.?

1

**Part (B)**

For clear understanding and solution for part (B) just watch Kamala krithivasan mam video lectures on Relations.

1

I didn't understand this part " LCM of 3 and 5 is 15. So, *m*=0 *a**n**d* *n*=15"

can someone please explain , how to get m and n

1

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

0

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

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

21 votes

First component repeats after every 3^{rd} power of R,

R^{0} -> R^{1} -> R^{2} -> R^{0}

R^{0} = R^{3} = R^{6} = ........

Second component repeats after every 5th power of R,

R^{0} -> R^{1} -> R^{2} -> R^{3} -> R^{4} -> R^{0}

R^{0} = R^{5} = R^{10} = ........

The relation R is the combination of two components.

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

Thus R^{0} = R^{15} = R^{30} = ........

So, m = 0 & n = 15.

For more information, watch this lecture: