Is there a fast way to see if a relation is transitive just by looking at its relation matrix?

Question

I don't want to do 5 matrix multiplication for this. Is there any easy way?

score 5 · Accepted Answer · answered Nov 23 '12 at 16:09

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.

answered Nov 23 '12 at 16:09

Brian M. Scott

616,228

small like 01234? – Math Nov 23 '12 at 19:42
@Math: That's certainly small enough, yes. – Brian M. Scott Nov 23 '12 at 19:50

score 4 · Answer 2 · answered Nov 23 '12 at 16:18

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.

Is there a fast way to see if a relation is transitive just by looking at its relation matrix?

2 Answers2