$$\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}$$
This is a matrix representation of a relation on the set $\{1, 2, 3\}$. I have to determine if this relation matrix is transitive. I know that the ordered-pairs that make this matrix transitive are $(1, 3)$, $(3,3)$, and $(3, 1)$; but what I am having trouble is applying the definition to see what the $a$, $b$, and $c$ values are that make this relation transitive. I am sorry if this problem seems trivial, but I could use some help.
Thank you!
Best Answer
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.