全單位模矩陣

全單位模矩陣

如果一個矩陣的任何子方陣的行列式等於1,-1或0,則稱這個矩陣是全單位模矩陣。把m階單位矩陣用Im表示。顯然,Im是全單位模矩陣。

基本介紹

  • 中文名:全單位模矩陣
  • 外文名:total unimodular matrix
  • 所屬學科:數學
  • 相關概念:行列式,整數線性規劃問題等
定義,相關性質,關於整數線性規劃問題,

定義

如果一個矩陣的任何方陣的行列式等於1,-1或0,則稱該矩陣為全單位模矩陣(total unimodular matrix)。
不難知道,全單位模矩陣的一個明顯的必要條件是它的元素為1,-1或0,下面的定理給出了全單位模矩陣的一個充分條件。
定理1
,且對一切
或0,如果下面兩個條件都滿足,則
是全單位模矩陣。
(1)B的每一列最多有兩個非零元素;
(2) B的行可分劃成兩個子集
,使得對於同一列中兩個非零元素,當這兩個非零元素符號相同時,對應的兩行在不同的行子集中;當符號不同時,對應的兩行在同一行子集中。
證明:歸納法證明。只需證明B的任何一個子方陣B'的行列式
=1,-1或0,設B'是n階方陣,對n進行歸納.若n=1時,則顯然成立。
由於B滿足(1)和(2),因此B的任何子矩陣也滿足這兩個條件,假設B的任何k階子方陣的行列式等於1,-1或0,任取B
階子方陣B',它也滿足條件(1)和(2),如果B'的某一列恰有一個非0元素,記該元素在B'中的餘子式為b,則
=±b,由歸納假設,b=1,-1或0,從而
=1,-1或0;如果B'的每一列恰有兩個非零元素,則對B'中任何列
,有
B'的第
行記為
,則
,即B'的所有行向量是線性相關的,故
=0。

相關性質

定理2非空無環有向圖的關聯矩陣是全單位模的。
順便指出:圖的關聯矩陣不一定是全單位模矩陣,例如
定理3
全單位模矩陣A有下列性質:
(1)
的任何子矩陣是全單位模矩陣。
(2)
是全單位模矩陣。
(3) 把A的兩行互換得到的矩陣是全單位模矩陣。
(4) 把A的兩列互換得到的矩陣是全單位模矩陣。
(5)
是全單位模矩陣。
(6)
是全單位模矩陣。
(7) 設
,則
是全單位模矩陣。
(8) 設
,則
是全單位模矩陣。
證明:性質(1)、(2)、(3)、(4) 是顯然的。
下證(5)。
B
的任一非奇異子矩陣,若BA
的子矩陣,則B的行列式的絕對值|det B|=1;否則,設
這裡
分別是
的子矩陣。互換B的某些行可得
其中
為單位矩陣。記
注意到
,並且
由於A是全單位模矩陣,故
或1,又因B是非奇異矩陣,所以|detB|=1,這就證明了
是全單位模矩陣。同理可證:
也是全單位模矩陣。
由(2)和(5)知,(6)成立。
根據證明(5)的類似推理,不難證明(7)。
(8)可以由(2)和(7)得到。

關於整數線性規劃問題

網路最最佳化的許多問題常常可以用一個整數線性規劃模型來描述。整數線性規劃是指要求變數取整數值的線性規劃。
考慮整數線性規劃問題
這裡,“
”是指
的每個分量都是非負整數。所有元素均是整數的矩陣稱為整數矩陣。所有分量都是整數的向量稱為整向量。我們假定(1)式中的A是整數矩陣,b是整向量。
在整數線性規劃問題(1)式中去掉整數約束就得到線性規劃問題
如果(2)式的可行解
是整向量,則稱
為(2)式的整數解。如果(2)式的最優解
是整數解。則稱
是(2)式的最優整數解。因此,整數線性規劃問題(1)式的求解可以化為求線性規劃問題(2)式的最優整數解。
定理4 A為行滿秩整數矩陣,則下面三個條件等價:
(i) A的任意基矩陣B的行列式
(ii) 對於任意整向量
的極點的每個分量都是整數。
(iii) A的任何基矩陣B的逆矩陣B-1都是整數矩陣。
定理5A是全單位模矩陣,如果線性規劃問題(2)式有最優解,則(2)式必有最優整數解。
由定理5知,若A是全單位模矩陣,則整數線性規劃問題(1)式中的整數約束可以去掉而化為線性規劃問題(2)式來求解。
考慮整數線性規劃問題問題
這裡A是整數矩陣,b是整向量。它對應的線性規劃問題為
因為
等價於
其中
是單位矩陣。並且由定理3中的(5)和(1)知:A為全單位模矩陣若且唯若
為全單位模矩陣。
定理6 A是全單位模矩陣,則整數線性規劃問題(3)式中的整數約束可以去掉而化為線性規劃問題(4)式。
定理5和定理6是整數線性規劃中兩個重要的結論,它們表明:在一定條件下,整數線性規劃可以化為線性規劃來解。這就大大簡化了整數線性規劃的求解。

相關詞條

熱門詞條

聯絡我們