一類非負本原矩陣對

羅美金

(河池學院 數學與統計學院，廣西 宜州 546300)

一類非負本原矩陣對

羅美金

(河池學院 數學與統計學院，廣西 宜州 546300)

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

非負；本原；矩陣對；上界

0 引言

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

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

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

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

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

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

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

圖1 未著色有色圖D

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

(1)

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

1 本原條件

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

證明充分性：結合圖1，顯然，D是強連通的。由引理1，可知D是本原的當且僅當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是本原的當且僅當a=k(m-1)+1,b=m-1(k,m∈Z+)。

2 γ2=2的指數上界

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

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

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

類型1：弧γ1-1→γ1是藍色的；類型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，比較各本原指數的大小，可得如圖1的雙色有向圖D的本原指數上界，即定理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] 羅美金,高玉斌.一類雙色有向圖的本原指數[J].中北大學學報:自然科學版,2008,29(2):95-100.

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

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

2014-06-24

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

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

O157.5

A

1008-4657(2014)04-0072-04

寸曉非]