不可约非负矩阵的最大特征值估计

潘自康，任芳国

(陕西师范大学数学与信息科学学院，陕西西安710062)

不可约非负矩阵的最大特征值估计

潘自康，任芳国

(陕西师范大学数学与信息科学学院，陕西西安710062)

利用不可约非负矩阵和Collatz—Wielandt函数的性质，给出了非负不可约矩阵最大特征值的一些界。比较这些界的大小，利用极限的思想得到了求非负不可约矩阵最大特征值的方法。利用这种方法可以去估计非负不可约矩阵最大特征值的大小，并通过计算和比较，验证了这种估计方法是可行的。

非负不可约矩阵；Collatz—Wielandt函数；最大特征值

非负矩阵在计算数学、图论、线性规划、自动控制等许多学科领域有着广泛的应用，对其特征值的估计有着很重要的意义。它由Perrn发现，后来由Frobenius发展的关于非负矩阵最大特征值的一个优美结果。[1]自此以后，A Brauer，O Taussky，R S Varga，A Ostrowski等人的杰出的工作，己经形成了较为完善的理论。[2-4]非负矩阵理论中最大特征值的界值估计是该理论的核心问题之一，如果上下界能表示为矩阵元素的易于计算的函数，那么这种估计的价值就更高。由于非负矩阵最大特征值估计问题在很多学科中的广泛应用，近年来国内学者开始研究这个问题，并提出了一些新的估计方法[5-6]，使计算更为简洁，结果更为精确。本文基于已有的研究成果，利用Collatz—Wielandt函数及其推广，得到最大特征值的一系列上界和下界；并通过比较这些界的大小用求极限的方法得到一种非负不可约矩阵最大特征值的估计方法；通过计算来验证这些估计方法的可行性，并比较它们的精确程度。

1 预备知识

为了叙述方便，我们对符号进行如下约定。pn：表示非负数域上的n维列向量的集合；Mn(P)：表示非负数域上n×n矩阵的集合；AT：表示矩阵A的转置；ri：表示矩阵A的第i行和；ci：表示矩阵A的第i列和。其他未加说明的符号参见文献[3]。

下面是与本文相关的几个定义及引理。

定义1[2]设A=(aij)∈Rm×n，B=(bij)∈Rm×n，记B≥0，如果所有bij≥0；B＞0，如果所有bij＞0，B≥A，如果所有B-A≥0，B＞A，如果所有B-A＞0。若A≥0，则称A为非负矩阵；若A＞0，则称A为正矩阵。

定义2[3]每行和每列都只有一个元素为1，其余元素是零的方阵称为置换矩阵。

定义3[3]设矩阵A∈Mn()P,如果存在一个置换矩阵P∈Rm×n使得

其中B和D分别是k，l阶方阵，k≥1和l≥1，称A是可约矩阵；否则称A是不可约矩阵。

引理1[4]设A∈Mn(P)是不可约矩阵，n≥2。y∈Pn正好有k个坐标为正，1≤k≤n-1，则(In+A)y的正坐标的个数超过k个。

推论1[4]设A∈Mn(P)是不可约矩阵，y∈Pn且y≠0，则(In+A)y＞0。

引理2[4]设A∈Mn(P)是不可约矩阵，r是A的一个特征值。如果r≥0，则必有r＞0。

下面讨论Collatz—Wielandt函数和不可约非负矩阵最大特征值的估计。

2 定理及证明

定义4[4]设A∈Mn()P是不可约矩阵，fA是从Pn到非负数的函数。

对任意向量x=(x1,x2,…,xn)∈Pn,且x≠0，fA被称作关于A的Collatz—Wielandt函数。

定理1设A∈Mn(P)是不可约矩阵，fA是定义4中的的函数。则有

（i）fA是零次齐次函数;

（ii）如果x∈Pn,且x≠0，和ρ是使Ax-ρx≥0成立的最大的实数，则ρ=fA(x);

（iii）如果x∈Pn,且x≠0。且y=(In+A)n-1x，则fA(y)≥fA(x);

（iv）fA可以在En中取得最大值；

（v）A存在一个特征值r=max{fA(x)|x∈En}使得，r≥|λi|，λi为A的任意特征值。此外，r对应一个正的特征向量。

定理的证明参见文献[4]。

定义5[4]设A∈Mn(P)是不可约矩阵，gA是从Pn到非负数的函数。

对任意向量x=(x1,x2,…,xn)∈Pn,且x≠0，当存在xi=0， (Ax)i≠0 时，定义gA(x)=+∞。

可以看出gA是通过Collatz—Wielandt函数的推广得到的，所以它具有与fA相似的一些性质。

定理2设A∈Mn(P)是不可约矩阵，gA是定义5中的的函数。则有

（i）gA是零次齐次函数;

（ii）如果x∈Pn,且x≠0，x和σ是使σx-Ax≥0成立的最小的实数，则σ=gA(x);

（iii）如果x∈Pn,且x≠0。且y=(In+A)n-1x，则gA(y)≤gA(x);

（iv）gA可以在En中取得最小值；

（v）A存在一个特征值r=min{gA(x)|x∈En}使得，r≥|λi|，λi为A的任意特征值。此外。r对应一个正的特征向量。

定理3设A∈Mn(P)是不可约矩阵，r为A最大特征值，则对任意x∈Pn,且x≠0，有

证明：对任意x∈Pn,且x≠0，令

则z∈En。

由定理1（i）可知fA是零次齐次函数，所以

由定理2（v）可知r=max{fA(x)|x∈En}，所以

同理可得r≤gA(z)=gA(x)，所以不等式（1）得证。定理4设A∈Mn()P是不可约矩阵，r为最大特征值，B=(In+A)n-1，则有

证明：令y=Bx，则y=(In+A)n-1x。由定理2（iii）可知

又因为Bx∈Pn且Bx＞0，由定理3可知

所以，fA(x)≤fA(Bx)≤r

同理可得，r≤gA(Bx)≤gA(x)所以，不等式（2）得证。

定理5设A∈Mn()P是不可约矩阵，r为最大特征值，B=(In+A)n-1，则对任意的x∈Pn，x≠0，k∈N，有

且有

证明：对任意的x∈Pn，x≠0，k∈N。有Bkx∈Pn,Bkx＞0。由定理3可知

又因为Bk+1x=BBkx=(I+A)n-1Bkx，所以由定理1（iii）可知

即，fA(Bkx)是单调递增的，且fA(Bkx)≤r。所以由单调有界定理[7]可得，

推论2设A∈Mn()P是不可约矩阵，r为最大特征值，B=(In+A)n-1，y为A的最大特征向量，且y∈En。则

解：由MATLAB计算可得，

由定理3可知，r∈[) 2,+∞。

由定理4可知,r∈[] 4,5.212 1。

由定理5可知,r∈[] 4.939 7,5.012 1。

由定理5和推论2可知,A的最大特征值r=5。对应的最大特征向量

且y∈En。

最后，通过求A的特征方程，解得A的特征值分别为λ1=0,λ2=0,λ3=5并且λ3=5对应的特征向量

所以，这种估计最大特征值和最大特征向量的方法是可行，并且是比较精确的。

下面用Collatz—Wielandt函数证明一些其他的估计方法。

定理6[1]设A∈Mn()P是不可约矩阵，r为最大特征值，则有

证明：由定理3可知fA(x)≤r≤gA(x)对任意的x∈Pn,x≠0成立，可令x=(1,1,…,1)T。则

所以式（6）得证。

又因为A与AT有相同的最大特征值r，所以由定理3可知

对任意的x∈Pn,x≠0成立，同理可得，

所以式（7）得证。

定理7[5]设A∈Mn()P是不可约矩阵，r为最大特征值，B=(In+A)n-1，则有

证明：由定理4可得fA(Bx)≤r≤gA(Bx)，对任意的x∈Pn,x≠0成立，可令x=(1,1,…,1)T。则和定理6的证明方法类似，便可证得式（8）和式（9）也是成立的。

定理8[6]设A∈Mn(P)是不可约矩阵，r为最大特征值，B=(In+A)n-1，则有

证明：由定理5可得fA(Bkx)≤r≤gA(Bkx)，对任意的x∈Pn,x≠0成立，且有

可对任意的x∈Pn,x≠0,k∈N成立，令x=(1,1,…,1)T。则和定理6的证明方法类似，便可证得式（10-13）式也是成立的。

这样，就可以不用向量x只用矩阵A和Bk=(In+A)(n-1)k，k∈N，对最大特征值进行估计。

[1]FROBENIUS G.Uber matrizen aus nicht negativen elementen[M].Berlin:Sitzungsber konussAkad Wiss，1912：465-477.

[2]ROGER A H,CHARLS R J.Matrix analysis[M].Cambridge University Press，1990，1：347-374.

[3]BERMAN A，PLEMMONS R J.Nonnegative matrices in the mathematical sciences[M].New York:Academic Press，1979：26-59.

[4]HENRYK M.Nonnegative matrices[M].New York:Wiley，1988：5-20.

[5]王忠全.非负矩阵谱半径的估计[J].宿州学院学报，2008（4）：99-100.

[6]殷剑宏.非负矩阵最大特征值的新界值[J].数值计算与计算机应用，2002(4)：292-295.

Estimation for the Maximal Eigenvalue of Irreducible Nonnegative Matrix

PAN Zikang,REN Fangguo
(College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062,Shaanxi,China)

In the paper,based on the property of irreducible nonnegative matrix and Collatz-Wielandt function,we derive some bounds for the maximal eigenvalue of irreducible nonnegative matrix.The method of seeking for the maximal eigenvalue of irreducible nonnegative matrix is given by the size of these bounds and the idea of limit.We can use this method to estimate the maximal eigenvalue of irreducible nonnegative matrix.It is proved that this estimation is feasible by calculating and comparing.

irreducible nonnegative matrix;Collatz-Wielandt function;maximum eigenvalue

O151.21

A

1672-2914（2015）02-0035-04

2014-12-08

国家自然科学基金项目(11171201)；陕西省自然科学基金项目（2011JM1007）。

潘自康（1984-），男，河北邯郸市人，陕西师范大学数学与信息科学学院硕士研究生，研究方向为矩阵论。

任芳国，副教授，E-mail：rfangguo@sohu.com。