ユニモジュラス行列

1.二部グラフの無向接続行列（二部マッチングの係数行列）は、完全ユニモジュラー（TU）である。（非二部グラフの無向接続行列はTUではない。）より一般的には、HellerとTompkinsの論文^{[ 2 ]}の付録で、AJ HoffmanとD. Galeが以下を証明している。${\displaystyle A}$行が互いに素な2つの集合に分割できるm × n行列とする。${\displaystyle B}$そして ${\displaystyle C}$すると、以下の4つの条件が満たされれば、Aは完全ユニモジュラーとなる。

• すべてのエントリー${\displaystyle A}$0、+1、または-1です。
• すべての列${\displaystyle A}$最大で2つの非ゼロ（つまり、+1または-1）エントリを含みます。
• 列に 2 つの非ゼロエントリがある場合${\displaystyle A}$同じ符号を持つ場合、1 の行は${\displaystyle B}$、そしてもう一方${\displaystyle C}$;
• 列に 2 つの非ゼロエントリがある場合${\displaystyle A}$反対の符号を持つ場合、両方の行は${\displaystyle B}$または両方${\displaystyle C}$。

後に、これらの条件がバランスのとれた符号付きグラフの接続行列を定義することがわかった。したがって、この例は、符号付きグラフがバランスされている場合、その接続行列は完全にユニモジュラーであることを示している。逆は、半辺のない符号付きグラフに対しても成り立つ（これは、グラフの無向接続行列の性質を一般化する）。^{[ 3 ]}

2.最大流量問題と最小費用流量問題の制約条件は、これらの特性を持つ係数行列（かつCが空行列）を生成します。したがって、容量が整数に制限されたネットワーク流量問題では、最適値は整数になります。ただし、これは複数商品流量問題には当てはまりません。複数商品流量問題では、容量が整数に制限されていても、最適値が小数になる場合があります。

3. 連続する1の性質：Aが、各行で1が連続して現れる0-1行列である場合（または、そのような行列に置換できる場合）、AはTUである。（TU行列の転置行列もTUであるため、列についても同様である。） ^{[ 4 ]}

4. すべてのネットワーク行列はTUです。ネットワーク行列の行は、ツリーT = ( V , R )に対応し、各アークは任意の方向を持ちます（ツリーが「rに根付く」または「 rから出る」ようなルート頂点rが存在する必要はありません）。列は、同じ頂点集合V上の別のアーク集合Cに対応します。行R、列C = stのエントリを計算するには、 T内のsからtへのパスPを参照します。すると、エントリは次のようになります。

• 弧RがPの前方に現れる場合、 +1
• −1 弧RがPで逆向きに現れる場合、
• 弧RがPに含まれていない場合は 0 となります。

詳細はSchrijver（2003）を参照のこと。

5. Ghouila-Houriは、行列がTUであるのは、行の任意の部分集合Rに対して割り当てが存在する場合であることを示した。${\displaystyle s:R\to \pm 1}$符号を行に割り当てて、符号付き合計${\displaystyle \sum _{r\in R}s(r)r}$（これは行列と同じ幅の行ベクトルです）のすべてのエントリは${\displaystyle \{0,\pm 1\}}$（つまり、行部分行列の不一致は最大で1である）。これと他のいくつかの条件付き特性は、Schrijver（1998）で証明されている。

6. ホフマンとクルスカル^{[ 5 ]} は次の定理を証明した。${\displaystyle G}$は2-ダイサイクルを持たない有向グラフである。${\displaystyle P}$は、すべてのダイパスの集合です。${\displaystyle G}$、 そして${\displaystyle A}$は 0-1 発生行列です${\displaystyle V(G)}$対${\displaystyle P}$。 それから${\displaystyle A}$は、 のすべての単純な任意に方向付けられたサイクルが である場合に限り、完全にユニモジュラーである。${\displaystyle G}$交互に前方と後方に弧を描く構成になっている。

7. 行列が 0-(${\displaystyle \pm }$1) エントリがあり、各列のエントリは上から下に向かって非減少です（つまり、すべての −1 が上にあり、次に 0、次に 1 が下にあります）。藤重は^{[ 6 ]} 、行列が TU であるのは、すべての 2 x 2 部分行列の行列式が である場合のみであることを示しました。${\displaystyle 0,\pm 1}$。

8. Seymour (1980) ^{[ 7 ] は}、すべての TU 行列の完全な特徴付けを証明しましたが、ここではそれを非公式に説明するだけです。Seymour の定理は、行列が TU であるのは、それがいくつかのネットワーク行列と特定の 5 x 5 TU 行列のいくつかのコピーの特定の自然な組み合わせである場合のみである、というものです。

1. 次の行列は完全ユニモジュラー行列です。

${\displaystyle A=\left[{\begin{array}{rrrrrr}-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{array}}\right].}$

この行列は、以下のネットワークにおける最大流量問題の線形計画法における制約条件の係数行列として現れる。

2. 次の形式の任意の行列

${\displaystyle A=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].}$

行列式が-2の正方部分行列を持つため、完全にはユニモジュラーではない。