羅美金

(河池學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 宜州 546300)

一類非負(fù)本原矩陣對

羅美金

(河池學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 宜州 546300)

研究一類非負(fù)矩陣對，它所對應(yīng)的伴隨有向圖中含有兩個圈γ1,γ2，公共弧γ1-1→γ1，證明了這類雙色有向圖本原的充分必要條件，并給出了γ2的頂點數(shù)為最小值2時的本原指數(shù)上界。

非負(fù)；本原；矩陣對；上界

0 引言

n階非負(fù)矩陣對(A,B)與其具有n個頂點的伴隨有向圖D(A,B)存在一一對應(yīng)關(guān)系。D(A,B)中弧存在與否可由非負(fù)矩陣對(A,B)中元素的數(shù)值來判斷。如：D(A,B)中是否存在紅弧(藍(lán)弧)可由矩陣A=(aij)(B=(bij))中元素的數(shù)值可判斷，若aij>0(bij>0)，則從頂點i到頂點j存在一條紅弧(藍(lán)弧)；若aij=0(bij=0)，則從頂點i到頂點j不存在紅弧(藍(lán)弧)[1]。

有向圖D中只含紅弧和藍(lán)弧，那么D是一個雙色有向圖。如果非負(fù)矩陣對(A,B)是本原的，那么非負(fù)矩陣對(A,B)所對應(yīng)的伴隨有向圖，即雙色有向圖D(A,B)也是本原的，D(A,B)的本原指數(shù)exp(D(A,B))即為非負(fù)矩陣對(A,B)的本原指數(shù)exp(A,B)。由非負(fù)矩陣對的本原指數(shù)的概念，可定義雙色有向圖的本原指數(shù)的概念為：

任給定D中的一條途徑ω，ω的分解為向量(r(ω),b(ω))或(r(ω),b(ω))T，稱ω為一條(r(ω),b(ω))-途徑，其中r(ω)和b(ω)分別表示ω中紅弧和藍(lán)弧的條數(shù)。若存在非負(fù)整數(shù)h和k，且h+k>0，使得D中的每一對頂點(i,j)都存在從i到j(luò)的(h,k)-途徑，則雙色有向圖D是本原的，且h+k的最小值為雙色有向圖D的本原指數(shù)，記作exp(D)。

設(shè)D中含有圈γ1,γ2,…,γl,C={γ1,γ2,…，γl}是D的圈集合，定義D的圈矩陣

其中ai，bi表示圈γi中的紅弧和藍(lán)弧的數(shù)目。若M的秩小于2，則M的content(記為content(M))定義為0，否則定義content(M)為M的所有非零2階主子式的最大公因數(shù)。

引理1[2]一個至少包含一條紅弧和一條藍(lán)弧的雙色有向圖D是本原的，當(dāng)且僅當(dāng)D是強連通的，且content(M)=1。

目前國內(nèi)外關(guān)于非負(fù)本原矩陣對的研究已取得了一些成果[1-6]。本文研究一類非負(fù)矩陣對，它所對應(yīng)的伴隨有向圖D的未著色圖如圖1所示。

圖1 未著色有色圖D

由圖1可知，D中僅含兩個圈，圈長分別為γ1和γ2，兩個圈有公共弧γ1-1→γ1。不妨設(shè)γ1>γ2≥2，則D的圈矩陣可寫為

(1)

其中a,b為正整數(shù)，且a≤γ1-1,b≤γ2-1。

1 本原條件

定理1D是如圖1的雙色有向圖，若γ1=km-1,γ2=m，那么D是本原的當(dāng)且僅當(dāng)a=k(m-1)-1,b=m-1(k,m∈Z+)。

證明充分性：結(jié)合圖1，顯然，D是強連通的。由引理1，可知D是本原的當(dāng)且僅當(dāng)content(M)=1，即det(M)=aγ2-bγ1=am-b(km-1)=±1。由此可得：

必要性：若a=k(m-1)-1,b=m-1時，易得det(M)=-1，故D是本原的。定理得證。

類似定理1的證明，可得以下三個定理。

定理2D是如圖1的雙色有向圖，若γ1=km+1,γ2=m，那么D是本原的當(dāng)且僅當(dāng)a=k(m-1)+1,b=m-1(k,m∈Z+)。

2 γ2=2的指數(shù)上界

由定理5可得，det(M)=-1時所對應(yīng)的圈矩陣及圈矩陣的逆矩陣分別為

det(M)=1時所對應(yīng)的圈矩陣及圈矩陣的逆矩陣分別為

以下分兩種類型討論雙色有向圖D的本原指數(shù)上界：

類型1：弧γ1-1→γ1是藍(lán)色的；類型2：弧γ1-1→γ1是紅色的。

定理6 若如圖1的雙色有向圖D是本原的，det(M)=-1且屬于類型1，則

定理7 若如圖1的雙色有向圖D是本原的，det(M)=-1且屬于類型2，則

類似定理6、定理7的證明，可得定理8、定理9。

定理8 若如圖1的雙色有向圖D是本原的，det(M)=1且屬于類型1，則

定理9 若如圖1的雙色有向圖D是本原的，det(M)=1且屬于類型2，則

綜合定理6～9，比較各本原指數(shù)的大小，可得如圖1的雙色有向圖D的本原指數(shù)上界，即定理10。

定理10 若如圖1的雙色有向圖D是本原的，則

[1] B L Shader,S Suwilo.Exponents of nonnegative matrix pairs[J].Linear Algebra Appl,2003,363:275-293.

[2] SHAO Yan-ling,GAO Yu-bin,SUN Liang.Exponent of a class of two-colored digraphs[J].Linear and Multilinear Algebra,2005,53(3):175-188.

[3] GAO Yu-bin,SHAO Yan-ling.Exponent of two-colored double directed cycles[J].Journal of Natural Science of Heilongjiang University,2004(4):55-58.

[4] 羅美金,高玉斌.一類雙色有向圖的本原指數(shù)[J].中北大學(xué)學(xué)報:自然科學(xué)版,2008,29(2):95-100.

[5] 羅美金,高玉斌.一類恰含三個圈的三色有向圖的本原指數(shù)[J].山東大學(xué)學(xué)報:理學(xué)版,2008,43(1):65-72.

[6] 羅美金.一類雙色有向圖的本原指數(shù)集[J].數(shù)學(xué)的實踐與認(rèn)識,2012,42(24):253-258.

2014-06-24

廣西壯族自治區(qū)教育廳項目：雙色及多色有向圖本原指數(shù)的研究(YB2014335)

羅美金(1981-)，女，江西廣豐人，河池學(xué)院講師，碩士。研究方向：組合數(shù)學(xué)。

O157.5

A

1008-4657(2014)04-0072-04

寸曉非]