文献あり

格子の道と行列式について

135

ゲッセルとヴィアンノの補題について

今回は参考文献tenshoを元にして、格子の道と行列式との関係について手短に見て行きます。
まず次の事を認めましょう。

$M = (m_{i j})$ を $n \times n$ 行列とする。この時、 $M$ の行列式は次の様な重み付きの有効2部グラフを用いて表すことができる。
すなわち、頂点 $A_{1}, A_{2}, . . ., A_{n}$ を行列Mのそれぞれの行に対応させ、頂点 $B_{1}, B_{2}, . . ., B_{n}$ を行列Mのそれぞれの列に対応する様にし、図の様に $A_{i}$ から $B_{j}$ への矢印を描き、重み $m_{i j}$ を与えた2部グラフを考えると次のように書ける。
$\det (M) = \sum_{σ \in S_{n}} s g n (σ) w (P_{σ})$
ただし、この式の意味は次の様だ。
$σ \in S_{n}$ を固定した時の $A = A_{1}, A_{2}, . . ., A_{n}$ から $B = B_{1}, B_{2}, . . ., B_{n}$ への頂点分離系の道を $P_{σ}$ 、また $w (P_{σ})$ は道 $P_{σ}$ の重みを表している。

3 \times 3

の場合

以下ゲッセルとヴィアンノの補題を証明するにあたって必要なものを定義します。

重み

重み付き有効グラフ $G$ の頂点 $A$ と頂点 $B$ を結ぶ道 $P$ が与えられているとき、道 $P$ の重み $w (P)$ を次の様に定義する。
$w (P) = \prod_{e \in P} w (e)$

行列

重み付き有向グラフ $G = (V, E)$ について、頂点の部分集合 $A = {A_{1}, A_{2}, . . ., A_{n}}, B = {B_{1}, B_{2}, . . ., B_{n}}$ に対して、 $n \times n$ 行列 $M = (m_{i j})$ を次のように定義する。
$m_{i j} = \sum_{P : A_{i} \to B_{j}} w (P)$

記号

重み付き有向グラフ $G = (V, E)$ について、頂点の部分集合 $A = {A_{1}, A_{2}, . . ., A_{n}}, B = {B_{1}, B_{2}, . . ., B_{n}}$ に対して、 $A$ から $B$ への道の系 $P_{σ}$ は $P_{i} : A_{i} \to B_{σ (i)} (i = 1, 2, . . ., n)$ とからなるもので、 $s i g n (P_{σ}) = s i g n (σ)$ と書く。また、道の系 $P_{σ}$ の重み $w (P)$ を次のように書く。
$w (P_{σ}) = \prod_{i = 1}^{n} w (P_{i})$

頂点分離

サイクルの無い重み付き有向グラフ $G = (V, E)$ について、頂点の部分集合 $A = {A_{1}, A_{2}, . . ., A_{n}}, B = {B_{1}, B_{2}, . . ., B_{n}}$ に対して、 $A$ から $B$ への道の系 $P_{σ} = (P_{1}, P_{2}, . . ., P_{n})$ が頂点分離であるとは、この道の系 $P_{σ}$ の任意の異なる二つの道を選んでも、それらの道が共通の頂点を持たない事である。

ゲッセルとヴィアンノの補題

サイクルの無い重み付き有向グラフ $G = (V, E)$ を考える。頂点の部分集合 $A = {A_{1}, A_{2}, . . ., A_{n}}, B = {B_{1}, B_{2}, . . ., B_{n}}$ に対して、 $M = (m_{i j})$ を $A$ から $B$ への道の行列とする。この時以下の式が成り立つ。
$\det M = \sum_{P \in (A から B への頂点分離な道の系)} s i g n (P) w (P)$

まず定義より、次の式が成り立つ。
$\begin{array}{rcl} \det M & = & \sum_{σ \in S_{n}} s i g n (σ) (\sum_{P_{1} : A_{1} \to B_{σ (1)}} w (P_{1})) (\sum_{P_{2} : A_{2} \to B_{σ (2)}} w (P_{2})) \dots (\sum_{P_{n} : A_{n} \to B_{σ (n)}} w (P_{n})) \\ = & \sum_{P \in (A から B への道の系)} s i g n (σ) \sum_{P_{1} : A_{1} \to B_{σ (1)}} \sum_{P_{2} : A_{2} \to B_{σ (2))}} \dots \sum_{P_{n} : A_{n} \to B_{σ (n)}} w (P_{1}) w (P_{2}) \dots w (P_{n}) \\ = & \sum_{P \in (A から B への道の系)} s i g n (P) w (P) \end{array}$
示すべきことは以下の事である。それは $A$ から $B$ への道の系のうち頂点分離でない道の系を $N$ とすると、次の事が成り立つことである。 $\sum_{P \in N} s i g n (P) w (P) = 0$
実際、 $P \in N$ を道 $P_{i} : A_{i} \to B_{σ (i)}$ を持つものとする。すると道 $N$ の定義より、少なくとも一つ道 $P_{j}$ が存在して共通の頂点を持つ。
その共通の頂点で $A_{i}$ から出発して一番最初に $P_{i}$ と $P_{j}$ の最初に共有する頂点を $X$ とする。
次に、 $π$ を $π P = (P_{1}^{^{'}}, P_{2}^{^{'}}, . . ., P_{i}^{^{'}}, . . ., P_{j}^{^{'}}, . . ., P_{n}^{^{'}})$ の様に定める。ただし、 $P_{i}^{^{'}} (i = 1, 2, . . ., n)$ は次の様な道をなす。
$\begin{array}{r} {\begin{cases} \cdot k \neq i, j に対しては P_{k}^{^{'}} = P_{k} \\ \cdot P_{i}^{^{'}} は頂点 A_{i} から頂点 X までの経路は P_{i} 、頂点 X から頂点 B_{σ (j)} への経路は P_{j} に沿う様にとる。 \\ \cdot P_{j}^{^{'}} は頂点 A_{j} から頂点 X までの経路は P_{j} 、頂点 X から頂点 B_{σ (i)} への経路は P_{i} に沿う様にとる。 \end{cases} \end{array}$
すると、以下の事が分かる。
まず、 $π (π P) = P$ 。これは明らか。また、 $π P$ と $P$ は同じ辺を使用しているので $w (π P) = w (P)$ となる。
また、新しい置換 $σ^{^{'}}$ は置換 $σ$ に $(i, j)$ をかけたものなので、 $s i g n (π P) = - s i g n (P)$ となる。ゆえに、補題は示された。

ゲッセル・ヴィアンノの補題参考画像

応用1.ビネ-コーシーの公式の証明

ビネ-コーシーの公式

$P を r \times s$ 行列、 $Q$ を $s \times r$ 行列 $(r \leq s)$ であれば以下の式が成り立つ。
$\det P Q = \sum_{Z} \det P_{Z} \det Q_{Z}$
ただし、 $Z = (j_{1}, j_{2}, . . ., j_{r}) \in N^{r} (1 \leq j_{1} \leq j_{2} \leq \dots \leq j_{r} \leq s)$ なるもの全体とし、 $P_{Z}$ は $P$ の $j_{1}, j_{2}, . . ., j_{r}$ 列を抜き出して作った $r \times r$ 行列。また、 $Q_{Z}$ は $Q$ の $j_{1}, j_{2}, . . ., j_{r}$ 行を抜き出した $r \times r$ 行列とした。

グラフ $G = (V, E)$ を $A = {A_{1}, A_{2}, . . ., A_{r}}, B = {B_{1}, B_{2}, . . ., B_{s}}, C = {C_{1}, C_{2}, . . ., C_{r}}$ とし、
$E = A \cap B \cap C$ とする。また、 $A$ と $m a t h c a l B$ の部分を見ると２部グラフ、また $B$ と $m a t h c a l C$ の部分を見たときも同様に２部グラフになる様に辺の集合 $V$ を構成する。
また、各辺の重みは $w (A_{i} \to B_{j}) = p_{i j}, w (B_{j} \to C_{k}) = q_{j k}$ となる様にとると、 $A$ から $C$ への道の $(i, k)$ 行列 $M$ の成分 $m_{i k}$ はグラフの構成の仕方から $m_{i k} = \sum_{j = 1}^{s} p_{i j} q_{j k}$ 。
また、繋いだグラフにおける $A$ から $C$ への頂点分離の道の系はそれぞれ $A$ から $B$ への頂点分離の道の系と $B$ から $C$ への頂点分離の道の系の対なので、下記の式が導かれるので証明が完了する。
$\begin{array}{rcl} \det M & = & \det P Q \\ = & \sum_{Z} s i g n (σ τ) p_{i σ (j)} q_{σ (j) k} \\ = & \sum_{Z} s i g n (σ) p_{i σ (j)} s i g n (τ) q_{σ (j) k} \\ = & \sum_{Z} \det P \det Q \end{array}$

ビネ-コーシの公式

応用2.行列式の計算

$a_{1} < a_{2} < \dots < a_{n}$ と $b_{1} < b_{2} < \dots < b_{n}$ を自然数の作る２つの集合とする。今 $m_{i j}$ が２項係数 $_{a_{i}} C_{b_{j}}$ である様な行列 $M = (m_{i j})$ の行列式を計算せよ。

下記図の様な格子を考える。
また点 $A_{i}$ の座標を $(0, - a_{i})$ 、点 $B_{j}$ の座標を $(b_{j}, - b_{j})$ の様に設定する。
この格子上で点 $A_{i}$ から $B_{j}$ まで最短で移動する(上あるいは右に移動するのみが許される)道の数は簡単な考察から $_{a_{i}} C_{b_{j}}$ ．ゆえに与えられた行列 $M$ はすべての辺の重みが1であり、すべての辺の向きが右向きあるいは上向きの有向グラフで、 $A = {A_{1}, A_{2}, . . ., A_{n}}$ から $B = {B_{1}, B_{2}, . . ., B_{n}}$ への道の行列になる。
また、 $A$ から $B$ への任意の頂点分離の道の系 $P$ はすべての $i$ に対して、 $P_{i} : A_{i} \to B_{i}$ である道からなっていないといけないことが分かる。
ゆえに、以下の結論を得る。
$\det M = # {A から B への頂点分離の道の系}$