完全単模行列(totally unimodular matrix)とは、どの正方部分行列の行列式も $0,1,-1$ のどれかである整数の行列である。整数の右辺に対して多面体 $\{x\ge0,\ Ax\le b\}$ の頂点がすべて整数になることと同値で(Hoffman–Kruskal の定理)、線形計画問題を解くだけで整数の最適解が得られる理由を与える。有向グラフと二部グラフの接続行列、各列の $1$ が連続する行列が代表例で、Ghouila-Houri の判定法で確かめられる。最大マッチングと最小頂点被覆の等式や最小費用流の整数性はその帰結である。
完全単模行列(totally unimodular matrix)は、どの正方部分行列の行列式も $0,1,-1$ のどれかである行列である。
一般の 整数計画法 は難しいが、線形計画問題の解がたまたま整数なら、整数の条件を外した問題を解けばすむ。たとえば人と仕事の割当を $0$–$1$ の変数で書き、$0$–$1$ の条件を $0\le x\le1$ に緩めても、最適解の頂点は整数である。これは偶然ではない。条件の行列が完全単模なら、整数の右辺に対して多面体の頂点はすべて整数になる。さらに逆も成り立ち、すべての整数の右辺で頂点が整数であることが、完全単模性の特徴づけになる。これが Hoffman–Kruskal の定理(thm-tu-hk)である。
定義のままでは指数個の行列式を調べることになる。そこで Ghouila-Houri の判定法(thm-tu-gh)が役に立つ。これを使うと、有向グラフ・二部グラフ の接続行列や、連続する $1$ をもつ行列が完全単模であることが数行で分かる。二部グラフの場合は、最大マッチングと最小頂点被覆の等式や、二重確率行列の分解が線形計画の双対から出る。
線形計画緩和への使い方の入口は 整数計画法 の節「完全単模の場合」、グラフの接続行列そのものは 接続行列(グラフ) にある。この記事は完全単模性そのものを主題にして、特徴づけの両方向を証明する。
行列 $A$ の 部分行列 とは、行の部分集合と列の部分集合を選んで、その交わりの成分を元の順で並べた行列である。行や列は隣り合っていなくてよい。
整数の行列 $A$ のすべての正方部分行列の行列式が $0,1,-1$ のどれかであるとき、$A$ は 完全単模 であるという。
$1\times1$ の部分行列を見ると、完全単模行列の成分は $0,\pm1$ である。正方行列でなくてもよい。
単模行列(unimodular matrix)は行列式が $\pm1$ の整数の正方行列である。完全単模性はこれよりずっと強い。$\begin{pmatrix}2&1\\1&1\end{pmatrix}$ は行列式が $1$ なので単模だが、成分 $2$ があるので完全単模でない。
$A$ を完全単模行列とする。次の行列も完全単模である。
1:部分行列の部分行列は部分行列であり、転置で行列式は変わらない。
2:正方部分行列の行列式の符号が変わるか、変わらないかである。
3:新しい行列の正方部分行列 $N$ をとる。元の行とその複製の両方を含むなら、同じ行が 2 本あるので $\det N=0$ である。そうでなければ、$N$ は(複製を元の行に読み替えて)$A$ の部分行列である。列も同じである。
4:加えた列が $N$ に入るとき、その列で余因子展開する。$N$ の中でその列が零ベクトルなら $\det N=0$ である。そうでなければ成分 $1$ がただ 1 つあり、$\det N$ は $\pm$(ひとまわり小さい部分行列の行列式)である。加えた列の本数についての帰納法で、$\det N\in\{0,\pm1\}$ を得る。行は転置に帰着する。$\square$
積や和では保たれない。ex-tu-counter を見よ。
| 行列 | 完全単模か | 理由 |
|---|---|---|
| 単位行列、零行列 | はい | 単位行列の正方部分行列は、行と列の選び方が同じなら単位行列で、違えば零の行をもつ |
| 有向グラフの接続行列 | はい | prop-tu-graph |
| 二部グラフの接続行列 | はい | prop-tu-graph |
| 各列の $1$ が連続している $0$–$1$ 行列 | はい | prop-tu-interval |
| $\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ | いいえ | 行列式が $-2$ |
| 三角形の接続行列 $\begin{pmatrix}1&1&0\\0&1&1\\1&0&1\end{pmatrix}$ | いいえ | 行列式が $2$ |
| $\begin{pmatrix}2&1\\1&1\end{pmatrix}$ | いいえ | 成分が $2$ |
成分が $0,\pm1$ であるだけでは足りないことが、この表から分かる。
$M$ を完全単模行列、$b$ を整数のベクトルとする。多面体 $\{x\mid Mx\le b\}$ の頂点はすべて整数のベクトルである。
$m\times n$ の整数の行列 $A$ と $b\in\mathbb Z^m$ に対し
$$
P(b):=\{x\in\mathbb R^n\mid x\ge0,\ Ax\le b\}
$$
とおく。
$A$ を整数の行列とする。次の 2 条件は同値である。
主張の後半が本質である。すべての整数の右辺で頂点が整数なら、任意の部分行列の行列式が $\pm1$ か $0$ に制限される。証明では、調べたい部分行列を基底に埋め込み、その逆行列の各列を頂点の座標として読み取る。
1 ⇒ 2。 $P(b)=\{x\mid Mx\le(b,0)\}$、$M:=\begin{pmatrix}A\\-I\end{pmatrix}$ である。prop-tu-ops の 2・4 により $M$ は完全単模なので、lem-tu-vertex から従う。
2 ⇒ 1。 $B$ を $A$ の正則な $k\times k$ 部分行列とし、$\det B=\pm1$ を示す。$B$ の行の添字の集合を $R$、列の添字の集合を $J$ とする。
$m$ 次の正方行列 $C$ を、$A$ の第 $j$ 列($j\in J$)と、$m$ 次の単位ベクトル $e_i$($i\notin R$)を列にもつ行列として定める。行と列を並べ替えると
$$
C=\begin{pmatrix}B&0\\D&I\end{pmatrix}
$$
の形になるので、$\lvert\det C\rvert=\lvert\det B\rvert\ne0$ である。$C$ の成分は整数なので、$C^{-1}$ の成分が整数であることを示せば、$\det C\cdot\det C^{-1}=1$ の両辺の因子が整数なので $\det C=\pm1$ を得る。
$i\in\{1,\dots,m\}$ を固定し、$w:=C^{-1}e_i$ とおく。整数のベクトル $y$ を、$z:=y+w\ge0$ となるように大きくとり、
$$
b:=Cz=Cy+e_i
$$
とおく。$b$ は整数のベクトルである。$z$ の成分は $C$ の列に対応している。$x\in\mathbb R^n$ を、$j\in J$ の成分は $z$ の対応する成分、ほかの成分は $0$ として定める。$s\in\mathbb R^m$ を、$l\notin R$ の第 $l$ 成分は $z$ の対応する成分、ほかの成分は $0$ として定める。すると $Ax+s=Cz=b$、$x\ge0$、$s\ge0$ なので $x\in P(b)$ である。
$x$ が $P(b)$ の端点であることを示す。$x=\frac12(x'+x'')$、$x',x''\in P(b)$ とし、$s':=b-Ax'\ge0$、$s'':=b-Ax''\ge0$ とする。$(x,s)=\frac12\bigl((x',s')+(x'',s'')\bigr)$ で、各成分は $0$ 以上なので、$(x,s)$ の $0$ の成分では $(x',s')$ の成分も $0$ である。よって $(x',s')$ は $C$ の列に対応する成分だけをもち、それを並べたベクトル $z'$ は $Cz'=b=Cz$ を満たす。$C$ は正則なので $z'=z$、すなわち $x'=x$ である。同様に $x''=x$ である。
多面体 の定理「頂点の特徴づけ」により $x$ は $P(b)$ の頂点なので、2 により $x$ は整数のベクトルである。すると $s=b-Ax$ も整数のベクトルで、$z$ の成分は $x,s$ の成分なので $z$ も整数のベクトルである。よって $w=z-y$ は整数のベクトルである。$i$ は任意なので、$C^{-1}$ の成分は整数である。$\square$
実際には次の形で使う。
$A$ を完全単模行列、$a,b,c,d$ を整数のベクトルとする。多面体 $\{x\mid c\le x\le d,\ a\le Ax\le b\}$ の頂点はすべて整数のベクトルである。
条件は $Mx\le(b,-a,d,-c)$、$M:=\begin{pmatrix}A\\-A\\I\\-I\end{pmatrix}$ と書ける。prop-tu-ops により $M$ は完全単模なので、lem-tu-vertex を使う。$\square$
$A$ を完全単模行列、$b,c$ を整数のベクトルとする。
$$
\max\{c^{\mathsf T}x\mid Ax\le b,\ x\ge0\}=\min\{y^{\mathsf T}b\mid y^{\mathsf T}A\ge c^{\mathsf T},\ y\ge0\}
$$
の両辺が有限なら、最大を達成する整数の $x$ と、最小を達成する整数の $y$ がある。
等式は 線形計画法 の定理「線形計画法の双対定理」である。主問題の実行可能領域は $x\ge0$ の中にあるので直線を含まず、同じ記事の定理「最適解は頂点でとれる」により最適解は頂点でとれる。thm-tu-hk によりそれは整数である。双対問題の条件は $y\ge0$、$-A^{\mathsf T}y\le-c$ で、$-A^{\mathsf T}$ は prop-tu-ops により完全単模なので、同じ議論が使える。$\square$
$A$ を整数の行列とする。次の 2 条件は同値である。
1 ⇒ 2。 $\chi\in\{0,1\}^n$ を $J$ の特性ベクトル、$g:=A\chi$ とする。$g$ は整数のベクトルである。多面体
$$
Q:=\bigl\{x\ \big|\ 0\le x\le\chi,\ \lfloor g/2\rfloor\le Ax\le\lceil g/2\rceil\bigr\}
$$
(切り捨て・切り上げは成分ごと)は $\frac12\chi$ を含むので空でなく、有界なので頂点をもつ。cor-tu-box により頂点 $x$ は整数のベクトルで、$0\le x\le\chi$ から $x$ は $J$ の部分集合 $J_1$ の特性ベクトルである。$J_2:=J\setminus J_1$ とすると、$\sum_{J_2}a_j-\sum_{J_1}a_j=g-2Ax$ で、$Ax$ の各成分は $g/2$ の切り捨てか切り上げなので、この成分は $0,\pm1$ である。$J_1,J_2$ を入れ替えてよい。
2 ⇒ 1。 $B$ を $A$ の $k\times k$ 部分行列とし、$\det B\in\{0,\pm1\}$ を $k$ に関する帰納法で示す。$J$ を 1 列にとると、2 から成分は $0,\pm1$ なので $k=1$ はよい。
$k\ge2$ とし、$B$ は正則としてよい。帰納法の仮定から、$B$ の余因子はすべて $0,\pm1$ である。$\delta:=\det B$ とし、余因子行列の第 1 列を $u$ とする。$u$ の成分は $0,\pm1$ で、$Bu=\delta e_1$ である。$u\ne0$ なので、$I:=\{j\mid u_j\ne0\}$ は空でない。第 $i$ 行($i\ge2$)について $\sum_{j\in I}b_{ij}u_j=0$ で $u_j=\pm1$ なので、$\sum_{j\in I}b_{ij}$ は偶数である。
$I$ に対応する $A$ の列の集合に 2 を当てて $I=I_1\sqcup I_2$ と分ける。$v:=\chi_{I_1}-\chi_{I_2}$ とおくと、$Bv$ の成分は $0,\pm1$ である。$(Bv)_i\equiv\sum_{j\in I}b_{ij}$ (mod 2) なので、$i\ge2$ では偶数で、$(Bv)_i=0$ である。$v\ne0$ で $B$ は正則なので $Bv\ne0$、よって $Bv=\pm e_1$ である。
$Bu=\delta e_1$ と $Bv=\pm e_1$ から $u=\pm\delta v$ である。$u,v$ の $I$ の上の成分はともに $\pm1$ なので、$\delta=\pm1$ である。$\square$
この判定法の主張は Kai10 Theorem 29(p. 11)にある。prf-tu-gh の 2 つの方向は、それぞれ cor-tu-box と余因子の偶奇だけを使っている。
判定法の使い方を見る。どちらも行についての形を使う。
ループのない有限グラフについて、次が成り立つ。
1:行の部分集合 $R$ を $R_1:=R$、$R_2:=\emptyset$ と分ける。各列の $R$ の行についての和は、$+1,-1$ のうち $R$ に入るものの和なので $0,\pm1$ である。thm-tu-gh から従う。
2:二部分割を $U\sqcup W$ とする。行の部分集合 $R$ を $R\cap U$ と $R\cap W$ に分ける。各列の $1$ は $U$ の行と $W$ の行に 1 つずつあるので、差の成分は $0,\pm1$ である。thm-tu-gh から完全単模である。
逆に、二部グラフでないなら長さが奇数 $k$ の閉路がある(二部グラフ の定理「閉路の長さによる特徴付け」)。閉路の頂点と辺からなる $k\times k$ の部分行列は、適当に並べ替えると、$(i,i)$ 成分と $(i+1,i)$ 成分($i+1$ は $k$ を法とする)が $1$ の巡回行列になる。第 1 行で展開すると行列式は $1+(-1)^{k+1}=2$ である。$\square$
$0$–$1$ 行列 $A$ の各列の $1$ が(行の順で)連続して並んでいるなら、$A$ は完全単模である。
行の部分集合 $R$ を $r_1< r_2< \dots$ と番号順に並べ、奇数番目を $R_1$、偶数番目を $R_2$ とする。1 つの列の $1$ のある行は連続しているので、$R$ の中でも番号が連続する。その上の $+1,-1$ の交互の和は $0,\pm1$ である。thm-tu-gh から従う。$\square$
この命題は Lee21 Theorem 8.12(p. 100)にあり、そこでは行列式の帰納法で証明されている。
時間帯 $1,2,3,4$ に、それぞれ $2,3,3,1$ 人以上の人員が要る。勤務の型は「時間帯 1, 2」「2, 3」「3, 4」の 3 つで、人数 $x_1,x_2,x_3$ の和を最小にする。
$$
A=\begin{pmatrix}1&0&0\\1&1&0\\0&1&1\\0&0&1\end{pmatrix},\qquad Ax\ge(2,3,3,1)^{\mathsf T},\quad x\ge0
$$
各列の $1$ は連続しているので、prop-tu-interval により $A$ は完全単模である。よって整数の条件を外した線形計画問題の頂点はすべて整数である。
頂点を調べると、最小値は $5$ で、$x=(2,1,2)$ と $x=(2,2,1)$ で達成される。双対問題の $y=(1,0,1,0)$ は実行可能で、値 $2+3=5$ を与えるので、最小であることが確かめられる。この $y$ も整数である(cor-tu-dual)。
二部グラフ $G$ の接続行列 $A$ は prop-tu-graph により完全単模である。cor-tu-dual を $b=\mathbf 1$、$c=\mathbf 1$ に当てる。
$$
\max\Bigl\{\sum_ex_e\ \Big|\ \sum_{e\ni v}x_e\le1\ (\forall v),\ x\ge0\Bigr\}=\min\Bigl\{\sum_vy_v\ \Big|\ y_u+y_w\ge1\ (\forall\{u,w\}\in E),\ y\ge0\Bigr\}
$$
どちらも有限で、整数の最適解がある。左の整数解は $x_e\in\{0,1\}$ で、$x_e=1$ の辺の集合はマッチングである。右の整数解について $\{v\mid y_v\ge1\}$ は頂点被覆で、その大きさは $\sum y_v$ 以下である。逆にマッチングと頂点被覆の特性ベクトルは実行可能解である。よって、最大マッチングの大きさと最小頂点被覆の大きさは等しい。これは マッチング の定理「二部グラフの最大マッチングと最小頂点被覆」の、線形計画による証明である。
成分が $0$ 以上で各行・各列の和が $1$ の $n$ 次正方行列を 二重確率行列 という。その全体は、完全二部グラフ $K_{n,n}$ の接続行列 $A$ と $x\ge0$ で $Ax=\mathbf 1$ と書ける。成分は $1$ 以下なので $0\le x\le\mathbf 1$ を加えてよく、cor-tu-box により頂点は整数である。各行の和が $1$ なので頂点は置換行列である。全体は有界なので頂点の凸包である(多面体 の定理「凸多面体は頂点の凸包」)。よって二重確率行列は置換行列の凸結合である。これは Hallの結婚定理 の定理「Birkhoff–von Neumann の定理」の別の証明である。たとえば
$$
\begin{pmatrix}\frac13&\frac23\\\frac23&\frac13\end{pmatrix}=\frac13\begin{pmatrix}1&0\\0&1\end{pmatrix}+\frac23\begin{pmatrix}0&1\\1&0\end{pmatrix}
$$
である。
最小費用流問題 の条件は、有向グラフの接続行列 $A$ と、需要 $b_v$、容量 $u_e$ を使って $Ax=b$、$0\le x\le u$ と書ける。prop-tu-graph と cor-tu-box により、$b,u$ が整数なら頂点は整数であり、最適解があれば整数の最適解がある(Lee21 Corollary 8.7、p. 97)。ネットワークフロー の定理「整数性定理」はこの現象の最大流の場合である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 右辺が整数 | $A=(1)$、$b=\frac12$ | 完全単模でも頂点 $\frac12$ は整数でない |
| すべての部分行列(行列式 $\pm1$ だけでは足りない) | $A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$、$b=(1,1)$ | $A$ は単模だが、$P(b)$ の頂点に $(\frac12,0)$ がある |
| 成分だけでなく小行列式まで | $A=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$、$b=(1,0)$ | 成分は $0,\pm1$ だが、頂点に $(\frac12,\frac12)$ がある |
| 二部グラフ | 三角形の接続行列、$b=\mathbf 1$ | 頂点 $(\frac12,\frac12,\frac12)$。マッチングの緩和の値は $\frac32$ で、最大マッチングは $1$ |
| すべての整数の右辺 | $A=(2)$、$b=2$ | $P(b)$ の頂点は $0,1$ で整数だが、$A$ は完全単模でない |
| 条件 $x\ge0$ | $A=(2\ \ 1)$ | $\{Ax\le b\}$ は頂点をもたず、主張の条件が空虚に成り立つが完全単模でない |
| 積・和で閉じること | $\begin{pmatrix}1&1\\0&1\end{pmatrix}\begin{pmatrix}1&0\\1&1\end{pmatrix}$ | 完全単模どうしの積が $\begin{pmatrix}2&1\\1&1\end{pmatrix}$ になる |
$A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$、$b=(1,1)$ では $P(b)$ の頂点は $(0,0),(\frac12,0),(0,1)$ である。$(\frac12,0)$ は $2x_1+x_2=1$ と $x_2=0$ の交点で、第 2 の条件も $\frac12\le1$ を満たす。prf-tu-hk の行列 $C$ は、ここでは第 1 列と $e_2$ からなる $\begin{pmatrix}2&0\\1&1\end{pmatrix}$ で、行列式は $2$ である。$A$ 自身の行列式が $\pm1$ でも、$(A\ \ I)$ の基底の行列式が $\pm1$ とは限らない。
$A=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$、$b=(1,0)$ では、$x_1+x_2=1$ と $x_1-x_2=0$ の交点 $(\frac12,\frac12)$ は $x\ge0$ を満たす頂点である。
三角形の接続行列の 3 本の等式 $x_1+x_2=x_2+x_3=x_1+x_3=1$ の解は $(\frac12,\frac12,\frac12)$ である。整数の実行可能解は辺 1 本だけのマッチングなので値は $1$ である。
$A=(2\ \ 1)$ の $\{2x_1+x_2\le b\}$ は半平面で、直線を含むので頂点をもたない。
和については、$\begin{pmatrix}1&0\\0&1\end{pmatrix}+\begin{pmatrix}1&1\\0&1\end{pmatrix}$ の $(1,1)$ 成分が $2$ である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 行列式が $\pm1$ の整数行列は完全単模である | 全部の部分行列を見る | ex-tu-counter |
| 成分が $0,\pm1$ なら完全単模である | 小行列式も $0,\pm1$ でなければならない | $\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ |
| 完全単模なら最適解はどれも整数である | 整数であるのは頂点である。最適解の集合の辺の中点は整数とは限らない | ex-tu-staffing の 2 つの最適解の中点 $(2,\frac32,\frac32)$ |
| 整数の頂点をもつ多面体の行列は完全単模である | 主張は「すべての整数の右辺で」である | 表の $A=(2)$、$b=2$ |
| 一般のグラフの接続行列も完全単模である | 二部グラフのときだけである | prop-tu-graph |
| 符号つきの向きを付けないと二部グラフに使えない | 符号なしの接続行列のままでよい。片方の組の行に $-1$ を掛けると有向グラフの形になる | prop-tu-ops の 2 |
すべての完全単模行列は、ネットワーク行列(有向グラフの接続行列から 1 行を除いた行列 $(B\ \ N)$ の、正則な部分 $B$ による $B^{-1}N$)と 2 つの $5\times5$ の例外の行列から、決まった操作で組み立てられる。これは Seymour の分解定理である(Mus07 §2.3、Theorem 2.6。この記事では証明しない)。例外の行列の 1 つは
$$
\begin{pmatrix}1&-1&0&0&-1\\-1&1&-1&0&0\\0&-1&1&-1&0\\0&0&-1&1&-1\\-1&0&0&-1&1\end{pmatrix}
$$
である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する