本原和非本原方阵

1、North University of China,目录,上页,下页,返回,结束,3.4,本原和非本原方阵,本节所论的不可约非负方阵均为,阶,并简称本原（非本原）的不可约非负方阵为本,原（非本原）方阵,1,n,设,D,是一个有向图,是,D,中一,条从,到,的路，则构成这条路的弧,的个数,称为这条路的长。同样,称回路,的长为,注意上述长为,的路或回路中的,条弧不必互不相同,0,1,l,i,i,i,V,V,V,0,i,V,l,i,V,0,1,1,t,l,l,0,1,1,0,l,i,i,i,i,V,V,V,V,l,l,l,1,t,t,i,i,V,V,North University of China

2、,目录,上页,下页,返回,结束,定义,设,是,个顶点的强连通图，则称,中,所有回路的长的最大公因数,为,的回路性,指标,D,1,n,D,d,D,定理,7,不可约非负方阵,的非本原性指标等于相应,的强连通图,的回路性指标,A,D,A,证,设,的非本原性指标是,的回路性指标,是,现证,A,k,D,A,d,d,k,i,由定理,2,可知,置换相似于分块矩阵,k,d,A,North University of China,目录,上页,下页,返回,结束,12,23,1,1,0,0,0,0,0,0,k,k,k,A,A,A,A,在此分别记块,的行标集合为,则它们的列标集合分别为,12,23,1,1,k,k,k

3、,A,A,A,A,1,2,1,k,k,W,W,W,W,2,3,1,k,W,W,W,W,的语言来说，就是,的顶点集,1,2,k,W,W,W,1,2,n,D,A,D,A,是,的一个划,分。用,North University of China,目录,上页,下页,返回,结束,1,2,n,有,一,个,划,分,1,2,k,V,V,V,1,i,t,i,V,t,W,i,k,它使,D,A,中任一起点属于,i,V,的弧，其终点一定属于,1,i,V,这里,1,1,k,V,V,因此,D,A,的任一回路的长一定是,k,的整数倍,ii,d,k,同定理,2,的推论,2,的记号一样，记,A,的特征多项式为,1,1,1,1,

4、0,0,s,n,n,n,s,s,s,c,c,c,c,n,n,n,North University of China,目录,上页,下页,返回,结束,则推论,2,断言,1,2,s,k,g,c,d,n,n,n,n,n,n,故只,需证明,1,i,d,n,n,i,s,因为,0,i,c,所以,A,必有,i,n,n,阶主子式不为零。不,妨,设,det,1,1,0,i,n,n,m,A,m,m,从,而,有,一,项,1,1,0,m,m,a,a,这里,是,1,m,上的一个置换。现,将,表成若干个循环置换的乘积,其中每个循环置,换都可写成,1,2,1,2,2,3,1,j,j,k,k,k,k,k,k,k,k,k,Nor

5、th University of China,目录,上页,下页,返回,结束,因此,1,2,2,3,1,0,j,k,k,k,k,k,k,a,a,a,也就是说，在,D,A,中有一,个长为,j,的简单回路,1,2,1,j,k,k,k,k,V,V,V,V,所以,d,j,因为这些循环置换的长度之和等于,i,m,n,n,所,以,1,i,d,n,n,i,s,D,的回路性指标可以等价的定义为,D,的所有简单回,路的长的最大公因数。因为任意一个回路看作其,中弧的集合必为若干简单回路的并集，从而一个,回路的长必为若干简单回路的长的和,North University of China,目录,上页,下页,返回,结束

6、,D,A,0,1,0,1,0,1,1,1,0,n,n,A,例,4,North University of China,目录,上页,下页,返回,结束,易,见,D,A,有,两,个,简,单,回,路,1,2,1,n,V,V,V,V,和,2,3,2,n,V,V,V,V,它们的长分别是,n,和,1,n,所,以,D,A,的回路性指标等于,1,从而,A,是本原,的,注意,A,的非本原性指标为,k,并不蕴含,D,A,中一,定有长为,k,的回路,North University of China,目录,上页,下页,返回,结束,例,5,0,1,0,0,0,0,1,0,0,1,0,0,1,0,1,0,0,0,B,B,

7、A,B,D,A,D,B,D,A,仅有长为,4,和,6,的简单回路，故,A,的非本原,性指标为,2,故,A,为非本原的，这时,B,为本原的,例,5,反映的事实可以推广成如下结论,North University of China,目录,上页,下页,返回,结束,推论,设不可约非负方阵,A,置换相似于,1,2,1,0,0,0,0,0,T,k,k,B,B,PAP,B,B,North University of China,目录,上页,下页,返回,结束,其中主对角都是非空零方阵。则,1,A,的非本原性指标一定是,k,的整数倍,2,A,的非本原性指标等于,k,当且仅当乘积方阵,1,2,k,B,B,B,是本

8、原的,North University of China,目录,上页,下页,返回,结束,证,1,由定理,7,的证明中,i,可得,2,的证明放在,证明了本原性的一个重要刻划,见以后的,4,之后,并将,2,表述为更完整的结论（定理,9,至今我们已证明了不可约非负方阵,A,是本原方阵的,三种充要条件，它们是,North University of China,目录,上页,下页,返回,结束,1,A,只有一个模为,A,得特征值，即,A,自身,2,记,A,的特征多项式为,1,1,1,1,0,0,s,n,n,n,s,s,s,c,c,c,c,n,n,n,则,1,2,1,s,g,c,d,n,n,n,n,n,n,

9、3,D,A,的所有回路（或所有简单回路）的长的,最大公因数是,1,North University of China,目录,上页,下页,返回,结束,注意到对一个非负方阵,B,来说,B,的,l,次幂,l,B,的,非零元分布模式是由,B,的非零元分布模式完全确定,的,与,B,中各非零元的具体数值无关,而,B,的非零,元分布模式又等价于有向图,D,B,因此，是否存,在正整数,p,使,0,p,B,这个矩阵性质实质上是一种,组合性质,下面再证明一种表述最简明的充要条件,不可约非负方阵,是本原的,存在正整数,p,A,使,0,p,A,North University of China,目录,上页,下页,返回

10、,结束,设,0,p,A,则易知,A,不可约,若,A,的非本原性指标,为,k,1,k,则,A,置换相似于,1,2,1,0,0,0,0,T,k,k,B,B,PAP,B,B,首先用反证法证明）中的充分性,North University of China,目录,上页,下页,返回,结束,其中主对角都是非空零矩阵。由此可知对任一正整,数,l,在,kl,T,PA,P,的分块表示中,除对角块外都是零块,因此,l,T,PA,P,从而,l,A,不可能是正矩阵,再注意到,2,定理,3,后面的命题，我们自然希,望通过,D,A,来证明,4,的必要性。先证明强连通有,向图中回路长度的一个结论，它本身有独立意义,Nort

11、h University of China,目录,上页,下页,返回,结束,引理,设,D,是强连通的有向图，记,D,的顶点集为,1,n,V,V,V,D,的回路性指标为,d,D,中所有通过顶,点,i,V,的回路的长的最大公因数为,1,i,d,i,n,则,i,1,n,d,d,d,ii,任给两点,i,j,V,V,V,从,i,V,到,j,V,的所有路的长模,d,同余,North University of China,目录,上页,下页,返回,结束,特别地，若,D,的一条弧的起点属于,i,V,则终点,必属于,1,0,0,1,1,i,d,V,i,d,V,V,iv,存在正整数,N,使得对任一整数,m,N,以及

12、,任意两点,i,j,v,V,v,V,D,中一定有一条从,v,到,v,的长为,j,i,md,的路,iii,可将,V,划分成,d,部分,0,1,1,d,V,V,V,V,使得,D,中,任,一,起,点,属,于,i,V,而,终,点,属,于,j,V,的,路,的,长,mod,l,j,i,d,North University of China,目录,上页,下页,返回,结束,证,任取,i,j,V,V,V,以及过,j,V,的回路,C,记,C,的长为,j,m,因,D,强连通，故可取一条从,i,V,到,j,V,的路,P,记,P,的,长为,s,又可取一条从,j,V,到,i,V,的路,Q,记,Q,的长为,t,由此可得两个

13、过,i,V,的回路,一个回路是在,P,后接,Q,另一个是在,P,后接,C,再接,Q,这两个回路的长分别是,s,t,和,j,s,t,m,根据,i,d,的定义，可知,i,j,d,m,因上述过,j,V,的,C,是任取的,所以,i,j,d,d,从而,1,n,d,d,d,显然,d,d,North University of China,目录,上页,下页,返回,结束,反之，在,D,中有某,r,个分别长,1,r,l,l,的回路，使,1,r,d,g,c,d,l,l,则,诸,i,d,的,公,共,值,d,显,然,整,除,1,r,l,l,从而,d,d,ii,设,P,和,P,是两条从,i,V,到,j,V,的路，它们的

14、长分别,为,l,和,l,再任取一条从,j,V,到,i,V,的路,Q,记,Q,的,长为,m,则在,P,后接,Q,和在,P,后接,Q,分别得到长,为,l,m,和,l,m,的,两,个,回,路,因,此,mod,l,m,l,m,d,从而,mod,l,l,d,North University of China,目录,上页,下页,返回,结束,由,ii,可知,i,V,是确切定义的,而且,0,1,1,d,V,V,V,是,V,的一个分划，它具有所要求的性质,1,0,1,1,i,j,j,V,v,V,v,v,d,i,i,d,从,到,的路的长模,同余,iii,令,North University of China,目录

15、,上页,下页,返回,结束,命题,设,S,是正整数集的一个子集,且,S,对加法封,闭,记,S,中全部正整数的最大公因数为,d,则存在正整数,N,使得,md,m,N,S,在证,iv,前，需先证明正整数集的一个性质,North University of China,目录,上页,下页,返回,结束,证明,可不妨设,1,d,因此,S,中必有,l,个数,1,1,1,l,l,n,n,g,c,d,n,n,从而有整数,1,l,a,a,使,1,1,1,l,l,a,n,a,n,把这个等式中,i,a,的正、负项,分开，可得,1,2,1,m,m,其中,1,2,0,0,i,i,i,i,i,i,a,a,m,a,n,S,m,

16、a,n,S,令,2,2,1,N,m,m,则,当,m,N,时,用,2,m,整,除,m,得,2,m,am,r,其中,2,2,0,1,1,r,m,a,m,所以,2,2,1,2,1,2,m,am,r,am,r,m,m,rm,a,r,m,S,命题证毕,North University of China,目录,上页,下页,返回,结束,iv,对,i,j,V,V,V,V,取定一条从,V,到,V,的路,记其长为,j,i,l,V,V,d,其中,l,V,V,是非,负整数,再记过,V,的所有回路的长的集合为,S,V,显然,S,V,对加法封闭，且其最大公,因数是,d,由命题可知存在正整数,N,V,只要,整数,p,N,V

17、,就一定有过,V,的长为,pd,的回,路,所以只要,m,l,V,V,N,V,就必有从,V,到,V,的,长,为,j,i,md,的,路,令,max,V,V,V,N,l,V,V,N,V,即为所求,North University of China,目录,上页,下页,返回,结束,定理,非负方阵,A,是本原方阵的充要条件是,存在正整数,p,使,0,p,A,证,充分性已经证过，现在证必要性：设,A,是本,原的,则,D,A,的回路性指标,1,d,D,A,的顶点集,V,按引理的,iii,所作的划分,现在是,0,V,V,由引理,的,iv,可知，存在正整数,N,使得对任一整数,m,N,和,V,中任意两点,i,V,

18、与,j,V,D,A,中一定有一条从,i,V,到,j,V,的长为,m,的路,用,A,的语言来说，就是当,m,N,时,0,m,A,North University of China,目录,上页,下页,返回,结束,定理,设,A,是不可约非负方阵,则,A,的非本,原性指标是,k,的充要条件为：有置换,方阵,P,使,1,2,1,0,0,0,0,T,k,k,B,B,PAP,B,B,其中主对角块都是非空零方阵。而且如记,1,2,k,T,k,PA,P,diag,A,A,A,则,1,k,A,A,都是本原方阵,North University of China,目录,上页,下页,返回,结束,证,设,A,的非本原性

19、指标是,k,则,D,A,的回路性指,标也是,k,因此,D,A,的顶点集,1,n,V,V,V,可按,引理的,iii,作分划,0,1,1,k,V,V,V,这时,D,A,中任,一起点在,i,V,中的弧,其终点一定在,1,i,V,中,再对,A,作置换相似，使得,A,中以,0,1,k,V,V,V,中点的下标,为行标和列标的行和列经置换后变成分组从小,到大的自然顺序，也就是说，经过这样置换相似,North University of China,目录,上页,下页,返回,结束,后所得到的方阵具有所要求的分块形式。显然在,这种分块形式下，有,1,2,k,T,k,PA,P,diag,A,A,A,其,中,1,1,

20、2,2,2,3,1,1,1,k,k,k,k,k,A,B,B,B,A,B,B,B,B,A,B,B,B,又因为对,l,V,来说,0,1,1,l,k,存在正整数,l,N,使得对,l,V,中任意两点,V,V,及任一整数,l,m,N,D,A,中必有从,V,到,V,的长为,mk,的路，从而,1,0,0,1,1,m,l,A,l,k,由,定理,可知,1,k,A,A,都是本原的,North University of China,目录,上页,下页,返回,结束,反之,设,T,PAP,有所说的分块形式,且,1,1,2,k,A,B,B,B,是本原的（注意这里仅要求,1,A,是本原的，因此比,定理的结论稍强些，而与定理后的推论的,一样,则有正整数,t,使,1,0,t,A,从而,1,1,0,t,A,因此,kt,T,PAP,和,1,k,t,T,PAP,的左上角块是正方,阵,从而左上角元素为正,即,D,A,中既有从,1,V,到,1,V,的长为,kt,的回路，又有长为,1,k,t,的回路,North University of China,目录,上页,下页,返回,结束,从而,k,作为,1,k,t,和,kt,的最大