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$.
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.$
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
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:
Gatecse
There is one more problem. Ppl who have...