构建具有 k-能力(k-potence)的符号模式,以及确定这些符号模式具备 k-能力的条件
《Discrete Applied Mathematics》:Construction of sign k-potent sign patterns and conditions for such sign patterns to allow k-potence
【字体:
大
中
小
】
时间:2026年09月25日
来源:Discrete Applied Mathematics 1.1
编辑推荐:
• 一种新的单次迭代算法可以构造所有具有符号幂等的符号模式。
• 开发了一种算法用于构造符号$k$-幂等的符号模式。
• 确定了符号$k$-幂等符号模式允许$k$-幂等的必要和充分条件。
**引言**
一个$n \times n$矩阵,其元素属于集合$\{+,
• 一种新的单次迭代算法可以构造所有具有符号幂等的符号模式。
• 开发了一种算法用于构造符号$k$-幂等的符号模式。
• 确定了符号$k$-幂等符号模式允许$k$-幂等的必要和充分条件。
**引言**
一个$n \times n$矩阵,其元素属于集合$\{+, -, 0\}$,称为符号模式矩阵或简称为符号模式。我们用$\mathcal{B}_n$表示所有$n \times n$符号模式的集合。如果$\mathbf{A} = [a_{ij}] \in \mathcal{B}_n$,那么$\mathcal{B}(\mathbf{A}) = \{ \mathbf{B} = [b_{ij} \in \mathbb{R}^{n \times n} | \text{sgn}(b_{ij}) = a_{ij} \forall i, j = 1, 2, \ldots, n} \}$被称为$\mathbf{A}$的质类。
加法$(+) + (-)$被称为模糊项,用$\#$表示。设$\mathbf{A} = [a_{ij}]$和$\mathbf{B} = [b_{ij}]$是两个阶为$n$的符号模式。如果对所有$i, j = 1, 2, \ldots, n$,都有$a_{ij} + b_{ij} \neq -$,则称$\mathbf{A} + \mathbf{B}$是明确定义的。如果对于每个$i$和$j$,求和$\sum_{k=1}^{n} a_{ik} b_{jk}$不包含相反符号的项,则称$\mathbf{A} \times \mathbf{B}$是明确定义的。
一个$n \times n$的符号模式$\mathbf{A}$被称为符号$k$-幂等的,当且仅当$k$是最小的正整数,使得$\mathbf{A}^k = \mathbf{A}$成立。特别地,当$k=1$时,矩阵$\mathbf{A}$被称为符号幂等的。符号幂等的符号模式类在以下操作下是封闭的(引理1.1,[1]):
- 符号相似性
- 排列相似性
- 转置
以下定理来自Eschenbach [1]:
**定理1.1**(定理1.4,[1])
如果$\mathbf{A}$是一个$n \times n$的不可约符号模式矩阵($n \geq 2$),那么$\mathbf{A}$是符号幂等的当且仅当它的每个元素都是正的。
假设$\mathbf{A}$是一个$n \times n$的实数矩阵。如果存在一个置换矩阵$\mathbf{P}$,使得$\mathbf{P}\mathbf{T}\mathbf{A}\mathbf{P} = [\mathbf{A}_{11}, \mathbf{A}_{12}, \ldots, \mathbf{A}_{nn}]$,其中$\mathbf{A}_{11}$和$\mathbf{A}_{nn}$是非空的方阵,则称$\mathbf{A}$是可约的。如果不存在这样的置换矩阵,则称$\mathbf{A}$是不可约的。设$\mathbf{A} \in \mathcal{B}_n$是一个可约符号模式。根据Frobenius定理,存在一个置换矩阵$\mathbf{P}$,使得$\mathbf{P}\mathbf{T}\mathbf{A}\mathbf{P} = \begin{pmatrix} \mathbf{A}_{11}, & \mathbf{A}_{12}, & \ldots, & \mathbf{A}_{nn} \end{pmatrix}$,其中每个$\mathbf{A}_{ij}$是一个$n \times n$的不可约矩阵或一个$1 \times 1$的零块,且$\mathbf{P}\mathbf{T}\mathbf{A}\mathbf{P}$被称为$\mathbf{A}$的Frobenius标准形。因此,如果$\mathbf{A}$是一个符号幂等的符号模式,那么根据定理1.1,$\mathbf{A}$的每个非零对角块都是每个元素都是正的符号模式。
假设$\mathbf{A}$处于Frobenius标准形,并且$\mathbf{A}$与$\begin{pmatrix} 0 & \mathbf{0} & \mathbf{0} & \ldots & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \ldots & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \ldots & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0} \end{pmatrix}$(对于某些正整数$\ell$和$p$)排列相似。那么显然,$\mathbf{A}$是符号$k$-幂等的当且仅当$\mathbf{B}$是符号$k$-幂等的。$\mathbf{A}$的零行和零列被称为额外的零行和零列。因此,我们假设所有考虑的矩阵都没有额外的零行或零列。
设$\mathcal{R}$表示一个实数矩阵可能满足也可能不满足的属性。如果每个属于$\mathcal{B}(\mathbf{A})$的矩阵都满足$\mathcal{R}$,则称符号模式$\mathbf{A}$需要$\mathcal{R}$;如果至少存在一个属于$\mathcal{B}(\mathbf{A})$的矩阵满足$\mathcal{R}$,则称$\mathbf{A}$允许$\mathcal{R}$。特别地,如果存在$\mathbf{B} \in \mathcal{B}(\mathbf{A})$使得$\mathbf{B}^2 = \mathbf{B}$,则称$\mathbf{A}$允许幂等。
如果$\mathbf{A}_1$和$\mathbf{A}_2$是两个符号模式,那么如果其中一个可以通过一系列的排列相似性、符号相似性、取反和转置从另一个生成,则称这两个模式是等价的。由于等价,$\mathbf{A}_1$允许幂等的当且仅当$\mathbf{A}_2$允许幂等。
给定两个符号模式$\mathbf{A}_1, \mathbf{A}_2 \in \mathcal{B}_n$,如果$\mathbf{A}_2$是通过将$\mathbf{A}_1$的部分或全部零元素替换为$+$或$-$得到的,则称$\mathbf{A}_1$是$\mathbf{A}_2$的子模式;否则称$\mathbf{A}_2$是$\mathbf{A}_1$的超模式。
Eschenbach [1]提出了一种构造符号幂等符号模式的算法。然而,Huang [2]后来提供了一个例子,表明该算法生成的符号模式不一定是符号幂等的。2011年,Park和Pyo [4]修改了Eschenbach的算法,并声称可以使用他们的修改版本获得所有符号幂等的符号模式。在本文中,我们提供了一个例子,证明Park和Pyo [4]的修改算法不一定会在单次迭代中终止。
在第二节中,我们提出了块符号模式的简化形式及其循环标准形。我们还回顾了关于符号$k$-幂等符号模式及其简化形式的基本定义和先前建立的结果。在第三节中,我们提出了一种构造所有可能的幂等符号模式的算法。利用定理3.1和定理3.3,我们证明该算法总是可以在单次迭代中终止。
Eschenbach [1]提出了一个问题,即用符号模式的对角块和非对角块来表征所有符号$k$-幂等的符号模式。在[7]中,Stuart等人完全表征了不可约符号$k$-幂等符号模式的结构;在[5]中,Stuart给出了表征符号$k$-幂等符号模式每个非对角块结构的必要结果。在第四节中,我们提供了一种构造所有循环标准形符号$k$-幂等符号模式的算法。
一个符号模式$\mathbf{A} \in \mathcal{B}_n$可能是符号幂等的,但仍可能不允许幂等。例如,$\mathbf{A} = [+ - 0 +]$是一个符号幂等的符号模式,但它不允许幂等。在[1]中,Eschenbach提出了表征那些允许幂等的符号幂等符号模式的问题。随后,Huang [2]确立了允许幂等的符号幂等符号模式的几个性质;Lee和Park [3]推导出了符号幂等符号模式允许幂等的必要和充分条件。在第五节中,我们考虑了循环标准形的符号$k$-幂等符号模式,并确定了在哪些条件下符号$k$-幂等符号模式允许幂等。
**代码片段**
**块矩阵的简化形式和循环标准形**
所有符号模式都承认一种对称的块划分,使得每个块的形式为$\lambda \mathbf{Y}$,其中$\lambda \in \{+, -, 0\}$,且$\mathbf{Y}$是适当大小的全$+$矩阵。如果一个符号模式的块划分不是任何其他对称块划分的真子划分,则称该块划分为最粗糙的块划分。根据[7]中的引理9,符号模式的最粗糙块划分是唯一的。
符号模式$\mathbf{A}$的简化块矩阵,记为$\mathbf{red}(\mathbf{A})$,是由其元素构成的矩阵。
**构造符号幂等符号模式的算法**
Eschenbach在[1]中给出了一种构造所有可约符号幂等符号模式的算法,并断言所有符号幂等符号模式都可以通过该算法构造。然而,在2008年,Huang [2]提供了一个例子,表明由Eschenbach算法生成的符号模式不是符号幂等的:$\mathbf{A} = \begin{pmatrix} + + + - + 0 + 0 + 0 \\ 0 + 0 + 0 \\ \vdots \\ 0 + 0 + 0 \end{pmatrix}$。
**构造符号$k$-幂等符号模式的算法**
在本节中,我们给出了一种构造所有循环标准形符号$k$-幂等符号模式的算法。假设$\mathbf{A}$是一个非零的、循环标准形的、没有额外零行和零列的可约符号模式,那么根据定理2.4,$\mathbf{A}$是符号$k$-幂等的当且仅当$\mathbf{red}(\mathbf{A})$是符号$k$-幂等的。因此,我们可以假设$\mathbf{A}$处于简化形式,其中对角块是不可约的或$1 \times 1$的零块。所以,$\mathbf{A}$的对角块要么是$1 \times 1$的零矩阵,要么是其他类型的矩阵。
**允许符号$k$-幂等的符号模式**
一个符号$k$-幂等的符号模式不一定允许$k$-幂等,如下例所示。
**示例5.1**
考虑符号模式$\mathbf{A} = [- + 0 -]$。那么$\mathbf{A}$是符号$2$-幂等的。然而,不存在$\mathbf{B} \in \mathcal{B}(\mathbf{A})$使得$\mathbf{B}^2 + 1 = \mathbf{B}$。
**允许符号$k$-幂等的条件**
在本节中,我们确定了符号$k$-幂等符号模式允许$k$-幂等的条件。设$\mathbf{A}$是一个不可约的符号$k$-幂等符号模式。Stuart等人[7]证明$\mathbf{A}$与$\begin{pmatrix} 0 & \mathbf{Y}_{11} & \ldots & \mathbf{Y}_{n2} \\ 0 & \ldots & 0 & \ldots & \mathbf{Y}_{n3} \\ \vdots \\ 0 & 0 & \ldots & \mathbf{Y}_{n\ell} & \ldots & \mathbf{Y}_{n\ell} \end{pmatrix}$(其中每个$\mathbf{Y}_{ij} \in \mathbb{R}^{n\ell})$符号相似和排列相似。
**致谢**
Partha Rana的研究工作得到了印度科学与工业研究委员会(CSIR)的支持(文件编号09/731(0186)/2021-EMR-I)。
Partha Rana | Sriparna Bandopadhyay
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号