互換

同義語：transposition

概要

定義

集合 $X$ から $X$ 自身への全単射を $X$ の置換といい、置換全体が写像の合成についてなす群を $S_X$ と書く（対称群）。$X=\{1,\dots,n\}$ のとき $S_X$ を $S_n$ と書く。置換の積 $\sigma\tau$ は「$\tau$ を先に、$\sigma$ を後に」施す合成 $\sigma\circ\tau$ とし、恒等置換を $e$ と書く。置換 $\sigma$ が $x\in X$ を動かすとは $\sigma(x)\neq x$ であることをいう。

互換

$X$ の相異なる 2 元 $a,b$ に対し、$a$ を $b$ に、$b$ を $a$ に移し、他の元をすべて動かさない置換を $(a\,b)$ と書き、互換（transposition）という。すなわち
$$ (a\,b)(a)=b,\qquad(a\,b)(b)=a,\qquad(a\,b)(x)=x\quad(x\neq a,b) $$
である。$S_n$ の互換 $(i\ \ i+1)$（$1\le i< n$）を 隣接互換 という。

互換は、相異なる $a_1,\dots,a_k$ を $a_1\mapsto a_2\mapsto\cdots\mapsto a_k\mapsto a_1$ と巡回させて他を動かさない巡回置換 $(a_1\,a_2\,\cdots\,a_k)$ の $k=2$ の場合である。定義から $(a\,b)=(b\,a)$ であり、$X$ の元が 1 個以下なら互換は存在しない。

互換の基本的な性質

$X$ を集合、$a,b\in X$ を相異なる元とする。

$(a\,b)^2=e$ であり、$(a\,b)^{-1}=(a\,b)$ である。互換の元の位数は $2$ である。
置換 $\sigma\in S_X$ が互換であることと、$\sigma$ が動かす元がちょうど 2 個であることは同値である。
任意の $\rho\in S_X$ について $\rho(a\,b)\rho^{-1}=(\rho(a)\,\rho(b))$ である。したがって $S_X$ の互換はすべて互いに共役である。
$S_n$ の互換の個数は $\binom n2=n(n-1)/2$ である。

1：$(a\,b)$ を 2 回施すと $a\mapsto b\mapsto a$、$b\mapsto a\mapsto b$ であり、他の元は動かないので $(a\,b)^2=e$ である。両辺に右から $(a\,b)^{-1}$ を掛けて $(a\,b)=(a\,b)^{-1}$ を得る。$(a\,b)\neq e$ なので位数は $2$ である。
2：互換 $(a\,b)$ が動かす元は $a,b$ の 2 個である。逆に $\sigma$ が動かす元がちょうど $a,b$ の 2 個であるとする。$\sigma(a)\neq a$ であり、$\sigma(a)$ が $a,b$ 以外の元 $c$ なら、$\sigma(c)=c=\sigma(a)$ となって $\sigma$ が単射であることに反する。よって $\sigma(a)=b$ であり、同様に $\sigma(b)=a$ である。他の元は動かないので $\sigma=(a\,b)$ である。
3：$x\in X$ について両辺の値を比べる。$x=\rho(a)$ なら左辺は $\rho((a\,b)(a))=\rho(b)$ であり、右辺も $\rho(b)$ である。$x=\rho(b)$ も同様である。$x\neq\rho(a),\rho(b)$ なら $\rho^{-1}(x)\neq a,b$ なので、左辺は $\rho(\rho^{-1}(x))=x$ であり、右辺も $x$ である。後半について、2 つの互換 $(a\,b)$、$(c\,d)$ に対し、$\rho(a)=c$、$\rho(b)=d$ となる置換 $\rho$ がとれる。実際、$\{a,b\}=\{c,d\}$ なら $(a\,b)=(c\,d)$ なので $\rho=e$ でよい。ちょうど 1 元を共有するときは、$(a\,b)=(b\,a)$、$(c\,d)=(d\,c)$ と書き直して $a=c$、$b\neq d$ としてよく、$\rho=(b\,d)$ とすればよい。交わらなければ $\rho=(a\,c)(b\,d)$ とすればよい。このとき $\rho(a\,b)\rho^{-1}=(c\,d)$ である。
4：2 により、互換 $(a\,b)$ は動かす元の 2 元部分集合 $\{a,b\}$ と一対一に対応する。$n$ 元集合の 2 元部分集合の個数は二項係数 $\binom n2$ である（二項係数の記事の命題「部分集合による特徴づけ」）。$\square$

直感

互換は「2 つだけを入れ替える」最も小さな並べ替えである。トランプを並べ替えるとき、2 枚ずつ入れ替える操作を繰り返せばどんな並びにも到達できる（thm-transposition-decomposition）。ただし同じ並べ替えに到達する入れ替えの手順は一通りでなく、手数も一定しない。それでも手数の偶奇だけは並べ替えから決まり（cor-transposition-parity）、この偶奇が置換の符号である。
互換は線形代数にも現れる。行列の 2 つの行を入れ替える操作は、行の番号に互換を施すことであり、行列式の符号を反転させる。行列式の展開で置換ごとに付く符号 $\pm1$ は、その置換を互換の積に書いたときの個数の偶奇から決まる。

例と反例

3 文字の置換

$S_3$ の $6$ 個の元は、$e$、互換 $(1\,2)$・$(1\,3)$・$(2\,3)$、3 文字の巡回置換 $(1\,2\,3)$・$(1\,3\,2)$ である。巡回置換は互換の積に何通りにも書ける。たとえば、右から順に施して確かめると
$$ (1\,2\,3)=(1\,2)(2\,3)=(1\,3)(1\,2)=(2\,3)(1\,3) $$
であり、$(1\,2)(1\,2)=e$ を挟めば $(1\,2\,3)=(1\,2)(1\,2)(1\,2)(2\,3)$ と 4 個の互換の積にも書ける。個数は $2$ と $4$ で異なるが、どちらも偶数である。また $(1\,2)(1\,3)=(1\,3\,2)\neq(1\,2\,3)=(1\,3)(1\,2)$ なので、互換どうしは一般に可換でない。互換 $(a\,b)$ と $(c\,d)$ が可換であるのは、$\{a,b\}=\{c,d\}$ であるか、$\{a,b\}$ と $\{c,d\}$ が交わらないときである。実際、この 2 つの場合には $(a\,b)(c\,d)$ と $(c\,d)(a\,b)$ はどちらも同じ置換（それぞれ $e$ と、$a,b$ および $c,d$ を入れ替える置換）である。残るのはちょうど 1 文字を共有する場合で、互換を $(x\,y)$、$(y\,z)$（$x,y,z$ は相異なる）と書くと $(x\,y)(y\,z)=(x\,y\,z)$、$(y\,z)(x\,y)=(x\,z\,y)$ であり、前者は $x$ を $y$ に、後者は $x$ を $z$ に移すので両者は異なる。

巡回置換の分解

相異なる $a_1,\dots,a_k$（$k\ge2$）について
$$ (a_1\,a_2\,\cdots\,a_k)=(a_1\,a_2)(a_2\,a_3)\cdots(a_{k-1}\,a_k)=(a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2) $$
である。2 番目の等号の右辺を確かめる（1 番目も同様である）。右端の $(a_1\,a_2)$ から順に施すと、$a_1$ は最初の因子で $a_2$ に移り、以後の因子 $(a_1\,a_j)$（$j\ge3$）は $a_2$ を動かさないので、$a_2$ に移る。$2\le i< k$ のとき、$a_i$ は因子 $(a_1\,a_i)$ までは動かず、そこで $a_1$ に移り、直後の因子 $(a_1\,a_{i+1})$ で $a_{i+1}$ に移り、以後は動かない。$a_k$ は最後の因子 $(a_1\,a_k)$ で初めて動き、$a_1$ に移る。$a_1,\dots,a_k$ 以外の元はどの因子でも動かない。よって右辺は $(a_1\,a_2\,\cdots\,a_k)$ に一致する。
したがって $k$ 文字の巡回置換は $k-1$ 個の互換の積である。たとえば $(1\,2\,3\,4)=(1\,2)(2\,3)(3\,4)$ である。

行の入れ替えと置換行列

体 $K$ 上の数ベクトル空間 $K^n$ の標準基底を $u_1,\dots,u_n$ とする。$\sigma\in S_n$ に対し、第 $j$ 列が $u_{\sigma(j)}$ である $n$ 次正方行列を $P_\sigma$ と書く（置換行列）。$P_\sigma u_j=u_{\sigma(j)}$ なので $P_\sigma P_\tau=P_{\sigma\tau}$ である。互換 $(i\,j)$ の置換行列 $P_{(i\,j)}$ は単位行列の第 $i$ 行と第 $j$ 行を入れ替えた行列であり、行列 $A$ に左から掛けると $A$ の第 $i$ 行と第 $j$ 行が入れ替わる。$\det P_{(i\,j)}=-1$ であり、行の入れ替えで行列式の符号が反転することの行列による表現になっている（行列式、Art10 Chapter 1）。

反例：無限集合のずらし

$X=\mathbb{Z}$ とし、$\sigma(x)=x+1$ で定まる置換 $\sigma\in S_{\mathbb{Z}}$ を考える。$\sigma$ は有限個の互換の積として書けない。実際、互換 $\tau_1,\dots,\tau_k$ の積は、どれかの $\tau_i$ が動かす元（高々 $2k$ 個）以外の元を動かさないが、$\sigma$ はすべての整数を動かす。この例は「$X$ の置換である」を満たすが「$X$ が有限集合である」を満たさず、thm-transposition-decomposition の有限性の仮定が省けないことを示す。無限集合の場合に互換の積で書ける置換がちょうど動かす元が有限個のものであることは prop-transposition-finitary で示す。

反例：対称群を生成しない互換の組

$S_4$ で互換 $(1\,2)$ と $(3\,4)$ が生成する部分群は、2 つが可換で位数 $2$ なので $\{e,(1\,2),(3\,4),(1\,2)(3\,4)\}$（位数 $4$）であり、$S_4$（位数 $24$）ではない。これらの置換はすべて 2 つの集合 $\{1,2\}$、$\{3,4\}$ をそれぞれ自分自身に移すので、$(2\,3)$ のようにこの分け方を崩す互換は得られない。prop-transposition-graph は、互換の集合が対称群を生成するための条件をこの「分け方を崩せるか」で与える。
互換と巡回置換の組でも生成しないことがある。$S_4$ の $(1\,3)$ と $(1\,2\,3\,4)$ は、どちらも 2 つの組 $\{1,3\}$、$\{2,4\}$ からなる分割を保つ（$(1\,3)$ は各組を自分自身に、$(1\,2\,3\,4)$ は 2 つの組を入れ替える）ので、生成する部分群の元はすべてこの分割を保つ。$(1\,2)$ は $\{1,3\}$ を $\{2,3\}$ に移して分割を保たないので、生成する部分群は $S_4$ でない（実際には位数 $8$ の二面体群になる）。この例は「互換と $n$ 文字の巡回置換である」を満たすが「$S_n$ を生成する」を満たさず、prop-transposition-generators の 4 で互換を隣接した文字の $(1\,2)$ に選んだことが省けないことを示す。

性質

互換の積への分解

$X$ を $n$ 元の有限集合（$n\ge1$）とする。任意の置換 $\sigma\in S_X$ は、高々 $n-1$ 個の互換の積として書ける。ただし恒等置換 $e$ は $0$ 個の互換の積（空な積）とみなす。

$n$ についての数学的帰納法で示す。$n=1$ なら $S_X=\{e\}$ であり、$e$ は $0$ 個の互換の積である。
$n\ge2$ とし、$n-1$ 元集合については主張が成り立つとする。$X$ の元 $z$ を 1 つ固定し、$Y=X\setminus\{z\}$ とおく。$\sigma\in S_X$ に対し、$\sigma(z)=z$ なら $\sigma':=\sigma$、$\sigma(z)\neq z$ なら $\sigma':=(\sigma(z)\,z)\,\sigma$ とおく。どちらの場合も $\sigma'(z)=z$ である。$\sigma'$ は $z$ を動かさない全単射なので、$Y$ を $Y$ に全単射に移し、その $Y$ への制限は $S_Y$ の元である。帰納法の仮定により、この制限は $Y$ の互換 $\tau_1,\dots,\tau_m$（$m\le n-2$）の積である。$Y$ の互換を $z$ を動かさない $X$ の互換とみなすと、$\sigma'$ と $\tau_1\cdots\tau_m$ は $Y$ 上で一致し、どちらも $z$ を動かさないので、$\sigma'=\tau_1\cdots\tau_m$ である。$\sigma(z)=z$ なら $\sigma=\tau_1\cdots\tau_m$ は $m\le n-2$ 個の互換の積である。$\sigma(z)\neq z$ なら、prop-transposition-basic の 1 により $\sigma=(\sigma(z)\,z)\,\sigma'=(\sigma(z)\,z)\,\tau_1\cdots\tau_m$ は $m+1\le n-1$ 個の互換の積である。$\square$

この定理は対称群の記事の定理「互換による生成」の前半と同じ内容である。同記事は置換を互いに素な巡回置換の積に分解して示しているが、ここでは巡回置換への分解を使わずに示した。

無限集合の置換と互換

$X$ を任意の集合とする。置換 $\sigma\in S_X$ が有限個の互換の積として書けることと、$\sigma$ が動かす元が有限個であることは同値である。

互換 $\tau_1,\dots,\tau_k$ の積は、どれかの $\tau_i$ が動かす元以外は動かさないので、動かす元は高々 $2k$ 個である。逆に、$\sigma$ が動かす元の集合 $F$ が有限であるとする。$F=\emptyset$ なら $\sigma=e$ である。$F\neq\emptyset$ なら、$x\in F$ について $\sigma(x)\neq x$ であり、$\sigma(\sigma(x))=\sigma(x)$ とすると単射性から $\sigma(x)=x$ となって矛盾するので $\sigma(x)\in F$ である。よって $\sigma$ は $F$ を $F$ に単射に移し、$F$ は有限なので全単射に移す。この制限は $S_F$ の元であり、thm-transposition-decomposition により $F$ の互換の積である。$F$ の互換を $F$ の外の元を動かさない $X$ の互換とみなすと、その積と $\sigma$ は $F$ の上で一致し、$F$ の外ではどちらも恒等写像なので、$\sigma$ は互換の積である。$\square$

互換の個数とその偶奇

置換を互換の積に書く書き方は一通りではない（ex-transposition-s3）が、必要な互換の最小個数と、個数の偶奇は置換から決まる。これを示すために、置換 $\sigma\in S_n$ の軌道を使う。$x\in\{1,\dots,n\}$ の $\sigma$ による軌道とは $\{\sigma^m(x)\mid m\in\mathbb{Z}\}$ のことである（群の作用の軌道の、$\sigma$ が生成する巡回群による場合）。$\sigma^\ell(x)=x$ となる最小の $\ell\ge1$ をとると、$x$ の軌道は相異なる $\ell$ 個の元 $x,\sigma(x),\dots,\sigma^{\ell-1}(x)$ からなり、$\sigma$ はこれらを $x\mapsto\sigma(x)\mapsto\cdots\mapsto\sigma^{\ell-1}(x)\mapsto x$ と巡回させる。$\{1,\dots,n\}$ は軌道に分割される。軌道の個数を $c(\sigma)$ と書く（動かない元もそれだけで 1 つの軌道と数える）。たとえば $c(e)=n$、互換について $c((a\,b))=n-1$、$n$ 文字の巡回置換について $c=1$ である。

互換を掛けたときの軌道の個数

$\sigma\in S_n$ と相異なる $a,b$ について、$a$ と $b$ が $\sigma$ の同じ軌道に属するなら $c(\sigma(a\,b))=c(\sigma)+1$ であり、異なる軌道に属するなら $c(\sigma(a\,b))=c(\sigma)-1$ である。

$\pi:=\sigma(a\,b)$ とおくと、$\pi(a)=\sigma(b)$、$\pi(b)=\sigma(a)$ であり、$a,b$ 以外の $x$ では $\pi(x)=\sigma(x)$ である。$a$ も $b$ も含まない $\sigma$ の軌道の上では $\pi$ と $\sigma$ は一致するので、それらはそのまま $\pi$ の軌道である。
同じ軌道に属する場合：その軌道の元を $a,\sigma(a),\dots,\sigma^{\ell-1}(a)$ と並べ、$b=\sigma^r(a)$（$1\le r\le\ell-1$）とする。$\pi$ で $a$ から始めると、$a\mapsto\sigma(b)=\sigma^{r+1}(a)$ であり、以後 $\sigma^{r+1}(a),\dots,\sigma^{\ell-1}(a)$ は $a,b$ でないので $\sigma$ と同じく進み、$\sigma^{\ell-1}(a)\mapsto\sigma^\ell(a)=a$ で戻る。よって $a$ の $\pi$ による軌道は $\{a,\sigma^{r+1}(a),\dots,\sigma^{\ell-1}(a)\}$ である（$r=\ell-1$ なら $\{a\}$）。同様に $b\mapsto\sigma(a)\mapsto\cdots\mapsto\sigma^{r-1}(a)\mapsto\sigma^r(a)=b$ なので、$b$ の $\pi$ による軌道は $\{b,\sigma(a),\dots,\sigma^{r-1}(a)\}$ である（$r=1$ なら $\{b\}$）。この 2 つは交わらず、合併はもとの軌道である。よって軌道が 1 つ増える。
異なる軌道に属する場合：$a$ の軌道を $a,\sigma(a),\dots,\sigma^{\ell-1}(a)$、$b$ の軌道を $b,\sigma(b),\dots,\sigma^{m-1}(b)$ とする。$\pi$ で $a$ から始めると
$$ a\mapsto\sigma(b)\mapsto\cdots\mapsto\sigma^{m-1}(b)\mapsto b\mapsto\sigma(a)\mapsto\cdots\mapsto\sigma^{\ell-1}(a)\mapsto a $$
と進む（$\sigma^{m-1}(b)\mapsto\sigma^m(b)=b$、$b\mapsto\sigma(a)$ に注意）。よって 2 つの軌道の合併が $\pi$ の 1 つの軌道になり、軌道が 1 つ減る。$\square$

互換の個数の下限と偶奇

$n\ge1$、$\sigma\in S_n$ とする。

$\sigma$ が $k$ 個の互換の積なら、$k\ge n-c(\sigma)$ であり、$k\equiv n-c(\sigma)\pmod 2$ である。
$\sigma$ はちょうど $n-c(\sigma)$ 個の互換の積として書ける。

1：$\sigma=\tau_1\tau_2\cdots\tau_k$ とし、$\sigma_0:=e$、$\sigma_j:=\tau_1\cdots\tau_j$ とおく。$\sigma_j=\sigma_{j-1}\tau_j$ なので、lem-transposition-orbits により $c(\sigma_j)=c(\sigma_{j-1})\pm1$ である。$c(\sigma_0)=n$ から $k$ 回で $c(\sigma_k)=c(\sigma)$ に達するので、$n-c(\sigma)\le k$ であり、各段で偶奇が入れ替わるので $c(\sigma)\equiv n+k\pmod 2$、すなわち $k\equiv n-c(\sigma)\pmod 2$ である。
2：$d:=n-c(\sigma)$ についての帰納法で示す。$d=0$ ならすべての軌道が 1 元なので $\sigma=e$ であり、$0$ 個の互換の積である。$d>0$ なら 2 元以上の軌道があり、その元 $a$ と $b:=\sigma(a)\neq a$ は同じ軌道に属する。lem-transposition-orbits により $\pi:=\sigma(a\,b)$ は $c(\pi)=c(\sigma)+1$、すなわち $n-c(\pi)=d-1$ を満たすので、帰納法の仮定により $\pi$ は $d-1$ 個の互換の積である。$\sigma=\pi(a\,b)$ なので $\sigma$ は $d$ 個の互換の積である。$\square$

互換の個数の偶奇の不変性

置換 $\sigma\in S_n$ を互換の積に書くとき、互換の個数の偶奇は書き方によらず、$n-c(\sigma)$ の偶奇に等しい。とくに置換の符号は $\operatorname{sgn}\sigma=(-1)^{n-c(\sigma)}$ である。

前半は thm-transposition-minimum の 1 である。後半について、符号 $\operatorname{sgn}\colon S_n\to\{\pm1\}$ は群準同型で、互換の符号は $-1$ である（交代群の記事の命題「符号準同型」）。thm-transposition-minimum の 2 により $\sigma$ は $n-c(\sigma)$ 個の互換の積なので、$\operatorname{sgn}\sigma=(-1)^{n-c(\sigma)}$ である。$\square$

偶奇の不変性は交代群の記事では符号を差積の比 $\prod_{i< j}(\sigma(j)-\sigma(i))/(j-i)$ で定めて示されている。上の証明は軌道の個数を数えるもので、筋が異なる（差積による証明は DF04 §3.5 にもある）。互換の個数が偶数である置換を偶置換、奇数である置換を奇置換といい、偶置換の全体が交代群 $A_n$ である。$n$ 文字の巡回置換は $c=1$ なので、最小で $n-1$ 個の互換を要し、$n$ が奇数なら偶置換、偶数なら奇置換である。

生成系

互換からなる生成系

$n\ge2$ とする。$S_n$ は次のそれぞれで生成される。

互換全体。
$1$ を含む互換 $(1\,2),(1\,3),\dots,(1\,n)$。
隣接互換 $(1\,2),(2\,3),\dots,(n-1\ \ n)$。
$(1\,2)$ と $n$ 文字の巡回置換 $(1\,2\,\cdots\,n)$。

1：thm-transposition-decomposition による。
2：$1$ と異なる相異なる $a,b$ について、prop-transposition-basic の 3 により $(1\,a)(1\,b)(1\,a)^{-1}=((1\,a)(1)\ \ (1\,a)(b))=(a\,b)$ である。よって互換はすべて $(1\,2),\dots,(1\,n)$ の積であり、1 に帰着する。
3：$2\le k\le n-1$ について、$(k\ \ k+1)$ は $1$ を動かさず $k$ を $k+1$ に移すので、同じく $(k\ \ k+1)(1\,k)(k\ \ k+1)^{-1}=(1\ \ k+1)$ である。$(1\,2)$ から始めて $k$ についての帰納法により $(1\,3),\dots,(1\,n)$ は隣接互換の積であり、2 に帰着する。
4：$\rho:=(1\,2\,\cdots\,n)$ とおくと、$1\le i\le n-2$ について $\rho(i)=i+1$、$\rho(i+1)=i+2$ なので $\rho(i\ \ i+1)\rho^{-1}=(i+1\ \ i+2)$ である。$(1\,2)$ から始めて順に共役をとると、隣接互換はすべて $(1\,2)$ と $\rho$ の積であり、3 に帰着する。$\square$

4 の互換は、$\rho$ で隣り合う 2 文字を入れ替えるものに選ぶ必要がある。ex-transposition-not-generating の $(1\,3)$ と $(1\,2\,3\,4)$ はそうでない例である。ただし $n$ が素数 $p$ なら、どの互換 $(a\,b)$ とどの $p$ 文字の巡回置換 $\rho$ も $S_p$ を生成する。実際、$\rho$ の軌道は $\{1,\dots,p\}$ 全体なので $\rho^m(a)=b$ となる $1\le m\le p-1$ があり、$p$ が素数なので $\rho^m$ も $p$ 文字の巡回置換で、$a$ の次に $b$ を置いて $\rho^m=(a\,b\,\cdots)$ と書ける。文字の名前を付け替えれば（共役をとれば）これは 4 の状況であり、$\langle(a\,b),\rho\rangle$ は $\langle(a\,b),\rho^m\rangle$ を含むので $S_p$ に一致する。
互換の集合 $T$ が $S_n$ を生成するかどうかは、グラフで判定できる。頂点集合を $\{1,\dots,n\}$ とし、$(a\,b)\in T$ のときに $a$ と $b$ を辺で結んだグラフを $\Gamma_T$ とする。

互換の集合が生成する部分群

$n\ge2$ とし、$T$ を $S_n$ の互換からなる集合とする。$T$ が $S_n$ を生成することと、グラフ $\Gamma_T$ が連結グラフであることは同値である。

$\Gamma_T$ が連結でないとし、連結成分の 1 つを $C$ とする（$\emptyset\neq C\neq\{1,\dots,n\}$）。$T$ の元 $(a\,b)$ は辺の両端 $a,b$ が同じ連結成分に属するので、$a,b$ はともに $C$ に属するか、ともに属さない。どちらの場合も $(a\,b)$ は $C$ を $C$ に移す。したがって $T$ が生成する部分群の元はすべて $C$ を $C$ に移す。$c\in C$、$d\notin C$ をとると互換 $(c\,d)$ は $C$ を $C$ に移さないので、$T$ は $S_n$ を生成しない。
逆に $\Gamma_T$ が連結であるとし、相異なる $a,b$ をとる。$a$ から $b$ への、同じ頂点を 2 度通らない道 $a=v_0,v_1,\dots,v_m=b$ がある。$(v_0\,v_m)$ が $T$ の元の積であることを $m$ についての帰納法で示す。$m=1$ なら $(v_0\,v_1)\in T$ である。$m\ge2$ なら、帰納法の仮定により $(v_0\ \ v_{m-1})$ は $T$ の元の積であり、$(v_{m-1}\,v_m)\in T$ は $v_0$ を動かさず $v_{m-1}$ を $v_m$ に移すので、prop-transposition-basic の 3 により $(v_{m-1}\,v_m)(v_0\ \ v_{m-1})(v_{m-1}\,v_m)^{-1}=(v_0\,v_m)$ である。よってすべての互換が $T$ の元の積であり、prop-transposition-generators の 1 により $T$ は $S_n$ を生成する。$\square$

prop-transposition-generators の 2 は星形のグラフ、3 は一直線のグラフの場合であり、どちらも連結である。ex-transposition-not-generating の $\{(1\,2),(3\,4)\}$ では $\Gamma_T$ が 2 つの辺に分かれて連結でない。$n$ 頂点で連結なグラフは辺を $n-1$ 本以上もつ。辺のないグラフでは連結成分が $n$ 個あり、辺を 1 本ずつ加えるごとに連結成分の個数は高々 $1$ しか減らない（新しい辺は高々 2 つの成分をつなぐだけである）ので、成分を 1 個にするには $n-1$ 本以上の辺が要るからである。したがって prop-transposition-graph により、$S_n$ を生成する互換の集合は $n-1$ 個以上の元をもつ。

隣接互換の関係式

$s_i:=(i\ \ i+1)$（$1\le i\le n-1$）とおく。

隣接互換の関係式

$s_i^2=e$ である。
$1\le i\le n-2$ について $s_is_{i+1}=(i\ \ i+1\ \ i+2)$ であり、$(s_is_{i+1})^3=e$ である。
$|i-j|\ge2$ なら $s_is_j=s_js_i$ である。

1 は prop-transposition-basic の 1 である。2 の前半は ex-transposition-cycle の式の $k=3$ の場合である。3 文字の巡回置換 $(x\,y\,z)$ は 3 回施すと各文字をもとに戻すので、$(s_is_{i+1})^3=e$ である。3：$|i-j|\ge2$ なら $\{i,i+1\}$ と $\{j,j+1\}$ は交わらない。各文字 $x$ について、$x\in\{i,i+1\}$ なら $s_j$ は $x$ と $s_i(x)$ を動かさないので $s_is_j(x)=s_i(x)=s_js_i(x)$ であり、$x\in\{j,j+1\}$ でも同様、どちらでもなければ両辺とも $x$ である。$\square$

この 3 種の関係式は、鏡映で生成される群を関係式で調べる Coxeter群の理論の出発点になっている（群の表示）。

符号と交代群との関係

互換は奇置換であり（cor-transposition-parity、$c((a\,b))=n-1$）、交代群 $A_n$ は互換を含まない。2 つの互換の積は、$\{a,b\}=\{c,d\}$ なら $e$、ちょうど 1 文字を共有するなら $(x\,y)(y\,z)=(x\,y\,z)$ の形の 3 文字の巡回置換、交わらないなら $(a\,b)(c\,d)$ である。交わらない場合も 3 文字の巡回置換の積に直せる。$(b\,c)(b\,c)=e$ を挟むと $(a\,b)(c\,d)=(a\,b)(b\,c)\cdot(b\,c)(c\,d)=(a\,b\,c)(b\,c\,d)$ である。偶置換は偶数個の互換の積なので 2 つずつ組にして書け、各組は上のとおり $e$ か 3 文字の巡回置換 1 個か 2 個の積である。よって $A_n$（$n\ge3$）は 3 文字の巡回置換で生成される（交代群の記事の定理「3 サイクルによる生成」）。
互換は $S_n$ の中で互いに共役であり（prop-transposition-basic の 3）、互換全体は $S_n$ の 1 つの共役類をなす。したがって、互換を 1 つでも含む $S_n$ の正規部分群は、共役で閉じているのですべての互換を含み、prop-transposition-generators の 1 により $S_n$ 全体である。