Matrix Representations of Various Types of Relations

On The Matrix Representation of a Relation page we saw that if $X$ is a finite $n$-element set and $R$ is a relation on $X$ then the matrix representation of $R$ on $X$ is defined to be the $n \times n$ matrix $M = (m_{ij})$ whose entries are defined by:

(1)

\begin{align} \quad m_{ij} = \left\{\begin{matrix} 1 & \mathrm{if} \: x_i \: R \: x_j \\ 0 & \mathrm{if} \: x_i \: \not R \: x_j \end{matrix}\right. \end{align}

We will now look at how various types of relations (reflexive/irreflexive, symmetric/antisymmetric, transitive) affect the matrix $M$.

Theorem 1: Let $X = \{x_1, x_2, .., x_n \}$ be a finite $n$-element set. If $R$ is a relation on $X$ then $R$ is reflexive if and only if the main diagonal of the matrix represent $M = (m_{ij})$ of $R$ on $X$ consists of all $1$'s. Furthermore, $R$ is irreflexive if and only if the main diagonal of the matrix $M = (m_{ij})$ of $R$ on $X$ consists of all $0$'s.

• Proof: We begin by proving the first statement in Theorem 1.

• $\Rightarrow$ Suppose that $R$ is reflexive. Then for all $i \in \{ 1, 2, ..., n \}$ we have that $x_i \: R \: x_i$. Since $x_i \: R \: x_i$ we have that $m_{ii} = 1$ for all $i$ and so the main diagonal of the matrix representation $M$ of $R$ on $X$ consists of all $1$'s.

• $\Leftarrow$ Suppose that the main diagonal of the matrix representation $M$ of $R$ on $X$ consists of all $1$'s. Then $m_{ii} = 1$ for all $i \in \{1, 2, ..., n \}$. Therefore $x_i \: R \: x_i$ for all $i$ so $R$ is reflexive on $X$.

• We will now prove the second statement in Theorem 1.

• $\Rightarrow$ Suppose that $R$ is irreflexive. Then for all $i \in \{1, 2, ..., n \}$ we have that $x_i \: \not R \: x_i$. Since $x_i \: \not R \: x_i$ we have that $m_{ii} = 0$ for all $i$ and so the main diagonal of the matrix representation $M$ of $R$ on $X$ consists of all $0$'s.

• $\Leftarrow$ Suppose that the main diagonal of the matrix representation $M$ of $R$ on $X$ consists of all $0$'s. Then $m_{ii} = 0$ for all $i \in \{1, 2, ..., n \}$. Therefore $x_i \: \not R \: x_i$ for all $i$ so $R$ is irreflexive on $X$. $\blacksquare$

Theorem 2: Let $X = \{ x_1, x_2, ..., x_n \}$ be a finite $n$-element set. If $R$ is a relation on $X$ then $R$ is symmetric if and only if the matrix representation $M = (m_{ij})$ of $R$ on $X$ is symmetric. Furthermore, $R$ is antisymmetric if and only if the sum of two symmetric entries that do not lie on the main diagonal do not sum to $2$, that is for $i, j \in \{1, 2, ..., n \}$ where $i \neq j$ we have that $m_{ij} + m_{ji} \neq 2$.

• Proof: We begin by proving the first statement in Theorem 2.

• $\Rightarrow$ Suppose that $R$ is symmetric. Then for all $i, j \in \{1, 2, ..., n \}$ where $x_i \: R \: x_j$ we have that $x_j \: R \: x_i$. Therefore $m_{ij} = 1 = m_{ji}$ for all $i$ and $j$ in this case. Similarly, for all $i, j$ such that $x_i \: \not R \: x_j$ we have that $x_j \: \not R \: x_i$. Therefore $m_{ij} = 0 = m_{ji}$ for all $i$ and $j$ in this case. Together these cases are exhaustive and in general $m_{ij} = m_{ji}$ for all $i, j \in \{1, 2, ..., n \}$ so the matrix representation $M$ of $R$ on $X$ is symmetric.

• $\Leftarrow$ Suppose that the matrix representation $M$ of $R$ on $X$ is symmetric. Then $m_{ij} = m_{ji}$ for all $i, j \in \{1, 2, ..., n \}$. Therefore $x_i \: R \: x_j$ implies $x_j \: R \: x_i$ and $x_i \: \not R \: x_j$ implies $x_j \: \not R \: x_i$ for all $i, j$. Therefore $R$ is symmetric.

• We will now prove the second statement in Theorem 2.

• $\Rightarrow$ Suppose that $R$ is antisymmetric. Then for all $i, j \in \{1, 2, ..., n \}$ where $i \neq j$ we have that if $x_i \: R \: x_j$ then $x_j \: \not R \: x_i$. Therefore if $m_{ij} = 1$ then $m_{ji} = 0$. Thus, $m_{ij} + m_{ji} \neq 2$ for all $i, j$ where $i \neq j$.

• $\Leftarrow$ Suppose that for all $i, j \in \{1, 2, ..., n \}$ where $i \neq j$ we have that $m_{ij} + m_{ji} \neq 2$. Therefore $m_{ij} + m_{ji} = 0$ or $m_{ij} + m_{ji} = 1$. If $m_{ij} + m_{ji} = 0$ then $m_{ij} = m_{ji} = 0$ so $x_i \: \not R \: x_j$ and $x_j \: \not R \: x_i$ which is fine. If $m_{ij} + m_{ji} = 1$ then either $m_{ij} = 1$ and $m_{ji} = 0$ or $m_{ij} = 0$ and $m_{ji} = 1$. In either case we have that $x_i \: R \: x_j$ implies that $x_j \: \not R \: x_i$ so $R$ is antisymmetric. $\blacksquare$