Is there any way to quickly check if a partial order is transitive?

Question

Is there any fail safe and quick way to check if a partial order $\preceq$ on a set $A$ is transitive without checking through trial and error?

Answer 1

We shall solve this problem by using a bit of graph theory.

First draw the directed,acyclic graph of the partially ordered set $(A,\preceq)$. Then compute the adjacency matrix, $M$, of the graph.

Note that in general for all graphs G and for all positive integers k, the $(i,j)$th entry of $M^{k}$ gives the number of walks of length $k$ between $v_{i}$ and $v_{j}$.

Now we find $M^{2}$, whose $(i,j)$th entry will give the total number of walks of length $2$ between $v_{i}$ and $v_{j}$. So for every non-zero entry of $M^{2}$, we just need to check if it's corresponding entry in $M$ is non-zero,and if it's the case, then the partial order $\preceq$ is transitive indeed!