0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Say, it is transitive and you are using the matrix representation. Pick some $a \sim b$ and $b \sim c$ and mark them in your matrix. What entry does $a \sim c$ represent? can you generalize this? $\endgroup$ – gt6989b Dec 15 '15 at 20:52
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so when I have first matrix with elements $m_{ij}$ and then square this matrix with elements $n_{ij}$ i have to do "union" of these 2 matrices what I mean by union is I put 1 where I had 1 before plus I add "1" from new matrix where I had 0 before ? is it enough to only look at first square or I have to do basicly transitive closure and do it as long until I see nothing is changed from previous step ? $\endgroup$ – lllook Dec 15 '15 at 21:00
  • $\begingroup$ Ah that is a good point. Since you are adding relations, yes I think you will have to repeat this process until you don't get anything new to add. $\endgroup$ – kccu Dec 15 '15 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.