Adjacency Matrices (Representing Binary Relations by Matrices)
A rectangular array of real numbers
\[
M=\begin{pmatrix}
m_{11} & m_{12} & \cdots & m_{1n}\\
m_{21} & m_{22} & \cdots & m_{2n}\\
\cdots & \cdots & \cdots & \cdots\\
m_{m1} & m_{m2} & \cdots & m_{mn}\end{pmatrix}
\]is called a matrix over \(\mathbb{R} \). Each real number \[
m_{ij}\quad\left( i=1,\cdots,m;\ j=1,\cdots,n\right)
\]that constitutes the matrix \(M\) is called the \(ij\)-entry of the matrix. It is the real number appearing in row \(i\) and column \(j\) of \(M\). If \(M\) has \(m\) rows and \(n\) columns, it is called an \(m\times n\) matrix.
A matrix with the same number of rows and columns, that is, an \(n\times n\) matrix
\[
M=\begin{pmatrix}
m_{11} & m_{12} & \cdots & m_{1n}\\
m_{21} & m_{22} & \cdots & m_{2n}\\
\cdots & \cdots & \cdots & \cdots\\
m_{n1} & m_{n2} & \cdots & m_{nn}\end{pmatrix}
\]is called a square matrix of order \(n\). Among the entries of a square matrix, the entries whose row and column indices are the same, \[
m_{11},m_{22},\cdots,m_{nn},
\]are called the diagonal entries of \(M\).
Suppose that a binary relation
\[
R\subset A\times A
\]is defined on a set \(A\). Suppose further that \(A\) is finite, and write its elements as \[
A=\left\{ a_{1},a_{2},\cdots,a_{n}\right\} .
\]For arbitrary \(i,j\in\left\{ 1,\cdots,n\right\} \), define an \(n\times n\) square matrix whose \(ij\)-entry is \[
m_{ij}=\left\{
\begin{array}
[c]{cc}1 & \left( if\ \left( a_{i},a_{j}\right) \in R\right) \\
0 & \left( if\ \left( a_{i},a_{j}\right) \not \in R\right)
\end{array}
\right.
\]and denote it by
\[
M_{R}.
\]This matrix is called the adjacency matrix of the binary relation \(R\).
A=\left\{ 1,2,3,4\right\}
\]is given by
\[
R=\left\{ \left( 1,1\right) ,\left( 1,2\right) ,\left( 2,3\right)
,\left( 3,3\right) \right\} .
\]Number the elements of \(A\) as \begin{align*}
a_{1} & =1\\
a_{2} & =2\\
a_{3} & =3\\
a_{4} & =4.
\end{align*}By definition of \(R\), \begin{align*}
\left( 1,1\right) & \in R\\
\left( 1,2\right) & \in R\\
\left( 2,3\right) & \in R\\
\left( 3,3\right) & \in R,
\end{align*}that is,
\begin{align*}
\left( a_{1},a_{1}\right) & \in R\\
\left( a_{1},a_{2}\right) & \in R\\
\left( a_{2},a_{3}\right) & \in R\\
\left( a_{3},a_{3}\right) & \in R.
\end{align*}Therefore, the entries of the adjacency matrix \(M_{R}\) satisfy \begin{align*}
m_{11} & =1\\
m_{12} & =1\\
m_{23} & =1\\
m_{33} & =1,
\end{align*}while every other entry \(m_{ij}\) satisfies \[
m_{ij}=0.
\]Hence,
\[
M_{R}=\begin{pmatrix}
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 0
\end{pmatrix}
.
\]
A=\left\{ 2,5,6\right\}
\]is given by
\[
R=\left\{ \left( 2,2\right) ,\left( 2,5\right) ,\left( 5,6\right)
,\left( 6,6\right) \right\} .
\]Number the elements of \(A\) as \begin{align*}
a_{1} & =2\\
a_{2} & =5\\
a_{3} & =6.
\end{align*}By definition of \(R\), \begin{align*}
\left( a_{1},a_{1}\right) & \in R\\
\left( a_{1},a_{2}\right) & \in R\\
\left( a_{2},a_{3}\right) & \in R\\
\left( a_{3},a_{3}\right) & \in R,
\end{align*}whereas, for every other pair \(i,j\), \[
\left( a_{i},a_{j}\right) \not \in R.
\]Therefore, the adjacency matrix of \(R\) is \[
M_{R}=\begin{pmatrix}
1 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 1
\end{pmatrix}
.
\]
A=\left\{ a,b,c\right\}
\]is given by
\[
R=\left\{ \left( a,a\right) ,\left( a,b\right) ,\left( b,c\right)
,\left( c,c\right) \right\} .
\]Number the elements of \(A\) as \begin{align*}
a_{1} & =a\\
a_{2} & =b\\
a_{3} & =c.
\end{align*}By definition of \(R\), \begin{align*}
\left( a_{1},a_{1}\right) & \in R\\
\left( a_{1},a_{2}\right) & \in R\\
\left( a_{2},a_{3}\right) & \in R\\
\left( a_{3},a_{3}\right) & \in R,
\end{align*}whereas, for every other pair \(i,j\), \[
\left( a_{i},a_{j}\right) \not \in R.
\]Therefore, the adjacency matrix of \(R\) is \[
M_{R}=\begin{pmatrix}
1 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 1
\end{pmatrix}
.
\]
Adjacency Matrices of Order Relations
A binary relation \(\leq\) on a set \(A\) is a partial order if it satisfies reflexivity, antisymmetry, and transitivity, that is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] .
\end{align*}If, in addition to these properties, \(\leq\) satisfies completeness, \[
\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right) ,
\]then \(\leq\) is called a total order. The discussion below applies to both partial orders and total orders. We therefore use the term order to refer collectively to partial orders and total orders. If an order \(\leq\) is defined on a set \(A\), the pair \[
\left( A,\leq\right)
\]is called an ordered set. When it is clear from context that the order \(\leq\) is defined, we may simply write the ordered set as
\[
A.
\]
Since an order relation \(\leq\) is also a binary relation, if the set \(A\) on which it is defined is finite, the order relation \(\leq\) can be represented by its adjacency matrix \(M_{\leq}\).
A=\left\{ 1,2,3,4\right\} ,
\]then
\[
\left( A,\leq\right)
\]is a totally ordered set. By definition of the usual order,
\begin{align*}
1 & \leq1,\ 1\leq2,\ 1\leq3,\ 1\leq4\\
2 & \leq2,\ 2\leq3,\ 2\leq4\\
3 & \leq3,\ 3\leq4\\
4 & \leq4
\end{align*}hold. Therefore, if we number the elements of \(A\) by \begin{align*}
a_{1} & =1\\
a_{2} & =2\\
a_{3} & =3\\
a_{4} & =4,
\end{align*}the adjacency matrix is
\[
M_{\leq}=\begin{pmatrix}
1 & 1 & 1 & 1\\
0 & 1 & 1 & 1\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 1
\end{pmatrix}
.
\]
What properties does the adjacency matrix of an order relation have?
A=\left\{ a_{1},a_{2},\cdots,a_{n}\right\} .
\]The adjacency matrix \(M_{\leq}\) of \(\leq\) is a square matrix of order \(n\). If \(\leq\) is a partial order, then it satisfies \begin{align*}
& \left( a\right) \ \forall i\in\left\{ 1,\cdots,n\right\} :m_{ii}=1\\
& \left( b\right) \ \forall i,j\in\left\{ 1,\cdots,n\right\} :\left[
i\not =j\Rightarrow\left( m_{ij}=0\vee m_{ij}=0\right) \right] \\
& \left( c\right) \ \forall i,j,k\in\left\{ 1,\cdots,n\right\} :\left[
\left( m_{ij}=1\wedge m_{jk}=1\right) \Rightarrow m_{ik}=1\right] .
\end{align*}If \(\leq\) is a total order, then in addition to these properties, \[
\left( d\right) \ \forall i,j\in\left\{ 1,\cdots,n\right\} :\left(
m_{ij}=1\vee m_{ji}=1\right)
\]holds.
Condition \(\left( a\right) \) means that every diagonal entry of the adjacency matrix \(M_{\leq}\) of the binary relation \(\leq\) is equal to \(1\). Condition \(\left( b\right) \) means that at least one of two entries in symmetric positions of the adjacency matrix \(M_{\leq}\) is equal to \(0\). Moreover, condition \(\left( b\right) \) is equivalent to \[
\forall i,j\in\left\{ 1,\cdots,n\right\} :\left( i\not =j\Rightarrow m_{ij}\cdot m_{ji}=0\right) .
\]In other words, the product of two entries in symmetric positions of the adjacency matrix \(M_{\leq}\) is \(0\).
A=\left\{ 1,2,3,4\right\} ,
\]then
\[
\left( A,\leq\right)
\]is a totally ordered set. As shown above, the adjacency matrix is
\[
M_{\leq}=\begin{pmatrix}
1 & 1 & 1 & 1\\
0 & 1 & 1 & 1\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 1
\end{pmatrix}
.
\]We verify that this adjacency matrix satisfies conditions \(\left( a\right) ,\left( b\right) ,\left( c\right) ,\left( d\right) \) in the preceding proposition. First, \[
m_{11}=m_{22}=m_{33}=m_{44}=1
\]holds, so condition \(\left( a\right) \) is satisfied. Also, \begin{align*}
m_{12}\cdot m_{21} & =1\cdot0=0\\
m_{13}\cdot m_{31} & =1\cdot0=0\\
m_{14}\cdot m_{41} & =1\cdot0=0\\
m_{23}\cdot m_{32} & =1\cdot0=0\\
m_{24}\cdot m_{42} & =1\cdot0=0\\
m_{34}\cdot m_{43} & =1\cdot0=0
\end{align*}holds, so condition \(\left( b\right) \) is satisfied. Also, \begin{align*}
m_{12} & =1\wedge m_{23}=1\Rightarrow m_{13}=1\\
m_{12} & =1\wedge m_{24}=1\Rightarrow m_{14}=1\\
m_{13} & =1\wedge m_{34}=1\Rightarrow m_{14}=1\\
m_{23} & =1\wedge m_{34}=1\Rightarrow m_{24}=1
\end{align*}holds, so condition \(\left( c\right) \) is satisfied. Finally, \begin{align*}
m_{12} & =1\\
m_{13} & =1\\
m_{14} & =1\\
m_{23} & =1\\
m_{24} & =1\\
m_{34} & =1
\end{align*}holds, so condition \(\left( d\right) \) is satisfied. These results are consistent with the preceding proposition.
Exercises
\[
A=\left\{ 1,2,3,4,5\right\}
\]is given by
\[
R=\left\{
\begin{array}
[c]{l}\left( 1,1\right) ,\left( 1,3\right) ,\left( 1,4\right) ,\left(
1,5\right) ,\\
\left( 2,2\right) ,\left( 2,3\right) ,\left( 2,4\right) ,\left(
2,5\right) ,\\
\left( 3,3\right) ,\left( 3,4\right) ,\left( 3,5\right) ,\\
\left( 4,4\right) ,\\
\left( 5,5\right)
\end{array}
\right\} .
\]Show that \(R\) is a partial order and determine its adjacency matrix \(M_{R}\).
\[
A=\left\{ 1,2,3,4,6,12,24\right\} .
\]Then
\[
\left( A,|\right)
\]is an ordered set. Determine its adjacency matrix \(M_{|}\).
A=\left\{ a,b,c,d\right\}
\]is
\[
M_{R}=\begin{pmatrix}
1 & 1 & 1 & 0\\
0 & 1 & 1 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}
.
\]Assume that the elements of \(A\) are numbered as \[
a_{1}=a,\quad a_{2}=b,\quad a_{3}=c,\quad a_{4}=d.
\]Express the binary relation \(R\) as a set of ordered pairs, and determine whether \(R\) is a partial order and whether it is a total order.
\[
U=\left\{ 1,2\right\}
\]and consider the inclusion relation \(\subset\) on the power set \[
2^{U}=\left\{ \phi,\left\{ 1\right\} ,\left\{ 2\right\} ,\left\{
1,2\right\} \right\} .
\]Number the elements as
\begin{align*}
a_{1} & =\phi\\
a_{2} & =\left\{ 1\right\} \\
a_{3} & =\left\{ 2\right\} \\
a_{4} & =\left\{ 1,2\right\} .
\end{align*}Find the adjacency matrix of \(\subset\), and determine whether \(\subset\) is a total order.
\[
A=\left\{ a_{1},a_{2},a_{3},a_{4}\right\}
\]and suppose that the total order \(\leq\) on \(A\) satisfies \[
a_{1}<a_{2}<a_{3}<a_{4}.
\]Find the adjacency matrix of \(\leq\). Also verify reflexivity, antisymmetry, and completeness from the form of the matrix.
\[
A=\left\{ a_{1},a_{2},\cdots,a_{n}\right\}
\]be a finite set, and let the adjacency matrix of a binary relation \(R\) on \(A\) be
\[
M_{R}=\left( m_{ij}\right) .
\]Show that the following three conditions are necessary and sufficient for \(R\) to be a partial order:
\begin{align*}
& \left( a\right) \ \forall i\in\left\{ 1,2,\cdots,n\right\} :m_{ii}=1\\
& \left( b\right) \ \forall i,j\in\left\{ 1,2,\cdots,n\right\} :\left[
i\not =j\Rightarrow\left( m_{ij}=0\vee m_{ji}=0\right) \right] \\
& \left( c\right) \ \forall i,j,k\in\left\{ 1,2,\cdots,n\right\} :\left[
\left( m_{ij}=1\wedge m_{jk}=1\right) \Rightarrow m_{ik}=1\right] .
\end{align*}
M=\left( m_{ij}\right) ,\quad N=\left( n_{ij}\right)
\]whose entries are \(0\) or \(1\), define their Boolean product \(M\odot N\) by \[
\left( M\odot N\right) _{ik}=\bigvee_{j=1}^{n}\left( m_{ij}\wedge n_{jk}\right) .
\]Let \(M_{R}\) be the adjacency matrix of a binary relation \(R\) on a finite set \(A\). Show that \(R\) is transitive if and only if \[
M_{R}\odot M_{R}\leq M_{R}\]holds, where the matrix inequality \(\leq\) is interpreted componentwise.
