魏其萍王 躍柳 彬

(1.貴州民族大學 數據科學與信息工程學院,貴州 貴陽 550025;2.貴州大學 數學與統(tǒng)計學院,貴州 貴陽 550025)

0 引言

極大線性無關組的個數,一般出現在代數問題中,而對于線性問題而言,這種問題一般轉變到矩陣之上.矩陣產生于生活并在生活中發(fā)展,然而在矩陣中,矩陣的秩扮演著重要角色.通常來說,把矩陣看成是滿足某些條件的向量按照一定的排列方法放在一起,其中給定的所有行向量(一般設其個數有限),如果在給出的極大線性無關組里面所含的向量是n個,則把這個n叫作是目標矩陣的行秩.[1]同樣有列秩的說法.給出具體線性方程組,一般要問有無實際意義的解,而矩陣的秩正是判斷的一種方法.向量空間中,矩陣扮演重要角色,因為矩陣的產生與向量空間中的向量有關,多個向量合在一起構成了向量組,它的線性相關與否這方面的理論,至今仍然是貫穿線性代數相關理論的主線.隨著時代發(fā)展,在科學技術、天文地理、橋梁建筑等各個領域都涉及這類問題,當然有部分非線性的方程也能夠近似或者直接化為線性問題來求解.[2]矩陣的秩仍然常常被用來判斷對向量滿足線性相關與否.因此,向量等矢量問題的極大線性無關組的數目在理論上具有實際意義.

1 求極大線性無關組的幾種方法

如前所述,求極大線性無關組實際上都等價于求矩陣的秩.下面以求解矩陣的秩為例,說明求解的幾種方法,并將在第二部分中對它們進行比較.

1.1 定義法

根據秩的定義,在一個給定的有限維矩陣中,行秩、列秩和秩相等,注意到是有限維,因此這個數目是確定的,并且這個數恰好就是行或列向量組中極大線性無關組的個數.在這樣的前提之下,只要通過適當的方法計算得到矩陣行或列向量組的秩,我們便可以很方便地達到矩陣求秩的目標.因為行秩等于列秩.[3]換言之,行或者列向量的極大線性無關組如果有k個,那么k就是該矩陣的秩.

利用定義法求矩陣秩的步驟為:

(1)設矩陣A的行或列的向量組是α1,α2,…,αn.

(2)假設存在n數使得k1α1+k2α2+…+k nαn=0.

(3)根據α1,α2,…,αn的各個分量寫出適當的方程組,并且顯然要滿足:

(4)解上述方程組.若存在非零解,則A的秩小于n.若只有零解,則A的秩為n.[4]

利用定義直接計算矩陣的秩,主要看行向量或列向量的線性相關的數目最多是多少,這種計算的方法類似于初等變換方法,但卻與初等變換有實質性的差異,需要我們在運用中慢慢體會.

1.2 初等變換法

初等變換方法的原理是通過類似于解線性方程組中的加減消元法那樣.初等變換之后,A變成等價階梯形.階梯形矩陣中,用行判斷時整行的數值都不是0的那些行數目數就是該矩陣的秩,一般記r(A)為矩陣A的秩.當然用列判斷的時候也類似.所謂的階梯形矩陣,指的是將一個矩陣化成是具有上三角形或者下三角形內的數值全為零的形式.矩陣的初等行變換有如下3種:[1]

(1)互換行列式任意兩行的位置,這樣的做法僅僅改變矩陣子行列式的符號;

(2)將某一行的所有元素都乘以一個非零常數;

(3)將某一行的所有元素都乘以一個非零常數后,再加到另一行去.

只要將上述中的行改成列,便對應了初等列變換.在利用初等變換求矩陣的秩時,為了方便,總可以在作初等變換時把那些很方便觀察的多個初等變換一次到位寫出來.由于矩陣的秩在這樣的變換之下還是同一個數,一般該數字在計算中不會出問題.

1.3 子式法

利用矩陣子式的方法尋找矩陣的秩,最主要的便要在矩陣的非零子式中,找出階數最高的.按照子式定義的方法來看,所有子式不是零的里面階數最高的那個,對應的階數就是對應矩陣的秩.[5]因此首先要劃分出矩陣的子式,然后在所有這些階子式中找出非零子式的最高階.

利用子式求秩,主要在能夠觀察的情況下運用,因為在一個矩陣中,它的子方陣很多,要計算諸多的子方陣的行列式,計算量是一個嚴重的問題.

1.4 特征值法

利用特征值法求矩陣的秩經常出現在方陣中,一般是將單位矩陣乘以一個未知的參數后與待求秩的矩陣作差,令作差后的矩陣行列式為零時解出非零參數.以n階矩陣為例,未知參數可能有n個,此時令行列式為零時解出非零參數.如果有k個,則矩陣的秩為k.特別地,如果待求矩陣容易主對角化,那樣很容易計算矩陣的秩.

利用特征值計算矩陣的秩,需要解行列式,因此在運用這種方法時,通常要求所求的矩陣是方陣,在方陣的前提下,才能夠有行列式一說.特征值與矩陣之間的實際應用很廣泛,特別在研究與矩陣相關的問題中,我們會遇到各種各樣的矩陣和特征值問題.

2 幾種方法的計算復雜度比較

2.1 不同方法求同一矩陣的秩

為了比較計算復雜度,我們分別用上述不同的方法求下面矩陣的秩:

注意,這里的矩陣為軟件隨機生成,若有雷同,純屬巧合.

解:方法1:利用初等行變換.對A進行初等變換得

顯然,最終所獲得的階梯形矩陣中,不全為0的行數是4,從而可得出所求矩陣的秩為4;當然,也可以用初等列變換,同樣能夠得出A的秩為4;

方法2:利用子式.若存在四階子式不為0,則A的秩為4.由行列式的初等變換可知

從而矩陣A的秩為4.事實上,方法一中我們施行的變換恰好也是行列式的初等變換;

方法3:利用定義求矩陣的秩.矩陣A的行向量組表示如下:

顯然f(0)=-1≠0,這說明矩陣A沒有0特征值,于是A的秩是4.

根據上述例子不難發(fā)現,對于同一個矩陣,利用初等變換、子式、定義以及特征值等4種方法都可以求出它的秩,但在求解過程中還是出現一定的差異.由于上述例子只是從4階方陣來表述矩陣的秩,對計算復雜度的比較不是很明顯,因此下面我們就這4種方法的適用范圍和差異做簡單介紹.下面僅僅從理論上說明計算的復雜度,不再用例子說明.

2.2 不同方法計算復雜度比較

在用初等變換的方法求秩時非常方便.對隨即給出的有限維矩陣,總可以采用恰當的初等變換.經過有限次后就把原來的矩陣變到了一個階梯形的.注意到矩陣的秩總是不隨著變換而改變,再利用得到的階梯形矩陣來對比判斷目標矩陣的秩總是很有必要的,因為此時階梯形矩陣的秩便是原矩陣的秩.另外,我們還可充分考慮其他問題,例如在施行初等變換把一個目標矩陣變成另一個階梯形矩陣的過程中,為了節(jié)省時間和篇幅,可以多個初等變換同時進行,最終很快便可以獲得想要的結果;當然,有時候可以將初等行與列變換混合使用以達到更方便有效地解決我們的目標問題的目的.

在利用定義來求矩陣的秩時,首先要明確該矩陣的行或列向量,利用向量是否線性相關來判斷矩陣的秩是多少.在這個方法中,以n行m列的矩陣為例,通常利用n和m的最小值來計算,假設n≤m,我們則利用行向量是否線性相關來計算,便要定義n個未知數,但是解n元一次方程組也是比較棘手的過程,這個過程中稍不留神便會出現很大的錯誤.

在采取特征值方法時,求矩陣的秩也比較難.由于涉及矩陣的行列式計算,因此特征值方法一般只用于方陣中.如果方陣能夠利用慧眼轉變到主對角型,很方便的就可以求出目標矩陣的秩;如果方陣中零元素特別多,相對也比較容易計算.對于n階方陣,如果其中的元素大多數都不為零,利用特征值方法時,單位矩陣的未知數倍與目標矩陣作差后的行列式也是n階,要解這樣的一個n階行列式為零的未知數,一般來說難度系數特別大,因為在包括4階及其以下的方陣中,求解未知數時總有計算公式,但大于或等于5階時便沒有公式可以遵循,因此當未知數為零時如果恒等式不成立,那么目標矩陣是滿秩的,但當出現多重零根時便不好判斷矩陣的秩是多少.

不難發(fā)現,對于行列數不大于4的矩陣而言,上述的4種方法在計算矩陣的秩時差異不是很大.但是對于行或者列中的最小數目比4更大時,初等變換方法適用于任意的矩陣,并且考慮到其他情況,如節(jié)省時間等等,計算矩陣的秩時可以同時實施很多個初等變換或者多步運算,并且初等行和列變換都可以混合使用以減少必要的步驟;子式判別法適用于稀疏矩陣,當矩陣的某幾行或某幾列能夠直觀表現出階梯形時,便可以直接判定目標矩陣的秩不會小于某一個正整數,再計算大一階的子式;根據秩的定義來計算矩陣的秩,需要解多元一次方程組,如果目標矩陣是稀疏矩陣,這種方法也非常實用;而在采用特征值方法計算矩陣的秩,一般要求目標矩陣是方陣,如果目標矩陣是稀疏的,也很容易求出非零特征值的個數.但出現多重零特征值時不好判斷矩陣的秩是多少.

因此,對于求行列數更高的矩陣的秩時,利用初等變換更方便,對于n行m列且n≤m的矩陣,在多個初等行變換同時施行時,如果所有行第1個數不為零,第一步便可以將第2行到第n行的第1個數都化為零,即n-1個初等行變換同時進行,假設第2行第2個數不為零,那么第二步便可以n-2個初等行變換同時進行,將第3行到第n行的第2個數都化為零,……,以此下去,也特別容易將目標矩陣化為階梯形.計算的時間復雜度約為

當用特征值方法判斷時,作差時計算復雜度為n,n階方陣的行列式復雜度為1,該行列式計算具有復雜度.采用行列式的定義時計算起來的時間復雜度約為

如果未知數表示的特征值為零時行列式成立,則說明矩陣不滿秩,那么求解不為零的特征值的個數又將增加復雜度,甚至可能算不出來.

關于極大線性無關組的求解,以上我們利用等價描述求矩陣的秩來介紹最為基本的幾種復雜度.而實際上關于極大線性無關組,求解方法遠不止這些,建議讀者研讀文獻[6-12],特別是線性規(guī)劃和線性系統(tǒng)的最優(yōu)控制問題方面,文獻[8-12]給出了很多優(yōu)化和計算方法,這些文獻涉及一般的線性方程以及微分積分方程的控制系統(tǒng),建議有興趣的讀者仔細研讀,必將有所收獲,此處不再一一介紹.

3 結語

綜上所述,求解極大線性無關組雖然方法各異,不同的方法對應的計算復雜度差異相當大,以矩陣求秩為例,對于低階矩陣,無論哪一種方法都很方便,但對于高階矩陣而言,我們更愿意推薦利用初等變換的方法求矩陣的秩.本文主要以矩陣求秩為例對求解極大線性無關組的幾種方法進行比較詳細的說明和比較,理論與實際結合,初衷是為那些基礎比較薄弱的學生提供矩陣分析和線性代數等基礎方面的幫助,不當之處在所難免,望各位讀者指正為謝!