Is the Cayley distance on permutation (matrices) equivalent to the Riemannian metric on $O(n)$?

Question

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$?)

Answer 1

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}\ . $$