Question

Let R be a symmetric relation on a finite set A, and let MR be the bit matrix representing R. Is MR necessarily a symmetric matrix? Why or why not?

Answer 1

If $R$ is a binary relation on a finite set $A$ , that is $R ⊆ A×A$, then $R$ can be represented by the logical matrix $M_R$ whose row and column indices index the elements of $A$ 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}}}$

Since $R$ be a symmetric relation on a finite set $A$, $(x,y)\in R$ implies $(y,x)\in R$, and therefore $m_{i,j}=1$ if and only if $m_{j,i}=1$. It follows that $M_R$ is necessarily a symmetric matrix.