The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 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$.

asked ago in Set Theory & Algebra by Veteran (355k points) | 30 views

2 Answers

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

answered by Boss (12.1k points)
selected ago by





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

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,009 questions
45,506 answers
48,691 users