三對角符號矩陣的最小秩完備化問題

牟谷芳, 汪天飛

(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