0
$\begingroup$

I am currently reading about portraying relations on a set as matrices. Firstly, I am not sure how to determine the dimensions of the matrix when given set(s). Secondly, when I go down the columns, which part of the order-pair is changing? For instance, if I was looking at the first column, would I look at the order pairs as (1, a) or (a, 1), where a number of elements in the column? The same goes for the rows.

Thank you!

  • 0
    You need to give a little more info...2012-11-03

1 Answers 1

1

Suppose that $R$ is a relation on a set $A$ that has $n$ elements. Then $M_R$, the matrix of $R$, will be an $n\times n$ matrix, with one row and one column for each element of $A$. The matrix will depend on how you order the elements of $A$. Suppose that $A=\{a_1,a_2,\dots,a_n\}$; then for $k=1,\dots,n$, both row $k$ and column $k$ of $A$ will correspond to $a_k$, though in different ways.

Let $m_{ij}$ be the element in row $i$, column $j$ of $M_R$; the usual convention is that this entry corresponds to the ordered pair $\langle a_i,a_j\rangle\in A\times A$. Specifically,

$m_{ij}=\begin{cases} 1,&\text{if }\langle a_i,a_j\rangle\in R\\ 0,&\text{if }\langle a_i,a_j\rangle\notin R\;. \end{cases}$

Let’s say temporarily that if $\langle a_i,a_j\rangle\in R$, then $a_i$ is related to $a_j$, and $a_j$ is related from $a_i$. With this terminology, row $i$ of the matrix contains $1$’s in the columns of elements related from $a_i$, and column $j$ of the matrix contains $1$’s in the rows of elements related to $a_j$.

If you’ve already represented relations by digraphs, this may be helpful: $M_R$ is the adjacency matrix of the digraph associated with $R$. That is, $M_R$ has a $1$ in row $i$, column $j$ exactly when the digraph has an edge from vertex $a_i$ to vertex $a_j$, and otherwise it has a $0$.