[Math] Matrices in discrete math

discrete mathematics

Let $A=\{0,1,2,3\}$ and let $R$ and $S$ be the relations on $A$ described by the matrices

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

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

Question 1

Compute $M_{R^{-1}}$, $M_{R \cap S}$, $M_{R \circ S}$.

Question 2

Use Warshall's algorithm to compute the transitive closure of $R \cup S$.

Can anyone help me step by step how to deal with these matrices?
Especially Warshall's algorithm, I really don't understand even though studying my lecture notes.

I really need the sample solutions for my later exam.

I know that your answer will be help in my exam. Thanks lot.

Best Answer

First of all, you will need to understand how to interpret these matrices. They are Boolean matrices where entry $M_{ij}=1$ if $(i,j)$ is in the relation and $0$ otherwise. As an example, the relation $R$ is \begin{align*} R=\{(0,3),(2,1),(3,2)\}. \end{align*}

Question 1

For the inverse relation, try writing the the pairs contained in $R^{-1}$ and represent this in matrix form. How does this matrix relate to $M_R$?

It's the transposed matrix. We have $(a,b)\in R^{-1}$ if $(b,a)\in R$, which corresponds to transposing the matrix.

The intersection of the relations is defined such that $(a,b)\in R\cap S$ if both $(a,b)\in R$ and $(a,b)\in S$. How does this translate to matrices? Consider the entry $(i,j)$ in $M_{R\cap S}$: When it is $1$, what must be true about the entries $(i,j)$ in $M_R$ and $M_S$?

Both of the entries must be $1$. Thus, $M_{R\cap S}=0_{4\times 4}$ in this example.

To find the composition, it can be shown that this corresponds to the Boolean product of the matrices.

Question 2

First, you have to find the matrix $M_{R\cup S}$. In the case of the intersection the entries of both matrices $M_R$ and $M_S$ had to be $1$, since both relations should contain the pair. In the union, only one of the relations need to contain the pair. How does this translate to the matrices?

Entry $(i,j)$ in $M_{R\cup S}$ is $1$ if entry $(i,j)$ is $1$ in either $M_R$ or $M_S$.

For $n\times n$ matrices, Warshall's algorithm consist of $n$ steps. First, we fix $k=1$ and construct a matrix $W$ where $W_{ij}=M_{ij}\vee (M_{ik}\wedge M_{kj})$ (here $M$ denotes the matrix representation of the relation). Consider a small example:

\begin{align*} M=\left[\begin{array}{c c c} 1 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 0 \end{array}\right] \end{align*}

Fix $k=1$. We can transfer the first row and column immediately. Further, all $1$'s can be transferred. For the remaining entries, we check the corresponding entries in the $k$'th row and column -- here marked with a box. If these are both $1$, we write $1$, otherwise $0$. \begin{align*} W_1=\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 1\\ 1 & ? & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & \boxed{0} & 0\\ 0 & 1 & 1\\ \boxed{1} & \mathbf{0} & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & 0 & \boxed{0}\\ 0 & 1 & 1\\ \boxed{1} & 0 & \mathbf{0} \end{array}\right]. \end{align*}

Next, fix $k=2$ and repeat the process on $W_1$. Again transfer the $k$'th row and column and any entries containing $1$. \begin{align*} W_2=\left[\begin{array}{ccc} 1 & 0 & ?\\ 0 & 1 & 1\\ 1 & 0 & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & \boxed{0} & \mathbf{0}\\ 0 & 1 & \boxed{1}\\ 1 & 0 & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & \boxed{1}\\ 1 & \boxed{0} & \mathbf{0} \end{array}\right]. \end{align*}

Finally, fix $k=3$ to find the last entries. \begin{align*} W_3=\left[\begin{array}{ccc} 1 & ? & 0\\ ? & 1 & 1\\ 1 & 0 & 0 \end{array}\right]=\left[\begin{array}{ccc} 1 & \mathbf{0} & \boxed{0}\\ ? & 1 & 1\\ 1 & \boxed{0} & 0 \end{array}\right]=\left[\begin{array}{ccc} 1 & 0 & 0\\ \mathbf{1} & 1 & \boxed{1}\\ \boxed{1} & 0 & 0 \end{array}\right]. \end{align*}

This final matrix $W_3$ is the transitive closure.

Related Question