1
$\begingroup$

Let $A=\{a,b,c\}$ and the relation given by the following matrix: $\mathcal M_r=\begin{pmatrix}1&0&1\\0&1&0\\1&1&0\end{pmatrix}$

The task is to find the smallest transitive relation $E$ such that $r\subseteq E$. Which is equivalent of saying find the transitive closure of $r$.

so what I know is that: $t(r)=\cup_{n\geq0}r^n, r^n=r\circ r\circ r\circ...\circ r, n$ times.

so $\mathcal M_{t(r)}=\sum_{n\in\mathbb{N}}\mathcal (M_r)^n$ and this gives me $$\mathcal M_{t(r)}=\begin{pmatrix}1&1&1\\0&1&0\\1&1&1\end{pmatrix}$$

Is there something wrong in my approach?

$\endgroup$
4
  • $\begingroup$ It's not clear how do you calculate $\mathcal M_r^n$ and their sum? $\endgroup$ – Berci Jan 18 '19 at 14:28
  • $\begingroup$ @Berci Using logic operators, $+$ is denoted as OR and $.$ is denoted as AND. And $n$ is the cardinal of set $A$ $\endgroup$ – C. Cristi Jan 18 '19 at 14:41
  • $\begingroup$ The result is correct. For this specific small example there's a shorter way to solve, though. $\endgroup$ – Berci Jan 18 '19 at 14:45
  • $\begingroup$ @Berci Which way? $\endgroup$ – C. Cristi Jan 18 '19 at 14:45
1
$\begingroup$

Your solution is correct

If our graph is small like this, we can simply draw it (loops at $a$ and $b$ and arrows $a\to c,\ b\to c,\ c\to a$), and then use that we have an arrow $x\to y$ in the transitive closure iff there is a path $x\leadsto y$ in the original graph.

$\endgroup$

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.