社交网络中求最小正影响支配集的改进算法

麦飞; 陈卫东

doi:10.6054/j.jscnun.2016.05.004

摘要: 网络中求解最小正影响支配集的问题已经被证明是NP难问题，且已有性能较好的贪心求解算法．通过分析现有的贪心近似算法（Wang-Greedy）和贪心启发式算法(Raei-Greedy)，融合其贪心策略，提出了1个改进的贪心近似算法(Hybrid-Greedy)．理论分析表明，Hybrid-Greedy仍保持Wang-Greedy的近似比性能和时间复杂度．在一些较大规模的真实社交网络实例中的实验研究表明，Hybrid-Greedy在这些社交网络中所得解的质量较Wang-Greedy和Raei-Greedy有明显提高．

关键词:

Abstract: The problem of finding the minimum positive influence dominating set in a given network has been proved to be NP-hard, and there are greedy algorithms with good performance to solve it. An existing greedy approximation algorithm (Wang-Greedy) and a heuristic algorithm (Raei-Greedy) are analyzed. Accordingly, an improved greedy approximation algorithm (Hybrid-Greedy) to find the minimum positive influence dominating sets in social networks is proposed. It is shown theoretically that hybrid-Greedy remains the same approximation ratio and time complexity as Wang-Greedy. Experimental results on some large real-world social network instances show that Hybrid-Greedy yields better solutions than Wang-Greedy and Raei-Greedy for these social network instances.

Keywords:

模糊蕴涵代数^[1], 简称FI代数, 揭示了蕴涵算子的本质。众多著名的模糊逻辑代数系统, 如MV代数^[2]、BL代数^[3]、R₀代数^[4]、剩余格^[5]和格蕴涵代数^[6]等，都是FI代数的特殊子类代数。

迄今为止, 许多科学工作者从事这方面的研究并取得了丰硕成果^[7-14]。例如，王国俊^[7]证明了3种不同形式的MV-代数刻画的等价性, 同时分析了MV-代数、BL-代数和R₀代数的逻辑背景；ZHU和XU^[9]发展了一般剩余格的滤波理论；裴道武等^[10]揭示了FI格与模糊逻辑中几个重要代数系统之间的紧密联系, 且一些重要的模糊逻辑代数系统都是FI格类的子类；吴达^[13]在FI代数中引进“交换”运算，从而得到了进一步刻画FI代数及HFI代数的若干结果。

矩阵半张量积是一种新的矩阵乘积, 是描述有限集上映射的强大工具, 已成功应用于布尔网络^[15]、密码学^[16]、图着色^[17]、信息安全^[18]和车辆控制^[19]等领域。基于此, 本文将矩阵半张量积应用于逻辑代数研究领域, 给出了FI代数的若干等价刻画：通过矩阵半张量积方法在统一的理论框架内刻画了有限FI代数; 利用矩阵表达式, 将有限FI代数上抽象的逻辑运算规律转化为具体逻辑矩阵的简单运算; 彻底解决了有限FI代数同构的分类问题。

1. 预备知识

在本文中, 采用以下符号：ℝ表示实数域; ℝⁿ表示所有n维实列向量集合; ℝ^m×n表示所有m×n阶实矩阵集合; $\mathcal{L}_{m \times n}$ 表示m×n阶逻辑矩阵集合; A^T表示矩阵A的转置, Col_i(A)表示矩阵A的第i列; I_n表示n阶单位矩阵, δ_nⁱ表示I_n的第i列, 1_t表示t个元素全为1的列向量; Δ_n: ={δ_nⁱ|i=1, …, n}, Δ: =Δ₂; D_n: ={1, 2, …, n}, D: ={0, 1};|X|表示集合X的基数; ⊗表示矩阵的Kronecker积; ○表示矩阵半张量积。

定义1^[20] 对于矩阵A=(a_ij)∈ℝ^m×n, B=(b_ij)∈ℝ^p×q, 定义A和B的Kronecker积为：

$\boldsymbol{A} \otimes \boldsymbol{B}:=\left(\begin{array}{cccc} a_{11} \boldsymbol{B} & a_{12} \boldsymbol{B} & \cdots & a_{1 n} \boldsymbol{B} \\ a_{21} \boldsymbol{B} & a_{22} \boldsymbol{B} & \cdots & a_{2 n} \boldsymbol{B} \\ \vdots & \vdots & & \vdots \\ a_{m 1} \boldsymbol{B} & a_{m 2} \boldsymbol{B} & \cdots & a_{m n} \boldsymbol{B} \end{array}\right) 。$

定义2^[20] 设矩阵A∈ℝ^m×n, B∈ℝ^p×q, 定义A与B的半张量积为

$\boldsymbol{A} \circ \boldsymbol{B}:=\left(\boldsymbol{A} \otimes \boldsymbol{I}_{\frac{t}{n}}\right)\left(\boldsymbol{B} \otimes \boldsymbol{I}_{\frac{t}{P}}\right),$

其中t为n和p的最小公倍数。当n=p时, A○B=AB，即矩阵半张量积是普通矩阵乘法的推广, 并且保留矩阵乘法的重要性质。

矩阵半张量积具有下列性质：

引理1^[20] 设A, B, C是实矩阵, a, b∈ℝ, 则

(1)(分配律) A。(aB±bC)=aA。B±bA。C, (aA±bB)○C=aA。C±bB。C；

(2)(结合律) (A。B)。C=A。(B。C)；

(3) 设x∈ℝ^m, y∈ℝⁿ, 则x○y=x⊗y。

引理2^[20] 设x∈ℝ^t, A∈ℝ^m×n, 则x。A=(I_t⊗A)○x。

定义3^[21] 换位矩阵W_{[m, n]}∈ℝ^mn×mn定义为

$\boldsymbol{W}_{[m, n]}=\left[\boldsymbol{I}_n \otimes \boldsymbol{\delta}_m^1, \boldsymbol{I}_{\mathrm{n}} \otimes \boldsymbol{\delta}_m^2, \cdots, \boldsymbol{I}_{\mathrm{n}} \otimes \boldsymbol{\delta}_m^m\right] 。$

换位矩阵的作用是交换2个不同维的列向量因子在矩阵半张量积运算下的顺序。

引理3^[21] 设x∈ℝ^m, y∈ℝⁿ, 则W_{[m, n]} ○x○y=y。x。

设H={h₁, h₂, …, h_r}是一个有限集, 如果可以用一个向量δ_rⁱ∈Δ_r表示集合H中的每个元素, 即

$h_i \sim \boldsymbol{\delta}_r^i \quad(i=1, 2, \cdots, r),$

则称这种表达为有限集的向量表达式, 其对应顺序可以任意指定。

例如，在经典逻辑中, D={0, 1}, 一个逻辑变量x∈D可以用向量形式表示:

$x \sim\left[\begin{array}{c} x \\ 1-x \end{array}\right]。$

类似地, 经典逻辑变量的向量表达式也可以用于多值逻辑。

例1 考虑k值逻辑, 定义

$\frac{i}{k-1} \sim \boldsymbol{\delta}_k^{k-i} \quad(i=0, 1, \cdots, k-1)。$

基于此, 有

$\boldsymbol{\delta}_k^i \wedge \boldsymbol{\delta}_k^j=\boldsymbol{\delta}_k^{\max (i, j)} ; \boldsymbol{\delta}_k^i \vee \boldsymbol{\delta}_k^j=\boldsymbol{\delta}_k^{\min (i, j)} ; \neg \boldsymbol{\delta}_k^i=\boldsymbol{\delta}_k^{k+1-i}。$

利用向量表达式, 一个n维变量逻辑函数f: Dⁿ→D可以表示为从Δ_n到Δ的一个映射。

引理4^[22] 设映射f: Dⁿ→D, 利用向量表达式, 有

$f\left(x_1, \cdots, x_n\right)=\boldsymbol{M}_f \circ x_1 \circ x_2 \circ \cdots \circ x_n，$

其中 $\boldsymbol{M}_f \in \mathcal{L}_{2 \times 2^n}$ 是唯一的, 叫做f的结构矩阵。

例2 在例1, 当k=2时, 有1~δ₂¹, 0~δ₂²。记∧、∨、¬的结构矩阵分别为M_c、M_d、M_n, 由引理4可得

$\begin{aligned} & \boldsymbol{\delta}_2^1 \wedge \boldsymbol{\delta}_2^1=\boldsymbol{\delta}_2^1=\boldsymbol{M}_c \circ \boldsymbol{\delta}_2^1 \circ \boldsymbol{\delta}_2^1=\operatorname{Col}_1\left(\boldsymbol{M}_c\right) ; \\ & \boldsymbol{\delta}_2^1 \wedge \boldsymbol{\delta}_2^2=\boldsymbol{\delta}_2^2=\boldsymbol{M}_c \circ \boldsymbol{\delta}_2^1 \circ \boldsymbol{\delta}_2^2=\operatorname{Col}_2\left(\boldsymbol{M}_c\right) ; \\ & \boldsymbol{\delta}_2^2 \wedge \boldsymbol{\delta}_2^1=\boldsymbol{\delta}_2^2=\boldsymbol{M}_c \circ \boldsymbol{\delta}_2^2 \circ \boldsymbol{\delta}_2^1=\operatorname{Col}_3\left(\boldsymbol{M}_c\right) ; \\ & \boldsymbol{\delta}_2^2 \wedge \boldsymbol{\delta}_2^2=\boldsymbol{\delta}_2^2=\boldsymbol{M}_c \circ \boldsymbol{\delta}_2^2 \circ \boldsymbol{\delta}_2^2=\operatorname{Col}_4\left(\boldsymbol{M}_c\right) 。 \end{aligned}$

计算显示M_c=δ₂[1 2 2 2]。类似地, 可以得到M_d=δ₂[1 1 1 2]和M_n=δ₂[2 1]。

2. 有限FI代数的矩阵表示

定义4^[1] 一个(2, 0)型代数(X, →, 0)称为模糊蕴涵代数, 简称为FI代数, 如果对任意x, y, z∈X, 有

(I₁)x→(y→z)=y→(x→z);

(I₂)(x→y)→((y→z)→(x→z))=1;

(I₃)x→x=1;

(I₄) x→y=y→x=1⇒x=y;

(I₅) 0→x=1,

其中1=0→0。

有限集合X={x₁, x₂, …, x_t}(t < ∞)，将X中的元素转化为向量的形式：x₁~δ_t¹, x₂~δ_t², …, 0=x_t~δ_t^t。记→的结构矩阵为M_→(t), 下面给出与FI代数等价的代数条件。

定理1 设|X|=t < ∞, (X, →, 0)是FI代数当且仅当M_→(t)满足

(I₁)′M_→(t)(I_t⊗M_→(t))=M_→(t)(I_t⊗M_→(t))W_{[t, t]};

(I₂)′(M_→(t))²(I_t²⊗(M_→(t))²)(I_t⁴⊗M_→(t))(I_t⊗W_{[t, t³]})PR_t(I_t⊗PR_t)(I_t²⊗PR_t)=1_t³^T⊗(M_→(t)δ_t²^t²);

(I₃)′M_→(t)PR_t=1_t^T⊗(M_→(t)δ_t²^t²);

(I₄)′M_→(t)xy=M_→(t)W_{[t, t]}xy=M_→(t)δ_t²^t²⇒x=y;

(I₅)′M_→(t)δ_t^t=1_t^T⊗(M_→(t)δ_t²^t²),

其中, 0~δ_t^t, 1~M_→(t)δ_t²^t², PR_t=diag(δ_t¹, δ_t², …, δ_t^t), 且对∀x∈Δ_t, x²=PR_tx, t≥2。

证明易证定义4的条件(I₁)~(I₅)可等价于定理1的条件(I₁)′~(I₅)′, 下面只给出条件(I₂)′等价于条件(I₂)的详细证明, 其他的证明过程类似或显见。设(X, →, 0)是有限FI代数, 且|X|=t < ∞, 定义0~δ_t^t, 由1=0→0可以得到1~M_→(t)δ_t²^t²。∀x, y, z∈X, 条件(I₂)的矩阵表示如下：

$\begin{aligned} & \boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{M}_{\rightarrow}(t) x y\right)\left(\boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{M}_{\rightarrow}(t) y z\right)\left(\boldsymbol{M}_{\rightarrow}(t) x z\right)\right)= \\ & \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}， \end{aligned}$

即

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right) x y^2 z\left(\boldsymbol{M}_{\rightarrow}(t) x z\right)= \\ & \quad \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}。 \end{aligned}$

进一步可得

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) x y^2 z x z= \\ & \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}, \end{aligned}$

则有

$\begin{aligned} &\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) x \times \\ & \boldsymbol{W}_{\left[t, t^3\right]} x y^2 z^2=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}, \end{aligned}$

从而

$\begin{gathered} \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{\left[t, t^3\right]}\right) \boldsymbol{P} \boldsymbol{R}_t x \boldsymbol{P} \boldsymbol{R}_t y \boldsymbol{P} \boldsymbol{R}_t z=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{\boldsymbol{t}^2}, \end{gathered}$

故

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ & \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{\left[t, t^3\right]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right)\left(I_{t^2} \otimes \boldsymbol{P} \boldsymbol{R}_t\right) x y z= \\ & \quad \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2 \circ}^{t^2}。 \end{aligned}$

由x、y、z的任意性，可得

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ & \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{\left[t, t^3\right]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right)\left(I_{t^2} \otimes \boldsymbol{P} \boldsymbol{R}_t\right)= \\ & \quad \boldsymbol{I}_{t^3}^{\mathrm{T}} \otimes\left(\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}\right), \end{aligned}$

由此可知条件(I₂)′等价于条件(I₂)。证毕。

例3 设t=2, 由于→为一个二元算子, 故可设M_→(2)=[m₁, m₂, m₃, m₄](m_i∈Δ, i=1, 2, 3, 4), 只有唯一的一组M_→(2)满足定理1的条件(I₁)′~(I₅)′, 即

$\boldsymbol{M}_{\rightarrow}(2)=\left(\begin{array}{llll} 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \end{array}\right) 。$

例4 设t=3, 类比上述步骤, 运用穷举法只得到4组满足FI代数的定义的M_→(3)：

$\begin{aligned} & \text { (1) } \boldsymbol{M}_{\rightarrow}^1(3)=\left(\begin{array}{lllllllll} 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) ; \\ & \text { (2) } \boldsymbol{M}_{\rightarrow}^2(3)=\left(\begin{array}{lllllllll} 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \end{array}\right) ; \\ & \text { (3) } \boldsymbol{M}_{\rightarrow}^3(3)=\left(\begin{array}{lllllllll} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \end{array}\right) \text {; } \\ & \text { (4) } \boldsymbol{M}_{\rightarrow}^4(3)=\left(\begin{array}{lllllllll} 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{array}\right) \text {。 } \end{aligned}$

可以在FI代数(X, →, 0)上定义一个二元关系≤：

$x \leqslant y \Leftrightarrow x \rightarrow y=1 \quad(x, y \in X) \text { 。 }$

显然, 由→诱导的关系≤是一个偏序。

引理5^[10] 设(X, →, 0)是一个FI代数, 对于任意x, y, z∈X, 下列性质成立：

(i) x→1=1;

(ii) 1→x=x;

(iii) x→(y→x)=1;

(iv) x≤y⇒z→x≤z→y, y→z≤x→z;

(v) x≤y→z⇔y≤x→z;

(vi)(y→z)≤(x→y)→(x→z)。

对于有限FI代数, 利用结构矩阵M_→(t)与矩阵半张量积, 可以将引理5的(i)~(vi)由定性运算转化为定量运算, 给出它们的代数表达式。

定理2 设(X, →, 0)是一个有限FI代数, 且|X|=t < ∞。对于FI代数上的偏序关系进行矩阵表示，得到

$\boldsymbol{M}_{\rightarrow}(t) x y=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}。$

由此二元关系可得到与引理5的(i)~(vi)等价的代数表达形式：

(i)′M_→(t)W_{[t, t]}M_→(t)δ_t²^t²=1_t^T⊗(M_→(t)δ_t²^t²);

(ii)′M_→(t)(M_→(t)δ_t²^t²)=I_t;

(iii)′M_→(t)(I_t⊗M_→(t))(I_t⊗W_{[t, t]})PR_t=1_t²^T⊗(M_→(t)δ_t²^t²);

(iv)′M_→(t)xy=M_→(t)δ_t²^t²⇒(M_→(t))²(I_t²⊗M_→(t))W_{[t, t]}(I_t⊗W_{[t, t²]})(I_t²⊗PR_t)xyz=M_→(t)δ_t²^t², (M_→(t))²(I_t²⊗M_→(t))W_{[t, t²]}(I_t²⊗PR_t)xyz=M_→(t)δ_t²^t²;

(v)′M_→(t)(I_t⊗M_→(t))=1_t³^T⊗(M_→(t)δ_t²^t²)⇔M_→(t)(I_t⊗M_→(t))W_{[t, t]}=1_t³^T⊗(M_→(t)δ_t²^t²);

(vi)′(M_→(t))²(I_t²⊗(M_→(t))²)(I_t⁴⊗M_→(t))W_{[t³, t²]}(I_t⊗W_{[t, t]})PR_t(I_t⊗PR_t)(I_t²⊗PR_t)=1_t³^T⊗(M_→(t)δ_t²^t²)。

证明 (i)′~(vi)′的证明方法类似, 这里只给出(vi)′的详细证明。首先, 可将(vi)等价表达成(y→z)→((x→y)→(x→z))=1, 其矩阵表示如下：

$\begin{aligned} & \boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{M}_{\rightarrow}(t) y z\right)\left[\boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{M}_{\rightarrow}(t) x y\right)\left(\boldsymbol{M}_{\rightarrow}(t) x z\right)\right]= \\ & \quad \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}， \end{aligned}$

即

$\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2 y z\left[\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2 x y \boldsymbol{M}_{\rightarrow}(t) x z\right]=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}，$

从而

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right) y z x y \boldsymbol{M}_{\rightarrow}(t) x z= \\ & \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}。 \end{aligned}$

进一步可得

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) y z x y x z= \\ & \quad \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}， \end{aligned}$

则有

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \boldsymbol{W}_{\left[t^3, t^2\right]} x y x y z^2= \\ & \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}， \end{aligned}$

即

$\begin{gathered} \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \boldsymbol{W}_{\left[t^3, t^2\right]} \times \\ \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) x^2 y^2 z^2=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}, \end{gathered}$

从而

$\begin{gathered} \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \boldsymbol{W}_{\left[t^3, t^2\right]} \times \\ \left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t x \boldsymbol{P R}_t y \boldsymbol{P} \boldsymbol{R}_t z=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}, \\ \end{gathered}$

则

$\begin{aligned} &\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \boldsymbol{W}_{\left[t^3, t^2\right]} \times \\ &\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{P} \boldsymbol{R}_t\right) x y z= \\ & \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2 }^{t^2}。 \end{aligned}$

由x, y, z的任意性, 则有

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\left(\boldsymbol{I}_{t^2} \otimes\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2\right)\left(\boldsymbol{I}_{t^4} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \boldsymbol{W}_{\left[t^3, t^2\right]} \times \\ & \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{P} \boldsymbol{R}_t\right)= \\ & \quad \boldsymbol{I}_{t^3}^{\mathrm{T}} \otimes\left(\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}\right) 。 \end{aligned}$

从而, (vi)′得证。证毕。

3. FI代数的同态与同构

定义5^[1] 设F_i=(X_i, →_i, 0_i)(i=1, 2)是2个FI代数, 若存在映射f: X₁→X₂, 使得

(i) f(x→₁y)=f(x)→₂f(y)(x, y∈X₁);

(ii) f(0₁)=0₂,

则称f为FI代数同态。

假设|X₁|=m, |X₂|=n, 即令X₁={δ_m¹, δ_m², …, δ_m^m}, X₂={δ_n¹, δ_n², …, δ_nⁿ}。则映射f: X₁→X₂可以表示成矩阵形式：

$f(x)=M_f x，$

其中 $\boldsymbol{M}_f \in \mathcal{L}_{n \times m}$ 是f的结构矩阵。

定理3 设F_i=(X_i, →_i, 0_i)(i=1, 2)是2个有限FI代数, 且|X₁|=m < ∞, |X₂|=n < ∞, 存在映射f: X₁→X₂, f为FI代数同态当且仅当

$(\mathrm{i})^{\prime} \boldsymbol{M}_f \boldsymbol{M}_{\rightarrow}(m)=\boldsymbol{M}_{\rightarrow}(n) \boldsymbol{M}_f\left(\boldsymbol{I}_m \otimes \boldsymbol{M}_f\right);\\ (\text{ii}) { }^{\prime} \operatorname{Col}_m\left(\boldsymbol{M}_f\right)=\boldsymbol{\delta}_n^n 。$

证明利用矩阵表示易得定理3的条件(i)′、(ii)′分别等价于定义5的条件(i)、(ii)。证明过程如下：∀x, y∈X₁, 条件(i)的矩阵表示如下：

$\begin{gathered} \boldsymbol{M}_f\left(\boldsymbol{M}_{\rightarrow}(m) x y\right)=\boldsymbol{M}_{\rightarrow}(n)\left(\boldsymbol{M}_f x\right)\left(\boldsymbol{M}_f y\right) \\ \boldsymbol{M}_f \boldsymbol{M}_{\rightarrow}(m)=\boldsymbol{M}_{\rightarrow}(n) \boldsymbol{M}_f\left(\boldsymbol{I}_m \otimes \boldsymbol{M}_f\right)_{\circ} \end{gathered}$

从而证得条件(i)′与条件(i)等价。对条件(ii), 由0_i~δ_iⁱ，并利用矩阵表示, 可以得到

$\begin{gathered} \boldsymbol{M}_f \boldsymbol{\delta}_m^m=\boldsymbol{\delta}_n^n, \\ \operatorname{Col}_m\left(\boldsymbol{M}_f\right)=\boldsymbol{\delta}_n^n \text { 。 } \end{gathered}$

从而证得条件(ii)′与条件(ii)等价。证毕。

定义6^[1] 设F_i=(X_i, →_i, 0_i)(i=1, 2)是2个FI代数, 且映射f: X₁→X₂为FI代数同态, 如果f是一对一且映上的, 那么f称为FI代数同构。

定义7^[20]给定一个置换τ∈S_n, 定义它的结构矩阵M_τ如下：

$\operatorname{Col}_i\left(\boldsymbol{M}_\tau\right)=\boldsymbol{\delta}_n^{\tau(i)} \quad(i=1, \cdots, n),$

称M_τ为置换矩阵。

定理4 设F_i(i=1, 2)为2个有限FI代数, 且|F₁|=|F₂|=n, M_→ⁱ(i=1, 2)为相应的结构矩阵。映射T: F₁→F₂为FI代数同构, 则

(i) T是一个置换矩阵, 即存在一个置换τ∈S_n, 使得T=M_τ, 因此T^T=T^－1;

(ii) M_→¹=T^TM_→²(T⊗T)。

证明由定义6知, 映射f: X₁→X₂是一对一且映上的, 则存在一个τ∈S_n, 使得f(i)=τ(i) (i=1, 2, …, n)。当x=i∈D_n表示为向量形式δ_nⁱ时, 有f(i)=τ(i)=M_τ(x)。于是

$\boldsymbol{M}_\tau \boldsymbol{M}_{\rightarrow}^1 x y=\boldsymbol{M}_{\rightarrow}^2\left(\boldsymbol{M}_\tau x\right)\left(\boldsymbol{M}_\tau y\right)。$

从而可得

$\begin{aligned} & \boldsymbol{M}_{\rightarrow}^2\left(\boldsymbol{M}_\tau x\right)\left(\boldsymbol{M}_\tau y\right)=\boldsymbol{M}_{\rightarrow}^2 \boldsymbol{M}_\tau\left(\boldsymbol{I}_n \otimes \boldsymbol{M}_\tau\right) x y= \\ & \quad \boldsymbol{M}_{\rightarrow}^2\left(\boldsymbol{M}_\tau \otimes \boldsymbol{M}_\tau\right) x y=\boldsymbol{M}_\tau \boldsymbol{M}_{\rightarrow}^1 x y， \end{aligned}$

即M_τM_→¹=M_→²(M_τ⊗M_τ)。进而有

$\begin{aligned} & \boldsymbol{M}_{\rightarrow}^1=\boldsymbol{M}_\tau^{-1} \boldsymbol{M}_{\rightarrow}^2\left(\boldsymbol{M}_\tau \otimes \boldsymbol{M}_\tau\right)=\boldsymbol{T}^{-1} \boldsymbol{M}_{\rightarrow}^2(\boldsymbol{T} \otimes \boldsymbol{T})= \\ & \quad \boldsymbol{T}^{\mathrm{T}} \boldsymbol{M}_{\rightarrow}^2(\boldsymbol{T} \otimes \boldsymbol{T})。 \end{aligned}$

证毕。

例5 在例3中, 当n=2时, 没有非平凡同构。

例6 在例4中, 当n=3时, 存在2组保持0不变的非平凡同构, $\boldsymbol{T}=\left(\begin{array}{lll} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array}\right)$ , 由定理4易知F₁={M_→¹}同构于F₂={M_→⁴}, F₁={M_→²}同构于F₂={M_→³}。

4. FI代数的导子

本节利用矩阵半张量积与逻辑矩阵运算来考虑有限FI代数上的导子：首先，引入(l, r)－导子、(r, l)－导子和导子的概念, 并给出它们的一些性质；然后，利用矩阵表达式, 将d、⊕、→所满足的运算规律转化为具体逻辑矩阵的简单运算；最后，通过逻辑矩阵运算给出FI代数关于导子的新性质。

定义8^[23] 设(X, →, 0)是FI代数, 对于映射d: X→X：

(i) 若d满足: ∀x, y∈X, 有

$d(x \rightarrow y)=(d(x) \rightarrow y) \oplus(x \rightarrow d(y)),$

则称d是X上的(l, r)－导子;

(ii) 若d满足: ∀x, y∈X, 有

$d(x \rightarrow y)=(x \rightarrow d(y)) \oplus(d(x) \rightarrow y),$

则称d是X上的(r, l)－导子;

(iii) 若d既是X上的(l, r)－导子, 又是X上的(r, l)－导子, 则称d是X上的导子, 并称(X, d)是导子FI代数;

(iv) 若d满足∀x∈X, 有d(x)=1, 则称d是X上的平凡导子。

利用矩阵半张量积以及矩阵表达式研究有限FI代数上的导子时, 定义一种新的二元运算⊕：∀x, y∈X, x⊕y=x′→y, 其中x′是x的伪补, 满足∀x∈X, x′=x→0。M_d、M_⊕(t)分别是d、⊕的结构矩阵, 且由⊕所满足的运算规律, 可以得到M_⊕(t)=(M_→(t))²W_{[t, t]}δ_t^t。

定理5 设(X, →, 0)是有限FI代数, 且|X|=t < ∞, 对于映射d: X→X：

(i)′d是X上的(l, r)－导子当且仅当

$\begin{gathered} \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right) ; \end{gathered}$

(ii)′d是X上的(r, l)－导子当且仅当

$\begin{gathered} \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P}_t\right) ; \end{gathered}$

(iii)′d是X上的导子当且仅当

$\begin{gathered} \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times\\ \left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{P}_t\right), \\ \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right) ; \end{gathered}$

(iv)′d是X上的平凡导子当且仅当

$\boldsymbol{M}_d=\boldsymbol{1}_t^{\mathrm{T}} \otimes\left(\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}\right)。$

证明这里只提供(i)′的详细证明，其他结论类似。定义8(i)中等式的矩阵表示如下：

$\boldsymbol{M}_d\left(\boldsymbol{M}_{\rightarrow}(t) x y\right)=\boldsymbol{M}_{\oplus}(t)\left(\boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{M}_d x\right) y\right)\left(\boldsymbol{M}_{\rightarrow}(t) x\left(\boldsymbol{M}_d y\right)\right)，$

即

$\boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t) x y=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) x y x \boldsymbol{M}_d y。$

进一步可得

$\begin{aligned} & \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t) x y=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ & \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) x^2 y \boldsymbol{M}_d y, \end{aligned}$

从而

$\begin{aligned} & \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t) x y=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_→(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ & \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t x y \boldsymbol{M}_d y, \end{aligned}$

则有

$\begin{gathered} \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t) x y=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right) x y^2， \end{gathered}$

进而有

$\begin{gathered} \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t) x y=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right) x y。 \end{gathered}$

由x, y的任意性, 则有

$\begin{gathered} \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right) 。 \end{gathered}$

故定理5(i)′的条件与定理8(i)的条件等价。证毕。

例7 设X={0, a, b, c, 1}, 其中0 < a < b < c < 1, 在X上定义→的运算表、映射d₁: X→X如下：

$\begin{array}{c|ccccc} \rightarrow & 0 & a & b & c & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 \\ a & c & 1 & 1 & 1 & 1 \\ b & a & a & 1 & 1 & 1 \\ c & a & a & b & 1 & 1 \\ 1 & 0 & a & b & c & 1 \end{array}$

$d_1(x)= \begin{cases}0 & (x=0)， \\ a & (x=a)， \\ 1 & (x=b, c, 1)。\end{cases}$

(1)

令0~δ₅⁵, a~δ₅⁴, b~δ₅³, c~δ₅², 1~δ₅¹，则由→的运算表和式(1)可以得到→和d₁的结构矩阵M_→(5)和M_d₁，并利用M_→(5)求得M_⊕(5)：

$\begin{aligned} & \boldsymbol{M}_{\rightarrow}(5)= \\ & \left(\begin{array}{lllllllllllllllllllllllll} 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right), \end{aligned}$

$M_{d_1}=\left(\begin{array}{ccccc} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right),$

$\begin{aligned} & \boldsymbol{M}_{\oplus}(5)= \\ & \left(\begin{array}{lllllllllllllllllllllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) 。 \\ & \end{aligned}$

则由定理1可得(X, →, 0)是FI代数，再将结构矩阵M_→(5)、M_⊕(5)和M_d₁代入定理5，满足定理5(iii)′的条件，即d₁既是X上的(l, r)－导子，又是X上的(r, l)－导子，因此，d₁是X上的导子。

例8 设X={0, a, b, c, 1}, 在X上定义→的运算表和映射d₂: X→X为：

$\begin{array}{c|ccccc} \rightarrow & 0 & a & b & c & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 \\ a & a & 1 & a & a & 1 \\ b & a & 1 & 1 & a & 1 \\ c & a & 1 & a & 1 & 1 \\ 1 & 0 & a & b & c & 1 \end{array}, d_2(x)= \begin{cases}a & (x=b, c) \\ 1 & (x=0, a, 1)\end{cases}$

类似地, 可以得到M_→(5)、M_d₂和M_⊕(5)：

$\begin{aligned} & \boldsymbol{M}_{\rightarrow}(5)= \\ & \left(\begin{array}{lllllllllllllllllllllllll} 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right), \end{aligned}$

$\boldsymbol{M}_{d_2}=\left(\begin{array}{ccccc} 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right),$

$\begin{aligned} & \boldsymbol{M}_{\oplus}(5)= \\ & \left(\begin{array}{lllllllllllllllllllllllll} 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) 。 \end{aligned}$

同样地, 将M_→(5)代入定理1得到(X, →, 0)是FI代数, 将M_→(5)、M_⊕(5)和M_d₂代入定理5, 可知d₂是X上的(r, l)－导子, 但不是X上的(l, r)－导子, 从而不是X上的导子。

引理6^[23] 设(X, →, 0)是FI代数。若d是X上的(l, r)－导子((r, l)－导子或导子), 则∀x, y∈X, 有

(i) x≤d(x);

(ii) d(x)→y≤x→d(y);

(iii) d(x)→d(y)≤d(x→y)。

定理6 设(X, →, 0)是有限FI代数, 且|X|=t < ∞。若d是X上的(l, r)－导子((r, l)－导子或导子), 则下列性质成立:

(i)′M_→(t)(I_t⊗M_d)PR_t=1_t^T⊗(M_→(t)δ_t²^t²);

(ii)′(M_→(t))²M_d(I_t²⊗M_→(t))(I_t³⊗M_d)(I_t⊗W_{[t, t]})PR_t(I_t⊗PR_t)=1_t²^T⊗(M_→(t)δ_t²^t²);

(iii)′(M_→(t))²M_d(I_t⊗M_d)(I_t²⊗M_dM_→(t))(I_t⊗W_{[t, t]})PR_t(I_t⊗PR_t)=1_t²^T⊗(M_→(t)δ_t²^t²)。

证明下面仅给出(iii)′的详细证明。利用偏序关系, 可将引理6的(iii)转化为

$(d(x) \rightarrow d(y)) \rightarrow d(x \rightarrow y)=1 \text { 。 }$

(2)

由定理1知1~M_→(t)δ_t²^t², 式(2)的矩阵表示如下：

$\begin{aligned} & \boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{M}_d x\right)\left(\boldsymbol{M}_d y\right)\right)\left(\boldsymbol{M}_d\left(\boldsymbol{M}_{\rightarrow}(t) x y\right)\right)= \\ & \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2} \text {, } \\ & \end{aligned}$

即

$\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2 \boldsymbol{M}_d\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right) x y\left(\boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t) x y\right)=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2},$

进一步可得

$\left(\boldsymbol{M}_{\rightarrow}(t)\right)^2 \boldsymbol{M}_d\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)\right) x y x y=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}。$

从而

$\begin{gathered} \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2 \boldsymbol{M}_d\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) x^2 y^2=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}， \end{gathered}$

则有

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2 \boldsymbol{M}_d\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ & \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right) x y=\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}， \end{aligned}$

由x、y的任意性, 有

$\begin{aligned} & \left(\boldsymbol{M}_{\rightarrow}(t)\right)^2 \boldsymbol{M}_d\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ & \quad\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right)=\boldsymbol{I}_{t^2}^{\mathrm{T}} \otimes\left(\boldsymbol{M}_{\rightarrow}(t) \boldsymbol{\delta}_{t^2}^{t^2}\right)。 \end{aligned}$

于是(iii)′得证。证毕

定理7 设(X, →, 0)是有限FI代数, 且|X|=t < ∞。若d₁, d₂, …, d_n均是X上的导子, 则d=d₁·d₂·…·d_n是X上的导子当且仅当

$\begin{gathered} \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t) \boldsymbol{M}_d\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right)， \\ \boldsymbol{M}_d \boldsymbol{M}_{\rightarrow}(t)=\boldsymbol{M}_{\oplus}(t) \boldsymbol{M}_{\rightarrow}(t)\left(\boldsymbol{I}_t \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_{\rightarrow}(t)\right) \times \\ \left(\boldsymbol{I}_{t^2} \otimes \boldsymbol{M}_d\right)\left(\boldsymbol{I}_t \otimes \boldsymbol{W}_{[t, t]}\right) \boldsymbol{P} \boldsymbol{R}_t\left(\boldsymbol{I}_t \otimes \boldsymbol{P} \boldsymbol{R}_t\right)， \end{gathered}$

其中，M_d=M_d₁·M_d₂·…·M_{d_n}, M_{d_i}(i=1, 2, …, n)为d_i的结构矩阵。

证明由定理5可得d是X上的导子, 则映射d的结构矩阵M_d满足定理5(iii)′的条件。又因为d是多个映射复合而成的, 可得其结构矩阵M_d满足M_d=M_d₁·M_d₂·…·M_{d_n}, 即结论成立。证毕。

5. 小结

本文基于矩阵半张量积对有限FI代数的基本性质进行了研究, 将有限FI代数上的逻辑表达式转化为逻辑矩阵的简单运算, 并以此为基础研究了有限FI代数上的同态与同构, 彻底解决了有限FI代数同构的分类问题。同时, 有限FI代数上的导子也被用矩阵半张量积方法进行了分析, 对于给定有限FI代数上的若干导子, 得到了可直接验证各导子复合运算之后是否仍为FI代数上导子的充要条件。

期刊类型引用(2)

1.	臧慧敏，梁凤英，杜艳青，额尔敦，申键，武世奎. Ag@AgCl/TiO_2/GO催化剂制备及其光催化性能. 工业催化. 2023(05): 36-41 . 百度学术
2.	张文平. 浅谈紫外光催化氧化技术在工业废水处理中的应用. 低碳世界. 2023(07): 7-9 . 百度学术