杜志斌

(肇慶學院數(shù)學與統(tǒng)計學院，肇慶 526061)

?

具有極大P-集的實對稱陣及其伴隨圖

杜志斌*

(肇慶學院數(shù)學與統(tǒng)計學院，肇慶 526061)

摘要：實對稱陣的P-集是一個基于矩陣的特征值重數(shù)以及Cauchy插值定理所提出的定義．設A為一個n階實對稱陣，記mA(0)為A的特征值為0的(代數(shù))重數(shù)，并記A(S)為將A的第i1,i2,…,ik行與第i1,i2,…,ik列去掉后所得的主子陣，其中S={i1,i2,…,ik}為{1,2,…,n}的一個非空子集．特別地，當mA(S)(0)=mA(0)+|S|時，稱S為A的一個P-集．記PS(A)為實對稱陣A的P-集所含元素個數(shù)的最大值．基于每個n階實對稱陣至多包含?n/2」個元素，文中研究了滿足PS(A)=?n/2」的n階實對稱陣A的結(jié)構特點，進而給出此類矩陣的若干性質(zhì)，并對n為偶數(shù)時A的伴隨圖進行特征刻畫，而對n為奇數(shù)時A的伴隨圖給出了猜想，推廣了具有極大P-集的樹矩陣的相關結(jié)果．

關鍵詞：實對稱陣； 伴隨圖； 特征值重數(shù)； P-集

給定一個n階實對稱陣A，根據(jù)A的主對角線以外的元素的零位模式，可定義A的伴隨圖，具體來說，n階實對稱陣A=(aij)的伴隨圖是以V={1,2,…,n}為點集，以E={ij|i≠j,aij≠0}為邊集的無向簡單圖．特別地，若實對稱陣A的伴隨圖為樹，則稱A為樹矩陣．

反過來，給定一個具有n個點的無向簡單圖G，可定義出一個相應的實對稱矩陣類：

S(G)={A|A是一個n階實對稱陣,且A的伴隨圖為G}．

顯然，S(G)中矩陣的主對角線元素可任意選取,各個矩陣的主對角線以外的元素的零位模式是一致的，并由圖G唯一決定．

對于任意實對稱陣A，若0是A的一個特征值，則記mA(0)為特征值為0的(代數(shù))重數(shù)．此外，若0不是A的特征值，則習慣上記作mA(0)=0．

設S={i1,i2,…,ik}為{1,2,…,n}的一個非空子集，現(xiàn)將n階實對稱陣A的第i1,i2,…,ik行與第i1,i2,…,ik列去掉，所得的主子陣記為A(S)．根據(jù)Cauchy插值定理[1] 242-243，可得

其中S為{1,2,…,n}的一個非空子集．JOHNSON等[2]353將滿足

mA(S)(0)=mA(0)+|S|

的集合S稱為實對稱陣A的一個P-集．特別地，若S是實對稱陣A的P-集，且S只含一個元素，比如S={i}，則稱i為A的一個P-點．

根據(jù)Cauchy插值定理，顯然P-集的每個元素都是P-點，但在一般情況下，若干個P-點所組成的集合并不是P-集．FERNANDES與DA CRUZ[3]、NELSON與SHADER[4]分別給出了若干類矩陣，使其任意多個P-點所組成的集合是P-集．

此外，P-集所含元素個數(shù)也是一個研究熱點．JOHNSON等[2]給出了樹矩陣的P-集所含元素個數(shù)的下界．而在研究實對稱陣的P-集所含元素個數(shù)的上界時，KIM與SHADER定義了PS(A)，表示實對稱陣A的P-集所含元素個數(shù)的最大值[5]400；證明了PS(A)≤?n/2」，其中A為任意n階實對稱陣，而且上界?n/2」可達[5]402-403．

文獻[6]研究了滿足PS(A)≤?n/2」的n階樹矩陣A，完全刻畫出A的伴隨圖(樹)．有趣的是，這些樹恰恰是匹配數(shù)為?n/2」的樹．本文將研究范圍從樹矩陣延伸到所有實對稱陣，研究了滿足PS(A)≤?n/2」的n階實對稱陣A，給出其相關性質(zhì)，并對n為偶數(shù)時A的伴隨圖進行特征刻畫，而對n為奇數(shù)時A的伴隨圖給出了猜想，推廣了樹矩陣的相關結(jié)果[6]．

1預備知識與引理

首先介紹2個重要引理．

引理1[6]29-30設A為n階實對稱陣，則PS(A)≤?n/2」．特別地，若PS(A)≤?n/2」，且α是A的一個P-集，|α|=?n/2」，則有下述情形之一：

(i)n為偶數(shù)，且mA(0)=0，從而mA(α)(0)=n/2，這表明A(α)的秩為0，即A(α)=0；

(ii)n為奇數(shù)，且mA(0)=1，從而mA(α)(0)=(n+1)/2，這表明A(α)的秩為0，即A(α)=0；

(iii)n為奇數(shù)，且mA(0)=0，從而mA(α)(0)=(n-1)/2，這表明A(α)的秩為1．

給定一個m×n矩陣A，記ρA為A的項秩，即矩陣A中兩兩不在同一行或者同一列的非零元素的最大個數(shù)．特別地，若rank A=m，則ρA=m．

設A、B皆為m×n矩陣，則由文獻[1]13知:

rank(A+B)≤rankA+rankB．

證明首先有

等價地，

即

□

2主要結(jié)果

首先考慮矩陣階數(shù)為偶數(shù)時的情形．

注意到，

|A|=(-1)n2/4|N|·|NT|=(-1)n2/4|N|2.

現(xiàn)取V=α，結(jié)果可證．

□

下面考慮矩陣階數(shù)為奇數(shù)時的情形．

由引理1(ii)、(iii)，可得A(α)的秩為0(即A(α)=0)或為1．

情形1：A(α)的秩為0，即A(α)=0．

首先，由A(α)=0可知G(α)為空圖，且A的結(jié)構如下：

現(xiàn)取V=α，結(jié)果可證．

情形2：A(α)的秩為1．

首先，由A(α)的秩為1，以及A為實對稱陣，可知G(α)包含一個完全圖(可能只含一個點)以及若干個孤立點．

此外，A的結(jié)構如下：

現(xiàn)取V=α，結(jié)果可證．

□

設G為具有n個點的圖，當n為偶數(shù)時，定理1給出了S(G)中存在實對稱陣A且PS(A)=n/2的一個必要條件．事實上，這也是S(G)中存在實對稱陣A使得PS(A)=n/2的一個充分條件．于是有下述定理．

定理3設G為具有n個點的圖，其中n為偶數(shù)．下述2個條件是等價的：

(a)S(G)中存在實對稱陣A使得PS(A)=n/2；

證明由定理1可得(a)?(b)．下面證明(b)?(a)．設G滿足條件(b)，且不妨設V={1,2,…,n/2}．

此外，注意到A(V)是一個n/2階的零矩陣,則

即V是矩陣A的一個P-集，這表明PS(A)≥n/2．最后，由引理1可得PS(A)=n/2，即條件(a)成立．

注1當G為具有n個點的樹時，文獻[6]33-34給出了S(G)中存在樹矩陣A使得PS(A)=n/2的充要條件．現(xiàn)在，定理3將該特征刻畫從樹矩陣推廣到所有實對稱陣，完全地刻畫出所有滿足PS(A)=n/2的n階實對稱陣A的伴隨圖．

下面給出1個例子來闡明定理3給出的特征刻畫．

設圖G如圖1所示，且有矩陣

圖1　圖G

設G為具有n個點的圖．當n為奇數(shù)時，定理2給出了S(G)中存在實對稱陣A使得PS(A)=(n-1)/2的一個必要條件．結(jié)合樹矩陣的相關結(jié)果[6]36，有下述猜想：

推想1設G為具有n個點的圖，其中n為奇數(shù)．下述2個條件是等價的：

(a) S(G)中存在實對稱陣A，使得PS(A)=(n-1)/2；

參考文獻：

[1]HORNRA,JOHNSONCR.Matrixanalysis[M]. 2nded.NewYork:CambridgeUniversityPress, 2013.

[2]JOHNSONCR,DUARTEAL,SAIAGOCM.TheParter-Wienertheorem:refinementandgeneralization[J].SIAMJournalonMatrixAnalysis&Applications, 2003, 25(2):352-361.

[3]FERNANDESR,DACRUZHF.SetsofParterverticeswhicharePartersets[J].LinearAlgebraandItsApplications, 2014, 448:37-54.

[4]NELSONCG,SHADERBL.AllpairssufficeforaP-set[J].LinearAlgebraandItsApplications, 2015, 475:114-118.

[5]KIMIJ,SHADERBL.Non-singularacyclicmatrices[J].LinearandMultilinearAlgebra, 2009, 57(4).

[6]DUZ,DAFONSECACM.TheacyclicmatriceswithaP-setofmaximumsize[J].LinearAlgebraandItsApplications, 2014, 468:27-37.

【中文責編：莊曉瓊英文責編：肖菁】

The Real Symmetric Matrices with a P-set of Maximum Size and Their Associated Graphs

DU Zhibin*

(School of Mathematics and Statistics, Zhaoqing University, Zhaoqing 526061, China)

Abstract：The concept of P-set of real symmetric matrices is proposed based on the multiplicity of eigenvalues of matrices and Cauchy interlacing theory. Suppose that A is a real symmetric matrix of ordern. LetmA(0) be the multiplicity of eigenvalue 0 of A, and let A(S) be the principal submatrix of A obtained from A by deleting thei1,i2,…,ikrows and columns, whereS={i1,i2,…,ik} is a nonempty subset of {1,2,…,n}. In particular, whenmA(S)(0)=mA(0)+|S|, thenSis a P-set of A. LetPS(A) be the maximum size among the P-sets of A. Based on the fact that every real symmetric matrix of ordernhas at most ?n/2」 elements, the structure and characteristics of the real symmetric matrices of ordernsatisfiedPS(A)=?n/2」 are studied; their corresponding properties are presented; the associated graphs whennis even is characterized; the associated graphs whennis odd is conjectured, which improve the results on the acyclic matrices with a P-set of maximum size.

Key words：real symmetric matrices; associated graphs; multiplicity of eigenvalues; P-set

收稿日期：2015-04-24《華南師范大學學報(自然科學版)》網(wǎng)址：http://journal.scnu.edu.cn/n

基金項目：國家自然科學基金項目(11426199)；廣東省自然科學基金項目(2014A030310277)；廣東省教育廳青年創(chuàng)新人才項目(2014KQNCX224)

*通訊作者:杜志斌，講師，Email:zhibindu@126.com.

中圖分類號：O157.5

文獻標志碼：A

文章編號:1000-5463(2016)01-0119-04