DOI: 10.12677/PM.2024.141035, PDF, HTML, XML,  被引量    科研立项经费支持
作者: 张利萍, 李思琸：云南财经大学，统计与数学学院，云南 昆明；苏 瑞：武汉生物工程学院，计算机科学与技术学院，湖北 武汉
关键词: 热带半环；热带矩阵；拟可逆；Tropical Semiring； Tropical Matrix； Quasi-Invertible

文章引用：张利萍, 苏瑞, 李思琸. S _max上2 × 2拟可逆矩阵的研究[J]. 理论数学, 2024, 14(1): 341-346. https://doi.org/10.12677/PM.2024.141035

1. 引言

热带几何是一种建立在热带半环 $ℝ$ 上的几何。热带半环是具有加法 $\oplus$ 和乘法 $\otimes$ 两种运算的集合 ${ℝ}_{\max }:=ℝ\cup \left\{-\infty \right\}$ ，其中加法为取最大，乘法为取加法。热带几何最初是在20世纪末的初期出现的，但围绕这个主题的基本定理和定义的整合在90年代才开始真正地出现。1990年，为解决热带中的加法不可逆，Max Plus引入balance，将热带推广到对称max-plus半环 ${\mathbb{S}}_{\max }$ 上 [1] 。随后在1992年，Francois Baccelli在对称max-plus半环中对矩阵的结构进行了推广和研究 [2] 。2014年，Pascal Benchimol建立了多面体基本点和边的热带对应概念，产生了单纯形法热带化的几何解释，并将经典线性规划的复杂度转化为热带线性规划 [3] 。

热带几何是一个强大的工具，因为它允许我们用线性、组合的方式分析固有的非线性问题。一般策略是先将经典非线性系统转换为热带线性系统，然后使用热带线性代数的方法来提供原始系统的信息 [4] 。由于在应用领域中出现的许多问题都是自然地用热带线性方程表示的，作为热带线性代数应用的直接结果，热带半环上的矩阵自20世纪60年代以来一直是积极研究的主题。在2018年，Zhang首次使用热带矩阵半环作为平台来构造密码系统，提出了基于热带矩阵的公钥密码体制 [5] 。之后Grigoreiv等人进行了改进，提出了基于热带矩阵半环的半直积的公钥密码体制 [6] 。对此，2022年黄华伟和李春华提出了一种攻击方法 [7] ，其中离不开2 × 2矩阵。

本文先对对称max-plus半环 ${\mathbb{S}}_{\max }$ 上的2 × 2矩阵的结构进行研究，得到2 × 2矩阵拟可逆的条件；再对系数矩阵拟可逆的二元一次方程解进行讨论，得出在 $A^{adj}b$ 非符号的情况下，方程 $AX\Delta b$ 的解与 $\left(\det A\right)X\Delta A^{adj}b$ 的解并不等价。

2. 预备知识

定义1 [8] 热带半环 ${ℝ}_{\max }$ 指在 $ℝ\cup \left\{-\infty \right\}$ 上，对于任意 $a,b\in {ℝ}_{\max }$ ，定义加法 $\oplus$ 和乘法 $\otimes$ 如下：

$a\oplus b=\max \left\{a,b\right\};a\otimes b=a+b$ .

显然，0是 $\otimes$ 上的单位元； $\epsilon :=-\infty$ 是 $\oplus$ 上的零元。

性质1 [1] 对于任意 $a,b,c\in {ℝ}_{\max }$ ，有：

1) $a\otimes b=b\otimes a$ ;

2) $a\oplus b=b\oplus a$ ;

3) $\left(a\oplus b\right)\oplus c=a\oplus \left(b\oplus c\right)$ ;

4) $\left(a\otimes b\right)\otimes c=a\otimes \left(b\otimes c\right)$ ;

5) $a\otimes \left(b\oplus c\right)=\left(a\otimes b\right)\oplus \left(a\otimes c\right)$ .

考虑基于Dioid结构下的 ${ℝ}_{\max }^2$ 代数，对于 $\left(x^{\prime },x^{″}\right),\left(y^{\prime },y^{″}\right)\in {ℝ}_{\max }^2$ ，

$\left(x^{\prime },x^{″}\right)\oplus \left(y^{\prime },y^{″}\right):=\left(x^{\prime }\oplus y^{\prime },x^{″}\oplus y^{″}\right)$ ,

$\left(x^{\prime },x^{″}\right)\otimes \left(y^{\prime },y^{″}\right):=\left(x^{\prime }{y}^{\prime }\oplus x^{″}{y}^{″},x^{\prime }{y}^{″}\oplus x^{″}{y}^{\prime }\right)$ .

显然， $\left(0,\epsilon \right)$ 是 $\otimes$ 上的单位元； $\left(\epsilon ,\epsilon \right)$ 是 $\oplus$ 上的零元。

定义2 [1] 设 $x=\left(x^{\prime },x^{″}\right)\in {ℝ}_{\max }^2$ ，定义

$\ominus x:=\left(x^{″},x^{\prime }\right)$ ;

$\left|x\right|:=x^{\prime }\oplus x^{″}$ ;

$x^{•}:=\left(\left|x\right|,\left|x\right|\right)$ .

性质2 [1] 对于任意 $a,b\in {ℝ}_{\max }^2$ ， $a\ne b$ ，有：

1) $a^{•}={\left(\ominus a\right)}^{•}$ ;

2) ${\left(a^{•}\right)}^{•}=a^{•}$ ;

3) $a\otimes b^{•}={\left(a\otimes b\right)}^{•}$ ;

4) $\ominus \left(\ominus a\right)=a$ ;

5) $\ominus \left(a\oplus b\right)=\left(\ominus a\right)\oplus \left(\ominus b\right)$ ;

6) $\ominus \left(a\otimes b\right)=\left(\ominus a\right)\otimes b=a\otimes \left(\ominus b\right)$ ;

7) $\left(\ominus a\right)\otimes \left(\ominus b\right)=a\otimes b$ .

特别的， $a\ominus b=a\oplus \left(\ominus b\right)$ 。

定义3 [1] 设 $x=\left(x^{\prime },x^{″}\right),y=\left(y^{\prime },y^{″}\right)\in {ℝ}_{\max }^2$ ，若 $x^{\prime }\oplus y^{″}=x^{″}\oplus y^{\prime }$ ，称 $x\Delta y$ 。

特别地， $\Delta$ 不具有传递性，不是等价关系，我们考虑 ${ℝ}_{\max }^2$ 上的 $\mathcal{R}$ 关系：

$x\mathcal{R}y\iff \{\begin{array}{l}{x}^{\prime }\oplus y^{″}=x^{″}\oplus y^{\prime },若x^{\prime }\ne x^{″}或y^{\prime }\ne y^{″},\\ \left(x^{\prime },x^{″}\right)=\left(y^{\prime },y^{″}\right),其他情况.\end{array}$

可以验证， $\mathcal{R}$ 关系是 ${ℝ}_{\max }^2$ 上的一种等价关系。

定义4 [1] 记 ${\mathbb{S}}_{\max }:={ℝ}_{\max }^2/\mathcal{R}$ ，称为对称max-plus半环。对 $a,b\in {ℝ}_{\max }^2$ ，记 $\overline{\left(a,b\right)}$ 为 $\left(a,b\right)$ 所在的等价类。

性质3 [1] 对 $t\in {ℝ}_{\max }$ ，如下结论成立：

$\overline{\left(t,\epsilon \right)}=\left\{\left(t,x^{″}\right);x^{″}<t\right\}$ ;

$\overline{\left(\epsilon ,t\right)}=\left\{\left(x^{\prime },t\right);x^{\prime }<t\right\}$ ;

$\overline{\left(t,t\right)}=\left\{t^{•}=\left(t,t\right)\right\}$ .

记

${ℝ}_{\max }^{\oplus }:=\left\{\overline{\left(t,\epsilon \right)}|t\in {ℝ}_{\max }\right\}$ ;

${ℝ}_{\max }^{\ominus }:=\left\{\overline{\left(\epsilon ,t\right)}|t\in {ℝ}_{\max }\right\}$ ;

${ℝ}_{\max }^{•}:=\left\{\overline{\left(t,t\right)}|t\in {ℝ}_{\max }\right\}$ .

显然， ${\mathbb{S}}_{\max }={ℝ}_{\max }^{\oplus }\cup {ℝ}_{\max }^{\ominus }\cup {ℝ}_{\max }^{•}$ ， ${ℝ}_{\max }^{\oplus }\cap {ℝ}_{\max }^{\ominus }\cap {ℝ}_{\max }^{•}=\left\{\left(\epsilon ,\epsilon \right)\right\}$ 。特别地，映射 ${ℝ}_{\max }\to {ℝ}_{\max }^{\oplus }$ ： $a\mapsto \overline{\left(a,\epsilon \right)}$ 定义了 ${ℝ}_{\max }$ 到 ${ℝ}_{\max }^{\oplus }$ 的同构映射。为方便起见，后面将用 ${ℝ}_{\max }$ 表示 ${ℝ}_{\max }^{\oplus }$ 。另外，对任意 $s\in {ℝ}_{\max }$ ，都有 $\left|s\right|=\left|\ominus s\right|=\left|s^{•}\right|=s\in {ℝ}_{\max }$ 。

易验证，对于任意 $a,b\in {\mathbb{S}}_{\max }$ ，有

$a\oplus b=\{\begin{array}{l}a\text{,}若\left|a\right|>\left|b\right|或a=b;\\ b\text{,}若\left|a\right|<\left|b\right|;\\ {\left|a\right|}^{•}\text{,}若\left|a\right|=\left|b\right|且a\ne b\text{.}\end{array}$

性质4 [1] 记 ${ℝ}_{\max }^{\vee }:={ℝ}_{\max }^{\oplus }\cup {ℝ}_{\max }^{\ominus }$ ，有 ${ℝ}_{\max }^{\vee }\backslash \left\{\epsilon \right\}={\mathbb{S}}_{\max }\backslash {ℝ}_{\max }^{•}$ 。若 $a\in {ℝ}_{\max }^{\vee }$ ，称a是符号的。

定义4 [1] 设n阶矩阵 $A\in Ma{t}_{n\times n}\left({\mathbb{S}}_{\max }\right)$ ，A的行列式为

$\det A={\oplus }_{\sigma }\mathrm{sgn}\left(\sigma \right){\otimes }_{i=1}^n{a}_{i\sigma \left(i\right)}$ ,

其中 $\sigma$ 是一种排列。当 $\sigma$ 为奇排列时， $\mathrm{sgn}\left(\sigma \right)=\ominus 0$ ；当 $\sigma$ 为偶排列时， $\mathrm{sgn}\left(\sigma \right)=0$ 。

定义5 设矩阵 $A\in Ma{t}_{n\times n}\left({\mathbb{S}}_{\max }\right)$ ，若 $\det A\notin {ℝ}_{\max }^{•}$ ，则称A是拟可逆的，否则称A是非拟可逆的。

3. 2 × 2拟可逆矩阵

性质5 矩阵 $\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\in Ma{t}_{2\times 2}\left({\mathbb{S}}_{\max }\right)$ 拟可逆当且仅当下列条件之一成立：

(i) $\left|ad\right|>\left|bc\right|$ 且 $a,d\notin {ℝ}_{\max }^{•}$ ，

(ii) $\left|ad\right|<\left|bc\right|$ 且 $b,c\notin {ℝ}_{\max }^{•}$ ，

(iii) $\left|ad\right|=\left|bc\right|$ ， $a,b,c,d\notin {ℝ}_{\max }^{•}$ 且 $ad=\ominus bc$ 。

证明 对任意矩阵 $A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$ ，行列式 $\det A=ad\ominus bc$ ，有以下三种情况：

1) 当 $\left|ad\right|>\left|bc\right|$ 时， $\det A=ad$ ，

(i) 若 $a,d$ 至少有一个属于 ${ℝ}_{\max }^{•}$ ， $\det A=ad\in {ℝ}_{\max }^{•}$ ，A非拟可逆；

(ii) 若 $a,d$ 都不属于 ${ℝ}_{\max }^{•}$ ， $\det A=ad\notin {ℝ}_{\max }^{•}$ ，A拟可逆。

2) 当 $\left|ad\right|<\left|bc\right|$ 时， $\det A=\ominus bc$ ，

(i) 若 $b,c$ 至少有一个属于 ${ℝ}_{\max }^{•}$ ， $\det A=\ominus bc\in {ℝ}_{\max }^{•}$ ，A非拟可逆；

(ii) 若 $b,c$ 都不属于 ${ℝ}_{\max }^{•}$ ， $\det A=\ominus bc\notin {ℝ}_{\max }^{•}$ ，A拟可逆。

3) 当 $\left|ad\right|=\left|bc\right|$ 时，

(i) 若 $a,b,c,d$ 中至少有一个属于 ${ℝ}_{\max }^{•}$ ，由性质2， $\det A\in {ℝ}_{\max }^{•}$ ，A非拟可逆；

(ii) 若 $a,b,c,d$ 中全不属于 ${ℝ}_{\max }^{•}$ ，

若 $a,b,c,d$ 全属于 ${ℝ}_{\max }^{\ominus }$ ，即 $ad=bc$ ， $\det A=ad\ominus bc\in {ℝ}_{\max }^{•}$ ，A非拟可逆；

若 $a,b,c,d$ 中有三个属于 ${ℝ}_{\max }^{\ominus }$ ，即 $ad=\ominus bc$ ， $\det A=ad=\ominus bc\notin {ℝ}_{\max }^{•}$ ，A拟可逆；

若 $a,b,c,d$ 中有两个属于 ${ℝ}_{\max }^{\ominus }$ ，即 $ad=bc$ ， $\det A\in {ℝ}_{\max }^{•}$ ，A非拟可逆；

若 $a,b,c,d$ 中有一个属于 ${ℝ}_{\max }^{\ominus }$ ，即 $ad=\ominus bc$ ， $\det A\notin {ℝ}_{\max }^{•}$ ，A拟可逆；

若 $a,b,c,d$ 全属于 ${ℝ}_{\max }$ ，即 $ad=\ominus bc$ ， $\det A\in {ℝ}_{\max }^{•}$ ，A非拟可逆。

综上所述，性质成立。

例1

1) $\left|\begin{array}{cc}5& 2\\ 3^{•}& \ominus 1\end{array}\right|=5\otimes \ominus 1\ominus 2\otimes 3^{•}=\ominus 6\notin {ℝ}_{\max }^{•}$ ，矩阵拟可逆，此时 $\left|5\otimes 1\right|>\left|2\otimes 3\right|$ 且 $5,\ominus 1\notin {ℝ}_{\max }^{•}$ ，符合条件(i)；

2) $\left|\begin{array}{cc}{1}^{•}& 2\\ 7& \ominus 3\end{array}\right|=1^{•}\otimes \ominus 3\ominus 2\otimes 7=\ominus 9\notin {ℝ}_{\max }^{•}$ ，矩阵拟可逆，此时 $\left|7\otimes 2\right|>\left|1\otimes 3\right|$ 且 $7,2\notin {ℝ}_{\max }^{•}$ ，符合条件(ii)；

3) $\left|\begin{array}{cc}3& 6\\ 4& \ominus 7\end{array}\right|=3\otimes \ominus 7\ominus 4\otimes 6=\ominus 10\notin {ℝ}_{\max }^{•}$ ，矩阵拟可逆，此时 $\left|7\otimes 3\right|=\left|4\otimes 6\right|$ ， $3,6,4,\ominus 7\notin {ℝ}_{\max }^{•}$ 且 $3\otimes \ominus 7=\ominus 4\otimes 6$ ，符合条件(iii)；

4) $\left|\begin{array}{cc}5& 6\\ 6& 7\end{array}\right|=5\otimes 7\ominus 6\otimes 6={12}^{•}\in {ℝ}_{\max }^{•}$ ，矩阵非拟可逆，此时 $\left|5\otimes 7\right|=\left|6\otimes 6\right|$ ， $5,6,7\notin {ℝ}_{\max }^{•}$ ，但 $5\otimes 7\ne \ominus 6\otimes 6$ ，不符合任一个条件。

4. 系数矩阵拟可逆的二元一次方程解

对于二元一次方程组

$AX\Delta b$ ,

其中， $A=\left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right]$ ， $b=\left[\begin{array}{c}e\\ f\end{array}\right]$ ， $X=\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]$ 。

1) 若A拟可逆(即 $\det A\notin {ℝ}_{\max }^{•}$ )， $A^{adj}b$ 是符号的(即 $A^{adj}b\in {ℝ}_{\max }^{\vee }$ )，对于方程 $AX\Delta b$ ，左乘 $A^{adj}$ ，有 $A^{adj}AX\Delta A^{adj}b$ ，由 $A^{adj}A\Delta \det A\cdot I$ ，得 $\left(\det A\right)X\Delta A^{adj}b$ 。即Cramer法则 [1] ，方程 $AX\Delta b$ 有唯一符号解

$X={\left(\det A\right)}^{-1}{A}^{adj}b$ .

2) 若A拟可逆， $A^{adj}b$ 非符号的，此时方程 $AX\Delta b$ 与方程 $\left(\det A\right)X\Delta A^{adj}b$ 的解并不等价。

例2 对方程

$\{\begin{array}{l}5x\oplus 1y\Delta 0\\ 2x\oplus 5y\Delta 4\end{array}$ .

解 $\det A=\left|\begin{array}{cc}5& 1\\ 2& 5\end{array}\right|=10\notin {ℝ}_{\max }^{•}$ ，

对于

$\left(\det A\right)X\Delta A^{adj}b\to 10\left[\begin{array}{c}x\\ y\end{array}\right]\Delta \left[\begin{array}{cc}5& \ominus 1\\ \ominus 2& 5\end{array}\right]\left[\begin{array}{c}0\\ 4\end{array}\right]\to 10\left[\begin{array}{c}x\\ y\end{array}\right]\Delta \left[\begin{array}{c}{5}^{•}\\ 9\end{array}\right]$ ,

方程有解 $\{\begin{array}{l}x=t,t\in {ℝ}_{\max }^{•}\\ y=-1\end{array}$ 。取一组解 $\{\begin{array}{l}x=1^{•}\\ y=-1\end{array}$ 带入方程 $\{\begin{array}{l}5x\oplus 1y\Delta 0\\ 2x\oplus 5y\Delta 4\end{array}$ ，有

$\{\begin{array}{l}5\otimes 1^{•}\oplus 1\otimes \left(-1\right)\Delta 6^{•}\\ 2\otimes 1^{•}\oplus 5\otimes \left(-1\right)\Delta 4\end{array}$ ,

不成立。

而方程的解为

$\{\begin{array}{l}x=t,\left|t\right|<-5,t\in {\mathbb{S}}_{\max }或x=-5\\ y=-1\end{array}$ ,

两者解集有交集。

例3 对方程

$\{\begin{array}{l}3x\oplus 4y\Delta 2^{•}\\ 1^{•}x\oplus \ominus 3y\Delta 0\end{array}$ .

解 由 $\left|\begin{array}{cc}3& 4\\ 1^{•}& \ominus 3\end{array}\right|=\ominus 6\notin {ℝ}_{\max }^{•}$ ，

对于方程

$\left(\det A\right)X\Delta A^{adj}b\to \ominus 6\left[\begin{array}{c}x\\ y\end{array}\right]\Delta \left[\begin{array}{cc}\ominus 3& \ominus 4\\ 1^{•}& 3\end{array}\right]\left[\begin{array}{c}{2}^{•}\\ 0\end{array}\right]\to \ominus 6\left[\begin{array}{c}x\\ y\end{array}\right]\Delta \left[\begin{array}{c}{5}^{•}\\ 3^{•}\end{array}\right]$ ,

方程只有 ${ℝ}_{\max }^{•}$ 解，解为 $\left\{x|x\in {ℝ}_{\max }^{•}\right\}$ ， $\left\{y|y\in {ℝ}_{\max }^{•}\right\}$ 。但这并不是方程 $\{\begin{array}{l}3x\oplus 4y\Delta 2^{•}\\ 1^{•}x\oplus \ominus 3y\Delta 0\end{array}$ 的解，取一组解 $\{\begin{array}{l}x=1^{•}\\ y=0^{•}\end{array}$ 带入，有

$\{\begin{array}{l}3\otimes 1^{•}\oplus 4\otimes 0^{•}\Delta 4^{•}\\ 1^{•}\otimes 1^{•}\oplus \ominus 3\otimes 0^{•}\Delta 3^{•}\end{array}$ ,

不成立。而方程 $\{\begin{array}{l}3x\oplus 4y\Delta 2^{•}\\ 1^{•}x\oplus \ominus 3y\Delta 0\end{array}$ 无解。

对于二元一次方程组 $AX\Delta b$ ，若A拟可逆， $A^{adj}b$ 符号，那么方程 $AX\Delta b$ 的解与 $\left(\det A\right)X\Delta A^{adj}b$ 的解等价，且有唯一符号解 $X={\left(\det A\right)}^{-1}{A}^{adj}b$ ；而 $A^{adj}b$ 非符号时，方程 $AX\Delta b$ 的解与 $\left(\det A\right)X\Delta A^{adj}b$ 的解并不等价，且两者解暂无关系，这就需要进一步讨论“ $\Delta$ ”的相关性质及传递条件。同时，这些结果为后续探究n元一次方程组解提供帮助。

基金项目

云南财经大学研究生创新基金项目(2023YUFEYC072)。

参考文献

[1]	Plus, M. (1990) Linear Systems in (Max, +)-Algebra. Proceedings of the 29th Conference on Decision and Control, Honolulu, December 1990, 6 p. https://www.researchgate.net/publication/224657696_Linear_systems_in_max_algebra
[2]	Baccelli, F., Cohen, G., Olsder, G.J., et al. (1992) Synchronization and Linearity: An Algebra for Discrete Event Systems. John Wiley & Sons, New York.
[3]	Benchimol, P. (2014) Tropical Aspects of Linear Programming. Ecole Polytechnique. https://pasteur.hal.science/INRIA/tel-01198482
[4]	Simon, I. (1988) Recognizable Sets with Multiplicities in the Tropical Semiring. In: Chytil, M.P., Koubek, V. and Janiga, L., Eds., Lecture Notes in Computer Science, Vol. 324, Springer, Berlin, Heidelberg, 107-120. https://doi.org/10.1007/BFb0017135
[5]	Zhang, Y. (2018) Cryptanalysis of a Key Exchange Protocol Based on the Ring Ep(m). Applicable Algebra in Engineering, Communication and Computing, 29, 103-112. https://doi.org/10.1007/s00200-017-0332-0
[6]	Grigoriev, D. and Shpilrain V. (2019) Tropical Cryptography II: Extensions by Homomorphisms. Communications in Algebra, 47, 4224-4229. https://doi.org/10.1080/00927872.2019.1581213
[7]	黄华伟, 李春华. 一种基于热带半环的密钥建立协议的安全性分析[J]. 计算机科学, 2022, 49(z1): 571-574.
[8]	Cuninghame-Green, R. (1979) Minimax Algebra. In: Fandel, G. and Trockel, W., Eds., Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 13-15. https://doi.org/10.1007/978-3-642-48708-8