# Transitive Relation

$$\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!

-
Since you are looking at a a matrix representation of the relation, an easy way to check transitivity is to square the matrix. The relation is transitive if and only if the squared matrix has no nonzero entry where the original had a zero. (If you don't know this fact, it is a useful exercise to show it.) –  Harald Hanche-Olsen Nov 4 '12 at 14:39
@Harald Hanche-Olsen, I am not sure I would know how to show that fact. –  Mack Nov 4 '12 at 15:14
The basic idea is this: Call the matrix elements $a_{ij}\in\{0,1\}$. The $(i,j)$ element of the squared matrix is $\sum_k a_{ik}a_{kj}$, which is non-zero if and only if $a_{ik}a_{kj}=1$ for some $k$, i.e., iff $(i,k)$ and $(k,j)$ are both in the relation. –  Harald Hanche-Olsen Nov 4 '12 at 20:59

Perhaps you could look at it like this:

How can it fail to be transitive?

It can only fail to be transitive if there are integers $a, b, c$ such that (a,b) and (b,c) are ordered pairs for the relation, but (a,c) is not. Can you show that this cannot happen?

-
I think I found it, would it be $(3,1)and(1,3)\rightarrow(3,3)$; and that's why it is transitive? I have another question, is there a list of tex commands? Because certain things I can't figure out how to type; for instance, the "and" symbol. –  Mack Nov 4 '12 at 15:08
For LaTeX, you might find what you want here or here. For the transitivity, it is not enough just to look at (3,1) and (1,3). You need to show that it works for all such pairs. –  Old John Nov 4 '12 at 15:15
Oh, I see. Because I am missing the element 2. –  Mack Nov 4 '12 at 15:18
For transitivity, can a,b, and c all be equal? Because if that is possible, then $(2,2)\wedge(2,2)\rightarrow(2,2)$; meaning that the relation is transitive for all a, b, and c. –  Mack Nov 4 '12 at 15:25
Yes, any (or all) of $a, b, c$ are allowed to be equal. –  Old John Nov 4 '12 at 15:27

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.

-
Quick question, what is this operation referred to as; that is, squaring the relation, $R^2$? I would like to read up more on it. I've tried to a google search, but I couldn't find a single thing on it. –  Mack Nov 6 '12 at 23:20
@EMACK: The operation itself is just matrix multiplication. Are you asking about the interpretation in terms of relations? If you’ve been introduced to the digraph of a relation, you may find this PDF helpful; the matrix of a relation is the adjacency matrix of the digraph of the relation. –  Brian M. Scott Nov 6 '12 at 23:33