ユニモジュラ行列のソースを表示

{{about|成分が[[整数]]であるような行列|[[多項式行列]]に関する'''ユニモジュラ'''という用語|ユニモジュラ多項式行列}}

[[数学]]の分野において、ある正方行列 ''M'' が'''ユニモジュラ行列'''（ユニモジュラぎょうれつ、{{Lang-en-short|unimodular matrix}}; 単模行列）であるとは、それが[[整数行列]]で、その[[行列式]]が +1 あるいは &minus;1 であることを言う。また同値であるが、整数について可逆であるような整数行列、すなわち、逆行列 ''N'' が整数行列であるような整数行列のことも、ユニモジュラ行列と言う。これら二つの定義が同値であることは、[[クラメルの公式]]より従う。したがって、いずれの成分も整数であるような行列 ''M'' とベクトル ''b'' に対する方程式 ''Mx'' = ''b'' には、''M'' がユニモジュラ行列であるとき、整数解が存在する。位数が ''n'' のユニモジュラ行列は[[群 (数学)|群]]を成し、それは <math>GL_n(\mathbb{Z})</math> と表記される。

== ユニモジュラ行列の例 ==
ユニモジュラ行列は[[行列の積]]の下で[[一般線型群]]の部分群を成す。すなわち、次に挙げる行列はすべてユニモジュラ行列である：
* [[単位行列]]
* ユニモジュラ行列の[[逆行列|逆]]
* 二つのユニモジュラ行列の[[行列の乗法|積]]
さらに、次も成立する：
* 二つのユニモジュラ行列の[[クロネッカー積]]もまたユニモジュラ行列である。このことは、次の等式により従う：
:<math> \det(A \otimes B) = (\det A)^q (\det B)^p, </math>
: ここで ''p'' と ''q'' はそれぞれ行列 ''A'' と ''B'' の次元を表す。

ユニモジュラ行列の具体例としては、次が挙げられる：
* [[シンプレクティック行列]]
* {{仮リンク|パスカル行列|en|Pascal matrix}}
* [[置換行列]]
* {{仮リンク|原始ピタゴラス数の木|label=原始ピタゴラス三つ組の木|en|tree of primitive Pythagorean triples}}における三つの変換行列

== 全ユニモジュラ性 ==
'''全ユニモジュラ行列'''（totally unimodular matrix, TU 行列）<ref group="注釈">この語は[[:en:Claude Berge|Claude Berge]]によって作られた。{{Citation
  | last = [[:en:Alan Hoffman (mathematician)|Hoffman]]
  | first = A.J.
  | last2 = [[:en:Joseph Kruskal|Kruskal]]
  | first2 = J.
  | contribution = Introduction to ''Integral Boundary Points of Convex Polyhedra''
  | editor-last = M. Jünger et al. (eds.)
  | title = 50 Years of Integer Programming, 1958-2008
  | publisher = Springer-Verlag
  | pages = 49–50
  | year = 2010}}を参照。</ref>とは、その[[正則行列|非特異]]なすべての正方[[部分行列]]がユニモジュラ行列であるような行列のことを言う。したがって、全ユニモジュラ行列は、必ずしもそれ自身が正方行列でなくてもよい。定義より、任意の全ユニモジュラ行列の成分は 0、+1 あるいは &minus;1 でしかあり得ないことが分かる。

全ユニモジュラ行列は、ある[[線型計画法|線型計画]]が整数計画であることを確かめるための迅速な方法を提供するため、{{仮リンク|多面体的組合せ論|en|polyhedral combinatorics}}や[[組合せ最適化]]において極めて重要な概念となる。特に、''A'' が全ユニモジュラ行列で ''b'' を整数ベクトルとしたとき、<math>\{\min cx \mid Ax \ge b, x \ge 0\}</math> あるいは <math>\{\max cx \mid Ax \le b\}</math> のような形状の線型計画は、任意の ''c'' に対して、整数の最適解を持つ。したがって、''A'' が全ユニモジュラ行列で ''b'' が整数ベクトルであるなら、実行可能領域（例えば、<math>\{x \mid Ax \ge b\}</math>）のすべての極値点は整数であり、したがってその実行可能領域は整数多面体となる。

=== よくある全ユニモジュラ行列 ===
1. [[2部グラフ]]の2部[[マッチング (グラフ理論)|マッチング]]に対する係数行列として得られる無向[[接続行列]]（unoriented incidence matrix）は、全ユニモジュラ行列である。一方、非2部グラフの無向接続行列は、全ユニモジュラ行列ではない。より一般に、Heller と Tompkins の論文 <ref>{{Citation
  | last = Heller
  | first = I.
  | last2 = Tompkins
  | first2 = C.B.Gh
  | contribution = An Extension of a Theorem of [[:en:George Dantzig|Dantzig]]'s
  | editor-last = [[ハロルド・クーン|Kuhn]]
  | editor-first = H.W.
  | editor2-last = [[アルバート・タッカー|Tucker]]
  | editor2-first = A.W.
  | title = Linear Inequalities and Related Systems
  | series = Annals of Mathematics Studies
  | publisher = Princeton University Press
  | location = Princeton (NJ)
  | pages = 247–254
  | volume = 38
  | year = 1956 }}</ref>
の補遺において、A.J. Hoffman と D. Gale は次を証明した。<math>A</math> を、各行が二つの[[素集合]] <math>B</math> と  <math>C</math> に区分できるようなある ''m''×''n'' 行列とする。このとき、以下の四つの条件は合わせて ''A'' が全ユニモジュラ行列であるための[[必要十分条件|十分条件]]となる：
* <math>A</math> のすべての列には、ゼロでない成分が高々二つしか存在しない；
* <math>A</math> のすべての成分は 0、+1 あるいは &minus;1 のいずれかである；
* <math>A</math> のある列の二つのゼロでない成分の符号が同一であるなら、その一つの行は <math>B</math> に属し、もう一つの行は <math>C</math> に属す；
* <math>A</math> のある列の二つのゼロでない成分の符号が異なるなら、それら両方の行は <math>B</math> あるいは <math>C</math> のいずれかに属す。
後に、これらの条件は、ある均衡{{仮リンク|符号付グラフ|en|Signed graph}}の接続行列を定義することが知られた。したがってこの例は、符号付グラフの接続行列が全ユニモジュラ行列であるための十分条件は、その符号付グラフが均衡グラフであること、ということについて述べたものである。その逆は、半辺（half edge）を含まない符号付グラフに対しては成立する（これはグラフの無向接続行列の性質を一般化したものである）<ref>T. Zaslavsky (1982), "Signed graphs," ''Discrete Applied Mathematics'' 4, pp. 401&ndash;406.</ref>。

2. [[最大フロー問題|最大フロー]]と{{仮リンク|最小費用フロー問題|en|Minimum-cost flow problem}}の制約条件は、これらの性質を備える係数行列（および空集合である ''C''）を導く。したがってそのような、有界の整数容量を備えるネットワークフロー問題には、整数の最適値が存在する。ここで、この事実は、有界の整数容量に対しても分数の最適値を持つことがあり得る{{仮リンク|多品種フロー問題|en|multi-commodity flow problem}}には適用されないことに注意されたい。

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'' に対して、行に符号を割り当てる関数 <math>s:R \to \pm1</math> でその和 <math>\sum_{r \in R} s(r)r</math>（これは、その考えている行列と等しい幅を持つ行ベクトル）が <math>\{0,\pm1\}</math> に全ての成分を持つようなものが存在すること（すなわち、その行部分行列が高々一つの  discrenpacy を持つこと）であることを証明した。このことと、他のいくつかの同値性のための条件は、Schrijver (2003) において示されている。

6. 
Hoffman と [[:en:Joseph Kruskal|Kruskal]]<ref>{{Citation
  | last = Hoffman
  | first = A.J.
  | last2 = [[:en:Joseph Kruskal|Kruskal]]
  | first2 = J.B.
  | contribution = Integral Boundary Points of Convex Polyhedra
  | editor-last = [[:en:Harold W. Kuhn|Kuhn]]
  | editor-first = H.W.
  | editor2-last = [[アルバート・タッカー|Tucker]]
  | editor2-first = A.W.
  | title = Linear Inequalities and Related Systems
  | series = Annals of Mathematics Studies
  | publisher = Princeton University Press
  | location = Princeton (NJ)
  | pages = 223–246
  | volume = 38
  | year = 1956 }}</ref>
は、次の定理を証明した。<math>G</math> はどのような 2-dicycle も含まない有向グラフであるとし、<math>P</math> は <math>G</math> 内のすべての dipaths の集合であるとし、<math>A</math> は <math>P</math> に対する <math>V(G)</math> の 0-1 接続行列であるとする。このとき、<math>A</math> が全ユニモジュラ行列であるための必要十分条件は、<math>G</math> 内の任意の方向へのすべての単閉路が、前方と後方への交互の弧を含むことである。

7. 0-(<math>\pm</math>1) 成分のある行列が、各列においてその成分が上から下へ非減少（すなわち、すべての -1 は一番上にあり、その次に 0 があり、一番下には 1 があるという具合）であると仮定する。このとき、Fujishige <ref>{{Citation
  | last = Fujishige
  | first = Satoru
  | title = A System of Linear inequalities with a Submodular Function on (0, +/-1) Vectors
  | journal = Linear Algebra and Its Applications
  | pages = 253–266
  | volume = 63
  | year = 1984 }}</ref>は、この行列が全ユニモジュラ行列であるための必要十分条件は、そのすべての 2 × 2 部分行列の行列式が <math>0, \pm1</math> であることであることを証明した。

8. [[:en:Paul_Seymour_(mathematician)|Seymour]] (1980) は、ここで非公式的に述べた全ユニモジュラ行列のすべての特徴について証明した。Seymour の定理では、ある行列が全ユニモジュラ行列であるための必要十分条件は、それが'''ネットワーク行列'''とある 5 × 5 全ユニモジュラ行列のコピーの自然な組み合わせである、ということが述べられている。

=== 具体例 ===
1. 以下の行列は全ユニモジュラ行列である：

:<math>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} </math>

この行列は、以下のネットワークに関する[[最大フロー最小カット定理|最大フロー問題]]の線型計画法における制約条件に対する係数行列として得られるものである：

2.  次の形状を持つ任意の行列は、全ユニモジュラ行列ではない：
:<math>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} </math>
なぜならば、このような行列には行列式が -2 であるような正方部分行列が存在するからである。

== 抽象線型代数学 ==
[[抽象代数学|抽象線型代数学]]においては、整数に限らず、任意の[[可換環]]からの成分による行列を考える。この文脈において、ユニモジュラ行列とはその環上の可逆行列、すなわち[[行列式]]が[[可逆元|単元]]となる行列のことを言う。この[[群 (数学)|群]]は <math>GL_n(R)</math> と表記される。

[[可換体|体]]上の行列に関して言えば、'''ユニモジュラ'''は[[正則行列|非特異]]と同じ意味になる。この場合「ユニモジュラ」は、環（しばしば整数環）に係数をとる行列がその環上で可逆であることを意味するために用い、「非特異」は体上で可逆な行列を表すものとして使い分けられることが多い。

== 関連項目 ==
* {{仮リンク|均衡行列|en|Balanced matrix}}
* [[正則マトロイド]]
* [[特殊線型群]]
* {{仮リンク|完全双対整数性|en|Total dual integrality}}

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
<references />

== 参考文献 ==
*{{Citation
  | last = Papadimitriou
  | first = Christos H.
  | last2 = Steiglitz
  | first2 = Kenneth
  | year = 1998
  | title = Combinatorial Optimization: Algorithms and Complexity
  | publisher = Dover Publications (Section 13.2)
  | location = Mineola, N.Y.
  | note = The 'section 13.2' is on the wrong place, but I don't know how to fix it}}
* [[:en:Alexander Schrijver|Alexander Schrijver]] (1998), ''Theory of Linear and Integer Programming''. John Wiley & Sons, ISBN 0-471-98232-6 (mathematical)
* {{Citation|author = Alexander Schrijver|authorlink=:en:Alexander Schrijver | year = 2003 | title = Combinatorial Optimization: Polyhedra and Efficiency | publisher = Springer}}

== 外部リンク ==
* [http://glossary.computing.society.informs.org/index.php?page=U.html Harvey J. Greenberg による数理プログラミング用語]
* [http://mathworld.wolfram.com/UnimodularMatrix.html MathWorld におけるユニモジュラ行列の記事]
* [http://www.math.uni-magdeburg.de/~walter/TUtest/ M. Walter と K. Truemper による全ユニモジュラ性を調べるためのソフトウェア]

{{Linear algebra}}

{{DEFAULTSORT:ゆにもしゆらきようれつ}}
[[Category:行列]]
[[Category:線型代数学]]
[[Category:数学に関する記事]]