What is the matrix and directed graph corresponding to the relation $\{(1, 1), (2, 2), (3, 3), (4, 4), (4, 3), (4, 1), (3, 2), (3, 1)\}$?

Question

Let $R$ be a relation on set $A = \{1, 2, 3, 4\}$ defined by $$R = \{(1, 1), (2, 2), (3, 3), (4, 4), (4, 3), (4, 1), (3, 2), (3, 1)\}.$$ Find the matrix and directed graph of relation $R$.

Answer 1

First and foremost, please note the corrections given by my colleagues. We discuss questions here...not just doing assignment for you.

A matrix of the form $C_{ij}$ below whose entries are either 0 or 1 is called the adjacency matrix of the directed graph of relation $R$.

$$B_{ij}=\begin{pmatrix} & 1 & 2 & 3 & 4 \\ \hline 1& - & - & - & - \\ 2& - & - & - & - \\ 3& - & - & - & - \\ 4& - & - & - & - \end{pmatrix}$$

In order to obtain matrix $C_{ij}$, you only fill the missing entries of matrix $B_{ij}$ with 1 or 0 according as whether there is a relation between the elements in the horizontal and vertical components or not.

For example, because $(1,1),(2,2),(4,1)\in R$, we filled their corresponding entries with 1, and since $(2,1),(3,4)\notin R$, we filled the corresponding entries with 0.

$$C_{ij}=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{pmatrix}.$$

Remarks: The word directed simply tells you that edge (i,j) is not the same as edge (j,i) while for an undirected graph, edge (i,j) is the same as edge (j,i).

Answer 2

Here's an illustrative example to get you going. We take the relation $$R=\{\color{red}{(1,2)},\color{blue}{(2,1)},\color{green}{(3,3)}\}$$ on the set $A=\{1,2,3\}$.

For the matrix representation, we write $1$ in cell $(i,j)$ whenever $(i,j) \in R$, and $0$ otherwise. In this case: $$ \begin{bmatrix} 0 & \color{red}{1} & 0 \\ \color{blue}{1} & 0 & 0 \\ 0 & 0 & \color{green}{1} \\ \end{bmatrix}. $$

In the directed graph representation, we have the vertex set $A$ and draw an edge $i \rightarrow j$ whenever $(i,j) \in R$, and no edge otherwise. In this example: