ユニモジュラ行列

この項目では、成分が整数であるような行列について説明しています。多項式行列に関するユニモジュラという用語については「ユニモジュラ多項式行列」をご覧ください。

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

ユニモジュラ行列は行列の積の下で一般線型群の部分群を成す。すなわち、次に挙げる行列はすべてユニモジュラ行列である：

• 単位行列
• ユニモジュラ行列の逆
• 二つのユニモジュラ行列の積

さらに、次も成立する：

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

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

ここで p と q はそれぞれ行列 A と B の次元を表す。

ユニモジュラ行列の具体例としては、次が挙げられる：

• シンプレクティック行列
• パスカル行列（英語版）
• 置換行列
• 原始ピタゴラス三つ組の木（英語版）における三つの変換行列

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

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

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

• ${\displaystyle A}$ のすべての列には、ゼロでない成分が高々二つしか存在しない；
• ${\displaystyle A}$ のすべての成分は 0、+1 あるいは −1 のいずれかである；
• ${\displaystyle A}$ のある列の二つのゼロでない成分の符号が同一であるなら、その一つの行は ${\displaystyle B}$ に属し、もう一つの行は ${\displaystyle C}$ に属す；
• ${\displaystyle A}$ のある列の二つのゼロでない成分の符号が異なるなら、それら両方の行は ${\displaystyle B}$ あるいは ${\displaystyle 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 に対して、行に符号を割り当てる関数 ${\displaystyle s:R\to \pm 1}$ でその和 ${\displaystyle \sum _{r\in R}s(r)r}$（これは、その考えている行列と等しい幅を持つ行ベクトル）が ${\displaystyle \{0,\pm 1\}}$ に全ての成分を持つようなものが存在すること（すなわち、その行部分行列が高々一つの discrenpacy を持つこと）であることを証明した。このことと、他のいくつかの同値性のための条件は、Schrijver (2003) において示されている。

6. Hoffman と Kruskal^[3] は、次の定理を証明した。${\displaystyle G}$ はどのような 2-dicycle も含まない有向グラフであるとし、${\displaystyle P}$ は ${\displaystyle G}$ 内のすべての dipaths の集合であるとし、${\displaystyle A}$ は ${\displaystyle P}$ に対する ${\displaystyle V(G)}$ の 0-1 接続行列であるとする。このとき、${\displaystyle A}$ が全ユニモジュラ行列であるための必要十分条件は、${\displaystyle G}$ 内の任意の方向へのすべての単閉路が、前方と後方への交互の弧を含むことである。

7. 0-(${\displaystyle \pm }$1) 成分のある行列が、各列においてその成分が上から下へ非減少（すなわち、すべての -1 は一番上にあり、その次に 0 があり、一番下には 1 があるという具合）であると仮定する。このとき、Fujishige ^[4]は、この行列が全ユニモジュラ行列であるための必要十分条件は、そのすべての 2 × 2 部分行列の行列式が ${\displaystyle 0,\pm 1}$ であることであることを証明した。

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

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

${\displaystyle 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. 次の形状を持つ任意の行列は、全ユニモジュラ行列ではない：

${\displaystyle 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 であるような正方部分行列が存在するからである。

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

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

• 均衡行列（英語版）
• 正則マトロイド
• 特殊線型群
• 完全双対整数性（英語版）

1. ^ 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 
2. ^ T. Zaslavsky (1982), "Signed graphs," Discrete Applied Mathematics 4, pp. 401–406.
3. ^ 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 
4. ^ 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 

• Harvey J. Greenberg による数理プログラミング用語
• MathWorld におけるユニモジュラ行列の記事
• M. Walter と K. Truemper による全ユニモジュラ性を調べるためのソフトウェア

表 話 編 歴 線型代数学・行列解析
連立一次方程式	ガウスの消去法 クラメルの公式 ガウス＝ザイデル法 ヤコビ法
ベクトル	線型独立 線型結合 基底 双対基底
ベクトル空間	双対空間 核空間 固有空間 広義固有空間 線型包 行空間 列空間 次元
計量ベクトル空間	ドット積 コーシー＝シュワルツの不等式 直交 正規直交系 正規直交基底 グラム・シュミットの正規直交化法 直交補空間
行列・線型写像	演算・操作 乗法 転置 逆行列 サラスの方法 基本変形 対角化 分解 LU QR コレスキー シューア 特異値 固有値 不変量 行列式 跡 階数 固有値と固有ベクトル 固有多項式 最小多項式 単因子 階数標準形 スミス標準形 ジョルダン標準形 有理標準形 小行列式 クラス 正則 基本 対称 エルミート 正規 直交 回転 ユニタリ 冪零 射影 正定値 ユニモジュラー 置換 区分
行列式	余因子展開 余因子行列 ヴァンデルモンドの行列式 終結式 コーシー・ビネの公式
多重線型代数	外積 外積代数 対称代数 テンソル代数
数値線形代数	基本的な概念 浮動小数点 数値的安定性 疎行列 Z-行列 M行列 条件数 ゲルシュゴリンの定理 クリロフ部分空間 ソフトウェア MATLAB 数値解析ソフトの比較/一覧 ライブラリ Armadillo Basic Linear Algebra Subprograms (BLAS) INTLAB Intel oneAPI Math Kernel Library LAPACK NumPy OpenBLAS 線型代数学ライブラリの比較 反復法・技法 SOR法 共役勾配法 GMRES法 固有値問題の数値解法 ランチョス法 QR法 べき乗法 逆べき乗法 ヤコビ法 (固有値問題) シュトラッセンのアルゴリズム ハウスホルダー変換 ギブンス回転 人物 ジェームズ・H・ウィルキンソン クリーブ・モラー ニコラス・ハイアム ジーン・ゴラブ リチャード・バルガ
行列値関数	行列指数関数 行列の対数 行列の平方根
その他	スカラー ケイリー・ハミルトンの定理 ペロン＝フロベニウスの定理 シューア補行列 シルヴェスターの慣性法則
カテゴリ