浅谈关系矩阵

什么是关系矩阵

关系矩阵就是用矩阵来表示关系，关系矩阵中的数值皆为**0**或**1**（也就是**bool**型）。

\[\begin{vmatrix} 1& 0& 1\\ 0& 0& 1\\ 1& 0& 0 \end{vmatrix} \]

\[\begin{vmatrix} 1->1有& 1->2没& 1->3有\\ 2->1没& 2->2没& 2->3有\\ 3->1有& 3->2没& 3->3没\\ \end{vmatrix} \]

关系矩阵和图论中的邻接矩阵本质上是一样的，所以我们也可以用图论的方式来理解关系矩阵。

对于元素集合 $A={a_1,a_2,a_3,...,a_n}$ ,关系$R\subseteq A\times A$。

$R$ 用关系矩阵表示为 $M(R)=(r_{i,j})_{n\times n}$

自反性

关系矩阵主对角线上所有元素的值都为1。在图论中则表示每个点都存在自环。
反自反性

关系矩阵主对角线上所有元素的值都为0。在图论中则表示每个点都不存在自环。
对称性

对于 $\forall {i,j}(i\ne j)$，关系矩阵D中的元素 $d_{i,j}$ 与 $d_{j,i}$ 相等。在图论中则表示为每一条边都为双向边或自环。
反对称性

对于 $\forall {i,j}(i\ne j)$，关系矩阵D中的元素 $d_{i,j}$ 与 $d_{j,i}$ 不相等或全为0。在图论中则表示为任意两点之间仅有一条单向边或无边，允许存在自环。
非对称性

对于 $\forall {i,j}(i\ne j)$，关系矩阵D中的元素 $d_{i,j}$ 与 $d_{j,i}$ 不相等或全为0，且 $d_{i,i}$ 等于0。在图论中则表示为任意两点之间仅有一条单向边或无边，无自环。

逆运算相关性质

$M(R^{-1})=(M(R))^T$

关系的逆的关系矩阵等于关系矩阵的逆
合成运算相关性质

$M(R_1 \circ R_2)=M(R_2)\bullet M(R_1)$

其中 $\bullet$ 是矩阵的逻辑乘法，运算法则与矩阵乘法类似，逻辑乘法使用 $\wedge$ 运算，逻辑加法使用 $\vee $ 运算

逻辑矩阵在图论中的应用十分广泛，例如邻接矩阵就是一种逻辑矩阵的拓展，由于应用的实在是太广了，所以就先鸽了这部分。

反演本身就是求两个函数之间的关系，很适合用关系矩阵来推导。

小试牛刀：

我们最常见到的反演关系就是前缀和与差分了，我们尝试用关系矩阵证明一下，设 $F_n$ 为前缀和，$G_n$ 为差分，则有：

\[\begin{align*} F_n&=\sum_{i=0}^{n}G_i\\ G_n&=F_n-F_{n-1} \end{align*} \]

我们设 $A$ 为关系矩阵，用于描述求和关系：

\[\begin{align*} F_{n}&=\sum_{i=0}^{n}G_i\\ &=\sum_{i=0}^{\infty}A_{n,i}G_i\\ \\ F&=G\times A\\ G&=A^T\times F \end{align*} \]

设 $B$ 为差分关系矩阵：

\[\begin{align*} G_n&=\sum_{i=0}^{\infty}B_{n,i}F_i\\ &=F_n-F_{n-1}\\ G&=F\times B\\ F&=B^T\times G \end{align*} \]

那么有

\[\begin{align*} \end{align*} \]