Solution to Let S be a finite set, with |S|=n. If the bit matrix MR representing R … - Sikademy
Author Image

Archangel Macsika

Let S be a finite set, with |S|=n. If the bit matrix MR representing R contains exactly r entries that are 0, how many entries of MRbar are 0? Note: "MRbar" is supposed to be just like MR, which you should know has R as a subscript, but with a bar over R. Just in case that got confusing.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

If R  is a binary relation on a set S, then R  can be represented by the logical matrix M_R  whose row and column indices index the elements of S, such that the entries of M_R  are defined by:

{\displaystyle m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\not \in R\end{cases}}}

Let |S|=n. If R is a binary relation on a set S , then \bar{R}=\{(x,y)\in S\times S\ |\ (x,y)\notin R\}.

It follows from defenition of \bar{R} that {\displaystyle \bar{m}_{i,j}={\begin{cases}0&(x_{i},y_{j})\in R\\1&(x_{i},y_{j})\not \in R\end{cases}}} .  If the bit matrix M_R representing R contains exactly r entries that are 0, then |R|=r. Since |\bar{R}|=|(S\times S)\setminus R|=n^2-r, we conclude that the bit matrix M_{\bar{R}} representing \bar{R} contains exactly n^2-r entries that are 0.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3484-qpid-2183