Matrix of a Relation

Topics: Discrete Mathematics

---

Let $R:A\to B$ be a relation, with $A=\{a_1,\dots ,a_n\}$ and $B=\{b_1,\dots ,b_m\}$.

We define the relation matrix $M_R\in \{0,1{\}}^{n\times m}$ (a boolean matrix) with:

$$M_R=(a_{ij})=\{\begin{array}{l}1,\text{ if }{a}_{i}R{b}_j\\ 0,\text{if }{a}_i\text{centernot}R{b}_j\end{array}$$

We can use this matrix to easily determine the properties of the relation.

Example

Let $R=\{(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)\}$.

The matrix for $R$ is:

$$\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1\end{array}\right)$$

Notice that we can tell that $R$ is reflexive since its matrix has $1$s in its diagonal.