非負矩陣中的不可約矩陣

張媛媛

【摘要】本文專注于對非負矩陣中的不可約矩陣的討論。首先引入錐的概念，然后在幾個重要定理的基礎上，研究非負矩陣不可約性的幾個等價命題，最終得出判定非負矩陣不可約的一些方法。

【關鍵詞】非負矩陣 錐 不可約矩陣 本原矩陣

一、不可約性

定義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為本原的，否則稱為非本原的。

四、結束語

本文由錐引出一個矩陣可約與不可約的定義，并以此為基礎對矩陣不可約性做了討論，另外還給出了等價的不可約的定義。本文還引進了非負舉證的有向圖的概念，并給出了一個判定矩陣不可約的很有用的定理，通過研究有向圖的性質而得到矩陣的性質，而有向圖簡單且有效，這是一個很好的方法，從而得出，要研究非負矩陣的不可約性可有兩種途徑，一種是直接研究矩陣的性質，如零型、特征值、特征向量等，另一種是研究矩陣的有向圖的性質。