Prove that every element of Sn (n ≥ 2) can be written as a product of transpositions
-
First, let phi = (x1 x2 . . . xk) be a cycle of length at least 2. Then
_ = (x1 x2)(x2 x3) ・ ・ ・ (xk−1 xk).
You can verify this by direct computation.
Now for a general non-identity element phi, just write it first as a product of disjoint cy-
cles (we proved in class this can always be done), then write each cycle as a product of
transpositions as above. This gives phi as a product of transpositions.
If phi= (), you can think of it a product of 0 transpositions, or if you don’t like that, write
() = (1 2)(1 2).
_ = (x1 x2)(x2 x3) ・ ・ ・ (xk−1 xk).
You can verify this by direct computation.
Now for a general non-identity element phi, just write it first as a product of disjoint cy-
cles (we proved in class this can always be done), then write each cycle as a product of
transpositions as above. This gives phi as a product of transpositions.
If phi= (), you can think of it a product of 0 transpositions, or if you don’t like that, write
() = (1 2)(1 2).