16
$\begingroup$

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

$\endgroup$
3
  • 8
    $\begingroup$ 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.) $\endgroup$ Commented Nov 4, 2012 at 14:39
  • $\begingroup$ @Harald Hanche-Olsen, I am not sure I would know how to show that fact. $\endgroup$
    – Mack
    Commented Nov 4, 2012 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 4, 2012 at 20:59

4 Answers 4

20
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mack
    Commented Nov 6, 2012 at 23:20
  • $\begingroup$ This is awesome, great answer! $\endgroup$
    – user459879
    Commented Sep 10, 2018 at 14:00
7
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – Mack
    Commented Nov 4, 2012 at 15:08
  • $\begingroup$ 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. $\endgroup$
    – Old John
    Commented Nov 4, 2012 at 15:15
  • $\begingroup$ Oh, I see. Because I am missing the element 2. $\endgroup$
    – Mack
    Commented Nov 4, 2012 at 15:18
  • $\begingroup$ 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. $\endgroup$
    – Mack
    Commented Nov 4, 2012 at 15:25
  • $\begingroup$ Yes, any (or all) of $a, b, c$ are allowed to be equal. $\endgroup$
    – Old John
    Commented Nov 4, 2012 at 15:27
4
$\begingroup$

This confused me for a while so I'll try to break it down in a way that makes sense to me and probably isn't super rigorous.

Transitivity on a set of ordered pairs (the matrix you have there) says that if $(a,b)$ is in the set and $(b,c)$ is in the set then $(a,c)$ has to be.

So we make a matrix that tells us whether an ordered pair is in the set, let's say the elements are $\{a,b,c\}$ then we'll use a $1$ to mark a pair that is in the set and a $0$ for everything else. Let's say we know that $(a,b)$ and $(b,c)$ are in the set. Transitivity hangs on whether $(a,c)$ is in the set:

$$ \begin{bmatrix} (a,a) & (a,b) & (a,c) \\ (b,a) & (b,b) & (b,c) \\ (c,a) & (c,b) & (c,c) \\ \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 1 & ? \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix} $$

I believe the answer from other posters about squaring the matrix is the algorithmic way of answering that question.

$\endgroup$
1
$\begingroup$

If your matrix $A$ describes a reflexive and symmetric relation (which is easy to check), then here is an algebraic necessary condition for transitivity (note: this would make it an equivalence relation).

Define the Kirchhoff matrix $$K:=\mathrm{diag}(A\vec 1)-A,$$ where $\vec 1=(1,...,1)^\top\in\Bbb R^n$ and $\mathrm{diag}(\vec v)$ is the diagonal matrix with the diagonal entries $v_1,...,v_n$. Comput the eigenvalues $\lambda_1\le\cdots\le\lambda_n$ of $K$. If $A$ describes a transitive relation, then the eigenvalues encode a lot of information on the relation:

  • If exactly the first $m$ eigenvalues are zero, then there are $m$ equivalence classes $C_1,...,C_m$.
  • To each equivalence class $C_m$ of size $k$, ther belong exactly $k$ eigenvalues with the value $k+1$. Each eigenvalue belongs to exactly one equivalence class.

If the matrix is not of this form, the relation is not transitive.


Another necessary condition is:

  • Choose some $i\in\{1,...,n\}$. Let's say the $i$-th row of $A$ has exactly $k$ ones, and one of them is in position $A_{ij}$. So also the row $j$ must have exactly $k$ ones.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .