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

1. 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

2. 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

3. 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.

4. 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

5. 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

6. 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

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

8. 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

9. 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?

10. 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

11. ah k that clears things up a bit

cheers