As commonly known you can write every permutation $f$ of $\{1,\dotso, n\}$ as product of transpositions of neighbored elements:
$f=(a_1, a_1+1)\circ\dotso\circ (a_k, a_k+1)$
with $k\geq 0$ and $a_j\in\{1,\dotso, n-1\}$ for every $j\in\{1,\dotso, k\}$.
The length $L(f)$ of $f$ is the minimal $k$, for which we can write $f$ as above.
I want to show that $d_L(f,g)=L(f^{-1}\circ g)$ is a metric on $S_n$. The set of permutations $\{1,\dotso, n\}$.
First of all it is clear, that
$d_L:S_n\times S_n\to\mathbb{N}$
also $d_L(f,g)=0\Leftrightarrow f=g$
For symmetry it has to hold $d_L(f,g)=d_L(g,f)$.
We have $d_L(f,g)=L(f^{-1}\circ g)\stackrel{!}{=} L((f^{-1}\circ g)^{-1})=L(g^{-1}\circ f)=d_L(g,f)$
Where it is 'clear' that $L(f)=L(f^{-1})$. Because when we can write $f=(a_1, a_1+1)\circ\dotso\circ (a_k, a_k+1)$, then $f^{-1}=((a_1, a_1+1)\circ\dotso\circ (a_k, a_k+1))^{-1}$.
For the triangle inequality, we have to show that:
For every $f,g,h\in S_n$ we have $d_L(f,h)\leq d_L(f,g)+d_L(g,h)$.
So $L(f^{-1}\circ h)\leq L(f^{-1}\circ g)+L(g^{-1}\circ h)$.
So if we have a presentation of $f^{-1}\circ g$ and $g^{-1}\circ h$ as products of transpositions, then we also have such presentation of
$f^{-1}\circ h=(f^{-1}\circ g)\circ (g^{-1}\circ h)$, which length is for sure smaller (or not greater, to be more precise), by definition, because there might be a 'shortcut'.
My 'proof' involves a little to much of hand-waving, but it should hit the core ideas. Can you verify this?
Thanks in advance.
I don't see any hand-waving there; it looks like a proper proof to me. The only minor error is that where you say “for sure smaller” it should be “not greater”, since they may well be equal.