Find transitive closure of relation $R$ described by the matrix $M_R$:
$$M_R = \begin{bmatrix}1 & 0 &0 \\0 & 1 & 1 \\1 & 0 & 1 \end{bmatrix}$$
I tried doing it like this $M_R \cdot M_R \cdot M_R$ but could not get the answer.
[Math] Find transitive closure of the relation, given its matrix
discrete mathematicselementary-set-theorymatricesrelations
Related Solutions
This is an answer to your second question, about the relation $R=\{\langle 1,2\rangle,\langle 2,2\rangle,\langle 3,2\rangle\}$. We can check transitivity in several ways.
(1) List all of the linked pairs:
$$\begin{align*} &\langle 1,2\rangle\land\langle 2,2\rangle\tag{1}\\ &\langle 2,2\rangle\land\langle 2,2\rangle\tag{2}\\ &\langle 3,2\rangle\land\langle 2,2\rangle\tag{3} \end{align*}$$
If $R$ is to be transitive, $(1)$ requires that $\langle 1,2\rangle$ be in $R$, $(2)$ requires that $\langle 2,2\rangle$ be in $R$, and $(3)$ requires that $\langle 3,2\rangle$ be in $R$. And since all of these required pairs are in $R$, $R$ is indeed transitive.
(2) Check all possible pairs of endpoints. For example, to see whether $\langle 1,3\rangle$ is needed in order for $R$ to be transitive, see whether there is a ‘stepping-stone’ from $1$ to $3$: is there an $a$ such that $\langle 1,a\rangle$ and $\langle a,3\rangle$ are both in $R$? If so, transitivity will require that $\langle 1,3\rangle$ be in $R$ as well. As it happens, there is no such $a$, so transitivity of $R$ doesn’t require that $\langle 1,3\rangle$ be in $R$. Do this check for each of the nine ordered pairs in $\{1,2,3\}\times\{1,2,3\}$.
(3) Use the matrix
$$M_R=\begin{bmatrix}0&1&0\\0&1&0\\0&1&0\end{bmatrix}$$
of the relation. You may not have learned this yet, but just as $M_R$ tells you what ‘one-step paths’ in $\{1,2,3\}$ are in $R$,
$$M_R^2=\begin{bmatrix}0&1&0\\0&1&0\\0&1&0\end{bmatrix}\begin{bmatrix}0&1&0\\0&1&0\\0&1&0\end{bmatrix}=\begin{bmatrix}0&1&0\\0&1&0\\0&1&0\end{bmatrix}$$
counts the number of $2$-step paths between elements of $\{1,2,3\}$. The entry in row $i$, column $j$ is the number of $2$-step paths from $i$ to $j$. (By a $2$-step path I mean something like $\langle 3,2\rangle\land\langle 2,2\rangle$: the first pair takes you from $3$ to $2$, the second takes from $2$ to $2$, and the two together take you from $3$ to $2$.)
In order for $R$ to be transitive, $\langle i,j\rangle$ must be in $R$ whenever there is a $2$-step path from $i$ to $j$. For this relation that’s certainly the case: $M_R^2$ shows that the only $2$-step paths are from $1$ to $2$, from $2$ to $2$, and from $3$ to $2$, and those pairs are already in $R$.
In the original problem you have the matrix
$$M_R=\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}\;,$$
and
$$M_R^2=\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}=\begin{bmatrix}2&0&2\\0&1&0\\2&0&2\end{bmatrix}\;.$$
The $2$’s indicate that there are two $2$-step paths from $1$ to $1$, from $1$ to $3$, from $3$ to $1$, and from $3$ to $3$; there is only one $2$-step path from $2$ to $2$. From $1$ to $1$, for instance, you have both $\langle 1,1\rangle\land\langle 1,1\rangle$ and $\langle 1,3\rangle\land\langle 3,1\rangle$. But the important thing for transitivity is that wherever $M_R^2$ shows at least one $2$-step path, $M_R$ shows that there is already a one-step path, and $R$ is therefore transitive.
In short, find the non-zero entries in $M_R^2$. If $M_R$ already has a $1$ in each of those positions, $R$ is transitive; if not, it’s not.
If $R,S$ are relations, then define $RS$ (or $R \circ S$) as $R \circ S = \{ (x,z) | \exists y \ xRy \text{ and } y S z\}$. Let $R^k$ be the composition of $R$ with itself $k$ times.
Then define $R^* = \cup_{k=1}^\infty R^k$. Since $R$ above is finite, then one can explicitly compute $R^*$ in a finite number of steps by a 'fixed point' computation starting with $R$.
By 'fixed point', I mean to find the smallest set $Q$ such that $R \subset Q$ and $RQ \subset Q$, and the scheme is $Q_0 = R$, $Q_{k+1}= Q_k \cup R Q_k$, stopping when $Q_{k+1} = Q_k$.
Best Answer
The relation indicated by this matrix can be described as $$ (x,x) \quad x = 1,2,3\\ (2,3)\\ (3,1) $$ In order for the relation to be transitively closed, you need to add $(2,1)$. So, the matrix we want is $$ \pmatrix{ 1&0&0\\ 1&1&1\\ 1&0&1 } $$