接続行列(グラフ)
概要
接続行列(グラフ)（incidence matrix of a graph）とは、ループのない有限グラフの頂点で行を、辺で列を添字づけ、頂点がその辺の端点なら $1$、そうでなければ $0$ とした行列のことであり、各辺に向きを決めて始点に $1$、終点に $-1$ を置いたものを向き付き接続行列という。向き付き接続行列 $N$ について $NN^{\mathsf T}$ は Laplacian 行列で、その階数は頂点数から連結成分の個数を引いたものである。接続行列の階数は、標数 $2$ の体の上では同じ値、それ以外の体の上では頂点数から二部グラフである連結成分の個数を引いたものになる。$N$ のどの正方小行列の行列式も $0,\pm1$ のいずれかであり、接続行列がこの性質をもつことはグラフが二部グラフであることと同値である。
グラフの頂点で行を、辺で列を添字づけ、「頂点がその辺の端点かどうか」を $0$ と $1$ で記録した行列を接続行列（incidence matrix）という。各辺に向きを決めて、始点に $1$、終点に $-1$ を置いたものが向き付き接続行列である。隣接行列が頂点どうしの関係を記録するのに対し、接続行列は頂点と辺の関係を記録する。
接続行列は、グラフの組合せ的な量を線形代数の言葉に移す道具である。行列の積をとると Laplacian行列 や符号なし Laplacian 行列が現れ、階数は連結成分の個数（体の標数によっては二部グラフである連結成分の個数）で決まり、$\mathbb{F}_2$ 上では核と行空間がそれぞれ閉路の側（偶数次数の辺集合）と切断の側（頂点集合の内と外を結ぶ辺の集合）を表す。さらに向き付き接続行列のどの正方小行列の行列式も $0,\pm1$ のいずれかであり、この性質から全域木を表す小行列式が $\pm1$ になる。
この記事では、接続行列を定義し、積の等式、階数と連結成分の関係、$\mathbb{F}_2$ 上の核と行空間の意味、向き付き接続行列の全単模性と、接続行列が全単模になることと二部グラフであることの同値を証明する。
定義
この記事のグラフは、有限集合 $V$（頂点の集合）と有限集合 $E$（辺の集合）と、各辺 $e$ にその端点の 2 元集合 $\partial(e)\subset V$ を対応させる写像 $\partial$ の組 $G=(V,E,\partial)$ とする。ループ（端点が 1 つの辺）は考えず、同じ 2 頂点を結ぶ辺が複数あること（平行辺）は許す。平行辺のないものが単純グラフ（グラフ の記事の定義「グラフの定義」）である。$n:=|V|$、$m:=|E|$ とし、頂点 $v$ の次数 $\deg v$ は $v$ を端点にもつ辺の本数とする。
グラフ $G=(V,E,\partial)$ の頂点を $v_1,\dots,v_n$、辺を $e_1,\dots,e_m$ と並べる。
- $n\times m$ 行列 $M=(M_{ij})$ を、$v_i\in\partial(e_j)$ のとき $M_{ij}:=1$、そうでないとき $M_{ij}:=0$ と定め、$G$ の接続行列（incidence matrix）という。
- 各辺に向きを 1 つずつ決める。すなわち $\partial(e_j)=\{u,w\}$ の一方を始点、他方を終点と定める。$n\times m$ 行列 $N=(N_{ij})$ を、$v_i$ が $e_j$ の始点なら $N_{ij}:=1$、終点なら $N_{ij}:=-1$、$e_j$ の端点でなければ $N_{ij}:=0$ と定め、$G$ の（この向きに関する）向き付き接続行列（oriented incidence matrix）という。
頂点と辺の並べ方を変えると、$M$ と $N$ の行と列が並べ替わるだけである。辺 $e_j$ の向きを逆にすると、$N$ の第 $j$ 列が $-1$ 倍される。以下の階数や全単模性はこれらの操作で変わらないので、並べ方や向きの選び方によらない。行と列の添字を頂点と辺そのものとし、$M_{ve}$、$N_{ve}$ とも書く。$G$ に平行辺がなければ、$N$ は、$G$ に向きを付けて得た有向グラフの接続行列とみることもできる。
直感
接続行列の列は辺 1 本ぶんの情報で、端点の 2 か所にだけ $0$ でない成分がある。行は頂点 1 つぶんの情報で、その頂点に接する辺の位置に $0$ でない成分が並ぶ。
向き付き接続行列は、頂点の上の関数と辺の上の関数を結ぶ「差分」として働く。頂点に値 $x_v$（電位や高さ）を置くと、行ベクトル $x^{\mathsf T}N$ の $e$ 成分は辺 $e$ の始点と終点の値の差 $x_u-x_w$ である。逆に辺に値 $y_e$（流量）を置くと、$Ny$ の $v$ 成分は $v$ から出ていく流量の和から入ってくる流量の和を引いたもの、すなわち $v$ で湧き出す量である。グラフを電気回路とみれば、$Ny=0$ は各頂点で電流が保存されること（Kirchhoff の電流の法則）、$y=N^{\mathsf T}x$ の形であることは電圧が電位の差として書けること（電圧の法則）にあたる。
例と反例
- 道 $P_3$（頂点 $1,2,3$、辺 $e_1=12$、$e_2=23$）で、辺を番号の小さい頂点から大きい頂点へ向けると
$$ M=\begin{pmatrix}1&0\\1&1\\0&1\end{pmatrix},\qquad N=\begin{pmatrix}1&0\\-1&1\\0&-1\end{pmatrix} $$
である。 - 三角形 $K_3$（頂点 $a,b,c$、辺 $ab,ac,bc$ の順）の接続行列は
$$ M=\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix},\qquad \det M=-2 $$
である。 - 4 頂点の閉路 $C_4$（頂点を一周の順に $1,2,3,4$、辺 $e_i=\{i,i+1\}$、ただし $e_4=\{4,1\}$）で、$e_i$ を $i$ から $i+1$（$e_4$ は $4$ から $1$）へ向けると
$$ N=\begin{pmatrix}1&0&0&-1\\-1&1&0&0\\0&-1&1&0\\0&0&-1&1\end{pmatrix} $$
であり、4 行の和は零ベクトルである。
$P_2$（頂点 $1,2$、辺 1 本）では $M=\begin{pmatrix}1\\1\end{pmatrix}$、$N=\begin{pmatrix}1\\-1\end{pmatrix}$ であり、
$$
MM^{\mathsf T}=\begin{pmatrix}1&1\\1&1\end{pmatrix},\qquad NN^{\mathsf T}=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}
$$
である。$NN^{\mathsf T}$ は Laplacian 行列 $D-A$ に等しいが、$MM^{\mathsf T}$ は等しくない（$D+A$ になる）。満たす性質：$M$ と $N$ は成分の絶対値が同じである。満たさない条件：各列の成分の和が $0$ であること（$M$ の列の和は $2$）。この違いのために、$MM^{\mathsf T}$ の 2 次形式は $\sum_{uw}(x_u+x_w)^2$ になり、差の 2 乗の和にならない（prop-inc-products）。
性質
積の等式
$A$ を $G$ の隣接行列（$A_{uv}$ は $u\neq v$ を結ぶ辺の本数、$A_{vv}=0$）、$D$ を次数を並べた対角行列とする。$L:=D-A$ が Laplacian 行列、$Q:=D+A$ が符号なし Laplacian 行列（符号なしLaplacian）である。
- $M$ の各列の成分の和は $2$、$N$ の各列の成分の和は $0$ である。$M$ の頂点 $v$ の行の成分の和は $\deg v$ である。
- $MM^{\mathsf T}=D+A=Q$、$NN^{\mathsf T}=D-A=L$ である（向きの選び方によらない）。
- 実ベクトル $x\in\mathbb{R}^V$ について
$$ x^{\mathsf T}Lx=\sum_{e\in E,\ \partial(e)=\{u,w\}}(x_u-x_w)^2,\qquad x^{\mathsf T}Qx=\sum_{e\in E,\ \partial(e)=\{u,w\}}(x_u+x_w)^2 $$
であり、$L$ と $Q$ は半正定値である。 - $G$ が単純グラフなら、$M^{\mathsf T}M=2I_m+A(L(G))$ である。ここで $A(L(G))$ は 線グラフ $L(G)$ の隣接行列である。
要点：どれも行列の積の成分を定義どおりに数える計算である。$(MM^{\mathsf T})_{uv}$ は $u$ と $v$ の両方を端点にもつ辺の本数、$(M^{\mathsf T}M)_{ef}$ は $e$ と $f$ の共通の端点の個数である。
詳しい計算を開く
1：各列には端点の 2 か所にだけ $0$ でない成分があり、$M$ では $1,1$、$N$ では $1,-1$ である。$M$ の $v$ の行で $1$ が立つ列は $v$ を端点にもつ辺なので、その個数は $\deg v$ である。
2：$(MM^{\mathsf T})_{uv}=\sum_eM_{ue}M_{ve}$ の項は、$e$ が $u$ と $v$ の両方を端点にもつときだけ $1$ で、それ以外は $0$ である。$u=v$ なら、それは $u$ を端点にもつ辺の本数 $\deg u$ である。$u\neq v$ なら、$u$ と $v$ を結ぶ辺の本数 $A_{uv}$ である。$N$ では $u=v$ の項は $N_{ue}^2=1$ で同じく $\deg u$ を与え、$u\neq v$ の項は $u,v$ の一方が始点、他方が終点なので $1\cdot(-1)=-1$ となり、和は $-A_{uv}$ である。向きを変えても各項は変わらない。
3：$(x^{\mathsf T}N)_e=x_u-x_w$（$u$ が始点、$w$ が終点）なので $x^{\mathsf T}Lx=(x^{\mathsf T}N)(x^{\mathsf T}N)^{\mathsf T}=\sum_e(x_u-x_w)^2\ge0$ である。$M$ では $(x^{\mathsf T}M)_e=x_u+x_w$ なので同様である。
4：$(M^{\mathsf T}M)_{ef}=\sum_vM_{ve}M_{vf}$ は $e$ と $f$ の共通の端点の個数である。$e=f$ なら $2$ である。$e\neq f$ のとき、単純グラフでは異なる 2 辺の端点の集合は異なるので共通の端点は $0$ 個か $1$ 個であり、$1$ 個であることは $L(G)$ で $e$ と $f$ が隣接することにほかならない。$\square$
2 は BH11 §1.1（p. 1）に、4 は同書 §1.4.5（p. 9）にある。3 から $L$ と $Q$ の固有値はすべて $0$ 以上であり、4 から線グラフの隣接行列の固有値はすべて $-2$ 以上である（$M^{\mathsf T}M$ も半正定値なので）。後者は 線グラフ の記事の定理「線グラフの固有値」で扱われている。
階数と連結成分
$G$ の連結成分（連結成分(グラフ)）の個数を $c(G)$、連結成分のうち二部グラフであるもの（孤立点を含む）の個数を $b(G)$ と書く。平行辺のあるグラフでも、連結成分と二部グラフであることは単純グラフの場合と同じく定める（平行辺を 1 本にまとめても変わらない）。頂点の部分集合 $C$ について、$C$ の頂点と、両端点が $C$ に属する辺すべてからなる部分グラフを $G[C]$ と書く。$F$ を体とし、$M$ と $N$ の成分を $F$ の元とみる。
- $F$ 上で $\operatorname{rank}N=n-c(G)$ である。
- $F$ の標数が $2$ なら、$F$ 上で $\operatorname{rank}M=n-c(G)$ である。
- $F$ の標数が $2$ でなければ、$F$ 上で $\operatorname{rank}M=n-b(G)$ である。
$n\times m$ 行列 $X$ について、$\operatorname{rank}X=n-\dim\{x\in F^V\mid x^{\mathsf T}X=0\}$ である（行列の階数。行の個数から左核の次元を引いたもの）。そこで左核を求める。
1：辺 $e$ の始点を $u$、終点を $w$ とすると $(x^{\mathsf T}N)_e=x_u-x_w$ なので、$x^{\mathsf T}N=0$ は「すべての辺で両端点の値が等しい」ことと同値である。この条件のもとでは道に沿って値が変わらないので、$x$ は各連結成分の頂点集合の上で定数である。逆に各連結成分の上で定数なら、どの辺も両端点が同じ連結成分にあるので条件を満たす。よって左核は「連結成分ごとに定数のベクトル」の全体で、次元は $c(G)$ である。
2：標数 $2$ では $x_u+x_w=x_u-x_w$ なので、$M$ の左核は $N$ の左核と同じであり、1 から従う。
3：左核の条件は「すべての辺で $x_w=-x_u$」である。条件は辺ごとに両端点だけにかかわり、両端点は同じ連結成分にあるので、左核は、連結成分 $C$ ごとに「$C$ の上の値が $C$ の辺について条件を満たす」ベクトルの空間 $K_C$ の直和である。$G[C]$ が二部グラフなら $\dim K_C=1$、そうでなければ $K_C=0$ であることを示せばよい。
$C$ の頂点 $r$ を固定する。$x\in K_C$ とし、$r$ から $v\in C$ への長さ $\ell$ の道をとると、条件を辺ごとに使って $x_v=(-1)^\ell x_r$ を得る。よって $x$ は $x_r$ で決まり、$\dim K_C\le1$ である。$G[C]$ が二部グラフで二部分割が $C=A\sqcup B$ のとき、$A$ で $1$、$B$ で $-1$ をとるベクトルは条件を満たし $0$ でないので、$\dim K_C=1$ である。逆に $0\neq x\in K_C$ とすると、上の式から $x_r\neq0$ で、各 $x_v$ は $x_r$ か $-x_r$ である。標数が $2$ でないので $x_r\neq-x_r$ であり、$A:=\{v\mid x_v=x_r\}$、$B:=\{v\mid x_v=-x_r\}$ とおくと、各辺 $uw$ で $x_w=-x_u\neq x_u$ なので $u,w$ は $A$ と $B$ に分かれる。よって $G[C]$ は二部グラフである。$\square$
$F=\mathbb{R}$ のとき、実行列 $X$ について $\operatorname{rank}XX^{\mathsf T}=\operatorname{rank}X$ なので、prop-inc-products の 2 とあわせて、$L$ の固有値 $0$ の重複度は $c(G)$、$Q$ の固有値 $0$ の重複度は $b(G)$ である。前者は Laplacian行列 の記事の定理「核の次元と連結成分の個数」、後者は BH11 Proposition 1.3.9（pp. 7–8）にある。
ex-inc-small の三角形 $K_3$ は連結で二部グラフでないので、$c=1$、$b=0$ である。$\mathbb{R}$ 上では $\det M=-2\neq0$ なので $\operatorname{rank}M=3=n-b$ である。$\mathbb{F}_2$ 上では $\det M=0$ で、3 行の和が $0$ になるので $\operatorname{rank}M=2=n-c$ である。$C_4$ は二部グラフなので、どの体の上でも $\operatorname{rank}M=3$ であり、$x=(1,-1,1,-1)$ が $x^{\mathsf T}M=0$ を満たす。
$\mathbb{F}_2$ 上の核と行空間
$\mathbb{F}_2$ 上では、ベクトルと集合を同一視できる。辺の部分集合 $S\subset E$ に、$e\in S$ で $1$、それ以外で $0$ をとるベクトル $y_S\in\mathbb{F}_2^E$ を対応させると、集合の対称差がベクトルの和にあたる。頂点の部分集合 $U\subset V$ にも同様に $x_U\in\mathbb{F}_2^V$ を対応させる。$U\subset V$ について、一方の端点が $U$ に、他方の端点が $V\setminus U$ にある辺の集合を $E(U,V\setminus U)$ と書き、$U$ の定める切断（cut）という（$U=\emptyset$ なら空集合）。辺の集合 $S$ は、全域部分グラフ $(V,S)$ のすべての頂点の次数が偶数のとき偶であるという。
$M$ を $\mathbb{F}_2$ 上の行列とみる。
- $My_S=0$ であることと、$S$ が偶であることは同値である。偶な辺集合の全体は $\mathbb{F}_2^E$ の部分空間で、次元は $m-n+c(G)$ である。
- $x_U^{\mathsf T}M=y_{E(U,V\setminus U)}$ である。したがって $M$ の行空間は切断の全体であり、次元は $n-c(G)$、相異なる切断はちょうど $2^{\,n-c(G)}$ 個ある。
- どの切断とどの偶な辺集合も、偶数本の辺を共有する。
1：$(My_S)_v=\sum_{e\in S}M_{ve}$ は、$v$ を端点にもつ $S$ の辺の本数を $2$ で割った余りである。よって $My_S=0$ は $S$ が偶であることと同値である。偶な辺集合の全体は $M$ の核なので部分空間であり、次元は次元定理と thm-inc-rank の 2 により $m-(n-c(G))$ である。
2：$(x_U^{\mathsf T}M)_e=\sum_{v\in U}M_{ve}$ は、$e$ の端点のうち $U$ に属するものの個数を $2$ で割った余りであり、ちょうど 1 個のとき $1$ になる。よって $x_U^{\mathsf T}M=y_{E(U,V\setminus U)}$ である。$U\mapsto x_U$ は $V$ の部分集合全体と $\mathbb{F}_2^V$ の全単射なので、行空間 $\{x^{\mathsf T}M\mid x\in\mathbb{F}_2^V\}$ は切断の全体である。その次元は $\operatorname{rank}M=n-c(G)$ であり、$\mathbb{F}_2$ 上の $d$ 次元の空間はちょうど $2^d$ 個の元をもつ。
3：切断 $E(U,V\setminus U)$ と偶な $S$ の共有する辺の本数を $2$ で割った余りは $y_{E(U,V\setminus U)}^{\mathsf T}y_S=x_U^{\mathsf T}(My_S)=0$ である。$\square$
単純グラフのとき、偶な辺集合の空間は 閉路 の記事の定義「閉路空間」の閉路空間と同じものであり、1 の次元は同記事の定理「閉路空間の次元と基本閉路」の次元の主張を接続行列から導き直したものである。2 の行空間は切断空間とよばれる。Die25 Proposition 1.9.6（p. 27）は 1 と 2 を「接続行列の核は閉路空間、転置の像は切断空間」と述べ、Theorem 1.9.4（p. 25）は 2 つの空間が互いの直交補空間であることを示している。
$C_4$（ex-inc-small の 3）では $n=m=4$、$c=1$ である。偶な辺集合は $\emptyset$ と $E$ の $2=2^{4-4+1}$ 個で、切断は $2^{4-1}=8$ 個ある。$U$ と $V\setminus U$ は同じ切断を定めるので、16 個の $U$ が 2 個ずつ組になる。たとえば $U=\{1\}$ は $\{e_4,e_1\}$、$U=\{1,2\}$ は $\{e_4,e_2\}$、$U=\{1,3\}$ は $E$ 全体を定める。どの切断も辺の本数が偶数で、$E$ と偶数本を共有する。
$\mathbb{R}$ 上では、向き付き接続行列の核 $\{y\in\mathbb{R}^E\mid Ny=0\}$ は、どの頂点でも湧き出しが $0$ の流れ（循環）の空間であり、次元は thm-inc-rank の 1 により $m-n+c(G)$ である。像 $\{N^{\mathsf T}x\}$ は電位の差として書ける辺の上の関数の空間で、次元は $n-c(G)$ である。$\mathbb{R}^E$ の標準内積について、行列の核は転置の像の直交補空間なので、2 つの空間は互いの直交補空間である。
全単模性
整数を成分とする行列 $X$ が全単模（totally unimodular）であるとは、$X$ のどの正方小行列（行と列をそれぞれいくつか選んで作る正方行列）の行列式も $0,1,-1$ のいずれかであることをいう。$1\times1$ の小行列を考えると、全単模な行列の成分は $0,\pm1$ である。行を $-1$ 倍しても、列を $-1$ 倍しても、全単模であることは変わらない（小行列式の符号が変わるだけなので）。
向き付き接続行列 $N$ は全単模である。
$N$ の $k\times k$ 小行列 $B$ について、$k$ に関する帰納法で $\det B\in\{0,\pm1\}$ を示す。$k=1$ なら $B$ は $N$ の成分なので正しい。$k\ge2$ とし、$B$ の列を 1 つずつ見る。$N$ の各列には $0$ でない成分が $1$ と $-1$ の 2 個だけあるので、$B$ の各列の $0$ でない成分は $0$ 個、$1$ 個、または $1$ と $-1$ の 2 個である。
- $0$ 個の列があれば $\det B=0$ である。
- $1$ 個だけの列があれば、その列で余因子展開すると $\det B=\pm\det B'$ である。$B'$ はその成分の行と列を除いた $(k-1)\times(k-1)$ 行列で、$N$ の小行列なので、帰納法の仮定により $\det B'\in\{0,\pm1\}$ である。
- どの列にも $1$ と $-1$ がちょうど 1 個ずつあれば、$B$ のすべての行の和は零ベクトルであり、行が線形従属なので $\det B=0$ である。
いずれの場合も $\det B\in\{0,\pm1\}$ である。$\square$
接続行列 $M$ が全単模であるための必要十分条件は、$G$ が二部グラフであることである。
$G$ が二部グラフで、$V=A\sqcup B$ がその二部分割（どの辺も $A$ と $B$ を結ぶ）とする。各辺を $A$ の端点から $B$ の端点へ向けた向き付き接続行列を $N$ とすると、$v\in A$ の行は $M$ と $N$ で等しく、$v\in B$ の行は $N$ が $M$ の $-1$ 倍である。よって $M$ は $N$ の $B$ の行を $-1$ 倍したものであり、thm-inc-tu-oriented により全単模である。
逆に $G$ が二部グラフでないとする。平行辺を 1 本にまとめた単純グラフも二部グラフでないので、二部グラフ の記事の定理「閉路の長さによる特徴付け」により奇数の長さ $k\ge3$ の閉路をもつ。その頂点を一周の順に $v_1,\dots,v_k$ とし、$v_i$ と $v_{i+1}$（$v_{k+1}:=v_1$）を結ぶ $G$ の辺を 1 本ずつ選んで $e_i$ とする。$M$ の行 $v_1,\dots,v_k$ と列 $e_1,\dots,e_k$ からなる小行列 $B$ の $(i,j)$ 成分は、$j=i$ または $j\equiv i-1\pmod k$ のとき $1$、それ以外で $0$ である。Leibniz の公式で $\det B=\sum_\sigma\operatorname{sgn}(\sigma)\prod_iB_{i\sigma(i)}$ を計算すると、項が $0$ でない置換 $\sigma$ は各 $i$ で $\sigma(i)\in\{i,i-1\}$ を満たす。ある $i$ で $\sigma(i)=i-1$ なら、$i-1$ は $\sigma(i-1)$ の値になれないので $\sigma(i-1)=i-2$ となり、これを繰り返すとすべての $i$ で $\sigma(i)=i-1$ である。よって項は恒等置換と巡回置換 $i\mapsto i-1$ の 2 つだけで、後者は長さ $k$ の巡回置換なので符号は $(-1)^{k-1}=1$ である。したがって $\det B=1+1=2$ となり、$M$ は全単模でない。$\square$
ex-inc-small の $K_3$ では $M$ 自身が $\det M=-2$ の正方行列である（辺の並べ方が上の証明と違うので符号が異なる）。$C_4$ では、同じ計算で $\det M=1+(-1)^{3}=0$ となる。
全単模性から、全域木に対応する小行列式が $\pm1$ であることが従う。頂点 $x$ の行を $N$ から除いた $(n-1)\times m$ 行列を $N_x$ とし、辺の集合 $S$ について $N_x$ の $S$ の列からなる小行列を $(N_x)_S$ と書く。
$x\in V$、$S\subset E$、$|S|=n-1$ とする。$(V,S)$ が全域木なら $\det(N_x)_S=\pm1$ であり、そうでなければ $\det(N_x)_S=0$ である。
$N$ の $S$ の列からなる $n\times(n-1)$ 行列 $N_S$ は、全域部分グラフ $(V,S)$ の向き付き接続行列なので、thm-inc-rank の 1 により $\mathbb{R}$ 上の階数は $n-c((V,S))$ である。$(V,S)$ で $x$ を含む連結成分を $K$ とすると、$N_S$ の $K$ の頂点の行の和は零ベクトルである（$K$ の中の辺の列には $1$ と $-1$ がともに $K$ の行にあり、$K$ の外の辺の列は $K$ の行で $0$ である）。よって $x$ の行は $K$ のほかの頂点の行の 1 次結合であり（$K=\{x\}$ なら零ベクトル）、これを除いても階数は変わらない。したがって $\operatorname{rank}(N_x)_S=n-c((V,S))$ である。
$(N_x)_S$ は $n-1$ 次の正方行列なので、$\det(N_x)_S\neq0$ は $c((V,S))=1$ と同値であり、これは $(V,S)$ が連結であること、すなわち辺の本数が $n-1$ なので全域木であること（全域木 の記事の命題「木の判定」）と同値である。このとき thm-inc-tu-oriented により $\det(N_x)_S=\pm1$ である。$\square$
Laplacian行列 から $x$ の行と列を除いた行列は $N_xN_x^{\mathsf T}$ である（prop-inc-products の 2）。これに Cauchy–Binetの公式 の系「行列とその共役転置の積」を当てると、$\det(N_xN_x^{\mathsf T})$ は小行列式 $\det(N_x)_S$ の 2 乗の和になり、cor-inc-tree-minor により全域木の個数に等しい。これが 行列木定理 の証明の骨組みである（同記事は小行列式の値を葉を 1 枚ずつ除く帰納法で求めている）。
全単模な行列は、線形計画法 で整数解を保証する性質として現れる。$X$ が全単模で $b$ が整数ベクトルなら、$X$ の正則な正方小行列 $X'$ についての方程式 $X'z=b'$ の解は、Cramerの公式 により行列式 $\pm1$ で割った整数の比なので整数ベクトルである。
仮定を外した場合
| 外す条件・替える条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-inc-rank の 3 の「標数が $2$ でない」 | $\mathbb{F}_2$ 上の $K_3$ | $\operatorname{rank}M=2\neq3=n-b$ |
| prop-inc-products の 2 で、$N$ を $M$ に替える | $P_2$ | $MM^{\mathsf T}=Q\neq L$ |
| thm-inc-tu-bipartite の「二部グラフ」 | $K_3$ | $\det M=-2$ で、$M$ は全単模でない |
| cor-inc-tree-minor の「$x$ の行を除く」（除かずに $n$ 本の辺の列で $n$ 次の正方行列を作る） | $K_3$ で $S=E$ | $(V,S)$ は連結なのに $\det N_S=0$ |
各行で外した条件が、証明のどこで使われていたかを確かめる。
各行の確かめを開く
1 行目：ex-inc-rank-field で確かめた。証明では $x_r\neq-x_r$ に標数が $2$ でないことを使っている。
2 行目：ex-inc-not-laplacian で確かめた。
3 行目：ex-inc-small の 2 の計算による。$K_3$ は長さ $3$ の閉路なので二部グラフでない。
4 行目：$N$ の行の和はつねに零ベクトルなので、行を除かない $n$ 次の正方小行列の行列式はつねに $0$ である。cor-inc-tree-minor の証明は、行を 1 つ除いても階数が下がらないことを使って、$n-1$ 次の正方行列の正則性に帰着している。
補足
- 有向グラフとハイパーグラフ：ループのない有向グラフの接続行列は、有向辺の始点に $1$、終点に $-1$ を置いた行列で、この記事の $N$ と同じ形である。辺が 3 頂点以上を含みうるハイパーグラフや、点とブロックの関係を記録する組合せデザインでも、「点が辺（ブロック）に含まれるか」を $0,1$ で記録した行列を接続行列とよぶ。
- 文献：接続行列と隣接行列の定義は BM76 §1.3（p. 7）、$\mathbb{F}_2$ 上の閉路空間・切断空間との関係は Die25 §1.9（pp. 23–27）、Laplacian 行列との関係は BH11 §1.1（p. 1）・§1.3.7（pp. 7–8）にある。全単模性の証明はこの記事で独自に書いた。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
