Show that transposition is an odd permutation

Question

This is in symmetric groups $S_n$. I don't know how to approach this problem. I guess I have to use the definition of $$\mathrm{sgn}(\sigma)=\prod_{1 \leq i < j \leq n} \frac{\sigma(j)-\sigma(i)}{j-i}$$

I know I have to use this on the permutation $(i \ j)$ which represents a transposition of the $i$th and $j$th elements of the permutation, but I don't know how to approach this.

Answer 1

Suppose the transposition $\tau$ permutes $i$ and $j=i+k$ ($k\ge 1$). So the list of elements between $1$ and $n$: $$1,\dots, i-1, i,i+1, \dots , i+k-1,j=i+k,i+k+1,\dots,n$$ becomes $$1,\dots, i-1, j=i+k ,i+1, \dots , i+k-1,i,i+k+1,\dots,n.$$ Therefore $k$ pairs with $j$: $(i,j), (i+1,j),\dots ,(i+k-1,j)$ undergo an inversion.

Also the $k-1$ pairs with $i$: $(i,i+1),\dots, (i, i+k-1)$ undergo an inversion (the pair $(i,j)$ has already been counted in the first series).

In all we therefore have $2k-1$ inversions — an odd number.

Answer 2

Take wlog the sequence $1, 2, \ldots, n$. An inversion is defined as a pair of elements in a sequence which are not in natural order. Just as a permutation can be decomposed into transpositions, let us decompose a transposition into something even simpler: adjacent transpositions, where two adjacent elements swap places. This is helpful, since it can easily be seen that an adjacent transposition always increments or decrements the inversion number by precisely 1.

A transposition makes two elements swap places, so how can we go about this using adjacent transpositions? One way is to first move the smaller element to the larger element's position then move the larger element to the smaller element's position.

As an example, take the sequence $1, 2, 3, 4, 5, 6, 7$ where we want to swap $2$ and $5$.

First step: $$1, 2, 3, 4, 5, 6, 7 \rightarrow 1,3,2,4,5,6,7 \rightarrow 1,3,4,2,5,6,7 \rightarrow 1,3,4,5,2,6,7$$

$2$ is in the right position and we have used three adjacent transpositions. Notice however that $5$ has been moved to the left one position, so one less adjacent transposition than were necessary for $2$ will be needed.

Second step: $$1,3,4,5,2,6,7 \rightarrow 1,3,5,4,2,6,7 \rightarrow 1,5,3,4,2,6,7$$

As expected, two adjacent transpositions were needed.

In fact, for any arbitrary transposition, we need an odd number of adjacent transpositions, since the last adjacent transposition in the first step "benefits" both steps. Note that although we started from a sequence in natural order, we can relabel the elements any way we like, we still have to use the same number of adjacent transpositions.

Now armed with the fact that an adjacent transposition increments or decrements (but does not leave constant!) the inversion number and the fact that a transposition can be decomposed into an odd number of adjacent transpositions, we can state that a transposition is an odd permutation.