Is the Cayley distance on permutation (matrices) equivalent to the Riemannian metric on $O(n)$? Denote by $d_C(\sigma,\mu)$ the minimal number of transpositions needed to go from a permutation $\sigma$ to a permutation $\mu$. E.g. if $d_C(\sigma,\mu)=0$, then $\sigma=\mu$, if $d_C(\sigma,\mu)=1$, then there exists a transposition $\tau$ such that $\sigma\circ\tau = \mu$, etc.
Identifying permutations $\sigma\in S_n$ with their respective permutation matrices, it is not hard to see that these matrices are all orthogonal. Now consider $d_R$, the natural (Riemannian) metric on $O(n)$ (viewed as the manifold of orthogonal matrices in $n$ dimensions). Via the above identification, this induces another metric on permutations.
Are there any comparison results? For example, do we have for some $c$ independent of $n$ that $$d_R(\sigma,\mu)\leq d_C(\sigma,\mu)\leq c d_R(\sigma,\mu)?$$
(Or something similar with $c$ not growing "too fast" in $n$?)
 A: Consider instead $d_E$ the Euclidean distance on the space of $n\times n$ real matrices, i.e., the one coming from the Hilbert-Schmidt norm:
$$
d_E(A,B)=\sqrt{{\rm tr}((A-B)^{\rm T}(A-B))}\ .
$$
We will consider its restriction to $O(n)$, which is a kind of chordal metric instead of the intrinsic metric $d_R$. Now for two permutations (identified with their permutation matrices) $\sigma,\tau$, we have
$$
d_E(\sigma,\tau)^2={\rm tr}(\sigma^{\rm T}\sigma)
+{\rm tr}(\tau^{\rm T}\tau)-2{\rm tr}(\sigma^{\rm T}\tau)
$$
Note that inverting a permutation amounts to taking the transpose of its matrix.
Also note that for a permutation $\rho$
$$
{\rm tr}(\rho)=f(\rho)
$$
where $f(\rho)$ is the number of fixed points of $\rho$.
So $d_E(\sigma,\tau)=\sqrt{2m(\sigma^{-1}\tau)}$ where $m(\rho)=n-f(\rho)$ is the number of points which are not fixed by $\rho$.
I didn't check but I suspect that when evaluating the distance between two orthogonal matrices $A,B$, all the action happens on a circle and therefore $d_E(A,B)\le d_R(A,B)\le \frac{\pi}{2}d_E(A,B)$. So basically it all comes down to comparing $m(\rho)$ and $d_C(Id,\rho)$ or rather $f(\rho)$ and $n-d_C(Id,\rho)=:c(\rho)$, the number of cycles of $\rho$.
In other words one needs to compare the number of cycles of length one with the total number of cycles. Clearly $f\le c$. Since the other cycles contain at least two elements we also have $n-f\ge 2(c-f)$, i.e., $c\le (n+f)/2$. It's easy to conclude from here given that
$$
\sqrt{2d_C}\le d_E\le 2\sqrt{d_C}\ .
$$
