01.1x.置換の符号

置換の符号はwell-definedか

置換 $\sigma$ の符号は, $\sigma$ が $k$ 個の互換の積として表されるとき, \begin{align} {\rm sign}(\sigma) = (-1)^k \end{align} と計算される. ところが, $\sigma$ を互換の積として表す方法は複数存在し, $k$ の値も一意には決まらない. つまり, 置換の符号を計算する手順は複数存在する.

置換の符号の定義に曖昧さがない, つまりwell-definedであることを言うためには, $k$ の偶奇がこの計算法によらず一意に決まることを示さなくてはならない. 既に差積の性質を利用した簡潔な証明は与えられている. しかし, もっと素朴で, 置換の偶奇性に関してより深い理解に繋がるような方法で示すことはできないだろうか?

一般の置換の符号

略. ある置換が互換の積で表されるとき, その個数の偶奇が一意に定まることを言うためには, 「恒等置換が偶数個の隣接互換の積であること」を示せばよいという証明.

恒等置換は偶数個の隣接互換の積であること

$N := \{1,2,\cdots,n\}$ 上の隣接互換の集合を \begin{align*} Adj_n = \{(1,2),(2,3),\cdots,(n\!-\!1,n)\} \subset {\mathfrak S}_n \end{align*} と表すことにする. なお, 置換は右からの作用で考える.

ある置換 $\sigma\in {\mathfrak S}_n$ が $\ell$ 個の隣接互換 $\alpha_1, \alpha_2,\cdots,\alpha_\ell\in Adj_n$ の積として $\sigma = \alpha_1\alpha_2\cdots\alpha_\ell$ であるとする. このとき, $0\leq t \leq \ell$ に対して $\sigma_t$ を以下で定義する: \begin{align} \sigma_t = \alpha_1\alpha_2\cdots\alpha_t \end{align} つまり $\sigma_t$ は $\sigma$ の左から $t$ 個だけをとった積. なお, $t=0$ のときは $\sigma_0 = e$ と約束する. $i\in N$ に対して, $t\in L:=\{1,2,\cdots,\ell\}$ のうち, $\sigma_t$ が $i$ の「経路」に寄与するような $t$ を集めた集合を $P_i$ とする: \begin{align*} P_i := \left\{t\in N\mid i^{\sigma_t} \neq i^{\sigma_{t-1}}\right\}. \end{align*} $i < j$ なる $i, j\in N$ に対して, その共通部分が \begin{gather} P_i \cap P_j = \{t_1,t_2,\cdots,t_{u_{ij}}\},\\ t_1 < t_2 < \cdots < t_{u_{ij}} \end{gather} であるとする. $t\in P_i \cap P_j $ で $\alpha_t = (i^{\sigma_t},j^{\sigma_t})$ であることに注意. 各 $t$ で $i, j$ の像の大小関係は以下のようになる. \begin{align} \begin{array}{rc} 0 \leq t < t_1 :& i^{\sigma_t} < j^{\sigma_t}\\ t_1 \leq t < t_2 :& i^{\sigma_t} > j^{\sigma_t}\\ t_2 \leq t < t_3 :& i^{\sigma_t} < j^{\sigma_t}\\ t_3 \leq t < t_4 :& i^{\sigma_t} > j^{\sigma_t}\\ \vdots& \\ \end{array} \end{align} $P_i\cap P_j$ に含まれない $t$ において $i, j$ の像は大小関係を変えないが, 逆に含まれれば必ず順序が入れ替わるということ. 隣接互換一つの作用では絶対値が高々1しか変わらないことからこのことが分かる.

$\sigma$ が恒等置換であるとき, $i^{\sigma_\ell} = i, j^{\sigma_\ell} = j$ だから, $t_u \leq t <\ell$ において $i^{\sigma_t} < j^{\sigma_t}$ でなくてはならない. したがって, $u_{ij}$ は偶数であって, 整数 $m_{ij}$ によって $u_{ij}=2m_{ij}$ と表せる.

$i < j < k$ なる $i,j,k$ に対しては \begin{align} P_i \cap P_j \cap P_k = \emptyset \end{align} である. 互換は $N$ のただ2つの元しか変えないことから明らか. 4つ以上の場合も同様.

以上より, \begin{align} \ell&=|L|\\ &= \left|\bigcup_{i\in N} P_i\right|\cdots(*) \\ &= \sum_{i}\left|P_i\right| - \sum_{i < j} \left|P_i \cap P_j\right| + \sum_{i < j < k} \left|P_i \cap P_j \cap P_k\right| - \cdots \cdots(**)\\ &= 2\ell - \sum_{i<j}u_{ij}.\label{2ell}\\ \therefore \ell &= \sum_{i<j} u_{ij}. \cdots(***) \end{align} が導かれる. (*)への変形で包除原理, また(**) では, 隣接互換はちょうど2つの元の入れ替えに寄与することから $\sum_i |P_i| = 2\ell$ となることを用いた. 特に, $\sigma$ が恒等置換であるとき, \begin{align} \ell = 2\sum_{i< j}m_{ij} \end{align} より, $\ell$ は偶数. すなわち恒等置換は偶数個の隣接互換の積であることが言える.

備考 - 転倒数

式(***)は置換の符号を転倒数から計算する方法を与える. \begin{align} u_{ij} \equiv \left\{ \begin{array}{cc} 0 & i^\sigma < j^\sigma, \\ 1 & i^\sigma > j^\sigma, \end{array}\right. \mod 2. \end{align} であるから, 置換の転倒数を \begin{align} {\rm inv}(\sigma) := \left|\{(i,j)\in N^2 \mid i<j,\ i^\sigma > j^\sigma\}\right| \end{align} によって定義すると, \begin{align} {\rm sign}(\sigma) = (-1)^\ell = (-1)^{{\rm inv}(\sigma)} \end{align} と計算できる.

なお, 転倒数は明らかに一意に決まるが, これによって符号を定義するべきではない. 符号の乗法性が明らかではないためである.