If $R$ is transitive relation. How can I prove that composition of its transpose is also transitive.

i.e. $R^T\ ;R^T$ is transitive too.

  • $\begingroup$ What is the transposition of a relation? $\endgroup$
    – Git Gud
    Oct 30 '15 at 16:22
  • 1
    $\begingroup$ @GitGud the matrix of a relation is its adjacency matrix. That is, the matrix of a relation on $n$ elements is an $n \times n$ matrix whose $a=i,j$ entry is a $1$ if $(x_i,x_j) \in R$ and $0$ otherwise. The transpose relation is the relation corresponding to the transposed graph. $\endgroup$ Oct 30 '15 at 16:25
  • $\begingroup$ More concisely: $xRy \iff y R^Tx$ $\endgroup$ Oct 30 '15 at 16:26

Let $x R^T y$ and $ y R^T z$. Then $ zRy $ and $ yRx$ by definition of the transpose relation. Since $R$ is transitive, that means that $zRx$. Again, by definition of the transpose relation, $xR^Tz$.

  • $\begingroup$ Thank you for your answer! $\endgroup$
    – TechJ
    Oct 30 '15 at 16:47

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.