ユニモジュラ行列

ユニモジュラ行列と全ユニモジュラ行列

ユニモジュラ行列

数学において、ユニモジュラ行列とは、成分が全て整数であり、行列式が+1または-1である正方行列のことです。言い換えると、整数係数の逆行列を持つ整数行列です。この二つの定義は、クラメルの公式から同値であることが分かります。

ユニモジュラ行列は、整数ベクトルに関する方程式を解く際に重要な役割を果たします。例えば、整数行列Mと整数ベクトルbに対する方程式Mx=bは、Mがユニモジュラ行列であれば、整数解が存在します。

位数nのユニモジュラ行列の全体は群をなし、GLₙ(ℤ)と表記されます。これは一般線形群の部分群です。

ユニモジュラ行列の例:

単位行列
ユニモジュラ行列の逆行列
二つのユニモジュラ行列の積
二つのユニモジュラ行列のクロネッカー積

具体的な例としては、シンプレクティック行列、パスカル行列、置換行列などが挙げられます。

全ユニモジュラ行列

全ユニモジュラ行列（Totally Unimodular matrix, TU行列）とは、そのすべての正方部分行列（非特異な部分行列）がユニモジュラ行列である行列です。正方行列である必要はありません。定義から、全ユニモジュラ行列の成分は0、+1、-1のみとなります。

全ユニモジュラ行列は、線形計画問題において重要な役割を果たします。特に、Aが全ユニモジュラ行列でbが整数ベクトルである場合、以下の線形計画問題は整数最適解を持ちます。

min cx | Ax ≥ b, x ≥ 0
max cx | Ax ≤ b

この性質により、実行可能領域のすべての極値点が整数となり、実行可能領域は整数多面体となります。

全ユニモジュラ行列の例:

1. 2部グラフの接続行列: 2部グラフの無向接続行列は全ユニモジュラ行列です。非2部グラフの場合は、必ずしも全ユニモジュラ行列とは限りません。HellerとTompkinsの論文の補遺では、A.J. HoffmanとD. Galeにより、全ユニモジュラ行列であるための十分条件が示されています。これは、均衡符号付きグラフの接続行列と関連しています。

2. ネットワーク行列: 最大フロー問題や最小費用フロー問題の制約条件は、全ユニモジュラ行列を導きます。そのため、整数容量のネットワークフロー問題は整数最適解を持ちます。ただし、多品種フロー問題には適用されません。

3. 連続した1の性質: 各行に1が連続して現れるような0-1行列は、全ユニモジュラ行列です。列についても同様です。

4. ネットワーク行列: 特定の木構造と関連した行列は全ユニモジュラ行列です。

5. Ghouila-Houriの条件: 行の全ての部分集合に対して特定の条件を満たす符号付けが存在する場合、全ユニモジュラ行列です。

6. HoffmanとKruskalの定理: 特定の条件を満たす有向グラフの接続行列は全ユニモジュラ行列です。

7. Fujishigeの条件: 特定の条件を満たす0- (±1)成分の行列は全ユニモジュラ行列です。

8. Seymourの定理: 全ユニモジュラ行列は、ネットワーク行列と特定の5x5行列の組み合わせで表現できます。

具体例:

いくつかの具体例が示されていますが、ここではスペースの都合上省略します。

抽象線形代数

抽象線形代数では、ユニモジュラ行列は任意の可換環上の可逆行列として定義されます。つまり、行列式がその環の単元である行列です。この群はGLₙ(R)と表記されます。体上の行列では、ユニモジュラ行列は非特異行列と同義となります。

まとめ

ユニモジュラ行列と全ユニモジュラ行列は、整数計画問題や最適化問題において重要な概念です。その性質を理解することで、効率的なアルゴリズムの設計や問題の解法の検討に役立ちます。 様々な応用分野で利用されており、今後も研究が続けられています。

もう一度検索