復(fù)方陣的行列式值域及賦權(quán)圖的保直徑生成樹.pdf

1、本文的研究課題來自于兩個方面,分別是復(fù)方陣的行列式值域和賦權(quán)連通圖的保直徑生成樹。其中復(fù)方陣的行列式值域來源于符號可解性理論從實數(shù)域向復(fù)數(shù)域的推廣,保直徑生成樹問題來源于網(wǎng)絡(luò)設(shè)計。
　　 符號可解性理論是為了解決經(jīng)濟(jì)學(xué)中的定性分析類問題而提出的數(shù)學(xué)理論,其開創(chuàng)性工作是由諾貝爾經(jīng)濟(jì)學(xué)獎獲得者、經(jīng)濟(jì)學(xué)家P.Samuelson在1947年作出的。經(jīng)過半個多世紀(jì)的發(fā)展,實數(shù)域下的符號可解性理論已臻于完善。目前的研究工作集中于該理論從實數(shù)

2、域向復(fù)數(shù)域推廣過程中出現(xiàn)的一些新問題。本文涉及的推廣有兩種,分別是Ray模式推廣及復(fù)符號模式推廣。其中Ray模式推廣是由J.J.McDonald等人在1997年引入的,復(fù)符號模式推廣則是由Eschenbach等人在1998年引入的。
　　 行列式值域是為了研究復(fù)推廣中矩陣的Ray非異性或復(fù)符號非異性而提出的概念。本文的第二至第四章主要研究了矩陣行列式值域的相關(guān)性質(zhì),包括行列式值域的拓?fù)湫再|(zhì)、拓?fù)湫再|(zhì)與矩陣的代數(shù)性質(zhì)之間的關(guān)系、以

3、及兩種不同復(fù)推廣在行列式值域類問題上的關(guān)系。第二及第三章中研究的是Ray模式行列式值域,第四章中討論兩種推廣在行列式值域類問題中的關(guān)系。
　　 確定行列式值域邊界的位置有利于理解其拓?fù)浣Y(jié)構(gòu)。1998年,Eschenbach等人對復(fù)符號模式行列式值域提出公開問題:是否復(fù)符號非異矩陣的行列式值域的邊界都落在軸上?2005年,Shao和Shan正面回答了這個問題,證明了任意復(fù)方陣的復(fù)符號模式行列式值域的邊界都落在坐標(biāo)軸上。本文的第二章

4、研究了Ray模式行列式值域RA的非0邊界,確定了其可能出現(xiàn)的位置。稱一個復(fù)方陣A的行列式展開式中非0項的Ray所構(gòu)成的集合為其行列式值域展開基,記為T(A)。我們證明了RA的邊界與單位圓的交集bU,(RA)是T(A)的子集。這個結(jié)論有一個直觀的幾何解釋:RA是由T(A)生成的錐的子集,而生成錐的邊界與單位圓的交集也是T(A)的子集。結(jié)合第四章中的結(jié)果可知,Shao和Shan在2005年的關(guān)于復(fù)符號模式行列式值域邊界的結(jié)論是此結(jié)論的一個推

5、論。
　　 復(fù)方陣的葉數(shù)nR(A)指的是RA＼{0}的連通分支個數(shù)。2006年,我們證明了任意復(fù)方陣的葉數(shù)只能等于0、1和2。其中葉數(shù)為0的情形是一種平凡情形,一個復(fù)方陣的葉數(shù)為0當(dāng)且僅當(dāng)其項秩不滿。于是滿項秩的所有復(fù)方陣可以按其葉數(shù)自然的分為兩類。若稱葉數(shù)為1的矩陣是第一類矩陣,葉數(shù)為2的矩陣是第二類矩陣,則就自然產(chǎn)生了如下的一個分類問題:能否找到判定第一、第二類矩陣的非平凡的充要條件?
　　 本文的第三章中,我們完全

6、解決了這個分類問題,給出了第二類矩陣即葉數(shù)為2的矩陣的特征刻畫。(這種特征刻畫等價的刻畫了第一類矩陣,即不是第二類的滿項秩矩陣都是第一類的。)為了給出第二類矩陣的特征刻畫,我們引入了三種基本矩陣,證明了葉數(shù)為2的矩陣都置換等價于這三種基本矩陣的半直和。于是葉數(shù)為2的矩陣的識別問題可以轉(zhuǎn)化為對三種基本矩陣的識別問題。文中同時用行列式值域展開基給出了三種基本矩陣的特征刻畫,這種特征刻畫等價于給出了識別這三種基本矩陣的算法。本章中的結(jié)論還說明

7、當(dāng)葉數(shù)為2時,矩陣的行列式值域是可計算的。
　　 在給出葉數(shù)為2的矩陣的特征刻畫的過程中,我們首先討論了復(fù)方陣的葉數(shù)與其部分可分性的關(guān)系,證明了當(dāng)葉數(shù)為2且Ray模式行列式值域不是一條經(jīng)過原點的直線時,矩陣都是部分可分的。證明的過程中我們使用了矩陣的伴隨有向圖作為工具,引入了圈鏈的概念,并證明了圈鏈在強(qiáng)連通有向圖中的普遍存在性。1997年,J.J.McDonald等人提出問題:是否存在完全不可分的Ray非異矩陣A,使得0是其行列

8、式值域展開基T(A)的凸包的相對內(nèi)點,即0∈ri(cone(T(A)))?2000年,G.Y.Lee等給出了兩個具體的4階方陣滿足上述性質(zhì),正面回答了此問題。作為證明部分可分性結(jié)論的副產(chǎn)品,在第三章中我們利用圈鏈給出了上述問題的一個較一般的例子。
　　 Ray模式推廣和復(fù)符號模式推廣是兩種不同方式的推廣,但當(dāng)矩陣中的元素都是實數(shù)和純虛數(shù)時,這兩種推廣方式等價。稱所有元素都是實數(shù)或純虛數(shù)的矩陣為軸元陣。本文的第四章中引入了復(fù)符號模

9、式矩陣規(guī)范型的概念。規(guī)范型矩陣都是軸元陣。我們證明任意矩陣的復(fù)符號模式行列式值域都與其規(guī)范型的復(fù)符號模式行列式值域相同,進(jìn)而跟其Ray模式行列式值域相同。此結(jié)論說明,復(fù)符號模式行列式值域的問題,如第二章中的邊界問題等,可以轉(zhuǎn)化為Ray模式行列式值域來考慮,Ray模式行列式值域的所有必要條件對復(fù)符號模式行列式值域均成立。此種意義下,我們可以認(rèn)為Ray模式推廣是一種更一般的推廣。
　　 生成樹問題是網(wǎng)絡(luò)設(shè)計中的一類常見問題,其典型代

10、表是最小生成樹問題。直徑是表征一個通訊網(wǎng)絡(luò)最大網(wǎng)絡(luò)時延的重要參數(shù),性能優(yōu)良的通訊網(wǎng)絡(luò)往往要求有較小的直徑。在生成樹問題中考慮直徑這個參數(shù),可得最小直徑生成樹問題。保直徑生成樹是一種特殊的最小直徑生成樹,并不是每一個通訊網(wǎng)絡(luò)所對應(yīng)的賦權(quán)圖都含有保直徑生成樹。第五章中我們給出了賦權(quán)連通圖含有保直徑生成樹的一個簡單的充分條件。具體的來說,設(shè)G=(V E,fE)是一個賦權(quán)連通圖,其中fE是邊權(quán)函數(shù)。記fV是由邊權(quán)函數(shù)fE誘導(dǎo)的點權(quán)函數(shù),其中fV