• 原地址

浅谈关系矩阵

什么是关系矩阵

关系矩阵就是用矩阵来表示关系，关系矩阵中的数值一般为**0**或**1**（也就是**bool**型），当然有些关系矩阵有自己的意义，具体情况具体分析。

• 举个例子：

$$\begin{vmatrix} 1& 0& 1\\ 0& 0& 1\\ 1& 0& 0 \end{vmatrix}$$

• 这个关系矩阵就表示了3个抽象物体的关系：

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

• 注意：关系是有向的，也就是说1->2有关系不一定2->1也有关系。

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

关系矩阵的表示

对于元素集合 ,关系。

用关系矩阵表示为

关系矩阵的性质

自身性质

1. 自反性

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

2. 反自反性

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

3. 对称性

   对于 ，关系矩阵D中的元素 与 相等。在图论中则表示为每一条边都为双向边或自环。

4. 反对称性

   对于 ，关系矩阵D中的元素 与 不相等或全为0。在图论中则表示为任意两点之间仅有一条单向边或无边，允许存在自环。

5. 非对称性

   对于 ，关系矩阵D中的元素 与 不相等或全为0，且 等于0。在图论中则表示为任意两点之间仅有一条单向边或无边，无自环。

运算性质

1. 逆运算相关性质

   关系的逆的关系矩阵等于关系矩阵的逆

2. 合成运算相关性质

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

食用方法及技巧

图论

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

反演

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

小试牛刀

我们最常见到的反演关系就是前缀和与差分了，设 为前缀和， 为差分，则有：

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

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

$$\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*}$$

设 为差分关系矩阵：

$$\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*} A_{n,i}&=i\le n\\ B_{n,i}&= \begin{cases} & -1 \ \ &(i=n-1)\\ & 1 &(i=n) \end{cases} \\ \\ (A\times B)_{n,m}&=\sum_{i=0}^{\infty}A_{n,i}B_{i,m}\\ &=\sum_{i=n}^{\infty}([m=i]-[m=i-1])\\ &=[n=m]\\ &=I \end{align*}$$

所以 ，、矩阵互逆。

由此观之，两个互为反演的关系矩阵互逆。

因此，我们就可以用关系矩阵是否互逆来证明反演。

多维反演叠加

若

$$\begin{align*} \begin{cases} F(n)=\sum_{i=0}A_{1}[n,i]G(i)\\ G(n)=\sum_{i=0}B_{1}[n,i]F(i) \end{cases}\\ \begin{cases} F(n)=\sum_{i=0}A_{2}[n,i]G(i)\\ G(n)=\sum_{i=0}B_{2}[n,i]F(i) \end{cases} \end{align*}$$

则

$$\begin{align*} \begin{cases} F(n,m)=\sum_{i=0}\sum_{j=0}A_{1}[n,i]A_{2}[m,j]G(i,j)\\ G(n,m)=\sum_{i=0}\sum_{j=0}B_{1}[n,i]B_{2}[m,j]F(i,j) \end{cases} \end{align*}$$

换而言之，反演系数等于每个维度反演系数之积。

证明：

设

$$\begin{align*} A[(n_1,n_2)(i_1,i_2)]&=A_1[n_1,i_1]A_2[n_2,i_2]\\ B[(n_1,n_2)(i_1,i_2)]&=B_1[n_1,i_1]B_2[n_2,i_2] \end{align*}$$

则

$$\begin{align*} &(A*B)[(n_1,n_2),(m_1,m_2)]\\ =&\sum_{i_1=0}\sum_{i_2=0}A_1[n_1,i_1]A_2[n_2,i_2]B_1[i_1,m_1]B_2[i_2,m_2]\\ =&\sum_{i_1=0}\sum_{i_2=0}A_1[n_1,i_1]B_1[i_1,m_1]A_2[n_2,i_2]B_2[i_2,m_2]\\ =&\sum_{i_1=0}A_1[n_1,i_1]B_1[i_1,m_1]\sum_{i_2=0}A_2[n_2,i_2]B_2[i_2,m_2]\\ =&[n_1=m_1][n_2=m_2]\\ =&[(n_1,n_2)=(m_1,m_2)] \end{align*}$$