Finding transitive closure of a 3×3 matrix

equivalence-relationsmatricesrelations

I have a relation $R$ that corresponds to the following matrix:

$$M_R = \begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
1 & 1 & 0
\end{bmatrix}$$

I want to find the transitive closure. I've read I can perform multiple matrix multiplications to find it, namely for an $n\times n$ matrix, you need to find $M_R \lor M_R^2 \lor … \lor M_R^n$.

I've done some work below:

$$M_R^2 = \begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
1 & 1 & 0 \end{bmatrix} \odot
\begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
1 & 1 & 0 \end{bmatrix} =
\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 0 \\
1 & 1 & 1 \end{bmatrix}$$

$$M_R^3 = \begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
1 & 1 & 0 \end{bmatrix} \odot
\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 0 \\
1 & 1 & 1 \end{bmatrix} =
\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 0 \\
1 & 1 & 1 \end{bmatrix}$$

In fact, all $\{M_R^n : n \in Z^+, n > 1\} = M_R^2$. So I've found:

$$M_R \lor M_R^2 \lor M_R^3 = \begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 0 \\
1 & 1 & 1 \end{bmatrix}$$

I wanted to know if there was a less laborious way to do this, or if there's a trick I'm missing. I wonder about $4 \times 4$ matrices or beyond which can become complicated.

If you considered the matrix in terms of letters instead:

$$\begin{bmatrix}
a & b & c \\
d & e & f \\
g & h & i \end{bmatrix}$$

I know $\{(a,a), (a,c), \dots \} \in R$ and I can manually go through this to find the missing tuples stopping it from being a transitive relation, but I'm looking for a method specifically to speed up the matrix multiplication?

Best Answer

An "other" method that works better for the human eye in such cases of a few vertices is to draw the corresponding oriented graph. In our case we have the "connections"

  • $1\to 1$
  • $1\to 3$
  • $2\to 2$
  • $3\to 1$
  • $3\to 2$

so we draw:

sage: D = DiGraph( [[1, 2, 3], [(1,1), (1,3), (2,2), (3,1), (3,2) ]], loops=True )
sage: D.show()
Launched png viewer for Graphics object consisting of 11 graphics primitives
sage: D.adjacency_matrix()
[1 0 1]
[0 1 0]
[1 1 0]

Closing transitively a given relation

and building the transitive closure of the given relation means finding all possible oriented paths.

This can be done iteratively by extending the list we have step by step. At the beginning we have:

  • from $1$ we may go to $1,3$.
  • from $2$ we may go to $2$.
  • from $3$ we may go to $1,2$.

Now we use the given steps and extend.

  • from $1$ we may go to $1,3$, and also to $2$ (because $3\to 2$), so all togehter to $1,2,3$ so far.
  • from $2$ we may go to $2$.
  • from $3$ we may go to $1,2$ and also $1,3$ (because $1\to 1,3$), so all together to $1,2,3$ so far.

From here we further try to extend. But we do not get a further connection.

So we get with the bare eye immediately the result delivered by sage:

sage: DT = D.transitive_closure()
sage: DT.adjacency_matrix()
[1 1 1]
[0 1 0]
[1 1 1]

(Well, sage always puts $v\to v$ in the transitive closure if the graph is allowed to have vertex loops.)

Related Question