Extending relation to be transitive

Question

I am lookign for an easy "algorithm" to extend relation (add some elements to it) to be transitive, say I use matrix representation of relation is there any trick that can help me to say if it is transitive or not?

Answer 1

I am assuming you have a finite set $\{x_1,\dots,x_n\}$ and your matrix is $(m_{ij})$ where $m_{ij}=1$ if $x_i \sim x_j$ and $0$ otherwise. Consider squaring the matrix. You end up with the matrix $(n_{ij})$ where $$n_{ij} = \sum_{k=1}^n m_{ik}m_{kj}.$$ The term $n_{ij}$ will be zero unless there exists at least one $k$ such that $m_{ik}=m_{kj}=1$. In this case, $n_{ij}\geq 1$. The fact that $m_{ik}=m_{kj}=1$ means $x_i \sim x_k$ and $x_k \sim x_j$. If you want to extend your relation to be transitive, this means you need to add the relation $x_i\sim x_j$. So to figure out which relations need to be added, square the matrix and add relations corresponding to any nonzero entries in the squared matrix (unless they are already in the relation). Since this adds elements to the relation, the process must be repeated for the new relation matrix to account for additional relations that will then need to be added. Eventually you'll reach a step where there is nothing new to add (all the nonzero elements of the squared matrix correspond to elements already in the relation), and then you know you're done.