GATE1998-10b

Question

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

Answer 1

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

Comments

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

---

yes exactly

---

Part (B)

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

---

@Soumya29   1,12 cannot be answer.

It should be 0,15

---

Thanks, @warrior and @Rahul. I edited my comment.

---

nice explanation debashish sir

---

How m=1 and n=12 is a solution

---

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

---

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

Answer 2

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

R⁰ -> R¹ -> R² -> R⁰

R⁰ = R³ = R⁶ = ........

Second component repeats after every 5th power of R,

R⁰ -> R¹ -> R² -> R³ -> R⁴ -> R⁰

R⁰ = R⁵ = R¹⁰ = ........

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⁰ = R¹⁵ = R³⁰ = ........

So, m = 0 & n = 15.

For more information, watch this lecture:

Comments

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