Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: May 2016

$\text{Writing down the Boolean matrix we get} \\ M_R=\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ \text{If we compute the higher powers of} \ \ M_R \text{we get}:$

$$(M_R)^2_\odot=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ (M_R)^3_\odot=\begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix} \\ (M_R)^4_\odot=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

$\text{Thus we observe that}(M_R)^n_\odot equals (M_R)^2_\odot \text{if n is even, and equals} (M_R)^3_\odot \text{if n is odd and greater than 1. Hence we get,}$

$$M_{R\infty}=M_R \vee (M_R)^2_\odot \vee (M_R)^3_\odot$$

$\text{thus}$

$$M_{R\infty}=\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$