全單位模矩陣

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

基本介紹

• 中文名：全單位模矩陣
• 外文名：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是 的任一非奇異子矩陣，若B是A或 的子矩陣，則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都是整數矩陣。

定理5 設A是全單位模矩陣，如果線性規劃問題(2)式有最優解，則(2)式必有最優整數解。

由定理5知，若A是全單位模矩陣，則整數線性規劃問題(1)式中的整數約束可以去掉而化為線性規劃問題(2)式來求解。

考慮整數線性規劃問題問題

這裡A是整數矩陣，b是整向量。它對應的線性規劃問題為

因為等價於

其中是單位矩陣。並且由定理3中的(5)和(1)知：A為全單位模矩陣若且唯若為全單位模矩陣。

定理6 設A是全單位模矩陣，則整數線性規劃問題(3)式中的整數約束可以去掉而化為線性規劃問題(4)式。

定理5和定理6是整數線性規劃中兩個重要的結論，它們表明：在一定條件下，整數線性規劃可以化為線性規劃來解。這就大大簡化了整數線性規劃的求解。