In group theory, "transposition" means almost the same thing it means in ordinary language: the swapping of two things.

More precisely, let *G* be a group acting (from the left) on a set *X*. A *transposition* is an element of *G* of order 2 that only moves two elements of *X*. In other words, if τ is in *G*, then τ is a transposition if for some *x* and *y* in *X*,

τ*x* = *y*; τ*y* = *x*

and τ*z* = *z* for any other *z* in *X*.

The most important example of transpositions are the elements of the symmetric group on *n* letters, often denoted *S*_{n}. This is the group that consists of all permutations of *n* things ("letters"). In cycle notation, transpositions are the elements of *S*_{n} of the form (*a b*) for any letters *a* and *b* taken from {1, 2, ..., *n*}.

Transpositions are important because they can generate any permutation in *S*_{n}, and because Cayley's theorem tells us that any group is isomorphic to a subgroup of some symmetric group. Thus, in a sense, transpositions can generate any group whatsoever (although this might be the most inefficient way to generate an arbitrary group). This fact is of theoretical interest and reveals the fundamental nature of transpositions.

That any permutation in *S*_{n} can be written as a product of transpositions, should be intuitively clear. In fact, to avoid overkill, we can take the *n* - 1 *adjacent* transpositions

(1 2), (2 3), (3 4), ..., (*n*-1 *n*)

as generators of *S*_{n}. I will not give a formal proof of this fact, as it is bound to be more confusing and notationally entangling than enlightening. Instead, let us prove this "by inspection", as the engineers say. An arbitrary permutation σ of *S*_{n} moves the *n* letters {1, 2, ..., *n*} in some fashion. Now, imagine that these moves are performed only by moving two adjacent elements, one at a time. These motions of adjacent elements are exactly the *n*-1 transpositions I contend to generate *S*_{n}. For example, if σ moves 2 to 5, this can be accomplished by three transpositions: (2 3) then (3 4), followed by (4 5). Now 2 is in its rightful place according to σ, although other elements have been moved around in some manner. So the way to write an arbitrary permutation as product of transpositions is to turn this heuristic into something more systematic. This is best explained through example.

Suppose we want to write

σ= (1 2 3 4 5)
(3 2 5 1 4)

as a product of transpositions. (The notation means that σ takes 1 to 3, 2 is fixed, 3 goes to 5, etc.) We have to move 3 into slot 1, and this can be done by two transpositions, (2 3), (1 2). 3 goes to 2 and then goes to 1. Now we have the following arrangement of the five letters:

1 2 3 4 5 <--- slot number
(3 1 2 4 5) <--- contents of slots

Now 3 is in the right place, but 2 should be fixed by σ. No problem, we can move 2 back into its place with the transposition (2 3) (switches slots 2 and 3), without touching letter 3 in slot 1 to obtain

1 2 3 4 5
(3 2 1 4 5)

and so on. So far, as a product of transpositions, σ is (2 3)(1 2)(2 3), with composition going from right to left. If we continue in this manner, we discover that as a product of transpositions

σ = (4 5)(3 4)(2 3)(1 2)(2 3).

It is worth pointing out that there is nothing unique about this decomposition of σ into transpositions. For example, since a transposition is its own inverse (to undo a swap, you must swap again), we can stick any number of equal transpositions anywhere in the decomposition of σ so long as they are adjacent, for example,

σ = (4 5)(3 4)(2 3)(1 2)(2 3)**(4 5)(4 5)(2 3)(2 3)**.

There are other more imaginative ways of decomposing σ into transpositions. Lack of uniqueness nonetheless, what *is* unique about the decomposition of σ is the *parity* of the number of transpositions. This is an important result.

**Theorem**. The parity of the number of transpositions in a decomposition of an arbitrary permutation is always the same regardless of the decomposition.

This result requires proof and is rather remarkable. It is what allows us to define even and odd permutations, as those who are formed by evenly many or oddly many transpositions, respectively. From this result, it is also clear that the product of two even permutations is again even (since even + even = even), so the *S*_{n} has a subgroup consisting of all even permutations. This is known as the alternating group on *n* letters, and for *n* > 4 is a nonabelian simple group. This is one of the deep reasons why the quintic equations and higher have no general solutions by radicals.