# GATE1998-10b

670 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

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

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
1

Part (B)

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

1

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
1

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

1

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

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.

1
Not 15th power but 15k power of R where k=0,1,2......

## Related questions

1
1.5k views
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$
The binary relation $R = \{(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)\}$ on the set $A=\{1, 2, 3, 4\}$ is reflexive, symmetric and transitive neither reflexive, nor irreflexive but transitive irreflexive, symmetric and transitive irreflexive and antisymmetric
Let $R_1$ and $R_2$ be two equivalence relations on a set. Consider the following assertions: $R_1 \cup R_2$ is an equivalence relation $R_1 \cap R_2$ is an equivalence relation Which of the following is correct? Both assertions are true Assertions (i) is true but assertions (ii) is not true Assertions (ii) is true but assertions (i) is not true Neither (i) nor (ii) is true
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$