What does the notation $M^{[2]}$ mean with regards to matrices?

148 Views Asked by At

I am busy studying transitive closures of relations.

The Matrix of the relation, $M_R$ is

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

As you might know the transitive closure is given by:

$$M_R^* = M_R\vee M_R^{[2]}\vee M_R^{[3]} $$

How can I find $M_R^{[2]}$ and $M_R^{[3]}$? It is not the same as $M_R \times M_R$ and $M_R \times M_R \times M_R$ right?

1

There are 1 best solutions below

0
On BEST ANSWER

We find $M^{[n]}$ in the same way we would find $M^n$, only we replace addition with $\vee$ and multiplication with $\wedge$. So, for example: we have $$ M_R = \pmatrix{ 1&0&\color{blue}1\\ \color{red} 0& \color{red} 1& \color{purple}0\\ 1&1&\color{blue}0 } $$ So, the entry of $M_R^{[2]}$ in the $\color{red}2$nd row and $\color{blue}3$rd column is given by $$ (\color{red}0 \wedge \color{blue}1) \vee (\color{red}1 \wedge \color{blue}0) \vee (\color{red}0 \wedge \color{blue}0) = 0 $$ Overall, we compute $$ M_R^{[2]} = \pmatrix{ 1&1&1\\ 0&1&0\\ 1&1&1 } $$