一類樹的鄰接矩陣的Moore-Penrose廣義逆

摘要： 根據矩陣結構性質， 利用分塊矩陣技巧給出任意點數、 任意長直徑的毛毛蟲樹鄰接矩陣的Moore-Penrose廣義逆的具體形式， 為進一步研究毛毛

蟲樹的代數性質提供理論支撐.

關鍵詞： 樹; 鄰接矩陣; 分塊矩陣; Moore-Penrose廣義逆

中圖分類號： O157.5" 文獻標志碼： A" 文章編號： 1671-5489（2024）04-0759-06

Moore-Penrose Generalized Inverse ofAdjacency Matrix of a Class of Trees

WANG Yuhao1， LIU Fenjin1， XU Jianfeng2

（1. School of Science， Chang’an University， Xi’an 710064， China；2. China Mobile Communications Group Zhejiang Co.， Ltd. Hangzhou Bran

ch， Hangzhou 310005， China）

Abstract： Based on the properties of the matrix structure， we used the block matrix techniques to give the specific form for the Moore-Penro

se generalized inverse of the adjacency matrix of caterpillar trees with any number of vertices and any diameter length， which provided theoretical support for further study of the algebraic properties of caterpillar trees.

Keywords： tree; adjacency matrix; block matrix; Moore-Penrose generalized inverse

0 引 言

設圖G是一個無向簡單圖， 其頂點集為V（G）={v1，v2，…，vn}， 圖G的鄰接矩陣A（G）=（aij）n×n， 其中： 當頂點

vi與vj相鄰時， aij=1; 反之aij=0. 對任意的A∈瘙綆m×n， 如果存在X∈瘙綆n×m， 滿足下面4個條件：

AXA=A， XAX=X， （AX）T=

AX， （XA）T=XA，

則稱X是A的Moore-Penrose廣義逆矩陣［1］， 記為A+. 如果矩陣A可逆， 則易得A

+=A-1， 反之可使用滿秩分解和奇異值分解去求解A+. 但事實上， 使用上述兩種方法得到的廣義逆的表示形式可能非常復雜， 圖的相關矩陣對研究圖的性質至關重要， 因

此給出圖矩陣廣義逆的簡便計算公式具有重要意義.

目前， 關于圖矩陣廣義逆的研究受到廣泛關注： 文獻［2-4］給出了距離正則圖和完全多部圖關聯矩陣的Moore-Penrose廣義逆， 并得到了偶數個頂點的輪圖的距離矩陣的求

逆公式； Hessert等［5-6］給出了圖的無符號Laplace矩陣和邊Laplace矩陣的Moore-Penrose廣義逆， 并給出了單圈圖關聯

矩陣的逆. 但關于圖的鄰接矩陣的廣義逆的研究結果目前報道較少， 本文證明對于一個對稱矩陣A， 如果它的某些行（列）相同， 則A

+的那些行（列）也相同， 并進一步利用分塊矩陣給出任意點數、 任意長直徑毛毛蟲樹的鄰接矩陣的Moore-Penrose廣義逆的具體形式. 毛毛蟲樹在網絡重構和基尼指數方面

應用廣泛［7-8］， 矩陣的廣義逆在概率統計、 數學規劃、 數值計算以及網絡理論等領域有重要應用［9］. 因此， 給出毛毛蟲樹鄰接矩陣的Moore-Penrose廣義逆結果的具體形式有一定的理論意義.

1 預備知識

引理1［9］ 設A∈瘙綆m×n， 且有滿秩分解A=FG， 其中F∈瘙綆

m×r， G∈瘙綆r×n， r=r（A）=r（F）=r（G）. 則有A+

=GT（FTAGT）-1FT.

引理2［1］ 設A∈瘙綆m×n， 則有：

1） 若A行滿秩， 則A有右逆， 且A-1R=AT（AAT）-1;

2） 若A列滿秩， 則A有左逆， 且A-1L=

（ATA）-1AT.

易證當一個矩陣行（列）滿秩時， 它的右（左）逆即為它的Moore-Penrose廣義逆.

引理3［10］ 設A∈瘙綆m×n， rank（A

）=r， 則矩陣A存在一個滿秩分解A=FG， 其中F∈瘙綆m×r，

G∈瘙綆r×n， 矩陣G為對A進行初等行變換后得到的行最簡形矩陣的前r行， 令j1，j2，…，jr表示G每一行第一個1所在的列數

， 矩陣F為A的第j1，j2，…，jr個列向量所構成的矩陣.

下面用jk表示長度為k的全1列向量， Jm×n表示階數

為m×n的全1矩陣， Ik表示階數為k的單位矩陣， O表示全零矩陣.

2 主要結果

命題1 設A是實數域上的n階對稱矩陣， 如果矩陣A的某

些行（列）完全相同， 即ait=ajt=…=amt， 其中i，j，…，m∈{1，2，…，n}， t=1，2，…，n， 則A+的那些行（列）對應也完全相同.

證明： 由引理3知， 實數域上的n階對稱矩陣A存在一個滿秩分解A=FG，

其中矩陣G為對A進行初等行變換后得到的行最簡形矩陣的前r行." 假設矩陣A的

第i行和第j行相等， 對任意的1≤k≤n， 由于Aik=Ajk且A=AT， 則有Aki=Akj. 又因G為對A進行初等行變換后得到， 故有（GT）ik=（GT）jk. 由引理1知， 對任意的1≤t≤n， A+的第i行和第j行元素為

（A+）it=∑nk=1（GT）ik（（FTAGT）-1FT）kt=∑nk=1（GT）jk（（FT

AGT）-1FT）kt=（A+）jt.

于是A的廣義逆矩陣A+的第i行和第j行元素對應相等. 證畢.

命題2 設A=OBB

TO， 則矩陣A的Moore-penrose廣義逆矩陣為

A+=O（BT）+B+O

=OCCTO，（1）

其中C=（BT）+， CT=B+.

證明： 對任意的矩陣B， 有（BT）+=（B+）

T. 其余證明可由Moore-penrose廣義逆的定義直接驗證.

定理1 設G是一個直徑為2k+1的毛毛蟲樹， 主干是一條具有

2k個頂點的路， 每個頂點懸掛的葉子數為m1，m2，…，m2k， 且有mi≥1（i=1，2，…，2k）， 則其鄰接矩陣的Moore-Penrose廣義逆為

A+=OCＣTO，

其中CT=MNPQ，

M=Ok×k，

N=1m1jTm11m3jTm3

1m2k-1jTm2k-1，（2）

P=1m2jm21m4jm4

1m2kjm2k，（3）

Q=-1m2m1Jm2×m1-1m2m3

Jm2×m3-1m4m3Jm

4×m3-1m2k-2m2k-1Jm2k-2×m2k-1-1m2km

2k-1Jm2k×m2k-1.（4）

證明： 根據二部劃分對圖G的頂點進行標號， 其鄰接矩陣可分塊表示為

A=OBBTO，

其中，

B=Dk×kE

k×（m2+m4+…+m2k）F（m1+m3+…+m2k-1）×k

O（m1+m3+…+m2k-1）×（m2+m4+…+m2k），（5）

D=11111，

E=jTm2jTm

4jTm2k，

F=jm1jm3

jm2k-1.（6）

由命題2， 矩陣A的Moore＼|Penrose廣義逆矩陣為式（1），

其中CT=B+. 由于矩陣B既不行滿秩也不列滿秩， 因此令

CT=MNPQ，

則有

BB+B=DMD+EPD+DNF+EQFDME+EPEFMD+FNF

FME=DE

FO=B，

于是

DMD+EPD+DNF+EQF=D，（7）

DME+EPE=E，（8）FMD+FNF=F，（9）

FME=O.（10）

對于式（10）， 由于矩陣F列滿秩有左逆， 矩陣E行滿秩有右逆， 因此在式（10）兩端

左乘F-1L， 右乘E-1R， 得M=O. 將M=

O代入式（9）得FNF=F， 對FNF=F兩端同時左乘F-1L

得NF=Ik， 由于分塊矩陣N所對應的某些列在原矩陣A中完全相同， 因此由命題1知， N中那些列的元素也相同， 令

N=n11jTm1n12jTm

3…n1kjTm2k-1n21jTm1n22jTm3…n2kjTm2k-1nk1jTm1nk2jT

m3…nkkjTm2k-1，

則有

NF=m1n11m3n12…m2k-1n

1km1n21m3n22…m2k-1n2km1nk1m3nk2…m2k-1nkk=111=Ik，

解得nii=1m2i-1（i=1，2，…，k）， nij=0（i≠j）， 即N為式（2）.

將M=O代入式（8）得EPE=E， 對EPE=

E兩端同時右乘E-1R得EP=Ik， 同理可得P為式（3）.

將M，N，P代入式（7）得EQF=-D， 由于分塊矩陣Q所對應的某

些行和列在原矩陣A中完全對應相同， 因此由命題1知Q中那些行和列的元素也對應相同， 令

Q=q11Jm2×m1q12J

m2×m3…q1kJm2×m2k-1q21Jm

4×m1q22Jm4×m3…q2kJm4×m

2k-1qk1Jm2k×m1q

k2Jm2k×m3…qkkJm2k×m2k-1，

則有

EQF=m2m1q11m2m3q12…m2

m2k-1q1km4m1q21m4m3q22…m4m2k-1q2km2km1qk1m2km3q

k2…m2km2k-1qkk=-1-1-1-1-1=-D，

解得qii=-1m2im2i-1（i=1，2，…，k）， qi，i+1=-1m2im2i+1（i=1，2，…，k-1）， 其余均為0， 即Q為式（4）.

易證CT=B+也同時滿足B的Moore-Penrose廣義逆的其他條件. 證畢.

當毛毛蟲樹G的直徑為2k+2時， 結合定理1的證明， 僅需考慮根據二部劃分對G的頂點進行標號后鄰接矩陣的分塊表示. 此時， 有

A=OBBTO，

其中，B=Dk×（k+1）Ek×（m2+m4+…+m2k）

F（m1+m3+…+m2k+1）×（k+1）O（m1+m3+…+m2k+1）×（m2+m4+…+m2k），

D=111111， E=jTm2jTm4jTm2k，

F=jm1jm3jm2k+1.

類似地， 可以證明：

定理2 "設G是一個直徑為2k+2的毛毛蟲樹， 主干是一條具有（2k+1）個頂點的路， 每個頂點懸掛的葉子數為m1，m2，…，m2k+1， 且有mi≥1

（i=1，2，…，2k+1）， 則其鄰接矩陣的Moore-Penrose廣義逆為

A+=OCCTO，

其中， CT=MNP

Q， M=O（k+1）×k，

P如式（3），

N=1m1jTm11m3jTm31m2k+1jTm2k+1，

Q=-1m2m1Jm2×m1-1m2m3

Jm2×m3-1m4m3Jm4×m3-1m4m5Jm4×m5

-1m2km2k-1Jm2k×m2k-1-1m2km

2k+1Jm2k×m2k+1.

例1 設圖G1是一個直徑為7的毛毛蟲樹， 主干是一條具有6個頂點的路， 每個頂點懸掛的葉子數為2，3，4，4，3，3， 如圖1所示.

根據二部劃分對其頂點標號后， 其鄰接矩陣可分塊表示為

A=OBBTO，

其中，

B=D3×3E3

×10F9×3O9×10， D=110011

001， E=jT3OOOjT4OOOjT3， F=j2OOOj4O

OOj3.

由定理1， 其鄰接矩陣的Moore-Penrose廣義逆為

A+=OCCTO，

其中，

CT=MNP

Q， M=O3×3，

N=12jT2OOO1

4jT4OOO13jT3， P=13j3OOO14j4OOO

13j3， Q=-16J3

×2-112J3×4OO-116J4

×4-112J4×3OO

-19J3×3.

例2 設圖G2是一個直徑為8的毛毛蟲樹， 主干是一條具有7個頂點的路， 每個頂點懸掛的葉子數為2，2，3，3，3，4，4， 如圖2所示.

根據二部劃分對其頂點標號后， 其鄰接矩陣可分塊表示為

A=OBBTO，

其中，

B=D3×4E3×9F12×4O12×9，" D=110001100011，E=jT2OOOjT3

OOOjT

4，" F=j2OOO

Oj3OOOOj

3OOOOj4.

由定理2知， 其鄰接矩陣的Moore-Penrose廣義逆為

A+=OCCTO，

其中

CT=MNP

Q， M=O4×3，

N=12j

T2OOOO13jT3OOOO13jT3O

OOO14jT4，

P=12j2OOO

13j3OOO14

j4，Q=-14J2

×2-16J2×3OOO-19J3×3-19J3×3O

OO-112J4×3

-116J4×4.

參考文獻

［1］ BEN-ISRAEL A， GREVILLE T N E. Generalized Inverses： Theory and Applications ［M］. 2nd ed. New York： Springer， 2003： 40-51.

［2］ AZIMI A， BAPAT R B. Moore-Penrose Inverse of the Incidence Matrix of a Distan ce Regular Graph ［J］. Linear Algebra and Its Applications， 2018， 551： 92-103.

［3］ AZIMI A， BAPAT R B. The Moore-Penrose Inverse of the Incidence Matrix of Comp lete Multipartite and Bi-block Graphs ［J］. Discrete Mathematics， 2019， 342（8）： 2393-2401.

［4］ BALAJI R， BAPAT R B， GOEL S. An Inverse Formula for "the Distance Matrix of a Wheel Graph with an Even Number of Vertices ［J］. Linear Algebra and Its Applications， 2021， 610： 274-292.

［5］ HESSERT R， MALLIK S. Moore-Penrose Inverses of the "Signless Laplacian and Edge-Laplacian of Graphs ［J］. Discrete Mathematics， 2021， 344（8）： 112451-1-112451-15.

［6］ HESSERT R， MALLIK S. The Inverse of the Incidence Matrix of a Unicyclic Graph ［J］. Linear and Multilinear Algebra， 2023， 71（4）： 513-527.

［7］ LINZ S， SEMPLE C. Caterpillars on Three and Four Leaves Are Sufficient to Reconstruct Binary Normal Networks ［J］. Journal of Mathematical Biology， 2020， 81（4/5）： 961-980.

［8］ ZHANG P P， DEY D K. The Degree Profile and Gini Index of Random Caterpillar Trees ［J］. Probability in the Engineering and Informational Sciences， 2019， 33（4）： 511-527.

［9］ 王松桂， 楊振海. 廣義逆矩陣及其應用 ［M］. 北京： 北京工業大學出版社， 1996： 82-123. （WANG S G， YANG Z H. Generalized Inverse Matrix and Its Application ［M］. Beijing： Beijing Polytechnic University Press， 1996： 82-123.）

［10］ 程云鵬， 張凱院， 徐仲. 矩陣論 ［M］. 西安： 西北工業大學出版社， 2006： 220-225. （CHENG Y P， ZHANG K Y， XU Z. Matrix Theory ［M］. Xi’an： Northwestern Polytechnical University Press， 2006： 220-225.）

（責任編輯：" 趙立芹）