正则竞赛矩阵的数目和竞赛矩阵的
整数特征值
侯耀平
(北京师范大学数学系北京100875)
摘　要　本文给出了n 阶正则竞赛矩阵的数目的一个下界，该下界优于文献中的结果；讨论了正竞赛矩阵的性质；得到了整数1为竞赛矩阵的特征值的等价条件及这类矩阵的谱根与得分向量之间的关系.
关键词　竞赛矩阵，正则竞赛矩阵，正竞赛矩阵，得分向量，谱根MR (1991)主题分类　15A15,05B20
中图分类　O151121,O15715
On the Number of R egular Tournament Matrices and Integral Eigenvalue of
Tournament Matrices
Hou Y aoping
(Depart ment of M athem atics ,Beijing Norm al U niversity ,Beining 100875,China )
Abstract  In this paper we give a better lower bound for the number of regular tourna 2ment matrices ,and obtain some properties of positive tournament matrices ,we also find several conditions which are equivalent to tournament matrix having 1as its eigenvalue.K eyw ords  Tournament matrix ,Regular tournament matrix ,Positive tournament ma 2trix ,Score vector ,Spectral radius
MR (1991)Subject Classif ication  15A15,05B20Chinese Library Classif ication  O151121,O15715
0　引言
完全图的定向图的邻接矩阵称为竞赛矩阵，它是满足A +A T =J -I 的(0,1)2矩阵，其中J 为元素全为1的方阵,I 为单位方阵.竞赛图和竞赛矩阵的研究由来已久，有关的结果可参看文后的参考文献.记e =(1,1,…,1)T ,s =Ae ,r =A T e ，则s 和r 分别是A 的行和向量及列和向量,s ,r 分别称为A 的得分向量和失分向量.显然有s T e =r T e =
n
2
,s
T
=r T
,s =(n -
1)e -r ，其中n 为A 的阶数.给出一非负整数序列s =(s 1,s 2,…,s n )
T
,s 1Φs 2Φ…Φs n ，则存在以s 为得分向量的n 阶竞赛矩阵充分必要条件为[1]:
6
k
i =1
s i Ε
k
2
这,k =1,2,…,n -
第41卷第5期1998年9月
数  学  学  报
ACTA MA THEMA TICA SIN ICA
Vol.41,No.5Sept.,1998
收稿日期:1997-06-27，修改日期:1997-12-19，接受日期:1998-02-12国家自然科学基金资助项目(19671013)
1.6n i=1s i=n2　.以F(s)表示以s为得分向量的竞赛矩阵的全体.当F(s)非空时，称s为有效的.如果F(s)中每一个矩阵为不可约时，称s为强有效的.s是强有效的充分必要条件是[1]:
6k i=1s i>
k
2
t
he
,
k=1,2,…,n-1.6n i=1s i=n2
ou pi.
n，它优于文献[2]中已有的结果；然后
讨论了正竞赛矩阵的一些性质；给出了利用已知平衡向量构造新平衡向量的方法；最后得到了整数1作为竞赛矩阵的特征值的等价条件及其这种竞赛矩阵的谱根与得分向量之间的关系.
1　正则竞赛矩阵的数目
如果竞赛矩阵A的每一行元素之和相等，则称A为正则的.易知当A为n阶正则竞赛矩
阵时,n必为奇数，且此时A的得分向量为u n=n-1
2,n-1
2,
…,n-1
2
s g
T
.对于一般的s,
计算|F(s)|的精确值是一个相当困难的问题，对于u n，文[2]给出了|F u n)|的一个下界，下面我们给出它的一个更好的下界，当n为奇数时，记a n=|F(u n)|.
引理111[3]　设s是n阶强有效的，则|F(s)|Ε2n-2.
引理112　设n为奇数,nΕ5,b为奇数,
s b=n-1
2
-1,…
n-1
2
-1
n-b
2
,
n-1
2
,…,
n-1
2
b
,
n-1
2
+1,…,
n-1
2
+1
n-b
2
T
,
则s b是强有效的.
证明　当kΦn-b
2时,6k i=1s i=k n-12-1…
=k
n-3
2,
因为kΦn-b
2,
所以k-
1Φn-b
2
-1<n-3，所以6k i=1s i>k2学.当n-b2<kΦn-b2+b时,6k i=1s i=
n-1 2-119
n-b
2
an+n-1
2k-n-b
2
ic
=
n-1
2
(k-1)+b-
1
2>
k
2
(k-1)>
k
2
tr B
os；当
n+b
2<k<n 时,6k i=1s i=n-12-1rc
n-b
2+
n-1
2b+
n+1
2k-
n+b
2
cr=n+
1
2k
-n，而n+1
2
k-n-
k
2
(k-1)=(n-k)k
2
-
1
,>0，所以6k i=1s i>k2
.引，又6n i=1s i=
n 2
, ，故s b是强有效的.
  定理113　设n为不小于7的奇数，则
a nΕ
n-1
n-1
2
X
a n-2+
n-2
n-1
2
P-1
p]2n-4p)
.
  证明　将F(u n)分成两类F1与F2，其中
F1={A∈F(u n):a1j+a2j=1,j=3,…,n.} F2=F(u n)\F1.则我们有:
  (i)(|F1|=n-1
n-1
2
a n-2.
1054
　数  学  学  报41卷
事实上，任取A =(a ij )∈F 1，则A 的前两行由A 的第一行完全确定，由于A 的第一行共有
n -12个1,a 11=0，故这n -1
2
个1在第一行的不同排列数为n -1
n -12
=，去掉A 的前两行与前两列后剩下的n -2阶矩阵是n -2阶的正则竞赛矩阵；反过来,F 1中的任一矩阵均可由一n -2阶正则竞赛矩阵添加满足:a 11=a 22=0,a 12+a 21=1,a 1j +a 2j =1,j =3,…,n.
的两行而得到.从而|F 1|=n -1
n -12
a n -2.
  (ii )(|F 2|Εn -1n -1212
n -2
n -221-12
n -4
.考虑2×n 阶(0,1)矩阵的集合
U =
X =(x ij );x 11=x 22=0,x 12+x 21=1,X 的行和向量为
n -1
2
,
n -1
2
F s )2
n
则|U |=
n -1
n -1
2
n -2
n -12
…n
.记b j =x 1j +x 2j ,j =3,…,n.则0Φb j Φ2，设b 3,…,b n
中为1的共有b 个，则1Φb Φn -2，且b 为奇数，这是因为b 3+b 4+…+b n =n -2为
奇数.U 中满足b =n -2的X 共有n -1
n -12i 1个.对于1Φb <n -2，令s ′=
n -12-b 3,n -12-b 4,…,n -1
2
-b n -T
,s ′为n -2维向量，则s ′是强有效的.这是因为将s ′重排后为
s ″=n -1
2
-2,…,
n -1
2
-2,
n -1
2
-1,…,
n -1
2
-1,
n -1
2
,…,
n -1
2
-T
=
n -32-1,…,n -32-1n -2-b
2
,n -32,…,n -32b ,n -32+1,…,n -3
2
+1n -2-b
2
k
T
  由引理111知s ″是强有效的，故|F (s ′)|Ε2n -4
，这样
|F 2|Εn -1n -121n -2
n -22
-11
2
n -4
.由(i ),(ii )有
a n =|F 1|+|F 2|Εn -1n -1
2
,
a n -2
+n -1n -12n -2
n -22
=-1
=
2n -4
Εn -1
n -1
2n a n -2+
n -2n -1
2
-
1
2n -4
1证毕.
推论114[2]　设n Ε5为奇数，则a n Εn -1
n -12
  a n -2，从而a n Ε7n -12
j =12j
j
(.
5期侯耀平：正则竞赛矩阵的数目和竞赛矩阵的整数特征值1055　
  推论115　设n Ε7为奇数，则
a n Ε
7
n -1
2
j =1
2j
j
,+n -1
n -12在第n -2
n -22
-1
A 两
行与
2n -4.
  很明显，由定理113得出的a n 下界比文[2]中得到的a n 的下界
7
n -1
2
j =1
2j
j
a 要好.
2　正竞赛矩阵的性质
设A 是n 阶竞赛矩阵，令K (A )=A -A T ，称K (A )为竞赛矩阵A 的支付矩阵.K (A )是反对称的.如果存在正向量z 使K (A )z =0，则称A 为正竞赛矩阵，其中z 称为A 的平衡向量.正竞赛矩阵和平衡向量在讨论竞赛对策时起着重要的作用[4,5].如果A 为正竞赛矩阵，则A 必为奇数阶的.下面我们给出正竞赛矩阵和平衡向量的基本性质.  定理211　正竞赛矩阵必是不可约的.
证明　设A 是正竞赛矩阵，若A 可约，由于置换相似保持竞赛矩阵的正性，故可设
A =A 10
J A 2
x1，其中A 1,A 2分别为n 1,n 2阶的方阵，且n 1>0,n 2>0.从而:K (A )
=
A 1-A T
1
-J
T J
A 2-A T
2-.设A 的平衡向量为z =
z 1z 2
j
，由K (A )z =0得:
A 1-A T
1z 1
=J T
z 2,A 2-A T
2
2
且z 2=-Jz 1，从而有z T
2A 2-A T
2n 2z 2=-z T
2J z 1，因为A 2-A T
2是反对
称的矩阵，故z T 2A 2-A T
2z 2=0，所以z T
2Jz 1=0，这与z >0矛盾!故正竞赛矩阵必是不
可约的.
由于K (A )是整数矩阵，故可取A 的平衡向量为分量全是正整数的向量z =(z 1,…,z n )T
，且gcd (z 1,z 2,…,z n )=1，下面的定理给出了平衡向量的一个必要条件.
  定理212　设z =(z 1,…,z n )T ，且gcd (z 1,z 2,…,z n )=1,z 是一正整数向量，如果z 是某个正竞赛矩阵的平衡向量，则gcd {z k :k ≠i ,j}=1,i ,j =1,2,…,n.
证明　设z 是正竞赛矩阵A 的平衡向量，记K (A )=(b ij )，由K (A )z =0得:
6
n
k =1
b ik z k
=0,i =1,2,…,n.对于i ≠j ，由6
n
k =1
b ik z k =0可得:b ij =-
6
k ≠j
b ik z k =-
6
k ≠i ,j
b ik z k .设
d =gcd {z k :k ≠i ,j}，则d 6
k ≠i ,j正则匹配正整数
b ik z k ，故d |b ij z j .因b ij =±1，故d |z j ，从而d |gcd {z k :
k ≠i}.再考虑b ri z i =-6k ≠i
b
rk
z k ,r ≠i ，则d |b ri z i ,d |z j ，所以d |z j ，从而d |gcd (z 1,
z 2,…,z n )=1故d =1；当i =j 时，由前面证明知也有gcd {z k :k ≠i}=1.证毕.
注　满足定理11312的条件的正整数向量未必为平衡向量，例z =(1,1,1,1,3)T 就不是平衡向量.事实上，若Kz =0,K =(k ij )，则k 11+k 12+k 13+k 14+3k 15=0，因k 11=0,k ij =±1.所以k 12+k 13+k 14=-3k 15，故k 12,k 13,k 14同号且与k 15异号，不妨设k 12=k 13=k 14=1,k 15=-1，则K 的第二行必为(-1,0,-1-,1,1)，从而k 31=-1,k 32=1，这样
k 31+k 32+k 33+k 34+3k 35=k 34+3k 35≠0，即z =(1,1,1,1,3)
T
就不是任何正竞赛矩阵
的平衡向量.
命题213　设n =2k +1,n 为奇数，则z =(1,1,…,1,k )T
是平衡向量.
证明　设A k 为k 阶正则竞赛矩阵，令
1056　数  学  学  报41卷
A =
A k J 0
A k
e e
T
j 1,
其中e =(1,1, (1)
T
为k 维向量，则可验证z =(1,1,…,1,k )
T
是A 的平衡向量.证毕.
命题214　设z =(z 1,z 2,…,z n )T
是n 阶平衡向量,z n +1为正整数，若z n +1=
6
n
i =1
a i z i ,
a i 为1或21，则z ′=(z 1,…,z n ,z n +1,z n +1)
T
是n +2阶的平衡向量.
证明　设z 是n 阶竞赛矩阵A 的平衡向量，记α1=(b 1,…,b n )
T
，当a i =1时,b i =1，当a i =-1时,b i =0.α2=(c 1,…,c n )
T
，当a i =1时,c i =0当a i =0时,c i =1，令A ′=A
α1α2αT
2
01αT
1
则容易验证z ′是A ′的平衡向量.证毕.
利用命题213和命题214可以从低阶的正竞赛矩阵和平衡向量出发构造高阶的正竞赛矩阵和平衡向量.
引理215[4]　设K 为阶竞赛矩阵A 的支付矩阵,n 为大于1的奇数，记x i =(-1)i +1pf (K (i ))其中K (i )为将K (A )划去第i 行和第i 列后所剩下来的矩阵,pf (K )为K 的
Pf f af f ians (定义见参[4])，令x =(x 1,…,x n )T
，则Kx =0.
引理216[5]　设K 是竞赛矩阵的支付矩阵，则
秩K =
n -
1,
n 是奇数;n ,
n 是偶数.
  由引理217和引理218得到正竞赛矩阵的一个充分必要条件:
推论219　设A 为n 阶竞赛矩阵,n >1为奇数，则A 为正竞赛矩阵的充分必要条件是pf K (A )(i )的符号交错出现,k =1,2,…,n.
3　具有特征值1的竞赛矩阵
具有整数谱的图的刻划曾是Harary [6]提出的一个公开问题，对于竞赛图，只有传递的竞赛图才具有整数谱(全为0)，不存在具有整数谱的强竞赛图.那么整数值r 为竞赛矩阵的特征值时，竞赛矩阵具有什么样的性质呢?下面以r =1为例进行讨论，一般情形有类似的结论.
引理311[7]　设A 是2n 阶竞赛矩阵,λ是A 的一个特征值,z 为相应的特征向量，则
(1)Re λΕ-1
2等号成立当且仅当z 3e =0;(2)Re λΦn -1
2
等号成立当且仅当A 是正则竞赛矩阵;
(3)如果Re λ≠-1
2，则λ的几何重数为1;(4)如果Re λ=-1
2
，则λ的几何重数与代数重数一致.引理312　设1是竞赛矩阵A 的一个特征值,x 为相应的特征向量，则3x T x =(e T x )2.证明　因A x =x ，故x T A x =x T x ，所以x T (A +A T )x =2x T x ，而A +A T =J -I ，故3x T x =x T J x =x T ee T x =(e T x )2.证毕.  定理313　设A 是一n 阶竞赛矩阵，则下列条件等价:
(1)1是A 的一个特征值;(2)A -I 的秩为n -1;
5期侯耀平：正则竞赛矩阵的数目和竞赛矩阵的整数特征值1057　

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。