How to check whether a relation is transitive from the matrix representation?

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.

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?

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.

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.