I don't want to do 5 matrix multiplication for this. Is there any easy way?
Is there a fast way to see if a relation is transitive just by looking at its relation matrix?
1
$\begingroup$
discrete-mathematics
2 Answers
5
In general there is not. If the relation is on a small set, the quickest approach is probably to draw the digraph of the relation and check it by eye for transitivity.
-
0@Math: That's certainly small enough, yes. – 2012-11-23
4
A relation is transitive if and only if it is contained in its square. If you're looking at a relation on a small finite set represented as a 0-1 matrix, you can easily find the square of the relation by squaring the matrix. You certainly don't need to perform five matrix multiplications.