ユニモジュラ行列
1. 2部グラフの2部マッチングに対する係数行列として得られる無向接続行列(unoriented incidence matrix)は、全ユニモジュラ行列である。一方、非2部グラフの無向接続行列は、全ユニモジュラ行列ではない。より一般に、Heller と Tompkins の論文 の補遺において、A.J. Hoffman と D. Gale は次を証明した。 A {\displaystyle A} を、各行が二つの素集合 B {\displaystyle B} と C {\displaystyle C} に区分できるようなある m×n 行列とする。このとき、以下の四つの条件は合わせて A が全ユニモジュラ行列であるための十分条件となる:
A {\displaystyle A} のすべての列には、ゼロでない成分が高々二つしか存在しない;
A {\displaystyle A} のすべての成分は 0、+1 あるいは −1 のいずれかである;
A {\displaystyle A} のある列の二つのゼロでない成分の符号が同一であるなら、その一つの行は B {\displaystyle B} に属し、もう一つの行は C {\displaystyle C} に属す;
A {\displaystyle A} のある列の二つのゼロでない成分の符号が異なるなら、それら両方の行は B {\displaystyle B} あるいは C {\displaystyle C} のいずれかに属す。