隣接行列（行列を用いた二項関係の表現）
実数を長方形に配列したもの\begin{equation*}
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}\end{equation*}を\(\mathbb{R} \)上の行列と呼びます。行列\(M\)を構成する個々の実数\begin{equation*} m_{ij}\quad \left( i=1,\cdots ,m;\ j=1,\cdots ,n\right)
\end{equation*}を行列の\(ij\)成分と呼びます。これは行列\(M\)の第\(i\)行、第\(j\)列に現れる実数です。行列\(M\)が\(m \)個の行と\(n\)個の列を持つ場合、\(m\times n\)行列と呼びます。
行の個数と列の個数が一致する行列、すなわち\(n\times n\)行列\begin{equation*} 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}\end{equation*}を次数\(n\)の正方行列と呼びます。正方行列の成分の中でも、行番号と列番号が一致する成分\begin{equation*} m_{11},m_{22},\cdots ,m_{nn}
\end{equation*}を\(M\)の対角成分と呼びます。
集合\(A\)上の二項関係\begin{equation*} R\subset A\times A
\end{equation*}が与えられた状況を想定します。加えて、\(A\)は有限集合であるものとし、その成分を、\begin{equation*} A=\left\{ a_{1},a_{2},\cdots ,a_{n}\right\}
\end{equation*}と表記します。その上で、任意の\(i,j\in \left\{ 1,\cdots ,n\right\} \)について、\begin{equation*} m_{ij}=\left\{
\begin{array}{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.
\end{equation*}を\(ij\)成分として持つ次数\(n\)の正方行列を定義し、これを、\begin{equation*} M_{R}
\end{equation*}で表記します。これを二項関係\(R\)に関する隣接行列（adjacency matrix）と呼びます。
A=\left\{ 1,2,3,4\right\}
\end{equation*}上の二項関係\(R\)が、\begin{equation*} R=\left\{ \left( 1,1\right) ,\left( 1,2\right) ,\left( 2,3\right) ,\left(
3,3\right) \right\}
\end{equation*}で与えられているものとします。集合\(A\)の要素に対して、\begin{eqnarray*} a_{1} &=&1 \\
a_{2} &=&2 \\
a_{3} &=&3 \\
a_{4} &=&4
\end{eqnarray*}と付番します。\(R\)の定義より、\begin{eqnarray*} \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{eqnarray*}すなわち、\begin{eqnarray*}
\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{eqnarray*}であるため、隣接行列\(M_{R}\)の成分について、\begin{eqnarray*} m_{11} &=&1 \\
m_{12} &=&1 \\
m_{23} &=&1 \\
m_{33} &=&1
\end{eqnarray*}が成り立ち、それ以外の任意の成分\(m_{ij}\)について、\begin{equation*} m_{ij}=0
\end{equation*}が成り立ちます。したがって、\begin{equation*}
M_{R}=\begin{pmatrix}
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0\end{pmatrix}\end{equation*}となります。
A=\left\{ 2,5,6\right\}
\end{equation*}上の二項関係\(R\)が、\begin{equation*} R=\left\{ \left( 2,2\right) ,\left( 2,5\right) ,\left( 5,6\right) ,\left(
6,6\right) \right\}
\end{equation*}で与えられているものとします。集合\(A\)の要素に対して、\begin{eqnarray*} a_{1} &=&2 \\
a_{2} &=&5 \\
a_{3} &=&6
\end{eqnarray*}と付番します。\(R\)の定義より、\begin{eqnarray*} \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{eqnarray*}である一方で、他の任意の\(i,j\)について、\begin{equation*} \left( a_{i},a_{j}\right) \not\in R
\end{equation*}であるため、\(R\)の隣接行列は、\begin{equation*} M_{R}=\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1\end{pmatrix}\end{equation*}となります。
A=\left\{ a,b,c\right\}
\end{equation*}上の二項関係\(R\)が、\begin{equation*} R=\left\{ \left( a,a\right) ,\left( a,b\right) ,\left( b,c\right) ,\left(
c,c\right) \right\}
\end{equation*}で与えられているものとします。集合\(A\)の要素に対して、\begin{eqnarray*} a_{1} &=&a \\
a_{2} &=&b \\
a_{3} &=&c
\end{eqnarray*}と付番します。\(R\)の定義より、\begin{eqnarray*} \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{eqnarray*}である一方で、他の任意の\(i,j\)について、\begin{equation*} \left( a_{i},a_{j}\right) \not\in R
\end{equation*}であるため、\(R\)の隣接行列は、\begin{equation*} M_{R}=\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1\end{pmatrix}\end{equation*}となります。
順序関係の隣接行列
集合\(A\)上に定義された二項関係\(\leq \)が半順序であることとは、\(\leq \)が反射律、反対称律、そして推移律を満たすこと、すなわち、\begin{eqnarray*} &&\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{eqnarray*}が成り立つことを意味します。これらの性質に加えて、完備律\begin{equation*}
\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{equation*}を満たす場合には\(\leq \)を全順序と呼びます。以降の議論は、半順序と全順序の双方を対象としています。そこで、半順序と全順序を総称して順序と呼ぶこととします。集合\(A\)上に順序\(\leq \)が定義されている場合、それらの組\begin{equation*} \left( A,\leq \right)
\end{equation*}を順序集合と呼びます。ただし、順序\(\leq \)が定義されていることが文脈から明らかである場合、順序集合を、\begin{equation*} A
\end{equation*}とシンプルに表記できるものと定めます。
順序関係\(\leq \)もまた二項関係であるため、順序関係\(\leq \)が定義された集合\(A\)が有限集合である場合、隣接行列\(M_{\leq }\)を用いて順序関係\(\leq \)を表現できます。
A=\left\{ 1,2,3,4\right\}
\end{equation*}上に通常の大小関係\(\leq \)を導入すれば、\begin{equation*} \left( A,\leq \right)
\end{equation*}は全順序集合になります。大小関係の定義より、\begin{eqnarray*}
1 &\leq &1,\ 1\leq 2,\ 1\leq 3,\ 1\leq 4 \\
2 &\leq &2,\ 2\leq 3,\ 2\leq 4 \\
3 &\leq &3,\ 3\leq 4 \\
4 &\leq &4
\end{eqnarray*}が成り立つため、集合\(A\)の要素に、\begin{eqnarray*} a_{1} &=&1 \\
a_{2} &=&2 \\
a_{3} &=&3 \\
a_{4} &=&4
\end{eqnarray*}と付番した場合、隣接行列は、\begin{equation*}
M_{\leq }=\begin{pmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1\end{pmatrix}\end{equation*}となります。
順序関係の隣接行列はどのような性質を備えているのでしょうか。
\end{equation*}と表記する。\(\leq \)の隣接行列\(M_{\leq }\)は次数\(n\)の正方行列であるとともに、\(\leq \)が半順序である場合には以下の性質\begin{eqnarray*} &&\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{eqnarray*}を満たす。\(\leq \)が全順序である場合には以上の性質に加えて、\begin{equation*} \left( d\right) \ \forall i,j\in \left\{ 1,\cdots ,n\right\} :\left(
m_{ij}=1\vee m_{ji}=1\right)
\end{equation*}を満たす。
条件\(\left( a\right) \)は、二項関係\(\leq \)の隣接行列\(M_{\leq }\)の対角成分はいずれも\(1\)であることを意味します。条件\(\left( b\right) \)は、二項関係の隣接行列\(M_{\leq }\)において対称的な位置にある2つの成分の少なくとも一方が\(0\)であることを意味します。また、条件\(\left( b\right) \)は、\begin{equation*} \forall i,j\in \left\{ 1,\cdots ,n\right\} :\left( i\not=j\Rightarrow
m_{ij}\cdot m_{ji}=0\right)
\end{equation*}と必要十分です。つまり、二項関係の隣接行列\(M_{\leq }\)において対称的な位置にある2つの成分の積は\(0\)になるということです。
A=\left\{ 1,2,3,4\right\}
\end{equation*}上に通常の大小関係\(\leq \)を導入すれば、\begin{equation*} \left( A,\leq \right)
\end{equation*}は全順序集合になります。先に示したように、隣接行列は、\begin{equation*}
M_{\leq }=\begin{pmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1\end{pmatrix}\end{equation*}となります。この隣接行列が先の命題中の条件\(\left( a\right) ,\left( b\right) ,\left( c\right) ,\left( d\right) \)を満たすことを確認します。まず、\begin{equation*} m_{11}=m_{22}=m_{33}=m_{44}=1
\end{equation*}が成り立つため条件\(\left( a\right) \)が満たされます。また、\begin{eqnarray*} m_{12}\cdot m_{21} &=&1\cdot 0=0 \\
m_{13}\cdot m_{31} &=&1\cdot 0=0 \\
m_{14}\cdot m_{41} &=&1\cdot 0=0 \\
m_{23}\cdot m_{32} &=&1\cdot 0=0 \\
m_{24}\cdot m_{42} &=&1\cdot 0=0 \\
m_{34}\cdot m_{43} &=&1\cdot 0=0
\end{eqnarray*}が成り立つため条件\(\left( b\right) \)が満たされます。また、\begin{eqnarray*} 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{eqnarray*}が成り立つため条件\(\left( c\right) \)が満たされます。また、\begin{eqnarray*} m_{12} &=&1 \\
m_{13} &=&1 \\
m_{14} &=&1 \\
m_{23} &=&1 \\
m_{24} &=&1 \\
m_{34} &=&1
\end{eqnarray*}が成り立つため条件\(\left( d\right) \)が満たされます。以上の結果は先の命題の主張と整合的です。
演習問題
A=\left\{ 1,2,3,4,5\right\}
\end{equation*}上に定義された二項関係\(R\)が、\begin{equation*} R=\left\{
\begin{array}{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\}
\end{equation*}で与えられているものとします。\(R\)が半順序であることを示すとともに、隣接行列\(M_{R}\)を明らかにしてください。
A=\left\{ 1,2,3,4,6,12,24\right\}
\end{equation*}上に整除関係\(|\)を定義すれば、\begin{equation*} \left( A,|\right)
\end{equation*}は順序集合になります。隣接行列\(M_{|}\)を特定してください。
\begin{equation*}
A=\left\{ a,b,c,d\right\}
\end{equation*}上の二項関係\(R\)の隣接行列が、 \begin{equation*}
M_{R}=\begin{pmatrix}
1 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1\end{pmatrix}\end{equation*}で与えられているものとします。ただし、\(A\)の要素には \begin{equation*}
a_{1}=a,\quad a_{2}=b,\quad a_{3}=c,\quad a_{4}=d
\end{equation*}と付番されているものとします。二項関係\(R\)を順序対の集合として表し、\(R\)が半順序であるか、また全順序であるかを判定してください。
\begin{equation*}
U=\left\{ 1,2\right\}
\end{equation*}のベキ集合
\begin{equation*}
2^{U}=\left\{ \phi ,\left\{ 1\right\} ,\left\{ 2\right\} ,\left\{
1,2\right\} \right\}
\end{equation*}上に包含関係\(\subset \)を定義します。要素を \begin{eqnarray*}
a_{1} &=&\phi \\
a_{2} &=&\left\{ 1\right\} \\
a_{3} &=&\left\{ 2\right\} \\
a_{4} &=&\left\{ 1,2\right\}
\end{eqnarray*}と付番したとき、包含関係\(\subset \)の隣接行列を求めてください。また、\(\subset \)が全順序であるかを判定してください。
\begin{equation*}
A=\left\{ a_{1},a_{2},a_{3},a_{4}\right\}
\end{equation*}上の全順序\(\leq \)について、 \begin{equation*}
a_{1}<a_{2}<a_{3}<a_{4}
\end{equation*}が成り立つものとします。\(\leq \)の隣接行列を求めてください。また、この行列の形から全順序の反射律、反対称律、完備律を確認してください。
\begin{equation*}
A=\left\{ a_{1},a_{2},\cdots ,a_{n}\right\}
\end{equation*}上の二項関係\(R\)の隣接行列を、 \begin{equation*}
M_{R}=\left( m_{ij}\right)
\end{equation*}とします。\(R\)が半順序であるための必要十分条件が、以下の3条件であることを示してください。 \begin{eqnarray*}
&&\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{eqnarray*}
M=\left( m_{ij}\right) ,\quad N=\left( n_{ij}\right)
\end{equation*}に対し、そのブール積\(M\odot N\)を、 \begin{equation*}
\left( M\odot N\right) _{ik}=\bigvee_{j=1}^{n}\left( m_{ij}\wedge
n_{jk}\right)
\end{equation*}と定義します。有限集合\(A\)上の二項関係\(R\)の隣接行列を\(M_{R}\)とするとき、\(R\)が推移的であることと、 \begin{equation*}
M_{R}\odot M_{R}\leq M_{R}
\end{equation*}が成り立つことが必要十分であることを示してください。ただし、行列の不等号\(\leq \)は成分ごとの大小関係を表すものとします。
