# If $\sigma$ is a product of $k$ transpositions, prove that $k \equiv$ inv $(\sigma)$ (mod $2$).

An inversion in a permutation $\sigma = \sigma_1...\sigma_n$ is a pair of indices $i < j$ such that $\sigma_i > \sigma_j$. Let inv($\sigma$) be the number of inversions of $\sigma$.

If $\sigma$ is a product of $k$ transpositions, prove that $k \equiv$ inv $(\sigma)$ (mod $2$).

attempt: Let inv($\sigma$) be the number of inversions of $\sigma$.

Suppose $\sigma$ is a product of $k$ transpositions,

then $\sigma$ can be written as $\sigma = (i_1i_2)(i_2i_3)...(i_{k-1}i_k) = \sigma_1\sigma_2...\sigma_k$.

We have $\text{sign}(\sigma)=(−1)^{\text{inv}(σ)}=(−1)^k$, where $k$ is the number of transpositions. If $\text{inv}(σ)$ is even then $k$ is even, so $2\mid\text{inv}(σ)-k$. If $\text{inv}(σ)$ is odd, then $k$ is also odd, and once again $2\mid\text{inv}(σ)-k$.