+3 votes
404 views

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 | 404 views

## 2 Answers

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

by Boss (16.3k points)
selected by
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.?
0
yes exactly
0

Part (B)

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

+1

@Soumya29   1,12 cannot be answer.

It should be 0,15

+1
Thanks, @warrior and @Rahul. I edited my comment.
0
nice explanation debashish sir
0
How m=1 and n=12 is a solution
0

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

can someone please explain , how to get m and n

0

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

+15 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:

by Active (2.1k points)
+1
Not 15th power but 15k power of R where k=0,1,2......

+17 votes
6 answers
1
+16 votes
3 answers
2
+19 votes
3 answers
3
+12 votes
2 answers
4