基于关系矩阵中等价关系的判定

宋泽成，石瑞平

（1. 唐山师范学院 数学与信息科学系，河北 唐山 063000；2. 石家庄信息工程职业学院 基础部，河北 石家庄 050000）

1 引言

设R是集合A上的二元关系，要判定R在A上是否是等价关系，一般来讲，只能从定义出发，有时也可以从关系图判定。当R包含的序偶较多时，从定义出发比较难于判定且计算量很大。

给定集合A上的一个二元关系R，设MR为R的关系矩阵，MR=(mij)n×n，这里mij只取1或0，它是一个布尔矩阵。下面从 MR出发，给出等价关系的判定方法，并讨论等价关系的性质。因自反性和对称性很容易直接判定，本文不再讨论，可参阅文献[1]、[2]。传递性一般无规律性可言，本文主要讨论传递性的判定。

2 传递性的判定方法

定义 1 设R是非空集合A上的二元关系，对任意的a, b, c∈A，每当(a, b)∈R，且(b, c)∈R时，就有(a, c)∈R，则称二元关系R在A上是传递的，也称R是A上的传递关系。

定义2 设A,B,C为三个非空集合，R1是A，B上的二元关系，R2是B，C上的二元关系，则集合

定义3 设R是非空集合A上的二元关系，R◦R，记作 R2，称为R的二次幂。

如果集合A上的二元关系R具有传递性，那么，每当(a, b)∈R，且(b, c)∈R时，就应有 ( a,c)∈ R,所以可得R2⊆R；若R2⊆R，则R是传递的。

设A为有限集，元数为n， R2的关系矩阵为 MR2，且

又设R的关系矩阵为MR

这里MR和 MR2都是布尔矩阵。

由R2⊆R可知，关系矩阵MR中某元素 αij=1，那么MR2中对应关系元素αi′j可以为1或者0，若MR中某元素αij=0那么MR2中对应元素′只能等于0，否则R就不能满足传递性，因此 αi′j≤αij(i,j = 1 ,2 … ,n)，而

这里的“.”是布尔运算，其中

由αi′j可以看出，当至少存在一个R，使αik和αkj同时为1时，αik⋅ αkj=1那么不论其它项是0还是1，此时 αi′j=1否则 αi′j=0这样求αij可以简化计算，提高运算速度。

由以上讨论，我们可以按以下步骤来验证非空集合A上的二元关系R是否具有传递性：

（1）写出R的关系矩阵：

（2）设复合关系 R2的关系矩阵 MR2=(′)n×n，逐一检查MR中元素是否为零，从α11开始，若 α11=1则接下去检查α12；若 α11=0，则求，看是否为零，否则 R 不具有传递性，若′ =0检查下一个元素α12。若 α12=1接下去检查α13；若α12=0，则求，看它是否为零，否则R不具有传递性。以此类推，直到αnn为止。

（3）若MR中所以零元素αij对应的MR2中元素′也全为零，那么R是传递的。

上述方法对应集合A的元数较大，且R中会有的序偶较多时，判定R是否具有传递性是相当好的，这是因为R中序偶较多，那么MR中“1”的个数也较多，相应的“0”元素个数就较少。下面通过具体的例子说明如何应用上述方法。例如，设集合：

二元关系

（1）写出关系矩阵

（2）设 R ◦ R= R的关系矩阵为 M2= (′ )，因

122R5×5为 α12=0，求′ 得：

（3）因为MR中13个零对应的 MR2中元素也全为零，故R是A上的传递关系。

当然，对应集合A上的一些特殊二元关系，比如“模2同余”；“模3同余”“模同余”关系，“整除”关系，“大于”关系等等，由于R的结构比较特殊，可以从这些关系本身的定义出发，来验证它的传递性。

3 等价关系的判定方法

定理1 以C1，C2，…，Cr为等价类，构造集合A上的一个二元等价关系 R，则等价关系R的关系矩阵 MR等价于PR，这里

此分块矩阵[3]对角线上的子块P11，P22，…，Prr都是元素均为1的方阵，其阶数分别对应C1，C2，…，Cr的基数，子块个数r等于R的等价类的个数，其他子块Pij（i≠j）均为零矩阵，即MR等价于一个分块对角矩阵。

证明 不妨设

这时A上的关系R的关系矩阵为MR。由集的无序性，可对集A中的元素任意排号，A中任意两个元素对调一次，相当于MR中对应的行和列同时对换一次，即对MR进行一次行变换则必须马上对它进行一次相同的列变换。设等价类C1，C2，…，Cr包含的元素如下，

这里b1，b2，…，bn就是a1，a2，…，an的一个排列。我们对集A进行有限次元素对调，目的就是对集A中的元素重新排号，使之元素顺序为如下形式，

对新的元素顺序，再来考察R的关系矩阵，由于C1，C2，…Cr为R的等价类，以C1为例，C1中任意两个元素都有关系，C1与Ci（i=2、…r）中任意两个元素都没有关系，所以P11= [ 1]i1×i1，P11的阶数就是 C1的基数，而 P12，P13，…，P1r均为零矩阵。同样，对于C2，C3，…，Cr，仅有P22，…，Prr这些子块是元素均为1的方阵，其阶数对应等价类的基数，而其他子块均为零矩阵。那末此时的 A，R的关系矩阵就是 PR了。在对A中元素对调位置的同时，对应着对MR施以前边约定的初等变换，一旦A中元素排成了

MR就化成了PR，所以MR等价于PR。

由定理1的证明可得如下判定方法：给定A上的一个二元关系R，首先写出R的关系矩阵MR，若MR经过初等变换后能化成一个分块对角阵PR，且PR具有下述形式：

这里子块P1，P2，…，PS都是元素均为1的方阵，那末R一定是A上的一个等价关系。

4 等价关系的性质

定理2 若R是A上的等价关系，其关系矩阵为MR，那末，秩(MR)就是R的商集Q的基数，即秩(MR)=。

证明：因为R是A上的等价关系，关系矩阵MR，不妨设此等价关系确定了s个等价类，即=s。由引理可知，MR经过有限次初等变换后可变成分块对角阵B，并且B的形式如下：

这里 Bi=[1]ti×ti，i=1，2，…，s，且s就是R确定的等价类的个数。由于初等变换不改变矩阵的秩，所以

任取Bi（1≤i≤s），显然，秩(Bi)=1，又因为对Bi做初等行、列变换，不会影响其他子块Bj（i≠j），因此，

所以，

5 结束语

研究了对集合A上的二元关系用关系矩阵来判定传递性和等价关系的问题，给出了对集合中元素较多时简便实用的一种方法，并讨论了等价关系的矩阵性质，证明了关系矩阵的秩就是商集的基数。

[1]耿素云,屈婉玲.离散数学[M].北京:高等教育出版社,2004:1.

[2]左孝凌,李为鉴,刘永才.离散数学[M].上海:上海科学技术文献出版社,1982:9.

[3]同济大学应用数学系.线性代数[M].北京:高等教育出版社,2003:1.