置換 (数学)
群論においてある集合上の置換は、その集合からその集合自身の上への全単射を言う。任意に与えられた集合の上の置換全体の成す集合は、写像の合成を積として、恒等変換を単位元とする群を成し、これを S の対称群と呼ぶ。対称群は、同型を除いてその集合の濃度のみに依存して決まり、S の元の具体的な特徴がどうであるかは群構造に影響を与えない。対称群は有限集合上のものを考えることがほとんどで、この場合には適当な自然数 n に対して S = {1, 2, ...,n} であるとして一般性を失わない。こうして n 次の対称群 Σn が定まる。
対称群の任意の部分群を置換群と呼ぶ。ケイリーの定理により、実は任意の群が何らかの置換群に同型であり、特に有限群は何らかの有限対称群の部分群に同型であることがわかる。しかし置換群は、抽象群よりも多くの構造を持つものであり、たとえば置換群の任意の元には巡回置換型を定義することができるが、置換群として実現されたのではない群がこれと同値な付加構造をもつことは必ずしも求められない。例えば、Σ3 は自然に置換群となり、その任意の互換は巡回型が (2,1) となるが、ケイリーの定理の証明に従って Σ3 を Σ6 の部分群として(つまり、Σ3 自身に属する全 6 個の元の置換として)実現すれば、この置換群での互換の巡回置換型は (2, 2, 2) になる。つまり、ケイリーの定理の成立にも拘らず、置換群の研究は抽象群の研究とは異なる部分を持っているということになる。
有限集合 S の置換に対して、その記法は大きく三種類が存在する。1815年、コーシーによって導入された二行記法は一行目に S の元を書き、その各元の下に置換による像を書いて二行目とするものである。例えば、集合 {1, 2, 3, 4, 5} のある置換は
σ = [ 1 2 3 4 5 2 5 4 3 1 ] {\displaystyle \sigma ={\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}}
と書くことができ、上と下の対応が同じなら横の順序は問わない記法である。
σ = [ 1 2 3 4 5 2 5 4 3 1 ] = [ 2 4 5 1 3 5 3 1 2 4 ] = [ 5 4 3 2 1 1 3 4 5 2 ] = ⋯ {\displaystyle \sigma ={\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}={\begin{bmatrix}2&4&5&1&3\\5&3&1&2&4\end{bmatrix}}={\begin{bmatrix}5&4&3&2&1\\1&3&4&5&2\end{bmatrix}}=\cdots }
1852年、エンリコ・ベッチはこれを
σ = [ 1 2 3 4 5 σ ( 1 ) σ ( 2 ) σ ( 3 ) σ ( 4 ) σ ( 5 ) ] {\displaystyle \sigma ={\begin{bmatrix}1&2&3&4&5\\\sigma (1)&\sigma (2)&\sigma (3)&\sigma (4)&\sigma (5)\end{bmatrix}}}
積が結合的で、単位元を持ち、任意の元が逆元を持つということから、S 上の置換全体の成す集合は群となり、S の対称群と呼ばれる。
有限集合上の任意の置換は互換の積に表すことができる。与えられた置換に対してそのような表示は無数に存在するけれども、それらの表示の中に現れる互換の数の偶奇は表示によらない。これにより、任意の置換は偶置換または奇置換に分類することができる。
置換の乗法を置換の巡回置換表現のもとで書くための平易なパターンというものは存在せず、積の巡回置換表示に現れる巡回置換は、積を取る個々の置換に現れる巡回置換とは全く異なるものになってしまう。しかし、置換 σ に対して別の置換 π による共軛変換を取る、つまり積 πσπ を作る特別の場合においては、巡回置換構造が保たれる。共軛変換で得られた置換の巡回置換表示は、σ の巡回置換表示に現れる各成分に π を施したものとして与えられる。
集合 {1, 2, ..., n} 上の置換を n 次正方行列として表すこともできる。これを行うのに自然な方法は二種類あるが、行列の積が置換の積に同じ順番で対応するのはそのうちの一方だけである。このとき、置換 σ には i = σ(j) のとき mi j = 1 でそれ以外のとき mi j = 0 となるような行列 M = [mi j ] が対応し、σ に対応する置換行列と呼ばれる。