Question

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.

Answer 1

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.