非负矩阵中的不可约矩阵

张媛媛

【摘要】本文专注于对非负矩阵中的不可约矩阵的讨论。首先引入锥的概念，然后在几个重要定理的基础上，研究非负矩阵不可约性的几个等价命题，最终得出判定非负矩阵不可约的一些方法。

【关键词】非负矩阵 锥 不可约矩阵 本原矩阵

一、不可约性

定义1.1.1：如果训在一个置换矩阵P使得X=PTYP成立，则称矩阵X同步于矩阵Y.即：如果X能通过若干次行的变换和相应的列的变换换成Y，就称X同步于Y.

定义1.1.2：（可约矩阵）若n×n矩阵A同步于矩阵E，其中E=■，且B为r阶子方阵，D为n-r阶子方阵，1┃r

定理1.1.1：如果A=（aij）m×n≥0是不可约的，且x=（x1，x2，…，xn）r≥0，且x恰有k个元素大于0，则（I+A）x有多于k个元素大于0 。

证：设P是置换矩阵，且y=Px的前k个元素是正数，其余元素为0.

显然，（I+A）x=x+Ax中0元素的个数不大于n-k。假设正好为n-k，这意味着，当xi=0时Ax的第i个元素也为0，同时也意味着当y的第i个元素为0时，PAPry的第i个元素也为0.

令B=（bij）=PAPr，对i=k+1，k+2，…，n我们有

■bijyj=■bijyj=0

而对j=1，2，…，k有yj>0，则bij=0，i=k+1，k+2，…，k这说明了矩阵A同步于B，A可约.

故假设不成立，（I+A）x不能有n-k个元素为0，即（I+A）x有多于k个元素大于0.

推论1.1.2： n×n非负矩阵A是不可约的，当且仅当

（I+A）n-1>0

证：必要性：已知对任意的ei，i=1，2，…，n都有

（I+A）n-1ei>0

所以（I+A）n-1的所有列都是正的，则A不可约.

充分性：（I+A）n-1不可约，则I+A不可约，A不可约当且仅当I+A不可约.证毕.

定理1.1.3：一个非负矩阵A不可约当且仅当对每个（i，j）都存在一个自然数q使（其中Aq的第（i，j）元素记为aij（q））。

证明：必要性：设A不可约则由定理我们知道（I+A）n-1>0，令，B=（I+A）n-1A，B为正矩阵，由于正矩阵与不可与矩阵的乘积仍是正矩阵。设B=An+cn-1An-1+…+c1A我们对任意的（i，j）有：

bij=αij（n）+cn-1αij（n-1）+…+c1αij>0

则对每个（i，j）都存在一个正数q满足αij（q）>0。

充分性：假设A可约，存在置换矩阵P使得

PTAP=■，

其中B是r阶方阵。由此，对满足r+1≤i≤n，1≤j≤s的i和j，有 PTAP的第（i，j）元素对任意的q都为0。

产生矛盾，则假设不成立，A不可约.

二、矩阵的有向图

我们知道，非负矩陣的许多性质，如不可约性、本原性，不可约性矩阵的Frobenius型及非本原性指标等都只依赖于零型矩阵，这里的零型指的是零元素的分布。而通过引进有向图的概念可以很好地说明非负矩阵的零型，非负矩阵的某些性质可以从它的有向图的相关性质推导出。下面我们先给出有向图的定义，然后给出一个判定矩阵不可约的定理。

定义2.2.1：对 非负矩阵A我们这样定义A的有向图G（A），包括n个顶点1，2，…，n和顶点间的弧i→j当且仅当αij≠0，形如i→t1，t1→t2，…，tm-1→j的弧的序列称为连接i到j的路，路的长度定义为序列中弧的条数m，连接顶点i到自身的路叫做循环。如果一个循环路过不同顶点的次数只有一次，则称该循环为回路.

比如：令A=■，B=■，

C=■，

则A的有向图G（A）={1→2；1→3；2→；3→1}；

B的有向图：

G（B）={1→1；1→3；2→2；2→3；2→4；3→1；3→3；4→1；4→2；4→4 }；

C的有向图：

G（C）={1→1；1→3；2→4；3→2；4→1；4→4}；

定义2.2.2：一个有向图G称为强连通的，若对G中顶点集的任意有序对（i，j），i≠j都有一条从i到j的路。

定理2.2.1：矩阵A是不可约的当且仅当A的有向图G（A）是强连通的.

证明：由于αij（q）>0当且仅当存在一条由q条弧组成的从i到j的路.

定理得证。

由定理可知，我们可以通过有向图来判定矩阵是否为不可约，如例2.2.1，因G（A）， G（C）是强连通的，则A和C不可约，而G（B）不是强连通的，则B是可约的。

此外，还可以通过有向图来确定一个不可约矩阵是否为本原矩阵，也就是可以求不可约矩阵的非本原性指标。而这个指标就等于有向图中所有循环的长度的最大公因数。如果指标为1，则说明该不可约矩阵是本原矩阵，否则不是本原矩阵。

定义2.2.2：设A是有最大特征值ρ（A）的n×n不可约矩阵，并且恰好有h个模为ρ（A）的特征值，数h称为A 的非本原性指标，或简称指标。如果h=1，则称A为本原的，否则称为非本原的。

四、结束语

本文由锥引出一个矩阵可约与不可约的定义，并以此为基础对矩阵不可约性做了讨论，另外还给出了等价的不可约的定义。本文还引进了非负举证的有向图的概念，并给出了一个判定矩阵不可约的很有用的定理，通过研究有向图的性质而得到矩阵的性质，而有向图简单且有效，这是一个很好的方法，从而得出，要研究非负矩阵的不可约性可有两种途径，一种是直接研究矩阵的性质，如零型、特征值、特征向量等，另一种是研究矩阵的有向图的性质。