What is the prove that the minimum number of transpositions of the form $[i, i+ 1]$
required to express a permutation will be equal to the number of inversions?
Let $\sigma$ be s.t.
\begin{align*}
\sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
4 & 5 & 1 & 2 & 3
\end{pmatrix}
\end{align*}
Then $I($$\sigma)=2+2+2=6,$ where $I($$\sigma)$ is the number of inversions in $\sigma$.
The integer 1 is said to introduce two inversions in g, because two of
Similarly,
the integers preceding 1 are greater than 1.
2 introduces two inversions: 4 and 5,
3 introduces two inversions: 4 and 5,
4 introduces no inversions,
5 introduces no inversions.
I am sorry for the bad formatting, this is my first post here. I used a book for writing this so I will include it as a reference.
Basically the book says that the minimum number of transpositions of the form $[i, i+ 1]$ will be equal to the number of inversions $I($$\sigma)$. Please can anyone prove this in a simple way? I am having a very hard time trying to prove it.
Best Answer
Every such adjacent transposition that you use will either remove exactly one inversion or it will create exactly one inversion. If we show that we can make it always remove an inversion, we're finished.
Take any permutation $\tau$. If this isn't the identity permutation, then there are inversions. Let's say $i<j$ but $\tau(i)>\tau(j)$. If $i+1=j$, we're done, because we can apply an adjacent transposition to $[i, i+1]$ and decrease the number of inversions.
If $i+1\neq j$, then either $\tau(i)>\tau(i+1)$ or $\tau(i+1)>\tau(j)$ (or both). Either way we have an inversion that's at least one step closer to being adjacent. If we repeat this process, sooner or later we will find an adjacent inversion, and we can apply a transposition to that.