如果一個矩陣的任何子方陣的行列式等於1,-1或0,則稱這個矩陣是全單位模矩陣。把m階單位矩陣用Im表示。顯然,Im是全單位模矩陣。
基本介紹
- 中文名:全單位模矩陣
- 外文名:total unimodular matrix
- 所屬學科:數學
- 相關概念:行列式,整數線性規劃問題等
定義,相關性質,關於整數線性規劃問題,
定義
如果一個矩陣的任何方陣的行列式等於1,-1或0,則稱該矩陣為全單位模矩陣(total unimodular matrix)。
不難知道,全單位模矩陣的一個明顯的必要條件是它的元素為1,-1或0,下面的定理給出了全單位模矩陣的一個充分條件。
定理1 設
,且對一切
和
或0,如果下面兩個條件都滿足,則
是全單位模矩陣。
![](/img/9/b69/621cdf328704a2d2daad03c92cb8.jpg)
![](/img/8/f35/bc3f78450a8a298a7d74543ab345.jpg)
![](/img/1/df7/2451fbc540802864a518074644cd.jpg)
![](/img/e/93b/ddc9140af371c6f385499181a9fc.jpg)
(1)B的每一列最多有兩個非零元素;
(2) B的行可分劃成兩個子集
和
,使得對於同一列中兩個非零元素,當這兩個非零元素符號相同時,對應的兩行在不同的行子集中;當符號不同時,對應的兩行在同一行子集中。
![](/img/b/ec8/703c4051ebb8221410be491edab6.jpg)
![](/img/b/a25/29248b523ae2ce2975ccc11597c9.jpg)
由於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'中任何列
,有
![](/img/1/9bf/37b27a216b43d5698c0e718975e5.jpg)
![](/img/7/835/61d1dff1b4974e5ed0ba7ffcb89e.jpg)
![](/img/7/835/61d1dff1b4974e5ed0ba7ffcb89e.jpg)
![](/img/0/5b4/f9b9317a8a7234c366eaf6f837ce.jpg)
相關性質
定理2非空無環有向圖的關聯矩陣是全單位模的。
順便指出:圖的關聯矩陣不一定是全單位模矩陣,例如
。
![](/img/c/6d8/5ebbde9c9cd087e219df0a5b74fb.jpg)
定理3
全單位模矩陣A有下列性質:
![](/img/c/1ff/887e3630006028bce5f2f673b641.jpg)
(1)
的任何子矩陣是全單位模矩陣。
![](/img/e/fdb/a6209db3366e646d13bc79d2331b.jpg)
(2)
和
是全單位模矩陣。
![](/img/e/256/06743ae4d9b45cd0b7e7a4c63503.jpg)
![](/img/3/ab1/b04580bcda545935a13d0d8de2d3.jpg)
(3) 把A的兩行互換得到的矩陣是全單位模矩陣。
(4) 把A的兩列互換得到的矩陣是全單位模矩陣。
(5)
和
是全單位模矩陣。
![](/img/1/a66/1b75f14af9addf0be2dee20e5eb4.jpg)
![](/img/5/7b2/399b49a717bd3620c47d321d2863.jpg)
(6)
和
是全單位模矩陣。
![](/img/2/8da/f3cf578a826d6840c38dd9fb19fc.jpg)
![](/img/d/8e6/f2f4f5b138b8ffdb7cb163608a50.jpg)
(7) 設
,則
和
是全單位模矩陣。
![](/img/b/627/8a7a9be0d251bcdff0291d9e0ba0.jpg)
![](/img/c/be0/15327eb5b0072e421c6d12504f7d.jpg)
![](/img/5/ca9/a2b2ed7237a6dbcc9e29500048f1.jpg)
(8) 設
,則
和
是全單位模矩陣。
![](/img/e/086/046725e37714340e69f42b4ab076.jpg)
![](/img/1/490/539cf564bb87186afdab741c578e.jpg)
![](/img/c/67c/20adb8493588a114fa45d90ea3ef.jpg)
證明:性質(1)、(2)、(3)、(4) 是顯然的。
下證(5)。
設B是
的任一非奇異子矩陣,若B是A或
的子矩陣,則B的行列式的絕對值|det B|=1;否則,設
![](/img/1/a66/1b75f14af9addf0be2dee20e5eb4.jpg)
![](/img/8/04f/6b851d3a413d085c7afdce9823f4.jpg)
![](/img/d/327/ad763fed391d56c33a8a29a5a8a0.jpg)
![](/img/6/c9e/15bd905fe413268d0555011756f2.jpg)
![](/img/b/619/00690743c5c87eb1a21de35d4b60.jpg)
![](/img/d/dc0/f05187539bfa2f8cd5e6cd0742ef.jpg)
![](/img/2/32d/4a6439a8e2e0a775d73611a2a715.jpg)
![](/img/4/462/fb314779f0fcf66f09bbea6ddba5.jpg)
![](/img/8/2b3/603094dae816cc832c1b748b67b6.jpg)
![](/img/d/07a/bf47343d03780fa34707a5f2c9e6.jpg)
![](/img/0/90d/1947cbe7de445487d6d6b482a07e.jpg)
![](/img/1/a66/1b75f14af9addf0be2dee20e5eb4.jpg)
![](/img/5/1ba/bf2622b2a9be0a4acf1164c7fb0b.jpg)
由(2)和(5)知,(6)成立。
根據證明(5)的類似推理,不難證明(7)。
(8)可以由(2)和(7)得到。
關於整數線性規劃問題
網路最最佳化的許多問題常常可以用一個整數線性規劃模型來描述。整數線性規劃是指要求變數取整數值的線性規劃。
考慮整數線性規劃問題
![](/img/f/2d6/a5b9e16da1bea5779846942367c8.jpg)
![](/img/e/86c/7469e9c4b1931f6d3a01df49458b.jpg)
![](/img/0/a02/649da55811a340f974cf02187c91.jpg)
在整數線性規劃問題(1)式中去掉整數約束就得到線性規劃問題
![](/img/d/f1f/70bb45e628600fa6ecfc884afb32.jpg)
![](/img/d/dc4/7eb475b7f3b5298ac8e780190b10.jpg)
![](/img/d/dc4/7eb475b7f3b5298ac8e780190b10.jpg)
![](/img/b/8ef/cabe03320423eafff5c7f010c393.jpg)
![](/img/b/8ef/cabe03320423eafff5c7f010c393.jpg)
定理4 設A為行滿秩整數矩陣,則下面三個條件等價:
(i) A的任意基矩陣B的行列式
;
![](/img/a/102/af16a2960397c3fccd65287e6c81.jpg)
(ii) 對於任意整向量
的極點的每個分量都是整數。
![](/img/f/99b/0e885e2d760e84f44dfc00161114.jpg)
(iii) A的任何基矩陣B的逆矩陣B-1都是整數矩陣。
定理5 設A是全單位模矩陣,如果線性規劃問題(2)式有最優解,則(2)式必有最優整數解。
由定理5知,若A是全單位模矩陣,則整數線性規劃問題(1)式中的整數約束可以去掉而化為線性規劃問題(2)式來求解。
考慮整數線性規劃問題問題
![](/img/3/4d5/4a2c35c4d642b1043f2e52242992.jpg)
![](/img/c/d03/b44e7d2458e15159371d85f40d3d.jpg)
![](/img/a/f98/2a81bc2ba81fa87985cdc374b2ab.jpg)
![](/img/4/e5a/ce4c7c4547f7c165a8afcb858b9d.jpg)
![](/img/9/36f/9fc4469fb4662daf111b9454fa00.jpg)
![](/img/d/14c/dc50c65c83cc95396f394bbda526.jpg)
定理6 設A是全單位模矩陣,則整數線性規劃問題(3)式中的整數約束可以去掉而化為線性規劃問題(4)式。
定理5和定理6是整數線性規劃中兩個重要的結論,它們表明:在一定條件下,整數線性規劃可以化為線性規劃來解。這就大大簡化了整數線性規劃的求解。