ユニモジュラ行列ぎょうれつ

数学すうがくの分野ぶんやにおいて、ある正方せいほう行列ぎょうれつ M がユニモジュラ行列ぎょうれつ（ユニモジュラぎょうれつ、英えい: unimodular matrix; 単たん模も行列ぎょうれつ）であるとは、それが整数せいすう行列ぎょうれつで、その行列ぎょうれつ式しきが +1 あるいは −1 であることを言いう。また同値どうちであるが、整数せいすうについて可逆かぎゃくであるような整数せいすう行列ぎょうれつ、すなわち、逆ぎゃく行列ぎょうれつ N が整数せいすう行列ぎょうれつであるような整数せいすう行列ぎょうれつのことも、ユニモジュラ行列ぎょうれつと言いう。これら二ふたつの定義ていぎが同値どうちであることは、クラメルの公式こうしきより従したがう。したがって、いずれの成分せいぶんも整数せいすうであるような行列ぎょうれつ M とベクトル b に対たいする方程式ほうていしき Mx = b には、M がユニモジュラ行列ぎょうれつであるとき、整数せいすう解かいが存在そんざいする。位い数すうが n のユニモジュラ行列ぎょうれつは群ぐんを成なし、それは $GL_{n}(\mathbb {Z} )$ と表記ひょうきされる。

ユニモジュラ行列ぎょうれつの例れい[編集へんしゅう]

ユニモジュラ行列ぎょうれつは行列ぎょうれつの積せきの下したで一般いっぱん線型せんけい群ぐんの部分ぶぶん群ぐんを成なす。すなわち、次つぎに挙あげる行列ぎょうれつはすべてユニモジュラ行列ぎょうれつである：

単位たんい行列ぎょうれつ
ユニモジュラ行列ぎょうれつの逆ぎゃく
二ふたつのユニモジュラ行列ぎょうれつの積せき

さらに、次つぎも成立せいりつする：

二ふたつのユニモジュラ行列ぎょうれつのクロネッカー積せきもまたユニモジュラ行列ぎょうれつである。このことは、次つぎの等式とうしきにより従したがう：

\det(A\otimes B)=(\det A)^{q}(\det B)^{p},

ここで p と q はそれぞれ行列ぎょうれつ A と B の次元じげんを表あらわす。

ユニモジュラ行列ぎょうれつの具体ぐたい例れいとしては、次つぎが挙あげられる：

シンプレクティック行列ぎょうれつ
パスカル行列ぎょうれつ（英語えいご版ばん）
置換ちかん行列ぎょうれつ
原始げんしピタゴラス三みつ組ぐみの木き（英語えいご版ばん）における三みっつの変換へんかん行列ぎょうれつ

全ぜんユニモジュラ性せい[編集へんしゅう]

全ぜんユニモジュラ行列ぎょうれつ（totally unimodular matrix, TU 行列ぎょうれつ）^{[注釈ちゅうしゃく 1]}とは、その非特異ひとくいなすべての正方せいほう部分ぶぶん行列ぎょうれつがユニモジュラ行列ぎょうれつであるような行列ぎょうれつのことを言いう。したがって、全ぜんユニモジュラ行列ぎょうれつは、必かならずしもそれ自身じしんが正方せいほう行列ぎょうれつでなくてもよい。定義ていぎより、任意にんいの全ぜんユニモジュラ行列ぎょうれつの成分せいぶんは 0、+1 あるいは −1 でしかあり得えないことが分わかる。

全ぜんユニモジュラ行列ぎょうれつは、ある線型せんけい計画けいかくが整数せいすう計画けいかくであることを確たしかめるための迅速じんそくな方法ほうほうを提供ていきょうするため、多面体ためんたい的てき組合くみあわせ論ろん（英語えいご版ばん）や組合くみあわせ最適さいてき化かにおいて極きわめて重要じゅうような概念がいねんとなる。特とくに、A が全ぜんユニモジュラ行列ぎょうれつで b を整数せいすうベクトルとしたとき、 $\{\min cx\mid Ax\geq b,x\geq 0\}$ あるいは $\{\max cx\mid Ax\leq b\}$ のような形状けいじょうの線型せんけい計画けいかくは、任意にんいの c に対たいして、整数せいすうの最適さいてき解かいを持もつ。したがって、A が全ぜんユニモジュラ行列ぎょうれつで b が整数せいすうベクトルであるなら、実行じっこう可能かのう領域りょういき（例たとえば、 $\{x\mid Ax\geq b\}$ ）のすべての極きょく値ち点てんは整数せいすうであり、したがってその実行じっこう可能かのう領域りょういきは整数せいすう多面体ためんたいとなる。

よくある全ぜんユニモジュラ行列ぎょうれつ[編集へんしゅう]

1. 2部ぶグラフの2部ぶマッチングに対たいする係数けいすう行列ぎょうれつとして得えられる無む向むかい接続せつぞく行列ぎょうれつ（unoriented incidence matrix）は、全ぜんユニモジュラ行列ぎょうれつである。一方いっぽう、非ひ2部ぶグラフの無む向こう接続せつぞく行列ぎょうれつは、全ぜんユニモジュラ行列ぎょうれつではない。より一般いっぱんに、Heller と Tompkins の論文ろんぶん ^[1] の補遺ほいにおいて、A.J. Hoffman と D. Gale は次つぎを証明しょうめいした。 $A$ を、各行かくこうが二ふたつの素す集合しゅうごう $B$ と $C$ に区分くぶんできるようなある m×n 行列ぎょうれつとする。このとき、以下いかの四よっつの条件じょうけんは合あわせて A が全ぜんユニモジュラ行列ぎょうれつであるための十分じゅうぶん条件じょうけんとなる：

$A$ のすべての列れつには、ゼロでない成分せいぶんが高々たかだか二ふたつしか存在そんざいしない；
$A$ のすべての成分せいぶんは 0、+1 あるいは −1 のいずれかである；
$A$ のある列れつの二ふたつのゼロでない成分せいぶんの符号ふごうが同一どういつであるなら、その一ひとつの行くだりは $B$ に属ぞくし、もう一ひとつの行くだりは $C$ に属ぞくす；
$A$ のある列れつの二ふたつのゼロでない成分せいぶんの符号ふごうが異ことなるなら、それら両方りょうほうの行くだりは $B$ あるいは $C$ のいずれかに属ぞくす。

後のちに、これらの条件じょうけんは、ある均衡きんこう符号ふごう付づけグラフ（英語えいご版ばん）の接続せつぞく行列ぎょうれつを定義ていぎすることが知しられた。したがってこの例れいは、符号ふごう付づけグラフの接続せつぞく行列ぎょうれつが全ぜんユニモジュラ行列ぎょうれつであるための十分じゅうぶん条件じょうけんは、その符号ふごう付づけグラフが均衡きんこうグラフであること、ということについて述のべたものである。その逆ぎゃくは、半はん辺あたり（half edge）を含ふくまない符号ふごう付づけグラフに対たいしては成立せいりつする（これはグラフの無む向こう接続せつぞく行列ぎょうれつの性質せいしつを一般いっぱん化かしたものである）^[2]。

2. 最大さいだいフローと最小さいしょう費用ひようフロー問題もんだい（英語えいご版ばん）の制約せいやく条件じょうけんは、これらの性質せいしつを備そなえる係数けいすう行列ぎょうれつ（および空そら集合しゅうごうである C）を導みちびく。したがってそのような、有界ゆうかいの整数せいすう容量ようりょうを備そなえるネットワークフロー問題もんだいには、整数せいすうの最適さいてき値ちが存在そんざいする。ここで、この事実じじつは、有界ゆうかいの整数せいすう容量ようりょうに対たいしても分数ぶんすうの最適さいてき値ちを持もつことがあり得える多た品種ひんしゅフロー問題もんだい（英語えいご版ばん）には適用てきようされないことに注意ちゅういされたい。

3. 連続れんぞく的てきな 1 の性質せいしつ：もし A が、各行かくこうにおいて 1 が連続れんぞく的てきに現あらわれるような 0-1 行列ぎょうれつである（あるいは、そのような行列ぎょうれつに置換ちかんされる）なら、A は全ぜんユニモジュラ行列ぎょうれつである（全ぜんユニモジュラ行列ぎょうれつの転置てんちはふたたび全ぜんユニモジュラ行列ぎょうれつであるため、列れつに対たいしても同様どうようのことが成立せいりつする）。

4. すべてのネットワーク行列ぎょうれつは全ぜんユニモジュラ行列ぎょうれつである。ネットワーク行列ぎょうれつの行くだりは、各かく弧こが任意にんいの方向ほうこうに向むかっているようなある木き T=(V,R) に対応たいおうする（この木きが r に根ねを持もつあるいは r から伸のびるような、根ね頂点ちょうてん r は必かならずしも存在そんざいしない）。列れつは、同おなじ頂点ちょうてん集合しゅうごう V 上うえの別べつの弧この集合しゅうごう C に対応たいおうする。行くだり R および列れつ C=st の成分せいぶんを計算けいさんするために、T 内うちの s から t への路みち P に着目ちゃくもくする。このとき、その成分せいぶんは次つぎのように決定けっていされる：

弧こ R が P において前方ぜんぽうに向むいているなら、+1;
弧こ R が P において後方こうほうに向むいているなら、-1;
弧こ R が P に現あらわれないなら、0.

詳細しょうさいについては、Schrijver (2003) を参照さんしょうされたい。

5. Ghouila-Houri は、ある行列ぎょうれつが全ぜんユニモジュラ行列ぎょうれつであるための必要ひつよう十じゅう分ふん条件じょうけんは、行くだりの全すべての部分ぶぶん集合しゅうごう R に対たいして、行くだりに符号ふごうを割わり当あてる関数かんすう $s:R\to \pm 1$ でその和わ $\sum _{r\in R}s(r)r$ （これは、その考かんがえている行列ぎょうれつと等ひとしい幅はばを持もつ行くだりベクトル）が $\{0,\pm 1\}$ に全すべての成分せいぶんを持もつようなものが存在そんざいすること（すなわち、その行くだり部分ぶぶん行列ぎょうれつが高々たかだか一ひとつの discrenpacy を持もつこと）であることを証明しょうめいした。このことと、他たのいくつかの同値どうち性せいのための条件じょうけんは、Schrijver (2003) において示しめされている。

6. Hoffman と Kruskal^[3] は、次つぎの定理ていりを証明しょうめいした。 $G$ はどのような 2-dicycle も含ふくまない有向ゆうこうグラフであるとし、 $P$ は $G$ 内うちのすべての dipaths の集合しゅうごうであるとし、 $A$ は $P$ に対たいする $V(G)$ の 0-1 接続せつぞく行列ぎょうれつであるとする。このとき、 $A$ が全ぜんユニモジュラ行列ぎょうれつであるための必要ひつよう十じゅう分ふん条件じょうけんは、 $G$ 内うちの任意にんいの方向ほうこうへのすべての単たん閉路へいろが、前方ぜんぽうと後方こうほうへの交互こうごの弧こを含ふくむことである。

7. 0-( $\pm$ 1) 成分せいぶんのある行列ぎょうれつが、各かく列れつにおいてその成分せいぶんが上うえから下したへ非ひ減少げんしょう（すなわち、すべての -1 は一番いちばん上じょうにあり、その次つぎに 0 があり、一番いちばん下かには 1 があるという具合ぐあい）であると仮定かていする。このとき、Fujishige ^[4]は、この行列ぎょうれつが全ぜんユニモジュラ行列ぎょうれつであるための必要ひつよう十じゅう分ふん条件じょうけんは、そのすべての 2 × 2 部分ぶぶん行列ぎょうれつの行列ぎょうれつ式しきが $0,\pm 1$ であることであることを証明しょうめいした。

8. Seymour (1980) は、ここで非公式ひこうしき的てきに述のべた全ぜんユニモジュラ行列ぎょうれつのすべての特徴とくちょうについて証明しょうめいした。Seymour の定理ていりでは、ある行列ぎょうれつが全ぜんユニモジュラ行列ぎょうれつであるための必要ひつよう十じゅう分ふん条件じょうけんは、それがあるネットワーク行列ぎょうれつの自然しぜんな組くみ合あわせであり、ある 5 × 5 全ぜんユニモジュラ行列ぎょうれつのコピーであること、ということが述のべられている。

具体ぐたい例れい[編集へんしゅう]

1. 以下いかの行列ぎょうれつは全ぜんユニモジュラ行列ぎょうれつである：

A={\begin{bmatrix}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\\\end{bmatrix}}

この行列ぎょうれつは、以下いかのネットワークに関かんする最大さいだいフロー問題もんだいの線型せんけい計画けいかく法ほうにおける制約せいやく条件じょうけんに対たいする係数けいすう行列ぎょうれつとして得えられるものである：

2. 次つぎの形状けいじょうを持もつ任意にんいの行列ぎょうれつは、全ぜんユニモジュラ行列ぎょうれつではない：

A={\begin{bmatrix}\vdots &\vdots &\vdots &\vdots &\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\\vdots &\vdots &\vdots &\vdots &\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\\vdots &\vdots &\vdots &\vdots &\vdots \\\end{bmatrix}}

なぜならば、このような行列ぎょうれつには行列ぎょうれつ式しきが -2 であるような正方せいほう部分ぶぶん行列ぎょうれつが存在そんざいするからである。

抽象ちゅうしょう線型せんけい代数だいすう学がく[編集へんしゅう]

抽象ちゅうしょう線型せんけい代数だいすう学がくにおいては、整数せいすうに限かぎらず、任意にんいの可か換かわ環たまきからの成分せいぶんによる行列ぎょうれつを考かんがえる。この文脈ぶんみゃくにおいて、ユニモジュラ行列ぎょうれつとはその環たまき上じょうの可逆かぎゃく行列ぎょうれつ、すなわち行列ぎょうれつ式しきが単元たんげんとなる行列ぎょうれつのことを言いう。この群ぐんは $GL_{n}(R)$ と表記ひょうきされる。

体からだ上うえの行列ぎょうれつに関かんして言いえば、ユニモジュラは非特異ひとくいと同おなじ意味いみになる。この場合ばあい「ユニモジュラ」は、環たまき（しばしば整数せいすう環たまき）に係数けいすうをとる行列ぎょうれつがその環たまき上じょうで可逆かぎゃくであることを意味いみするために用もちい、「非特異ひとくい」は体からだ上じょうで可逆かぎゃくな行列ぎょうれつを表あらわすものとして使つかい分わけられることが多おおい。

脚注きゃくちゅう[編集へんしゅう]

[脚注きゃくちゅうの使つかい方かた]

注釈ちゅうしゃく[編集へんしゅう]

^ この語かたりはClaude Bergeによって作つくられた。Hoffman, A.J.; Kruskal, J. (2010), “Introduction to Integral Boundary Points of Convex Polyhedra”, in M. Jünger et al. (eds.), 50 Years of Integer Programming, 1958-2008, Springer-Verlag, pp. 49–50 を参照さんしょう。

出典しゅってん[編集へんしゅう]

^ Heller, I.; Tompkins, C.B.Gh (1956), “An Extension of a Theorem of Dantzig's”, in Kuhn, H.W.; Tucker, A.W., Linear Inequalities and Related Systems, Annals of Mathematics Studies, 38, Princeton (NJ): Princeton University Press, pp. 247–254
^ T. Zaslavsky (1982), "Signed graphs," Discrete Applied Mathematics 4, pp. 401–406.
^ Hoffman, A.J.; Kruskal, J.B. (1956), “Integral Boundary Points of Convex Polyhedra”, in Kuhn, H.W.; Tucker, A.W., Linear Inequalities and Related Systems, Annals of Mathematics Studies, 38, Princeton (NJ): Princeton University Press, pp. 223–246
^ Fujishige, Satoru (1984), “A System of Linear inequalities with a Submodular Function on (0, +/-1) Vectors”, Linear Algebra and Its Applications 63: 253–266

参考さんこう文献ぶんけん[編集へんしゅう]

Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Mineola, N.Y.: Dover Publications (Section 13.2)
Alexander Schrijver (1998), Theory of Linear and Integer Programming. John Wiley & Sons, ISBN 0-471-98232-6 (mathematical)
Alexander Schrijver (2003), Combinatorial Optimization: Polyhedra and Efficiency, Springer

外部がいぶリンク[編集へんしゅう]

[1] この語かたりはClaude Bergeによって作つくられた。Hoffman, A.J.; Kruskal, J. (2010), “Introduction to Integral Boundary Points of Convex Polyhedra”, in M. Jünger et al. (eds.), 50 Years of Integer Programming, 1958-2008, Springer-Verlag, pp. 49–50 を参照さんしょう。

[2] Heller, I.; Tompkins, C.B.Gh (1956), “An Extension of a Theorem of Dantzig's”, in Kuhn, H.W.; Tucker, A.W., Linear Inequalities and Related Systems, Annals of Mathematics Studies, 38, Princeton (NJ): Princeton University Press, pp. 247–254

[3] T. Zaslavsky (1982), "Signed graphs," Discrete Applied Mathematics 4, pp. 401–406.

[4] Hoffman, A.J.; Kruskal, J.B. (1956), “Integral Boundary Points of Convex Polyhedra”, in Kuhn, H.W.; Tucker, A.W., Linear Inequalities and Related Systems, Annals of Mathematics Studies, 38, Princeton (NJ): Princeton University Press, pp. 223–246

[5] Fujishige, Satoru (1984), “A System of Linear inequalities with a Submodular Function on (0, +/-1) Vectors”, Linear Algebra and Its Applications 63: 253–266

[注釈ちゅうしゃく 1]

[1]

[2]

[3]

[4]