ユニモジュラ行列

数学の分野において、ある正方行列 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]

ユニモジュラ行列

目次