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

• May 10th 2007, 06:58 AM
cpklas
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
• May 10th 2007, 08:05 AM
CaptainBlack
Quote:

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
• May 10th 2007, 08:15 AM
Plato
Quote:

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.
• May 10th 2007, 10:10 AM
CaptainBlack
Quote:

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.

RonL
• May 10th 2007, 05:12 PM
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.

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
• May 10th 2007, 09:00 PM
CaptainBlack
Quote:

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.

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
• May 10th 2007, 10:17 PM
cpklas
Quote:

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```

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

Thanks a lot!

Henrik
• May 11th 2007, 12:07 AM
CaptainBlack
Quote:

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?

needed to specify the assumptions on A.

RonL
• May 12th 2007, 10:30 PM
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?
• May 13th 2007, 01:04 AM
CaptainBlack
Quote:

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
• May 13th 2007, 01:26 AM
Papakanos
ah k that clears things up a bit:)

cheers