Thread: 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

Originally Posted by cpklas

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

Originally Posted by CaptainBlack

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.

Originally Posted by Plato

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

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

Originally Posted by cpklas

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

Originally Posted by CaptainBlack

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

Originally Posted by cpklas

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

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?

Originally Posted by Papakanos

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

ah k that clears things up a bit

cheers