2
$\begingroup$

I was studying but realized that I am having trouble grasping the representations of relations using Zero One Matrices. For example if I have a set A = {1,2,3} and a relation R = {(1,1), (1,2), (2,3), (3,1)}.

What is the resulting Zero One Matrix representation? How exactly do I come by the result for each position of the matrix? How to tell if it is reflexive, transitive, antisymmetric or symmetric?

$\endgroup$
2
$\begingroup$

The resulting zero-one representation is the $|A|\times |A|$ matrix $M$ with $M_{ij} = 1$ if $(i,j) \in R$, and $M_{ij} = 0$ if $(i,j) \notin R$. In our case, the matrix is $$ M = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}. $$ Take it as an exercise to prove the following properties:

  1. $R$ is reflexive iff the diagonal of $M$ is all 1s.
  2. $R$ is symmetric iff $M$ is symmetric.
  3. $R$ is antisymmetric iff the off-diagonal entries of $M+M^T$ are 0/1 (but not 2).
  4. $R$ is transitive iff the support of $M^2$ is a subset of the support of $M$, where the support is the set of non-zero entries.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.