# Binary relation finding the transitive closure

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?

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

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.