Question

Suppose that the relation \(R\) on the finite set \(A\) is represented by the matrix \({{\bf{M}}_R}\). Show that the matrix that represents the symmetric closure of \(R\) is \({{\bf{M}}_R} \vee {\bf{M}}_R^t\).

Short answer

The matrix representing the symmetric closure of \(R\) is \({{\bf{M}}_R} \vee {\bf{M}}_R^t\).

Step-by-step solution

Given

The relation \(R\) on the finite set \(A\) is represented by the matrix \({{\bf{M}}_R}\).

Concept of Reflexive Closure and Symmetric Closure

The symmetric closure of\(R\)is the union of the relation\(R\)with its inverse relation\({R^{ - 1}}\).

The inverse relation\({R^{ - 1}}\)is the set\(\{ (b,a)\mid (a,b) \in R\} \).

A relation\(R\)can be represented by the matrix\({{\bf{M}}_R} = \left( {{m_{ij}}} \right)\)

\({m_{ij}} = \left\{ {\begin{array}{*{20}{l}}1&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \in R}\\0&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \notin R}\end{array}} \right.\).

Statement

Let\({{\bf{M}}_R}\)be the matrix that represents the relation\(R\).

The matrix that represents the symmetric closure of\(R\)is then the matrix that represents the relation\(R \cup {R^{ - 1}}\).

\({{\bf{M}}_{R \cup {R^{ - 1}}}} = {{\bf{M}}_R} \vee {{\bf{M}}_{{R^{ - 1}}}}\quad \)

We then note that the matrix is\({{\bf{M}}_R} \vee {\bf{M}}_R^t\)if\({{\bf{M}}_{{R^{ - 1}}}} = {\bf{M}}_R^t\). Let\({{\bf{M}}_{{R^{ - 1}}}} = \left( {{m_{ij}}} \right)\)and\({{\bf{M}}_R} = \left( {{n_{ij}}} \right)\)

\(\begin{array}{c}{m_{ij}} = \left\{ {\begin{array}{*{20}{l}}1&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \in {R^{ - 1}}}\\0&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \notin {R^{ - 1}}}\end{array}} \right.\\ = \left\{ {\begin{array}{*{20}{l}}1&{{\rm{ if }}\left( {{b_i},{a_j}} \right) \in R}\\0&{{\rm{ if }}\left( {{b_i},{a_j}} \right) \notin R}\end{array}} \right.\\ = {n_{ji}}\end{array}\)

We then note that\({{\bf{M}}_{{R^{ - 1}}}} = \left( {{m_{ij}}} \right) = \left( {{n_{ij}}} \right) = {\bf{M}}_R^t\)

\(\begin{array}{c}{{\bf{M}}_{R \cup {R^{ - 1}}}} = {{\bf{M}}_R} \vee {{\bf{M}}_{{R^{ - 1}}}}\\ = {{\bf{M}}_R} \vee \left( {{m_{ij}}} \right)\\ = {{\bf{M}}_R} \vee \left( {{n_{ji}}} \right)\\ = {{\bf{M}}_R} \vee {\bf{M}}_R^t\end{array}\).

Thus, the matrix representing the symmetric closure of .\(R\). is \({{\bf{M}}_R} \vee {\bf{M}}_R^t\).