三对角符号矩阵的最小秩完备化问题

牟谷芳, 汪天飞

(1. 乐山师范学院 数学与信息科学学院, 四川 乐山 614004; 2. 电子科技大学 数学科学学院, 四川 成都 611731)

三对角符号矩阵的最小秩完备化问题

牟谷芳1,2, 汪天飞1*

(1. 乐山师范学院 数学与信息科学学院, 四川 乐山 614004; 2. 电子科技大学 数学科学学院, 四川 成都 611731)

利用图论方法研究不完备的三对角全符号矩阵的最小秩完备化问题.通过符号二部图的二部迫零法获得不完备的三对角全符号矩阵的最小秩为1、2、3的完备化问题.

全符号矩阵; 符号二部图; 二部迫零数; 最小秩完备化问题

近年来,符号矩阵的性质与最小秩问题受到广泛的关注[1].为了更直观研究最小秩问题,可利用与之对应的n阶符号有向图来分析符号矩阵P的符号特征.然而,对于n×m型的符号模式矩阵P,不能直接应用n阶符号有向图来研究其最小秩.因此,在文献[2]中,利用符号二部图来研究n×m符号矩阵P的符号特征.利用图参数研究P的最小秩问题是一种常见有效的方法,其中的迫零集被广泛应用[3-4].迫零集最早由AIMMinimumRankSpecial-Graphs研究团队在研究无向图的最小秩问题[5]中提出来的,他们给出了与迫零集相关的一些定义,如染色规则、迫零数，借助这些参数来确定无向图最小秩的界.在无向图迫零数的基础上，该研究团队又将迫零数应用于有向图的最小秩问题中[6-7].

之后，F.Goldberg等在无向图和有向图迫零数的基础上提出了新的迫零变量——符号迫零变量[4]，给出了新的染色规则、符号迫零集、符号迫零数;并利用符号迫零数确定了符号矩阵最小秩的下界.但无向图、有向图及符号矩阵的迫零数只能解决方阵的最小秩问题，对于非方阵的情况，迫零数就失效了.因此，符号矩阵最小秩问题一直是公开问题.利用图论的方法来研究某些特殊矩阵类的完备化问题是组合矩阵论中的一个重要研究方向，近几年来受到学者们的广泛关注[8-9].不完备矩阵的最小秩完备化问题是将未知元素以某种特定的方式确定下来,使得完备后的矩阵的秩达到最小.本文利用二部图的迫零法研究了不完备的三对角全符号矩阵P的最小秩完备化问题.

1 预备知识

首先，给出与迫零数相关的一些定义与性质.

定义 1.1[3]若对无向图G的每个顶点进行染色，染成白色或黑色.设u是黑色顶点，且v是与u连接的唯一白色顶点，则v被u染成黑色.若G中所有的白色顶点在染色过程中全部被染成黑色，则称此染色过程为G的染色规则.

定义 1.2[3]设在G的顶点集中，已有的黑色顶点能将剩余的白色顶点都染黑，则称黑色顶点集为颜色驱动集.

定义 1.3[3]在G的所有颜色驱动集中，称顶点个数最少的集合为G的迫零集，记为Z(G).称Z(G)的元素个数为迫零数，记为|Z(G)|.

例如，路的迫零集为路的任一端点，迫零数为1.封闭圈相邻的2个顶点为其迫零集，迫零数为2.

定义 1.4[10]在一个无向图G中，若i与j′连接，称j′是i的一个“邻居”点.在一个有向图Γ中，若(i,j′)是一条弧，称j′是i的一个“外邻居”点或i是j′的“内邻居”点.特别地，环(i,i)，则i是其自身的“外邻居”点或“内邻居”点.

定义 1.5[10](有向图的染色规则) 设Γ为有向图，其顶点染成白色或黑色.设u是被染成黑色的顶点，且v是u连接的唯一的白色“外邻居”点，则v被染成黑色.若所有的白色顶点被染成黑色，则称此染色过程为Γ的染色规则.

下面给出符号迫零集的一些相关定义和性质.

定义 1.6[10]在符号二部图G(U,V)中(i∈U,j′∈V)，若(i,j′)为G(U,V)的一条边，则称顶点i是顶点j′一个“邻居点”.若边(i,j′)的符号为正时，称j′是i的一个“外邻居点”.若边(i,j′)的符号为负时，称j′是i的一个“内邻居点”.顶点i的所有“外邻居点”的个数，称为i的出度，记为deg+(i);顶点i的所有“内邻居点“的个数，称为i的入度，记为deg-(i);在U(V)的所有顶点中，U(V)的最小出度记为δ+(U)=min{deg+(i):i∈U}(或者δ+(V)=min{deg+(j′):j′∈V}))，U(V)的最小入度记为δ-(U)=min{deg-(u):u∈U}(或者δ-(V)=min{deg-(j′):j′∈V}).

性质 1.1[10]若在符号二部图G(U，V)中，存在某一顶点i∈U或者j′∈V为deg-(i)=0或者deg+(j′)=0，则i或者j′在每一个迫零集中.

对于全符号模式矩阵P,下面将给出其伴随图符号二部图的染色规则.

Rule A 设符号模式矩阵P的符号二部图为G(U，V)，其部集为U={1,2,…,n}(对应P的行标集)和V={1′,2′,…,n′}(对应P的列标集).

1) 若存在一顶点i∈U为deg-(i)=0，或者存在一顶点j′∈V为deg+(j′)=0,则将i与j′染成黑色;否则,转2).

2) 若顶点i∈U是U中最小出度点与顶点j′∈V是V中最小入度点，则将i与j′染成黑色.

设i表示U中的黑色顶点，则与i相连接的白色顶点的集合

W={w′|w′是白色顶点∧w′→i，w′∈V}.

设G(U1,V1)是符号模式矩阵P({i}|{j})所对应的符号二部图，其部集为U1=U-{i}(对应P({i}|{j})的行标集)和V1=V-{j′}(对应P({i}|{j})的列标集).

设P′({i}|{j})是元素(i1,j1)为零的符号模式矩阵，G(U2,V2)是与之所对应的符号二部图，其部集为U2=U-{i}(对应于P′({i}|{j})的行标集)和V2=V-{j′}(对应于P′({i}|{j})的列标集).

5) 根据文献[4]的定理3.2可知，若Pitjt是非奇异的，则将V中所有的白色顶点染成黑色;否则，转入1)或2).

定义 1.7 在RuleA中，V中白色顶点被染成黑色的顶点集合,且个数最小的顶点集T称为n阶符号模式矩阵P的二部迫零集，记为Zb(P)，它的元素个数称为二部迫零数，记为|Zb(P)|.

由文献[4]的定理3.2和定义1.7，可得如下的定理.

定理 1.1 设n阶的全符号模式矩阵P的迫零数为|Zb(P)|，M(P)为P的最大代数零度，则M(P)≤|Zb(P)|.

2 三对角符号模式矩阵的最小秩完备化问题

不完备的三对角全符号模式矩阵P是其部分元素已知、其余元素未知,即

在线性方程组的求解中也常用到三对角矩阵[11].不完备矩阵的最小秩完备化问题是将未知元素,以某种方式确定下来,使得完备后的矩阵的秩达到最小.矩阵的最小秩完备化问题最早由H.J.Woerdemany[12]在研究不完备块状矩阵的最小秩完备化问题中提出来的.在此基础上，文献[13-14]利用代数的方法研究了不完备矩阵的最小秩完备化问题.

3阶不完备的全符号矩阵P有如下4种形式:

3阶不完备的全符号矩阵的形式简单,因此不难得到如下定理.

引理 2.1 若全符号模式矩阵P中每一行符号发生变化的次数至多为k，则mr(P)≤k+1.

证明 通过排列变换，4阶不完备的三对角全符号模式矩阵P有如下4种情况.

情况 1 设

若P完备后的矩阵

为非奇异矩阵.

情况 2 设

若P完备后的矩阵

若所有未知元素“?”为“-”，P完备后的矩阵

为奇异矩阵.

再利用RuleA的2)，将顶点4和4′染成黑色，其余顶点染成白色.

为非奇异矩阵.

情况 3 设

若所有未知元素“?”为“-”，P的完备后的矩阵

再利用RuleA的2)，将顶点1和4′染成黑色，其余顶点染成白色.

再利用RuleA的3)，将G(U1,V1)中的边{2,1′}、{3,2′}和{4,3′}的符号改变为零后,得矩阵

为非奇异矩阵.

情况 4 设

若P完备后的矩阵

利用RuleA的2)，将顶点3和3′染成黑色，其余顶点染成白色.

利用RuleA的3)，将G(U1,V1)中的边(2,1′)、(4,2′)和(1,4′)的符号改变为零后,得矩阵

为非奇异矩阵.

下面将4阶全符号模式矩阵的完备化问题推广到n(n≥5)阶全符号模式矩阵的完备化问题.

证明n(n≥5)阶不完备的三对角全符号模式矩阵P有如下4种情况.

情况 1 设P=diag(+，+，+)为n阶不完备的三对角全符号模式矩阵.

若P完备后符号的模式矩阵

情况 2 设P=diag(+，+，-)为n阶不完备的三对角全符号模式矩阵.

若P完备后的符号矩阵

情况 3 设P=diag(+，-，-)为n阶不完备的三对角全符号模式矩阵.

若P的完备化符号模式矩阵

情况 4 设P=diag(+，-，+)为n阶不完备的三对角全符号模式矩阵.

若P完备后的符号模式矩阵

致谢 乐山师范学院资助科研基金(Z1521)对本文给予了资助,谨致谢意.

[1] HOGBEN L. A note on minimum rank and maximum nullity of sign patterns[J]. Electronic J Linear Algebra,2011,22:203-213.

[2] HELTON J W, KLEP I, GOMEZ R. Determinant expansions of signed matrices and of certain Jacobians[J]. SIAM J Mat Anal Appl,2009,31:732-754.

[3] HOGBEN L. Minimum rank problems[J]. Linear Algebra and Its Applications,2010,432:1961-1974.

[4] GOLDBERG F, BERMAN A. Zero forcing for sign patterns[J]. Linear Algebra and Its Applications,2014,447:56-67.

[5] FALLAT S M, HOGBEN L. The minimum rank of symmetric matrices described by a graph:a survey[J]. Linear Algebra and Its Applications,2007,426:558-582.

[6] BERLINER A, CATRAL M, Hogben L, et al. Minimum rank, maximum nullity, and zero forcing number for simple digraphs[J]. Electronic J Linear Algebra,2013,26:762-780.

[7] CATRAL M, CEPEK A, HOGBEN L, et al. Zero forcing number, maximum nullity, and path cover number of subdivided graphs[J]. Electronic J Linear Algebra,2012,23:906-922.

[8] 孙峰,屈小兵,汪天飞,等. 模糊团的一个注记[J]. 四川师范大学学报(自然科学版),2016,39(3):309-313.

[9] 杨柳娇,舒畅,莫智文. 广义不完备直觉模糊信息系统的属性约简[J]. 四川师范大学学报(自然科学版),2014,37(6):802-805.

[10] BERLINER A, CATRAL M, HOGBEN L, et al. Minimum rank, maximum nullity, and zero forcing number for simple digraphs[J].Electronic J Linear Algebra,2013,26:762-780.

[11] 李安志,任继念,崔蔚. 三对角方程组通用性迭代解法[J]. 四川师范大学学报(自然科学版),2013,36(1):33-37.

[12] BOSTIAN A A, WOERDEMANY H J. Unicity of minimum rank completions for tri-diagonal partial block matrices[J]. Linear Algebra and Its Applications,2001,325:23-55.

[13] MCTIGUE J, QUINLAN R. Partial matrices whose completions have ranks bounded below[J]. Linear Algebra and Its Applications,2011,435:2259-2271.

[14] MCTIGUE J, QUINLAN R. Partial matrices whose completions all have the same rank[J]. Linear Algebra and Its Applications,2013,438:348-360.

[15] LI Z S, GAO Y B, ARAV M, et al. Sign patterns with minimum rank 2 and upper bounds on minimum ranks[J]. Linear and Multilinear Algebra,2012,61:1-14.

2010 MSC:05C05; 15A18

(编辑 余 毅)

The Minimum Rank Completion Problems for Tri-diagonal Partial Full Sign Patterns

MOU Gufang1,2, WANG Tianfei1

( 1.DepartmentofMathematicsandInformationScience,LeshanNormalUniversity,Leshan614004,Sichuan; 2.SchoolofMathematicalSciences,UniversityofElectronicScienceandTechnologyofChina,Chengdu611731,Sichuan)

In this paper，the minimum rank completion problem for a tri-diagonal partial full sign pattern P is studied by the theories and methods of graphs． The minimum rank completion for P with either mr( 珘P) = 1 or mr( 珘P) = 2 or mr( 珘P) = 3 is obtained according to the bipartite zero forcing number of the signed bipartite graph．

full sign pattern; signed bipartite graph; bipartite zero forcing number; minimum rank completion problem

2016-05-25

国家自然科学基金(11501260)和宿迁市自然科学基金(Z201444)

陆海霞(1976—)，女，副教授，主要从事非线性泛函分析及其应用的研究，E-mail：luhaixia76@126.com

基金项目：四川省教育厅自然科学基金(17ZB0193和16TD0029)

O157

A

1001-8395(2017)03-0295-06

10.3969/j.issn.1001-8395.2017.03.003

收稿日期:2016-08-12

*通信作者简介:汪天飞(1973—),男,教授,主要从事图论及其应用的研究,E-mail:wtf818@163.com