0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Is this considered the "least" transitive closure? I also find $\begin{bmatrix}1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1\end{bmatrix}$ to be a transitive closure. $\endgroup$ – gator Jul 12 at 16:00
  • $\begingroup$ @gator if we are referring to the transitive closure, then we are interested specifically in the one which required the fewest changes, in the language of matrices the one which minimizes the total number of $1$'s. Yes, the closure that dan_fulea refers to here will be the least possible. $\endgroup$ – JMoravitz Jul 12 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.