Question

Consider the following relation on the set ? = {?, ?, ?}.

? = {(?, ?), (?, ?), (?, ?), (?, ?), (?, ?)}

? = {(?, ?), (?, ?), (?, ?), (?, ?), (?, ?)}

a) (4%) Find the matrices that represent the relations R and S.

b) (8%) Find the matrix that represents the composite relation R ° S. Show all your computations with intermediate results!

c) (6%) Determine whether the relation R ° S is transitive. Supply arguments!

Answer 1

(a) To find the matrix for a relation, create a matrix of size . The entries are if , otherwise .

Hence, the matrix for R is

	a	b	c
a	0	0	1
b	1	1	0
c	1	1	0

The matrix for S is

	a	b	c
a	0	1	1
b	1	0	1
c	1	0	0

(b) To find the matrix for , compute the matrix .

Then if, , this means there exists such that .

Hence . Otherwise, not.

The matrix is

2	2	0
1	1	1
0	0	1

Hence the matrix for , is

	a	b	c
a	1	1	0
b	1	1	1
c	0	0	1

(c) To check if is transitive, consider . If , then this means after applying the relation again, it remains the same. Hence, the relation is transitive

The matrix is

2	2	1
2	2	2
0	0	1

Note that but , hence the relation is not transitive.

Comment in case of any doubts.