Transposition

I matematiken är en transposition en permutation av en mängd, där alla element utom precis två är fixpunkter. Intuitivt sett betyder detta att man "byter plats på två element, men lämnar alla andra element på sina platser".

Transpositioner utgör ett slags "grundläggande byggstenar" för permutationer, därför att varje permutation av en ändlig mängd är en produkt av transpositioner.

Exempel

Betrakta permutationen σしぐま av mängden {1, 2, 3, 4, 5}  som omvandlar begynnelseordningen 12345 till 34521. Denna kan erhållas genom tre transpositioner: byt först plats på 1 och 3, sedan på 2 och 4, och till sist på 1 och 5.

$\sigma ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}={\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}{\begin{pmatrix}1&5\end{pmatrix}}[={\begin{pmatrix}1&5\end{pmatrix}}{\begin{pmatrix}5&3\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}].$

Det finns många andra sätt att skriva σしぐま som en produkt (sammansättning) av transpositioner, till exempel

σしぐま = (2 3) (1 2) (2 4) (3 5) (4 5).

En permutation som kan erhållas genom ett jämnt antal transpositioner säges ha jämn paritet, en som kan åstadkommas genom ett udda antal transpositioner har udda paritet.