Use the matrix representation of relations to compute the following

**Runty** · March 18th 2010, 09:55 AM

Let $C=\{a,b,c,d,e,f,g,h\}$ . Let $R=\{(f,g),(h,a),(d,e),(e,e),(g,h),(b,c),(b,f),(c,g )\}$ be a relation on the set $C$ . Use the matrix representation of relations in order to compute the following:

a) Let $S$ be the reflexive closure of $R$ . Compute $S$ .
My current answer is $S=\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\0& 1&1&0&0&1&0&0\\0&0&1&0&0&0&1&0\\0&0&0&1&1&0&0&0\\0 &0&0&0&1&0&0&0\\0&0&0&0&0&1&1&0\\0&0&0&0&0&0&1&1\\ 1&0&0&0&0&0&0&1\end{array}\right)$

b) Let $T$ be the transitive closure of $R$ . Compute $T$ . (I used Warshall's algorithm)
My current answer is $T=\left(\begin{array}{cccccccc}0&0&0&0&0&0&0&0\\0& 0&1&0&0&1&0&0\\1&0&1&0&0&0&1&1\\0&0&0&0&1&0&0&0\\0 &0&0&0&1&0&0&0\\1&0&0&0&0&1&1&1\\1&0&0&0&0&0&0&1\\ 1&0&0&0&0&0&0&0\end{array}\right)$

c) Let $D=S\cup T$ . Compute the symmetric closure of $D$ and call this set $F$ .
My current answer is $F=\left(\begin{array}{cccccccc}1&0&1&0&0&1&1&1\\0& 1&1&0&0&1&0&0\\1&1&1&0&0&0&1&1\\0&0&0&1&1&0&0&0\\0 &0&0&1&1&0&0&0\\1&1&0&0&0&1&1&1\\1&0&1&0&0&1&1&1\\ 1&0&1&0&0&1&1&1\end{array}\right)$

d) Prove or disprove that $F$ is an equivalence relation on the set $C$ . If $F$ is an equivalence relation, then list the elements in each of the equivalence classes. If $F$ is not an equivalence relation, then list what elements need to be added to $F$ to make it an equivalence relation.
(I have not completed this part yet, so I could use a hand here)

I mainly need to know whether my work on the first three parts has yielded correct answers (it'd be pretty easy to make a mistake). As for the last part, any help would be appreciated.

**Black** · March 18th 2010, 08:11 PM

Originally Posted by Runty

b) Let $T$ be the transitive closure of $R$ . Compute $T$ . (I used Warshall's algorithm)
My current answer is $T=\left(\begin{array}{cccccccc}0&0&0&0&0&0&0&0\\0& 0&1&0&0&1&0&0\\1&0&1&0&0&0&1&1\\0&0&0&0&1&0&0&0\\0 &0&0&0&1&0&0&0\\1&0&0&0&0&1&1&1\\1&0&0&0&0&0&0&1\\ 1&0&0&0&0&0&0&0\end{array}\right)$

Looking at this matrix, we have $(b,c),(c,a) \in T$ , but $(b,a) \notin T$ , so $T$ can't be transitive.

**Runty** · March 21st 2010, 09:39 AM

So, does that mean my answer was wrong? I'll assume you mean no since $T$ is not transitive.

**Black** · March 21st 2010, 01:59 PM

Yeah, $T$ must be the smallest transitive relation that contains $R$ .

Using the method here (under 'Existence and description'), I was able to get

$T=\left(\begin{array}{cccccccc}0&0&0&0&0&0&0&0 \\ 1&0&1&0&0&1&1&1 \\ 1&0&0&0&0&0&1&1 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&1&0&0&0 \\ 1&0&0&0&0&0&1&1 \\ 1&0&0&0&0&0&0&1 \\ 1&0&0&0&0&0&0&0 \end{array}\right)$ (might want to check it though).

Now to get $S \cup T$ , you just use the Boolean operation " $\vee$ " on each of the corresponding entries of $S$ and $T$ (since the 1,1 entry of $S$ is 1 and for $T$ it's 0, then the 1,1 entry of $S \cup T$ is: $1 \vee 0=1$ , and so on).

Finally, if $S \cup T$ is a symmetric matrix, then it is an equivalence relation (since $S \cup T$ is reflexive and transitive).

**Runty** · March 22nd 2010, 07:26 AM

Originally Posted by Black

Yeah, $T$ must be the smallest transitive relation that contains $R$ .

Using the method here (under 'Existence and description'), I was able to get

$T=\left(\begin{array}{cccccccc}0&0&0&0&0&0&0&0 \\ 1&0&1&0&0&1&1&1 \\ 1&0&0&0&0&0&1&1 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&1&0&0&0 \\ 1&0&0&0&0&0&1&1 \\ 1&0&0&0&0&0&0&1 \\ 1&0&0&0&0&0&0&0 \end{array}\right)$ (might want to check it though).

Now to get $S \cup T$ , you just use the Boolean operation " $\vee$ " on each of the corresponding entries of $S$ and $T$ (since the 1,1 entry of $S$ is 1 and for $T$ it's 0, then the 1,1 entry of $S \cup T$ is: $1 \vee 0=1$ , and so on).

Finally, if $S \cup T$ is a symmetric matrix, then it is an equivalence relation (since $S \cup T$ is reflexive and transitive).

Ran through it and got a corrected answer. My new answer for $F$ (which is the symmetric closure of $D$ ) is as follows:

$F=\left(\begin{array}{cccccccc}1&1&1&0&0&1&1&1 \\ 1&1&1&0&0&1&1&1 \\ 1&1&1&0&0&0&1&1 \\ 0&0&0&1&1&0&0&0 \\ 0&0&0&1&1&0&0&0 \\ 1&1&0&0&0&1&1&1 \\ 1&1&1&0&0&1&1&1 \\ 1&1&1&0&0&1&1&1 \end{array}\right)$

Now I just need to do the last part for it: prove or disprove that $F$ is an equivalence relation on the set $C$ and, if it is an equivalence relation, list the elements in each of its equivalence classes. Easier said than done, so any assistance would be appreciated.

**Runty** · March 23rd 2010, 05:14 AM

Originally Posted by Runty

Ran through it and got a corrected answer. My new answer for $F$ (which is the symmetric closure of $D$ ) is as follows:

$F=\left(\begin{array}{cccccccc}1&1&1&0&0&1&1&1 \\ 1&1&1&0&0&1&1&1 \\ 1&1&1&0&0&0&1&1 \\ 0&0&0&1&1&0&0&0 \\ 0&0&0&1&1&0&0&0 \\ 1&1&0&0&0&1&1&1 \\ 1&1&1&0&0&1&1&1 \\ 1&1&1&0&0&1&1&1 \end{array}\right)$

Now I just need to do the last part for it: prove or disprove that $F$ is an equivalence relation on the set $C$ and, if it is an equivalence relation, list the elements in each of its equivalence classes. Easier said than done, so any assistance would be appreciated.

Sorry for doublepost, but I'd like to update. For my answer for $F$ , I've come to the assumption that it is NOT an equivalence relation because it is not transitive. My reasoning is this:
$(c,a)\in F$ and $(a,f)\in F$ , but $(c,f)\notin F$
$(f,a)\in F$ and $(a,c)\in F$ , but $(f,c)\notin F$
Am I right or wrong in my thinking?

**Black** · March 23rd 2010, 07:25 AM

Yes, you are right; the set F isn't transitive. Fortunately, the two elements you pointed out: (c,f) and (f,c), makes up for the transitive closure of F (which is an equivalence relation).

Thread: Use the matrix representation of relations to compute the following

LinkBack

Thread Tools

Display

Use the matrix representation of relations to compute the following

Similar Math Help Forum Discussions

Matrix Representation

compute matrix inversion

COMPUTE MATRIX

Matrix representation

Matrix Representation

Search Tags