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 reflexive closure of \(R\)is \({{\bf{M}}_R} \vee {{\bf{I}}_n}\).

Short answer

The matrix representing the reflexive closure of \(R\) is \({{\bf{M}}_R} \vee {{\bf{I}}_n}\).

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

The reflexive closure of\(R\)is the relation that contains all ordered pairs of\(R\)and to which all ordered pairs of the form\((a,a) \in R(a \in A)\)were added (when they were not present yet).

\(R \cup \Delta = R \cup \{ (a,a)\mid a \in A\} \).

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

Determine the Reflexive closure

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

The matrix that represents the reflexive closure of\(R\)is then the matrix that represents the relation\(R \cup \Delta \).

\({{\bf{M}}_{R \cup \Delta }} = {{\bf{M}}_R} \vee {{\bf{M}}_\Delta }\)

We then note that the matrix is\({{\bf{M}}_R} \vee {{\bf{I}}_n}\)if\({{\bf{M}}_\Delta } = {{\bf{I}}_n}\).

Note:\(n\)represents the number of elements in the set.\(A\).

Let\({{\bf{M}}_\Delta } = \left| {{m_{ij}}} \right|\)

\(\begin{aligned}{m_{ij}} &= \left\{ {\begin{aligned}{*{20}{l}}1&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \in \Delta }\\0&{{\rm{ if }}\left( {{a_i},{b_j}} \right) \notin \Delta }\end{aligned}} \right.\\ &= \left\{ {\begin{aligned}{*{20}{l}}1&{{\rm{ if }}i = j}\\0&{{\rm{ if }}i \ne j}\end{aligned}} \right.\end{aligned}\)

We then note that the matrix\({{\bf{M}}_\Delta } = \left[ {{m_{ij}}} \right]\)only contains l's on the main diagonal and thus the matrix is the identity matrix.

\(\begin{aligned}{{\bf{M}}_\Delta } &= {{\bf{I}}_n}\\{{\bf{M}}_{R \cup \Delta }} &= {{\bf{M}}_R} \vee {{\bf{M}}_\Delta }\\ &= {{\bf{M}}_R} \vee {{\bf{I}}_n}\end{aligned}\)

Thus, the matrix representing the reflexive closure of \(R\) is \({{\bf{M}}_R} \vee {{\bf{I}}_n}\).