Results 1 to 7 of 7

Math Help - Use the matrix representation of relations to compute the following

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    Use the matrix representation of relations to compute the following

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    Quote Originally Posted by Runty View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2010
    Posts
    232
    So, does that mean my answer was wrong? I'll assume you mean no since T is not transitive.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jan 2010
    Posts
    232
    Quote Originally Posted by Black View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jan 2010
    Posts
    232
    Quote Originally Posted by Runty View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Matrix Representation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 19th 2010, 04:52 AM
  2. compute matrix inversion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 8th 2009, 11:21 AM
  3. COMPUTE MATRIX
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 19th 2008, 10:11 AM
  4. Matrix representation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 17th 2008, 09:41 AM
  5. Matrix Representation
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 5th 2008, 08:43 AM

Search Tags


/mathhelpforum @mathhelpforum