非負(fù)矩陣中的不可約矩陣

張媛媛

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

【關(guān)鍵詞】非負(fù)矩陣 錐 不可約矩陣 本原矩陣

一、不可約性

定義1.1.1：如果訓(xùn)在一個(gè)置換矩陣P使得X=PTYP成立，則稱矩陣X同步于矩陣Y.即：如果X能通過(guò)若干次行的變換和相應(yīng)的列的變換換成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個(gè)元素大于0，則（I+A）x有多于k個(gè)元素大于0 。

證：設(shè)P是置換矩陣，且y=Px的前k個(gè)元素是正數(shù)，其余元素為0.

顯然，（I+A）x=x+Ax中0元素的個(gè)數(shù)不大于n-k。假設(shè)正好為n-k，這意味著，當(dāng)xi=0時(shí)Ax的第i個(gè)元素也為0，同時(shí)也意味著當(dāng)y的第i個(gè)元素為0時(shí)，PAPry的第i個(gè)元素也為0.

令B=（bij）=PAPr，對(duì)i=k+1，k+2，…，n我們有

■bijyj=■bijyj=0

而對(duì)j=1，2，…，k有yj>0，則bij=0，i=k+1，k+2，…，k這說(shuō)明了矩陣A同步于B，A可約.

故假設(shè)不成立，（I+A）x不能有n-k個(gè)元素為0，即（I+A）x有多于k個(gè)元素大于0.

推論1.1.2： n×n非負(fù)矩陣A是不可約的，當(dāng)且僅當(dāng)

（I+A）n-1>0

證：必要性：已知對(duì)任意的ei，i=1，2，…，n都有

（I+A）n-1ei>0

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

充分性：（I+A）n-1不可約，則I+A不可約，A不可約當(dāng)且僅當(dāng)I+A不可約.證畢.

定理1.1.3：一個(gè)非負(fù)矩陣A不可約當(dāng)且僅當(dāng)對(duì)每個(gè)（i，j）都存在一個(gè)自然數(shù)q使（其中Aq的第（i，j）元素記為aij（q））。

證明：必要性：設(shè)A不可約則由定理我們知道（I+A）n-1>0，令，B=（I+A）n-1A，B為正矩陣，由于正矩陣與不可與矩陣的乘積仍是正矩陣。設(shè)B=An+cn-1An-1+…+c1A我們對(duì)任意的（i，j）有：

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

則對(duì)每個(gè)（i，j）都存在一個(gè)正數(shù)q滿足αij（q）>0。

充分性：假設(shè)A可約，存在置換矩陣P使得

PTAP=■，

其中B是r階方陣。由此，對(duì)滿足r+1≤i≤n，1≤j≤s的i和j，有 PTAP的第（i，j）元素對(duì)任意的q都為0。

產(chǎn)生矛盾，則假設(shè)不成立，A不可約.

二、矩陣的有向圖

我們知道，非負(fù)矩陣的許多性質(zhì)，如不可約性、本原性，不可約性矩陣的Frobenius型及非本原性指標(biāo)等都只依賴于零型矩陣，這里的零型指的是零元素的分布。而通過(guò)引進(jìn)有向圖的概念可以很好地說(shuō)明非負(fù)矩陣的零型，非負(fù)矩陣的某些性質(zhì)可以從它的有向圖的相關(guān)性質(zhì)推導(dǎo)出。下面我們先給出有向圖的定義，然后給出一個(gè)判定矩陣不可約的定理。

定義2.2.1：對(duì) 非負(fù)矩陣A我們這樣定義A的有向圖G（A），包括n個(gè)頂點(diǎn)1，2，…，n和頂點(diǎn)間的弧i→j當(dāng)且僅當(dāng)αij≠0，形如i→t1，t1→t2，…，tm-1→j的弧的序列稱為連接i到j(luò)的路，路的長(zhǎng)度定義為序列中弧的條數(shù)m，連接頂點(diǎn)i到自身的路叫做循環(huán)。如果一個(gè)循環(huán)路過(guò)不同頂點(diǎn)的次數(shù)只有一次，則稱該循環(huán)為回路.

比如：令A(yù)=■，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稱為強(qiáng)連通的，若對(duì)G中頂點(diǎn)集的任意有序?qū)Γ╥，j），i≠j都有一條從i到j(luò)的路。

定理2.2.1：矩陣A是不可約的當(dāng)且僅當(dāng)A的有向圖G（A）是強(qiáng)連通的.

證明：由于αij（q）>0當(dāng)且僅當(dāng)存在一條由q條弧組成的從i到j(luò)的路.

定理得證。

由定理可知，我們可以通過(guò)有向圖來(lái)判定矩陣是否為不可約，如例2.2.1，因G（A）， G（C）是強(qiáng)連通的，則A和C不可約，而G（B）不是強(qiáng)連通的，則B是可約的。

此外，還可以通過(guò)有向圖來(lái)確定一個(gè)不可約矩陣是否為本原矩陣，也就是可以求不可約矩陣的非本原性指標(biāo)。而這個(gè)指標(biāo)就等于有向圖中所有循環(huán)的長(zhǎng)度的最大公因數(shù)。如果指標(biāo)為1，則說(shuō)明該不可約矩陣是本原矩陣，否則不是本原矩陣。

定義2.2.2：設(shè)A是有最大特征值ρ（A）的n×n不可約矩陣，并且恰好有h個(gè)模為ρ（A）的特征值，數(shù)h稱為A 的非本原性指標(biāo)，或簡(jiǎn)稱指標(biāo)。如果h=1，則稱A為本原的，否則稱為非本原的。

四、結(jié)束語(yǔ)

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