三對(duì)角符號(hào)矩陣的最小秩完備化問題

牟谷芳, 汪天飛

(1. 樂山師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院, 四川 樂山 614004; 2. 電子科技大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 四川 成都 611731)

三對(duì)角符號(hào)矩陣的最小秩完備化問題

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

(1. 樂山師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院, 四川 樂山 614004; 2. 電子科技大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 四川 成都 611731)

利用圖論方法研究不完備的三對(duì)角全符號(hào)矩陣的最小秩完備化問題.通過符號(hào)二部圖的二部迫零法獲得不完備的三對(duì)角全符號(hào)矩陣的最小秩為1、2、3的完備化問題.

全符號(hào)矩陣; 符號(hào)二部圖; 二部迫零數(shù); 最小秩完備化問題

近年來,符號(hào)矩陣的性質(zhì)與最小秩問題受到廣泛的關(guān)注[1].為了更直觀研究最小秩問題,可利用與之對(duì)應(yīng)的n階符號(hào)有向圖來分析符號(hào)矩陣P的符號(hào)特征.然而,對(duì)于n×m型的符號(hào)模式矩陣P,不能直接應(yīng)用n階符號(hào)有向圖來研究其最小秩.因此,在文獻(xiàn)[2]中,利用符號(hào)二部圖來研究n×m符號(hào)矩陣P的符號(hào)特征.利用圖參數(shù)研究P的最小秩問題是一種常見有效的方法,其中的迫零集被廣泛應(yīng)用[3-4].迫零集最早由AIMMinimumRankSpecial-Graphs研究團(tuán)隊(duì)在研究無向圖的最小秩問題[5]中提出來的,他們給出了與迫零集相關(guān)的一些定義,如染色規(guī)則、迫零數(shù)，借助這些參數(shù)來確定無向圖最小秩的界.在無向圖迫零數(shù)的基礎(chǔ)上，該研究團(tuán)隊(duì)又將迫零數(shù)應(yīng)用于有向圖的最小秩問題中[6-7].

之后，F(xiàn).Goldberg等在無向圖和有向圖迫零數(shù)的基礎(chǔ)上提出了新的迫零變量——符號(hào)迫零變量[4]，給出了新的染色規(guī)則、符號(hào)迫零集、符號(hào)迫零數(shù);并利用符號(hào)迫零數(shù)確定了符號(hào)矩陣最小秩的下界.但無向圖、有向圖及符號(hào)矩陣的迫零數(shù)只能解決方陣的最小秩問題，對(duì)于非方陣的情況，迫零數(shù)就失效了.因此，符號(hào)矩陣最小秩問題一直是公開問題.利用圖論的方法來研究某些特殊矩陣類的完備化問題是組合矩陣論中的一個(gè)重要研究方向，近幾年來受到學(xué)者們的廣泛關(guān)注[8-9].不完備矩陣的最小秩完備化問題是將未知元素以某種特定的方式確定下來,使得完備后的矩陣的秩達(dá)到最小.本文利用二部圖的迫零法研究了不完備的三對(duì)角全符號(hào)矩陣P的最小秩完備化問題.

1 預(yù)備知識(shí)

首先，給出與迫零數(shù)相關(guān)的一些定義與性質(zhì).

定義 1.1[3]若對(duì)無向圖G的每個(gè)頂點(diǎn)進(jìn)行染色，染成白色或黑色.設(shè)u是黑色頂點(diǎn)，且v是與u連接的唯一白色頂點(diǎn)，則v被u染成黑色.若G中所有的白色頂點(diǎn)在染色過程中全部被染成黑色，則稱此染色過程為G的染色規(guī)則.

定義 1.2[3]設(shè)在G的頂點(diǎn)集中，已有的黑色頂點(diǎn)能將剩余的白色頂點(diǎn)都染黑，則稱黑色頂點(diǎn)集為顏色驅(qū)動(dòng)集.

定義 1.3[3]在G的所有顏色驅(qū)動(dòng)集中，稱頂點(diǎn)個(gè)數(shù)最少的集合為G的迫零集，記為Z(G).稱Z(G)的元素個(gè)數(shù)為迫零數(shù)，記為|Z(G)|.

例如，路的迫零集為路的任一端點(diǎn)，迫零數(shù)為1.封閉圈相鄰的2個(gè)頂點(diǎn)為其迫零集，迫零數(shù)為2.

定義 1.4[10]在一個(gè)無向圖G中，若i與j′連接，稱j′是i的一個(gè)“鄰居”點(diǎn).在一個(gè)有向圖Γ中，若(i,j′)是一條弧，稱j′是i的一個(gè)“外鄰居”點(diǎn)或i是j′的“內(nèi)鄰居”點(diǎn).特別地，環(huán)(i,i)，則i是其自身的“外鄰居”點(diǎn)或“內(nèi)鄰居”點(diǎn).

定義 1.5[10](有向圖的染色規(guī)則) 設(shè)Γ為有向圖，其頂點(diǎn)染成白色或黑色.設(shè)u是被染成黑色的頂點(diǎn)，且v是u連接的唯一的白色“外鄰居”點(diǎn)，則v被染成黑色.若所有的白色頂點(diǎn)被染成黑色，則稱此染色過程為Γ的染色規(guī)則.

下面給出符號(hào)迫零集的一些相關(guān)定義和性質(zhì).

定義 1.6[10]在符號(hào)二部圖G(U,V)中(i∈U,j′∈V)，若(i,j′)為G(U,V)的一條邊，則稱頂點(diǎn)i是頂點(diǎn)j′一個(gè)“鄰居點(diǎn)”.若邊(i,j′)的符號(hào)為正時(shí)，稱j′是i的一個(gè)“外鄰居點(diǎn)”.若邊(i,j′)的符號(hào)為負(fù)時(shí)，稱j′是i的一個(gè)“內(nèi)鄰居點(diǎn)”.頂點(diǎn)i的所有“外鄰居點(diǎn)”的個(gè)數(shù)，稱為i的出度，記為deg+(i);頂點(diǎn)i的所有“內(nèi)鄰居點(diǎn)“的個(gè)數(shù)，稱為i的入度，記為deg-(i);在U(V)的所有頂點(diǎn)中，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}).

性質(zhì) 1.1[10]若在符號(hào)二部圖G(U，V)中，存在某一頂點(diǎn)i∈U或者j′∈V為deg-(i)=0或者deg+(j′)=0，則i或者j′在每一個(gè)迫零集中.

對(duì)于全符號(hào)模式矩陣P,下面將給出其伴隨圖符號(hào)二部圖的染色規(guī)則.

Rule A 設(shè)符號(hào)模式矩陣P的符號(hào)二部圖為G(U，V)，其部集為U={1,2,…,n}(對(duì)應(yīng)P的行標(biāo)集)和V={1′,2′,…,n′}(對(duì)應(yīng)P的列標(biāo)集).

1) 若存在一頂點(diǎn)i∈U為deg-(i)=0，或者存在一頂點(diǎn)j′∈V為deg+(j′)=0,則將i與j′染成黑色;否則,轉(zhuǎn)2).

2) 若頂點(diǎn)i∈U是U中最小出度點(diǎn)與頂點(diǎn)j′∈V是V中最小入度點(diǎn)，則將i與j′染成黑色.

設(shè)i表示U中的黑色頂點(diǎn)，則與i相連接的白色頂點(diǎn)的集合

W={w′|w′是白色頂點(diǎn)∧w′→i，w′∈V}.

設(shè)G(U1,V1)是符號(hào)模式矩陣P({i}|{j})所對(duì)應(yīng)的符號(hào)二部圖，其部集為U1=U-{i}(對(duì)應(yīng)P({i}|{j})的行標(biāo)集)和V1=V-{j′}(對(duì)應(yīng)P({i}|{j})的列標(biāo)集).

設(shè)P′({i}|{j})是元素(i1,j1)為零的符號(hào)模式矩陣，G(U2,V2)是與之所對(duì)應(yīng)的符號(hào)二部圖，其部集為U2=U-{i}(對(duì)應(yīng)于P′({i}|{j})的行標(biāo)集)和V2=V-{j′}(對(duì)應(yīng)于P′({i}|{j})的列標(biāo)集).

5) 根據(jù)文獻(xiàn)[4]的定理3.2可知，若Pitjt是非奇異的，則將V中所有的白色頂點(diǎn)染成黑色;否則，轉(zhuǎn)入1)或2).

定義 1.7 在RuleA中，V中白色頂點(diǎn)被染成黑色的頂點(diǎn)集合,且個(gè)數(shù)最小的頂點(diǎn)集T稱為n階符號(hào)模式矩陣P的二部迫零集，記為Zb(P)，它的元素個(gè)數(shù)稱為二部迫零數(shù)，記為|Zb(P)|.

由文獻(xiàn)[4]的定理3.2和定義1.7，可得如下的定理.

定理 1.1 設(shè)n階的全符號(hào)模式矩陣P的迫零數(shù)為|Zb(P)|，M(P)為P的最大代數(shù)零度，則M(P)≤|Zb(P)|.

2 三對(duì)角符號(hào)模式矩陣的最小秩完備化問題

不完備的三對(duì)角全符號(hào)模式矩陣P是其部分元素已知、其余元素未知,即

在線性方程組的求解中也常用到三對(duì)角矩陣[11].不完備矩陣的最小秩完備化問題是將未知元素,以某種方式確定下來,使得完備后的矩陣的秩達(dá)到最小.矩陣的最小秩完備化問題最早由H.J.Woerdemany[12]在研究不完備塊狀矩陣的最小秩完備化問題中提出來的.在此基礎(chǔ)上，文獻(xiàn)[13-14]利用代數(shù)的方法研究了不完備矩陣的最小秩完備化問題.

3階不完備的全符號(hào)矩陣P有如下4種形式:

3階不完備的全符號(hào)矩陣的形式簡單,因此不難得到如下定理.

引理 2.1 若全符號(hào)模式矩陣P中每一行符號(hào)發(fā)生變化的次數(shù)至多為k，則mr(P)≤k+1.

證明 通過排列變換，4階不完備的三對(duì)角全符號(hào)模式矩陣P有如下4種情況.

情況 1 設(shè)

若P完備后的矩陣

為非奇異矩陣.

情況 2 設(shè)

若P完備后的矩陣

若所有未知元素“?”為“-”，P完備后的矩陣

為奇異矩陣.

再利用RuleA的2)，將頂點(diǎn)4和4′染成黑色，其余頂點(diǎn)染成白色.

為非奇異矩陣.

情況 3 設(shè)

若所有未知元素“?”為“-”，P的完備后的矩陣

再利用RuleA的2)，將頂點(diǎn)1和4′染成黑色，其余頂點(diǎn)染成白色.

再利用RuleA的3)，將G(U1,V1)中的邊{2,1′}、{3,2′}和{4,3′}的符號(hào)改變?yōu)榱愫?得矩陣

為非奇異矩陣.

情況 4 設(shè)

若P完備后的矩陣

利用RuleA的2)，將頂點(diǎn)3和3′染成黑色，其余頂點(diǎn)染成白色.

利用RuleA的3)，將G(U1,V1)中的邊(2,1′)、(4,2′)和(1,4′)的符號(hào)改變?yōu)榱愫?得矩陣

為非奇異矩陣.

下面將4階全符號(hào)模式矩陣的完備化問題推廣到n(n≥5)階全符號(hào)模式矩陣的完備化問題.

證明n(n≥5)階不完備的三對(duì)角全符號(hào)模式矩陣P有如下4種情況.

情況 1 設(shè)P=diag(+，+，+)為n階不完備的三對(duì)角全符號(hào)模式矩陣.

若P完備后符號(hào)的模式矩陣

情況 2 設(shè)P=diag(+，+，-)為n階不完備的三對(duì)角全符號(hào)模式矩陣.

若P完備后的符號(hào)矩陣

情況 3 設(shè)P=diag(+，-，-)為n階不完備的三對(duì)角全符號(hào)模式矩陣.

若P的完備化符號(hào)模式矩陣

情況 4 設(shè)P=diag(+，-，+)為n階不完備的三對(duì)角全符號(hào)模式矩陣.

若P完備后的符號(hào)模式矩陣

致謝 樂山師范學(xué)院資助科研基金(Z1521)對(duì)本文給予了資助,謹(jǐn)致謝意.

[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] 孫峰,屈小兵,汪天飛,等. 模糊團(tuán)的一個(gè)注記[J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,39(3):309-313.

[9] 楊柳嬌,舒暢,莫智文. 廣義不完備直覺模糊信息系統(tǒng)的屬性約簡[J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 李安志,任繼念,崔蔚. 三對(duì)角方程組通用性迭代解法[J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版),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

國家自然科學(xué)基金(11501260)和宿遷市自然科學(xué)基金(Z201444)

陸海霞(1976—)，女，副教授，主要從事非線性泛函分析及其應(yīng)用的研究，E-mail：luhaixia76@126.com

基金項(xiàng)目：四川省教育廳自然科學(xué)基金(17ZB0193和16TD0029)

O157

A

1001-8395(2017)03-0295-06

10.3969/j.issn.1001-8395.2017.03.003

收稿日期:2016-08-12

*通信作者簡介:汪天飛(1973—),男,教授,主要從事圖論及其應(yīng)用的研究,E-mail:wtf818@163.com