Results 1 to 11 of 11

Math Help - How do I write an algorithm that tests if a relation on a matrix is a function

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    7

    How do I write an algorithm that tests if a relation on a matrix is a function

    Hello all!

    I have a problem that I don't know where to start with. I have to write an algorithm that finds out if a relation is a function. Okay, the question goes like this:

    Write an algorithm that receives as input the matrix A of relation R on set X and tests whether R is a function. The matrix A will be n x n , where n = |X|. Find the best-case and worst-case number of comparisons used by your algorithm in terms of n.

    Does anyone know how to write this algorithm? I hope so because I'm stuck.

    Cheers,
    Henrik
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by cpklas View Post
    Hello all!

    I have a problem that I don't know where to start with. I have to write an algorithm that finds out if a relation is a function. Okay, the question goes like this:

    Write an algorithm that receives as input the matrix A of relation R on set X and tests whether R is a function. The matrix A will be n x n , where n = |X|. Find the best-case and worst-case number of comparisons used by your algorithm in terms of n.

    Does anyone know how to write this algorithm? I hope so because I'm stuck.

    Cheers,
    Henrik
    I think you need something like the following to start this (I am assuming R is a binary relation):

    Suppose that we number the elements of X, so X={x1, x2, ..., xn}

    Lets suppose that the matrix A has 1 in position (i,j) if (xi,xj) is in R, and
    0 otherwise.

    R is a function iff for all (x,y) in R (x,z) => if (x,z) is in R then z=y, then we
    may write r(x)=y.

    Hence R is a function iff there is at most 1 "1" in each row of A.

    So your algorithm has to check that each row of A contains no more than 1 "1"
    and all other elements are 0.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    So your algorithm has to check that each row of A contains no more than 1 "1" and all other elements are 0.
    That may well be the case. But I think that it depends upon the particular textbook. All of the set theory texts I have ever used require the the domain of the relation be the entire set in order for the relation to be a function. If that is the case here then each row would have exactly one 1.

    So check the definition of function in your textbook.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Plato View Post
    That may well be the case. But I think that it depends upon the particular textbook. All of the set theory texts I have ever used require the the domain of the relation be the entire set in order for the relation to be a function. If that is the case here then each row would have exactly one 1.

    So check the definition of function in your textbook.
    Agreed, look up your definitions.


    RonL
    Last edited by CaptainBlack; May 10th 2007 at 09:48 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2007
    Posts
    7
    Hi guys, thanks for your help. It made things a lot more clear to me.

    The definition in my book is that every row must contain exactly one 1 for the relation to be a function.

    What do you think about this code to test it:

    Code:
    Input: A (Matrix, n x n)
    Output: Boolean (true=function)
    
    function_test(A) {
      for i = 1 to n {
        ones = 0
        for j = 1 to n {
          if(Aij = 1)
            ones = ones + 1
        }
        if(ones != 1)
          return false
      }
      return true
    }
    Thanks a lot!

    Henrik
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by cpklas View Post
    Hi guys, thanks for your help. It made things a lot more clear to me.

    The definition in my book is that every row must contain exactly one 1 for the relation to be a function.

    What do you think about this code to test it:

    Code:
    Input: A (Matrix, n x n)
    Output: Boolean (true=function)
     
    function_test(A) {
      for i = 1 to n {
        ones = 0
        for j = 1 to n {
          if(Aij = 1)
            ones = ones + 1
        }
        if(ones != 1)
          return false
      }
      return true
    }
    Thanks a lot!

    Henrik
    What about the values in the elements of A which are not 1's? Or are
    you assuming the A is a matrix of 0's and 1's. I would have though you
    would at least have required as assumption statement of some kind.

    Something like:

    Assumption: A is the incidence matrix of a relation, and so consists only of 0's and 1's

    Your algorithm makes exactly 1 comparison for every element of A and one to check
    if ones==1 for each row, so the best and worst case number of comparisons are equal
    to n^2+n.

    RonL
    Last edited by CaptainBlack; May 10th 2007 at 09:16 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2007
    Posts
    7
    Quote Originally Posted by CaptainBlack View Post
    What about the values in the elemnts of A which are not 1's? Or are
    you assuming the A is a matrix of 0's and 1's.

    RonL
    Well, does that matter? If the definition is that every row must contain exactly one 1 for the relation to be a function then it shouldn't matter what the other elements are? Or?



    I had a look at the second part of the question (if my algorithm works):
    Find the best-case and worst-case number of comparisons used by your algorithm in terms of n.

    I got best case to: n + 1
    and worst case to: n^2 + n

    To calculate worst case I did
    Code:
     
    i    j       this i     total
    1    1...n    n+1        n+1
    2    1...n    n+1        2n+2
    3    1...n    n+1        3n+3
    ...
    n    1...n    n+1        n^2 + n
    May I ask you what you think about that?

    edit: while I was writing this you edited your message with the best/worst, hehe weird.


    Thanks a lot!

    Henrik
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by cpklas View Post
    Well, does that matter? If the definition is that every row must contain exactly one 1 for the relation to be a function then it shouldn't matter what the other elements are? Or?
    In addition to adding something about the best worst case analysis I also
    added something about this. Namely that perhaps an assumption statement is
    needed to specify the assumptions on A.

    RonL
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    May 2007
    Posts
    4
    I also have a similar problem to that so that being said does this mean with the algorithm used that in the end the relation is NOT a function as each row in the matrix contains more than one 1?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Papakanos View Post
    I also have a similar problem to that so that being said does this mean with the algorithm used that in the end the relation is NOT a function as each row in the matrix contains more than one 1?
    The relation is a function iff each row of A contains exactly one "1", so
    if any row of A has more than one "1" R is not a function (when A is defined
    in the manner we have here)

    RonL
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    May 2007
    Posts
    4
    ah k that clears things up a bit

    cheers
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Write the given matrix as a product of elementary matrices
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 10th 2010, 01:22 AM
  2. Write the inverse of A in terms of the matrix A
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 15th 2010, 06:00 AM
  3. integer relation finding algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 11th 2010, 06:24 PM
  4. a- Write the simplex matrix to maximize the profit.
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 22nd 2009, 07:51 AM
  5. Write a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2009, 09:03 AM

Search Tags


/mathhelpforum @mathhelpforum